C++ Logo

SG14

Advanced search

Subject: Re: New colony proposal - feedback requested
From: Bryce Adelstein Lelbach aka wash (brycelelbach_at_[hidden])
Date: 2020-05-12 19:56:02


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?
> LEWG? SGXX?
> 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?
>> LEWG? SGXX?
>> 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
>> "26.3.8.5 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 26.3.8.1 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 list run by sg14-owner@lists.isocpp.org

Older Archives on Google Groups