On 06/05/2020 01.59, Matthew Bentley via SG14 wrote:
> Ah, whoops - thanks. But you added the incorrect list address- correcting here.

I hope we're back on track now.

> 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".
>
>
> Torn here between obviating future improvements and being specific. It needs to stay in order for current implementations to be useful to, in particular, embedded folk, so it would be an unsigned integer type. If future implementations don't use it or use something different, it can be gracefully deprecated I guess.

We have the usual cognitive issue of implementation vs. specification here.
I have no objection that your implementation feels that a Skipfield template
parameter is a good idea here. However, your implementation is not the
specification. The specification is what goes into the standard text wording
and which (I presume) you strive to provided in your "Technical
Specification" section.

The purpose of that wording is to allow independent implementations
to exist, and to judge whether such independent implementations are
conforming ("good") or not. It's not dissimilar to some legal text,
which allows to judge whether some real-world action is objectionable
or not. That means, the wording must be self-contained, unambiguous
and complete.

The end goal is to allow porting of user programs from one implementation
to another. The user program needs to know which features it can rely
on, by carefully inspecting the standard wording only.

This e-mail exchange is solely about getting the "Technical Specification"
as complete and unambiguous and generally high-quality as possible.

Note that implementations (in general) are allowed to add additional
(defaulted) template parameters, I believe, as a conforming extension.

So, back to "Skipfield". If the "Skipfield" template parameter is mentioned
in the specification anywhere, it establishes a requirement on independent
implementations to provide such a Skipfield parameter. However, what
should they do with that parameter? Just ignore it? If you don't tell
implementations in the wording, they won't know.

In the interest of clarity, let me state I will strongly oppose progressing
this paper at any level (SG14, LEWG, LWG, WG21, CD, DIS) with such known
glaring holes in the wording. (My expectation is, though, that simply
pointing out the hole to LWG will stop it in its tracks right there.
See https://cplusplus.github.io/LWG/lwg-active.html#3213 and
https://cplusplus.github.io/LWG/lwg-active.html#3439 where we discovered
similar holes a bit late.)

> 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.
>
>
> I don't think the C++ spec specifies that iterators have to be bounded?
> But certainly including bounding creates performance detriment and should be optional.
> In a bounded iterator --end() would be non-problematic, in a non-bounded would result in undefined behaviour.

What do you mean by "bounded"?

The C++ standard library containers generally assert that
[ begin(), end() ) denotes a half-open range. You can move
around within that range using ++ and -- on iterators. Using
iterator operations to attempt to go outside that range is
undefined behavior.

> 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.
>
>
> I'm going to look into whether or not specifying min/max limits for block capacities without changing the capacities of existing blocks can have any adverse effects ie. if block 1 is capacity 4, and set_block_capacity_limits sets min capacity to 10, whether leaving block 1 at capacity 4 could have any adverse effects.
> If not, will re-implement so that it's a simple "set variables" operation without any side effects.
> If so, will re-implement so that set_block_capacity_limits doesn't include the reallocation code when the type is non-copyable/movable (via constexpr and type_traits).

That seems a step in the wrong direction. If you want to offer an
interface that does not reallocate, but just sets the new min/max
parameters (and thus has different requirements on the contained T),
that's fine.

However, that's a different operation (and thus should get a different name)
compared to an operation that does perform the reallocation and thus
has a few more requirements on T.

Both operations appear to be useful in general; the second one probably
more so than the third.

> 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.
>
>
> I tried implementing it your way, but the code-smell got bad pretty quickly.
> You end up with code like:
> plf::colony<int, my_allocator_type>::minmax block_sizes;
> block_sizes = i_colony.get_block_capacity_limits();

auto block_sizes = i_colony.get_block_capacity_limits();

or, as I said earlier, just use structured bindings.

I'd also expect you to have a typedef for your container type
if you are, in fact, using a non-standard allocator.

> You have to make the struct internal to colony otherwise you can't guarantee that the allocator will supply the same size_type to block_sizes as it does to colony.

Yes.

> You could just go with size_t I guess.

Would it be a problem if the outward-facing interface would always use size_t here?
Block sizes > 2^32 should be rare anyway, right?
(My guess is you get a std::length_error exception if the value given in the interface
doesn't fit into the Allocator's size_type.)

If so, you can just have a
  struct X { size_t min, max; };

which is non-dependent and thus doesn't need to be a nested class of std::colony.

I'm not sure I like the "runtime failure if overflow" approach here, though.
As opposed to forwarding the Allocator's size_type in the interface.

> But the main issues were with using it with constructors, where you end up with this:
> plf::colony<int, my_allocator_type>::minmax block_sizes = {50, 500};
> plf::colony<int, my_allocator_type> i(block_sizes, my_allocator_instance);
>
> or worse:
>
> plf::colony<int, my_allocator_type> i(plf::colony<int, my_allocator_type>::minmax block_sizes(50, 500), my_allocator_instance);
>
> I tried passing via a bracketed pair of ints, but of course that makes it go into the initializer_list constructor instead.

Ah. A crowded space.

> I think in this instance, the way I've done it is best, or results in less ugly code for the end user. I think the frequency of usage of get_block_capacity_limits does not justify creation of a struct for this purpose. The standard does use pass-by-reference for return parameters, in places - eg. istream& getline - so it's not a big deal I feel.

getline and "std::cin >> x" is probably 3 decades old and hardly a role model.

> >> 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.
>
>
> It doesn't - it does a basic merge-sort in all implementations I've seen. I pretty much came up with the pointer-sort dereferencing hack (https://plflib.org/list.htm#details) - or at least I haven't seen it elsewhere - that's why plf::list sorting is 77% faster than std::list (see: https://plflib.org/benchmarks_haswell_gcc.htm#sort).
> From my old reading of gcc/boost posts, I think the libstdC++ people are pretty against allocating memory during a sort.

Hm.

Does your "allocate a pointer array" approach in any way depend on the
internals of std::colony?

If not, maybe the right approach is to offer a stand-alone, self-contained
algorithm "indirect_sort" or so that can sort any range of forward iterators
and that expressly allocates memory, instead of providing a specialized
member function just for this single container.

With that approach, std::list would also benefit indirectly.

> > 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.
>
>
> I don't think there are abstract explanations for all the parameters which the other containers are able to influence either, at least not to the depth you're talking about. Prove me wrong?

Proving a "for all" theorem over prose text is hard, of course.
Let's turn this around:

If you find an example of an unspecified parameter in the existing standard text,
please tell me about it, because that needs to become an LWG issue urgently.
(For example, std::deque also has a block size internally, but it is never
exposed in the interface.)

> > 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.
>
>
> Not really. I think the C++ abstract machine is based on some fairly old understandings which don't hold true anymore ie. that time complexity is strongly relevant in some capacity (latency, overall performance) which it isn't outside of large N or large sizeof(N). That being the case, it's not something I should overly concern myself with, as the computers it was designed for no longer exist.

The O(N or whatever) complexities given in the standard library descriptions
concern observable behavior of the algorithms, e.g. the number of invocations
of the copy constructor or the number of invocations of a comparison.

You can observe by simply counting the number of calls in your container
element type T.

If you believe the C++ abstract machine description is no longer fit for its purpose,
you're very welcome to propose an update to EWG/CWG. Note that the entire
state-of-the-art of compiler optimizations critically depends on the as-if
rule formulated in [intro.abstract], so please tread carefully.
(Allowing to specify something like P1315 secure_clear is in the same realm.)

> 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.
>
>
> There has been no pushback so far from colony having bidirectional iterators with additional relational operators. The iterators have always been specified as bidirectional. If you have a rational objection I'd be interested in hearing it.

All I'm saying is that the "technical specification" doesn't say that
std::colony's iterators have relational operators, so independent
implementations won't provide them, so portable user programs can't use
them. If that's not your desired end-state, the "technical specification"
needs to say something about relational operators, and probably specify
their semantics (because you can't use the RandomAccessIterator
specification framework, obviously).

Jens