D array expansion and non-deterministic re-allocation

[Andrei Alexandrescu]

Bartosz Milewski wrote:
> Andrei Alexandrescu Wrote:
> 
> 
>>> Some of the points are in my message from Sat, 05:19 pm. Especially
>>> this point: Can a conforming implementation simply re-allocate on
>>> every expansion? You make it sound like that would violate some
>>> performance guarantees but there are no specifics.
>> I don't think a conforming implementation is allowed to do that. The 
>> functioning of many algorithms assumes constant-time append. If D can't 
>> guarantee that, those algorithms won't work.
>>
>> I've been deliberately vague in the book because I wasn't sure we can 
>> offer a guarantee if the cache is filled. Now I know we can: if a memory 
>> block stores the requested size in addition to today's effective 
>> capacity, then the allocator can overallocate growing arrays and then 
>> detect and correctly handle in-place reallocation requests, even when 
>> the MRU cache capacity is exceeded. There would be a larger cost for 
>> that (acquiring a lock), but it's still a constant amortized per-element 
>> cost.
> 
> I wish we had some performance numbers to support this optimization. There's always a break-even point between O(1) and O(N) and I wonder at what N it happens. Also, how often does it happen that the cache is full--whether it's normal state or an exception. Hitting the cache and the heap lock on every extension will also break locality. There are so many factors...

Very true. It would be great if you or someone else interested could 
find the time to run a few tests. I am committed way over the top and 
simply cannot look into this.

Andrei