D array expansion and non-deterministic re-allocation

[Andrei Alexandrescu]

Bartosz Milewski wrote:
> Andrei Alexandrescu Wrote:
> 
>> I'm not sure I figure what the issue is, and I'd appreciate a
>> rehash of the few other issues brought up. (I thought they had been
>> responded to.)
> 
> 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.


Andrei