D array expansion and non-deterministic re-allocation

[Andrei Alexandrescu]

Steven Schveighoffer wrote:
[snip]
> Andrei has mentioned that he thinks we can store the allocated length in 
> the GC block, which I think would also work.  You also wouldn't need an 
> MRU cache in that case, but he says it's in *addition* to the MRU cache, 
> so I'm not sure what he means.
[snip]

Reaching the GC block is relatively expensive, so the MRU still helps. 
In essence it's like this. When appending:

a) look up the cache, if there, you have O(1) amortized append that's 
really fast

b) if not in the cache, talk to the GC, still O(1) amortized append 
that's not as fast

Both help providing an important performance guarantee. I was a bit 
worried about guaranteeing "O(1) amortized append for up to 8 arrays at 
a time."


Andrei