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
