>
> 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.)

As noted, part of my submitting this paper to SG14 is to try and find opinions and solutions to such ambiguities. For the next revision I'll try to include wording at the front of the tech spec which shows the explicitness of the multiple-memory block model, capacity limits + the relationship to the skipfield_type parameter. But in the interests of SG14 and it's members, including embedded, the whole thing is of less worth without the skipfield_type or capacity limiting capability - partially because capacity limiting allows developers to customise block sizes for a specific cache.

 

>     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"?

Some implementations such as MSVC have optional bounded iterators which will refuse to go before begin() or after end().

 
> 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.

The way I've got it implemented in a test implementation, is that it's the same interface, but if the type is non-copyable/movable, and the container isn't empty, it returns an error code. It would essentially move the responsibility from the interface to the programmer to clear() the container first if they're (a) using a non-copyable/movable type (b) they want to change the capacities but (c) have already inserted elements. It would also return an error code in this scenario if the type was copyable/movable but not empty and it failed in it's allocation of the memory for the new memory blocks to reallocate to. Alternatively it could throw instead of returning an error code, I have no strong feelings either way on that one. Your feeling?

I think it's better to do this than simply set the values and assume that these are for future block capacities only, as there is no way for the programmer to know what blocks currently use which capacities, and hence no way for them to make a decision on that basis to reallocate from existing blocks.

 
> 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();

I'm aware of that but my personal bugbear is to try and discourage the use of auto, it moves the required knowledge of what type you're using from the code to an external function definition, which isn't great for readability in my view.



>   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?

I think so. From my measurements, there's no performance advantage to be had in almost any scenario from having block sizes larger than 65535, but I can't predict a potentially better future implementation, so *shrug*.



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.

You could, I suppose, template the struct and supply the allocator direct to it, but then, there's no 100% guarantees.



> 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.

So long as that allowed for specializations for a given container, that might work,
but the main reason std::list has it's own internal sort function is because it only changes the next/previous pointers, no elements get reallocated -  unlike colony and most other containers.
You can of course do the same pointer technique with the next/previous pointers of std::list, which is more or less what I did with plf::list, but that requires a specialization.
 


> 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.)

Okay, so the precondition for inclusion in the tech spec is that it is exposed in the interface. Good to know and fair enough.

 
> 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.

My point is that the reasoning as to why the standard focuses on these things seems to be that they have an impact on performance in some way.
If they don't, it's hard to make a case for relevance. Why would you care about the number of calls, if the number of calls has no discernable impact on runtime behaviour? Or is there some other overarching reason to record about the number of calls?
From my point of view, if the relevance is performance-related then their relevance is greatly diminished compared to other factors. It seems to be a gap in vision to not see that the relevance of these things is as hardware-dependent as almost anything else. The greater the gap between memory and processor speeds becomes, the less relevance time complexity has on performance.

 
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 point is not-so-much that it's not useful, just that the necessary gap between it and realworld machines means that not everything which is pertinent to allowing a given construct to exist, in a given way, is going to be expressible within the language of the abstract machine. If cache locality were to be part of the language of the abstract - that would also be a mistake. Because it's a realworld constraint which may change in 30 years. See my point above about time complexity. That *was* very relevant to performance, once.
But that means I can't justify or express everything within the scope of that language.


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).

Okay cool, will do.
Thanks again,
Matt