On 2/20/12 10:13 AM, Daniel Murphy wrote:
"H. S. Teoh"<[email protected]> wrote in message
news:[email protected]...
Won't this reallocate every time you pop an element and then push a
new one?
[..]
Nope, it doesn't. That's the power of D slices. When you create a
dynamic array, the GC allocates a certain amount of memory, let's call
it a "page", and sets the array to point to the beginning of this
memory. When you append to this array, it simply uses up more of this
memory. No reallocation actually occurs until the page is used up, at
which point the GC allocates a larger page to store the array in.
This scheme means that this code is very efficient for small stacks,
because there's no repeated allocation/deallocation (which if you ever
played with malloc/free, you'd know are expensive), just updating a few
pointers. For large stacks, the reallocations only take place
occasionally, so even in that case performance is still pretty good.
This is incorrect.
eg:
T[] stack = new immutable(int)[](20);
stack ~= 3; // probably does it in place
auto stack2 = stack[]; // take a slice of the full stack
stack = stack[0..$-1]; // ok, take a slice
stack ~= 7; // must reallocate to avoid overwriting immutable memory
Try it out, it works the same with mutable elements.
Yah, assumeSafeAppend() needs to be used in the stack implementation. I
don't know how we can address this better.
Andrei
