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
