Hi, thanks again for the clarifications-

> I don't follow your choice of the word "ambiguities".
> I'm not seeing anything ambiguous here, just "not sufficiently specified".

I guess I was referring to questions as to whether the skipfield
parameter should be left entirely as a class with no specifications, or
whether it should receive some specifications which are, through lack of
knowledge for future potential options, entirely based around the
implementations that've been done to date.


>> > 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().
>
> That seems more a debugging aid than anything relevant to the specification.

Yes, I was confusing your note about preconditions with actual
implementation dynamics.


>> 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?
>
> "throw" or "error code" is way too much decision-making at runtime for
> a function that fundamentally changes its requirements on the T.

I'm not following you here - the function doesn't change requirements of
T, only the storage of T.


> Summarizing my view on the design here:
>
> - make a pre-existing colony empty with new min/max parameters:
> my_colony = std::colony(min, max); // needs syntactic sugar to disambiguate
> - set new parameters with reallocation (requires T to be movable)
> my_colony.reshape(min, max); // some name that expresses "lots of stuff going on"

Regardless of what ends up here, I quite like 'reshape'.



> It seems the most consistent approach is to go with a nested class
> that implicitly depends on the outer template parameter.
>
> Again, block size manipulations should be rare, so any visual
> impairment of the surrounding code is a fairly minor concern,
> it seems.

Yeah, but if we're using it to disambiguate the constructor when
supplying min/max, it's still a lot of messing about for something
that's just a couple of integers. If anybody has any alternative
suggestions for getting a couple of size_type integers into a
constructor without conflicting with the fill/initializer_list
constructors, I welcome it.


> Would you need/want to specialize for std::colony? At the end, you move the
> contained T's to their appropriate place within the existing std::colony
> (or other container), right?

No, as you say, it's just standard sorting with colony, same as it would
be with most of the forward_iterator-and-upwards containers. I was only
thinking of std::list in that sense.



>> Okay, so the precondition for inclusion in the tech spec is that it is exposed in the interface. Good to know and fair enough.
>
> Or have some other observable behavior. For example, std::future talks about
> "shared state", but that's not directly exposed in the interface per se.

Okay cool.


>> 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?
>
> Well, the number of calls to a client-supplied function is certainly
> performance-relevant: If that function is expensive, going from O(n^2) to,
> say, O(n^3), can certainly be noticeable in real life even for small-ish n.

Sure, it *can* be performance-relevant - it also may not be.
Sorting is slow for std::list, for anything but large sizeof(n) (we're
talking ~480bytes - https://plflib.org/benchmarks_haswell_gcc.htm#sort).
It shouldn't be, because there's no reallocation of elements happening
(unlike with other containers), and the time complexity is n log n, same
as std::sort. It's purely the cache locality - the fact that each
element is allocated individually and is *anywhere* in memory - that
makes it slow.
I would consider time complexity an implementation detail. Of no more
consideration than the number of branch statements involved in the process.



> And the standard library implementation, of course, can't say whether
> an unknown future client-supplied function is expensive or not.

But it also doesn't know whether the data has high locality or not - or
whether the function uses a lot of branching, or whether the machine
it's running on has high tolerance for branch failure (most i-series
processors) or not (core2).


> That said, part of the rationale of the current complexity specification
> language is, of course, that this actually refers to measurable and
> specifiable things in the framework of the abstract machine.

Personally I think the only thing a pure abstract machine should be
concerned about is the machine state before&after an operation, and
whether there are any side effects.


>> 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.
>
> That might be true for your data structures, but not for my (possibly hostile)
> ones. For example, T = std::array<int, 1000000> is expensive to move and swap
> and possibly expensive to compare. For me, a complexity specification for
> sorting a std::vector<T> is very relevant.

Yes, but more relevant is the fact that the vector data is highly local,
as opposed to map or list. Again, see those benchmarks above. If time
complexity is relevant to the abstract machine on the basis of potential
performance, so are a wide variety of other things - locality included.



> You're conflating "justify" and "express". The former is the "why", which goes
> into "Design Decisions" and can have as much hardware cache-locality talk as you
> want. Only the latter is what goes into the "technical specification".

Granted.


> If you feel the cache-locality hint is needed for implementations to do the
> right thing, then maybe you should add a (non-normative) "Note" near the top
> of the std::colony subclause, explaining that fact.
>
> As I said elsewhere, I do believe that the min/max block size has an impact
> on observable behavior of std::colony, e.g. when allocations happen and for
> some complexity statements. And those can certainly be described. Maybe the
> relationship is intricate enough that a separate paragraph at the start of the
> subclause is the more appropriate way of description, instead of stuffing
> that into the individual function descriptions.
>
> Jens
>

Okay, thanks again. At any rate, I think I've got enough to work on now.
I'll be in touch with the group again once I've processed all of the above.