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