std.collection lets rename it into std,ridiculous.

[Jonathan M Davis]

On Monday, February 20, 2012 10:34:20 Andrei Alexandrescu wrote:
> On 2/20/12 10:13 AM, Daniel Murphy wrote:
> > "H. S. Teoh"<hsteoh at quickfur.ath.cx> wrote in message
> > news:mailman.666.1329752861.20196.digitalmars-d at puremagic.com...
> > 
> >>> 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.

The reality of the matter is that you need to understand how arrays work in D 
in order to use them efficiently. And for something like a stack or a queue, you 
really should use a wrapper. Yes, D arrays are extremely powerful, but that 
doesn't mean that you won't need to wrap them in a container type for some 
types of usage, just like you'd wrap an array in many other languages.

- Jonathan M Davis