Let's try again to the right list.


-------- Forwarded Message --------
Subject: Re: [SG14] New colony proposal - feedback requested
Date: Mon, 4 May 2020 09:44:04 +0200
From: Jens Maurer <Jens.Maurer_at_[hidden]>
To: Matthew Bentley <mattreecebentley_at_[hidden]>, SG14 - Game Dev and Low Latency <sg14_at_[hidden]>

On 04/05/2020 01.52, Matthew Bentley wrote:
> Thanks again, and once more, take anything I don't comment on as accepted criticism/explanation.

Your response didn't go to the list. I've added the list again.

>
> > I don't think it's necessary to leave it anything other than implementation-defined? The reference implementation must use unsigned integral types, but I don't want to obviate future potential improvements on implementations, that could, for example, use a floating-point type (somehow).
>
> If this is not a type that the user can/should influence, then it
> shouldn't be a template parameter for colony in the first place.
>
>
> See "Do we really need the skipfield_type template argument?"in Appendix D.3,
> my concern over this is that the skipfield_type relates (Strongly) to the current skipfield implementation. However, I don't see any other potential skipfield implementations while maintaining O1 amortized iterator operations. But I don't have a crystal ball in front of me, so I can't rule it out either.
> In current implementation, skipfield_type is always an unsigned integer of some sort. The appendix explains how this is useful.

You either need to say which constraints a user-supplied type for Skipfield
is required to satisfy (note it's a template parameter, so the user can
choose), or the template parameter must go. Currently, the wording is
silent on any constraints for "Skipfield".

> The existing unordered_* containers are associative containers.
> In contrast, "colony" seems very much like a deque, which does
> have assign member functions (because the memory allocated for
> the blocks might be reused).
>
>
> Okay - so the point of assign is to - essentially - reuse existing memory space to avoid additional allocation/deallocations? Makes sense. WIll implement.

Thanks.

>
> > The only way to avoid that behaviour is to store a permanent reference to the current back element in-code, which would need to be updated in many places, and that's costly. I don't like reverse iterators for performance reasons and I personally wouldn't ever sacrifice overall performance to obtain an undefined-behaviour free function for rbegin. I want to give implementors the same ability. Frankly, as an unordered-insert container, the relevance of reverse_iterators is sparse at-best.
>
> So, maybe you don't want to provide reverse iterators
> at all, since clients shouldn't really rely on iteration
> order anyway.
>
>
> That might be viable given that unordered_map/set also only support forward iterators - given, as you've said, that those are associative containers not sequence containers.
> However having thought about it more clearly, there might be a use-case for it, in the sense that colony is sortable, so processing a sorted colony in reverse might be something that somebody wants to do, for some reason, at some point. Will put it in the Questions for Commitee section, I think this needs clarification but if you have any further thoughts let me know.

Sorting does establish an order, so reversing the order does make sense.
Which means colony should provide a bidirectional iterator. This needs
to be said in the spec, after the class synopsis or so. And that means
a reverse_iterator comes for granted.

I haven't yet understood the "reverse iterator", --end(), empty container,
and undefined behavior train of thought. I believe you can only do --end()
on a non-empty container, as a matter of precondition for that operation.

> > - In general, the standard doesn't do "get_" and "set_" prefixes for getting/setting values.
> > Instead, we have
> > name_for_value(x) to set a value
> > name_for_value() to retrieve the value
> >
> >
> > I don't think that's clear, but okay.
>
> The story is a bit different if there's a lot of work involved
> with the "set" part.
>
>
> My reservation is mostly that name_for_value(x) doesn't give a strong description about what the function Does with that value, but if it's what's common I'll go along with it.

This area probably needs a bit more thought / design work.
It does not seem to be a frequent operation to change min/max
mid-way during your container's lifetime, so offering a small
interface surface here is probably a good idea.

> You can use structured bindings in the caller, which makes your call a lot
> more compact plus gets you the right lifetimes for the variables:
>
> auto [min,max] = my_colony.block_parameters();
>
> Plus you have at least a chance of avoiding allocating
> memory for min and max, which is a lot harder with
> a reference.
>
>
> How does that avoid allocating memory as opposed to passing in the variables as reference parameters? Surely if the values are to be used at any point, they have to be stored somewhere?
> Maybe I'm reading you wrong.

Some ABIs can return trivially-copyable structs of sufficiently small size
in registers. The structured binding above has a good chance that no
stack memory will ever be used, because min/max will be kept in a register
in the caller, too.

If you pass-by-reference, ABIs generally convert that into a pointer,
i.e. the caller needs to pass a memory region and later needs to load
the data from the filled memory region. That is more work.

>> Any sorting near O(n^2) is not worth talking about, so you should simply
>>prescribe O(n log n) with a "remarks" paragraph that this might allocate
>> memory (which might cause std::bad_alloc to be thrown).
>
> The time complexity doesn't relate to the speed of sorting (if it did, std::list sorting would be as fast as std::vector sorting). The schema I'm discussing simply allows for faster sort algorithms which rely on random access, as opposed to relying on a slower algorithm which doesn't ala list.

I'm guessing that std::list::sort also does some tricks with an
intermediate pointer array, so I'm not seeing the point.

>
> I don't care for the implementation. I care for the specification that aspires
> to be in the standard.
>
>
> Well, the implementation has driven the specification, and it gives ample evidence, in this case, of why this function has a right to exist independently of distance - reading it is just a suggestion.
>
>
>
>
>
> > you'll find there's a lot of code you can get rid of when you have the assumption of counting from begin(), which makes for a faster function. Whether an implementor decides to act on that is up to them.
>
> If that's so much of a win, can't you just run-time check whether the first
> iterator in std::distance is begin() ? Or is the "begin" information lost
> at that point?
>
>
> Because that's an edge case outside of get_index_from_iterator and results in performance loss in general use when you specialize for it.

One missed branch, I hope?

Anyway, there seems to be rationale for going beyond std::distance(begin(), it)
that should be recorded in the "Design Decisions" section.

>
> > ctor p6:
> >
> > "If n is larger than min_block_capacity, the capacity of the first block created will be the smaller of n or max_block_capacity."
> >
> > If you want the min/max block capacity to have any normative impact,
> > you need to establish an actual abstract model you can tie into.
> > Otherwise, why does the capacity of some block matter at all?
> >
> >
> > Because the length of the block affects potential cache locality. The abstract model is described in Design Decisions.
>
> As I said, I'm only reading the specification. And this "block capacity" business
> appears in the specification without an overarching model that would make sense to
> me. That needs to be fixed (e.g. by adding a paragraph or two after the class synopsis),
> or any mention of "block capacity" needs to go.
>
>
> I don't think that's not the right place for the explanation, the right location is in Design decisions.
> You wouldn't expect an explanation of how a map/vector/deque works, or why some approaches allow for better performance, to be included in the tech spec, so I don't think you can expect the same of this.

std::deque doesn't allow me to specify block size parameters
from the outside, so I don't care on the specification level.

The interface for std::colony that you offered does allow me to
influence min/max, so you need to normatively specify what such
influence does, otherwise the parameter is meaningless and
therefore needs to go.

>
> The C++ abstract machine has no way of expressing "cache locality", btw.
>
>
> Not really my concern. I'm interested in high-performance containers, not the C++ abstract machine.

Then you're in the wrong forum here.

[intro.abstract] is a subclause of [intro.compliance],
which is one of the foundational aspects of the ISO C++
standard.

> > - Why do we need MoveInsertable for "reserve" anyway? Aren't we just allocating
> > a new memory block of the desired size, without any moves?
> >
> > That's an open question that I want addressed, so thanks for bringing it up - see 'questions for the committee' section.
>
> Fine. Answer: Let's have "reserve" only handle memory pre-allocation.
> If you want compaction or rearrangement of the elements, provide a different
> function (such as the set(min,max) function you already have).
>
>
> That's not what that function does, but I think that's a reasonable conclusion - I would like to hear other's thoughts before it's settled.
>
>
>
>
> > - approximate_memory_use p19
> > "Complexity: Implementation-defined. Should typically be constant."
> >
> > If there is a reasonable implementation strategy to make this constant, then make it so
> > in the spec.
> >
> >
> > Constant relies on the same code (maintaining sequential memory block numbers or alternatively having vector of memory blocks rather than linked-list) that allows operators >/</>=/<= to exist. If the committee decides that they don't want those, you would have to maintain those just to allow for constant implementation of this function, which I'm not in favour of. However I see benefit to retaining >/</>=/<= , so adopting a wait-and-see attitude at this point.
>
> I'm not seeing any mention of relational operators in the specification section,
> so they don't exist. Also, there is no related "question for the committee".
>
>
> To be clear I'm talking about iterator operators here. There's been no real pushback against keeping them, so I'm adopting a wait-and-see attitude for the moment.

My understanding is that std::colony does not provide random-access iterators.
Only those have relational operators, though, in the general scheme of
iterator operations [random.access.iterators].

There is no specification that the iterators std::colony provides have
relational operators.
>
> > - Why is reinitialize needed? Can't you just do my_colony = colony(min_block_size, max_block_size) ?
> > Oh, we don't have that constructor, but it seems we should definitely have it.
> >
> >
> > That constructor is not possible as it creates overload conflict with the fill constructor when using integers.
>
> Well, if you make a struct for min/max for the get_parameters() function,
> you can use that struct for the constructor as well, avoiding the
> ambiguity.
>
>
> That's a good idea. Will give it a shot.
>
>
>
>
>
> > - get_iterator_from_pointer p1: "pointer is not invalid" : The name of the parameter is element_pointer
> > (which is a bit verbose, though, just call it "p"). I think we need a precondition that the pointer
> > points to an element of *this.
> >
> > - In general, I think we need to be more clear which operations invalidate iterators,
> > and we should do so in an overall introductory paragraph of the normative wording.
> >
> >
> > This is in the first appendix, but I'm happy to move it upwards if you can name the section you think it should be in.
>
> It should be right after the class synopsis.
>
> > and of course the lengthy explanation of the complexity doesn't belong here. Just say O(n)
> >
> >
> > Where? You mean in the technical spec? Or in the paper in general?
>
> As I said, I'm only reading the specification part of your paper. Any
> explanations (which are good to have, in general) should go somewhere
> above, maybe near "Design Decisions".
>
>
> Okay, you're trying to get me to move some prose to the tech spec and some to the design decisions. Is there a guide as to what prose belongs where?

Anything explaining "why" should go to the "Design Decisions".

Anything allowing to judge whether my independent (assume bad-faith) implementation
of std::colony is conforming or not (given arbitrarily hostile template parameters
and arbitrarily hostile sequences of operations) needs to into the specification.

Example:
As I said above, "cache-locality" (for instance) is nothing you can talk about
in the C++ standard (because the abstract machine doesn't provide vocabulary
for it), but you might want to talk about only allowing at most one memory
allocation (observable via the Allocator template parameter) per "min"
inserts or so.

Jens