C++ Logo


Advanced search

Subject: Re: New colony proposal - feedback requested
From: Patrice Roy (patricer_at_[hidden])
Date: 2020-05-12 21:29:04

I've been in at least two LEWG sessions discussing Colony in the past, but
these were pre-LEWGI sessions (in the sense that LEWGI did not exist).

The current process seems solid to me. I think it will help the proposal
move along smoother.


Le mar. 12 mai 2020 à 20:58, Bryce Adelstein Lelbach aka wash via SG14 <
sg14_at_[hidden]> a écrit :

> The last time this was presented in the Incubator, it was determined that
> we needed more information and a better understanding of this facility to
> evaluate if we wanted it. The author was asked for a class synopsis at
> least, and wording if possible. We also wanted more prior art - a list of
> references to things in the wild that are similar to this (in C++ or other
> languages). We also wanted to see more usage experience and reports from
> the field.
> There was enough interest to ask for more work to get to a place where we
> could evaluate this.
> The biggest question is not whether this is a good data structure, the
> biggest question is whether it makes sense to standardize this.
> Having the wording is good. The most important thing for Library Evolution
> will probably be field experience.
> --
> Bryce Adelstein Lelbach aka wash
> US Programming Language Standards (PL22) Chair
> ISO C++ Library Evolution Chair
> CppCon and C++Now Program Chair
> CUDA Core C++ Libraries (Thrust, CUB, libcu++) Lead @ NVIDIA
> --
> On Tue, May 12, 2020, 16:34 Tony V E <tvaneerd_at_[hidden]> wrote:
>> I asked for a few reasons. One was to have a feel for how much wording
>> review should happen at this time.
>> I greatly appreciate Jens' wording input, it is obviously top notch; but
>> I also worry about spending time on function foo() only to have LEWG say
>> they don't want foo() at all (or colony at all, but that doesn’t quite feel
>> like the case).
>> There is a balance here; early wording review definitely makes a paper
>> better - *including better design* ‎by pointing out flaws we might
>> otherwise miss. I think in this case we see some of that happening - Jens
>> is pointing out things that highlight some of those design questions -
>> thank you! But keep in mind some of the wording work will probably be
>> thrown away.
>> When I asked about status, I specifically did NOT mention why I was
>> asking, because I didn't want to discourage wording review. But I also
>> wanted to make sure everyone knew what state we were in (and could make
>> their own decisions).
>> Also, plainly, I wondered if it had been through LEWG (at least once,
>> even if it might be coming back) and I had missed it. (which I could maybe
>> have figured out via spelunking the wiki...)
>> How much wording review would you like at this time? The more the better
>> I suppose?
>> Sent from my BlackBerry portable Babbage Device
>> *From: *Bryce Adelstein Lelbach aka wash
>> *Sent: *Tuesday, May 12, 2020 2:35 AM
>> *To: *Low Latency:Game Dev/Financial/Trading/Simulation/Embedded Devices
>> *Cc: *Matthew Bentley; Tony V E; Jens Maurer
>> *Subject: *Re: [SG14] New colony proposal - feedback requested
>> This paper is in the hands of Library Evolution.
>> It is in the Incubator queue.
>> wg21.link/P0447/github
>> It's priority is P2.
>> > What stage is this proposal at? Where has it been seen so far? LEWGI?
>> Where will it be seen next?
>> Why do you ask, Librarian Van Eerd?
>> What decisions about this paper does Library Evolution need to make?
>> P.S. Not everyone on this list knows Jens. I would consider his review a
>> very fortunate and charitable boon and err strongly on the side of doing as
>> he suggests.
>> --
>> Bryce Adelstein Lelbach aka wash
>> US Programming Language Standards (PL22) Chair
>> ISO C++ Library Evolution Chair
>> CppCon and C++Now Program Chair
>> CUDA Core C++ Libraries (Thrust, CUB, libcu++) Lead @ NVIDIA
>> --
>> On Sat, May 2, 2020, 17:55 Tony V E via SG14 <sg14_at_[hidden]>
>> wrote:
>>> What stage is this proposal at? Where has it been seen so far? LEWGI?
>>> Where will it be seen next?
>>> Sent from my BlackBerry portable Babbage Device
>>> Original Message
>>> From: Jens Maurer via SG14
>>> Sent: Saturday, May 2, 2020 3:39 PM
>>> To: Matthew Bentley
>>> Reply To: sg14_at_[hidden]
>>> Cc: Jens Maurer; Low Latency:Game
>>> Dev/Financial/Trading/Simulation/Embedded Devices
>>> Subject: Re: [SG14] New colony proposal - feedback requested
>>> On 02/05/2020 07.05, Matthew Bentley wrote:
>>> > First of all, thanks Jens for the thorough overview - please consider
>>> any points I don't comment on below as accepted criticism and as things I
>>> will action upon:
>>> >
>>> > On Fri, 1 May 2020 at 22:21, Jens Maurer <Jens.Maurer_at_[hidden] <mailto:
>>> Jens.Maurer_at_[hidden]>> wrote:
>>> >
>>> > - Please suggest stable labels and a location in the standard
>>> > where the additional container should go.
>>> >
>>> >
>>> > When you say "stable labels", do you mean numbered headings as in
>>> " deque specialized algorithms".
>>> All sections in the standard have labels, e.g. [basic.def.odr].
>>> Please make a suggestion for each of the (sub)sections you add.
>>> Also, please give a pointer where in the (numerical) order
>>> of sections you want your new sections about colony to
>>> appear.
>>> > - The "Skipfield" template parameter is not specified.
>>> > Which restrictions apply? (For example, can it be void,
>>> > an array of unknown bound, an abstract base class, a function
>>> > type, or a non-copyable class type?)
>>> >
>>> >
>>> > 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.
>>> > - Would it be useful to give the default template argument
>>> > for Skipfield a user-visible name? We also use the public
>>> > name std::allocator for the default argument of Allocator etc.
>>> >
>>> >
>>> > Since the type is meant to be implementation-defined, I'm unsure how
>>> to do this.
>>> "implementation-defined"? What benefit does the user gain from
>>> knowing what type it is?
>>> > - "const size_type min/max_block_capacity"> drop "const"; it's
>>> ignored in a non-defining function declaration anyway.
>>> >
>>> >
>>> > There's plenty of use of const in the existing standard, for
>>> containers, not sure what is different about what I'm doing. For example:
>>> > "iterator insert(const_iterator position, size_type n, const T& x);"
>>> > under Class template deque overview.
>>> const T& is "reference to const T", which is not a top-level const.
>>> However, "const size_type" is a top-level const, and those
>>> get ignored when forming function types. See [dcl.fct] p5.
>>> The definition of "top-level cv-qualifier" is in
>>> [basic.type.qualifier] p6.
>>> > - The synopsis should show "assign" member functions near
>>> "operator=".
>>> >
>>> >
>>> > There are no assign member functions. I was following the path of
>>> other unordered containers by not including them. Is there an obvious
>>> reason for including them? Implementation would be
>>> clear();reserve();insert().
>>> 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).
>>> > - " // Since this could be derived from --end() depending on
>>> implementation, and that could result in undefined behaviour in a colony
>>> with no insertions and unbounded iterators, whether this is noexcept is
>>> implementation-defined"
>>> >
>>> > "Since" is rationale that doesn't belong in normative text. Do you
>>> want to say
>>> > noexcept( see below ) , or what?
>>> >
>>> > Why is "rbegin() const" not so marked? Same question for crbegin().
>>> >
>>> >
>>> > I assumed the reader would be able to extrapolate from one to the
>>> others. Plus it's a large block of text. Maybe should go in a footnote and
>>> use a reference marker.
>>> "extrapolate" makes no sense in a specification intended for an
>>> ISO standard. If you want to say something, you need to say it
>>> explicitly.
>>> In particular for noexcept, we want to be rather conservative.
>>> So, if you don't want to prescribe "noexcept" for all implementations,
>>> this should never be noexcept.
>>> > Why do we need this funny restriction anyway? Can the implementation
>>> > specialize reverse_iterator<colony::iterator> to do the right thing and
>>> > avoid the undefined behavior for rbegin() with no runtime cost and no
>>> > insane code cost? If so, that should be required, not
>>> implementation-defined.
>>> >
>>> >
>>> > 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.
>>> > - 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.
>>> > If you need to return several values, use a struct with nice member
>>> names.
>>> >
>>> >
>>> > ... Why. How is creating an arbitrary struct type, having the user
>>> instantiate one, and then have to get rid of it, any better than
>>> passing-by-reference. It's a waste of time for both the implementor and the
>>> user.
>>> 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.
>>> I don't care for the (small) implementation effort.
>>> See the range-based algorithms in clause 25, where this
>>> pattern is rather pervasive.
>>> > - similar for get_index_from_iterator; Why can't we use
>>> std::distance(begin(), it)
>>> > instead?
>>> > (We have "Complexity: Same as distance specialized algorithm, see
>>> below.", so there
>>> > seems to be no benefit.)
>>> >
>>> >
>>> > If you read the implementation
>>> I don't care for the implementation. I care for the specification that
>>> aspires
>>> to be in the standard.
>>> > 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?
>>> > 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.
>>> The C++ abstract machine has no way of expressing "cache locality", btw.
>>> > - 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).
>>> > "Complexity: Implementation-defined. One strong strategy involves
>>> using the standard library's sort function to sort an array of pointers to
>>> colony elements by the value of the elements they point to, and would have
>>> std::sort()'s complexity."
>>> >
>>> > This is, of course, idle chatter. If there is a reasonable
>>> implementation
>>> > strategy that is O(n log n), we should simply require that complexity
>>> and be
>>> > done with it.
>>> > That also is an open question. See Questions for Committee section.
>>> 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).
>>> > - 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".
>>> > - 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.
>>> > - 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".
>>> Jens
>>> _______________________________________________
>>> SG14 mailing list
>>> SG14_at_[hidden]
>>> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>>> _______________________________________________
>>> SG14 mailing list
>>> SG14_at_[hidden]
>>> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>> _______________________________________________
> SG14 mailing list
> SG14_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/sg14

SG14 list run by sg14-owner@lists.isocpp.org

Older Archives on Google Groups