> Thanks again, and once more, take anything I don't comment on as accepted criticism/explanation.
Your response didn't go to the list. I've added the list again.
Ah, whoops - thanks. But you added the incorrect list address- correcting here.
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.
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.
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).
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();
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. You could just go with size_t I guess. 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.
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.
>> 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.
From my old reading of gcc/boost posts, I think the libstdC++ people are pretty against allocating memory during a sort.
> Because that's an edge case outside of get_index_from_iterator and results in performance loss in general use when you specialize for it.
One missed branch, I hope?
More than one.
Anyway, there seems to be rationale for going beyond std::distance(begin(), it)
that should be recorded in the "Design Decisions" section.
Fair enough.
> 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?
>
> 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.
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.
> Okay, you're trying to get me to move some prose to the tech spec and some to the design decisions. Is there a guide as to what prose belongs where?
Anything explaining "why" should go to the "Design Decisions".
Anything allowing to judge whether my independent (assume bad-faith) implementation
of std::colony is conforming or not (given arbitrarily hostile template parameters
and arbitrarily hostile sequences of operations) needs to into the specification.
Example:
As I said above, "cache-locality" (for instance) is nothing you can talk about
in the C++ standard (because the abstract machine doesn't provide vocabulary
for it), but you might want to talk about only allowing at most one memory
allocation (observable via the Allocator template parameter) per "min"
inserts or so.
Okay. Will contemplate that.
Thanks once again,
Matt