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