Subject: Re: New colony proposal - feedback requested
From: Matthew Bentley (mattreecebentley_at_[hidden])
Date: 2020-05-02 00:05:53
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
On Fri, 1 May 2020 at 22:21, Jens Maurer <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 "184.108.40.206
deque specialized algorithms".
> - 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
- 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
> - "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 220.127.116.11 Class template deque overview.
- 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().
- " // 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
> "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
> 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
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.
> - These block capacity functions use a "Skipfield" type (plus redundant
> but the default arguments in the constructor use size_type. That seems
Good point. This is relevant to the current implementation but possibly not
to others. Will fix.
> - 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.
> If you need to return several values, use a struct with nice member
... 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
> - similar for get_index_from_iterator; Why can't we use
> std::distance(begin(), it)
> (We have "Complexity: Same as distance specialized algorithm, see below.",
> so there
> seems to be no benefit.)
If you read the implementation 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 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.
- Why do we need MoveInsertable for "reserve" anyway? Aren't we just
> 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.
"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
> done with it.
That also is an open question. See Questions for Committee section.
> - splice p17:
> "Better performance may be gained in some cases by allowing the source
> blocks to go to the front rather than the back, depending on how full the
> final block in x's iterative sequence is. This is because unused elements
> that are not at the back of colony's iterative sequence will need to be
> marked as skipped, and skipping over large numbers of elements will incur a
> small performance disadvantage during iteration compared to skipping over a
> small number of elements, due to memory locality."
> You must be kidding me, right? Burn that with fire and move the ashes
> to the prose section of the paper.
Okay calm down.
> - 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.
> - 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
That constructor is not possible as it creates overload conflict with the
fill constructor when using integers.
> - 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
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.
> 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?
SG14 list run by email@example.com
Older Archives on Google Groups