D array expansion and non-deterministic re-allocation

Bartosz Milewski bartosz-nospam at relisoft.com
Mon Nov 23 11:40:08 PST 2009


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




More information about the Digitalmars-d mailing list