== Quote from Andrei Alexandrescu (seewebsiteforem...@erdani.org)'s article > 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
But one of my biggest gripes about the current appending implementation, far more important from a practical perspective than any theoretical safety guarantees, is that it doesn't scale to multiple threads. I've experienced this in a real-world program that I translated from someone else's C++ code that used vector::push_back() quite liberally inside core algorithms. (The reason is that it was written more for simplicity/readability than performance, so the person who wrote it never thought to optimize this kind of stuff.) When I did a literal translation of this to D, everything was completely serialized. It didn't even scale to two cores. I had to rewrite significant portions of the code in a way that did not use appending to get it to scale at all. D is supposed to be a language that is geared toward multi-threading. If something as simple as array appending is a threading bottleneck (and it was for me in a real-world program), I don't care if it is O(1) because effectively it has a constant the size of Jupiter.