On 02/20/2012 06:30 AM, James Miller wrote:
> On 20 February 2012 16:43, H. S. Teoh<hsteoh@quickfur.ath.cx>  wrote:
>> On Mon, Feb 20, 2012 at 04:19:10PM +1300, James Miller wrote:
>> [...]
>>> My feedback is that for most people's purposes, associative arrays and
>>> arrays (dynamic and static) are fine. PHP doesn't have a well-used
>>> collections library (though it does exist) but it is used by millions
>>> of sites every day. I don't normally need an explicit
>>> queue/stack/priority queue.
>> [...]
>>
>> The convenience and flexibility of D's arrays have, for the most part,
>> replaced my need for explicit stacks or queues. For example, here's a
>> stack:
>>
>>         T[] stack;
>>         void push(elem) {
>>                 stack ~= elem;
>>         }
>>         T pop() {
>>                 T elem = stack[$-1];
>>                 stack = stack[0..$-1];
>>                 return elem;
>>         }
>>
>> Here's a queue:
>>
>>         T[] queue;
>>         void enqueue(elem) {
>>                 queue ~= elem;
>>         }
>>         T dequeue() {
>>                 T elem = queue[0];
>>                 queue = queue[1..$];
>>                 return elem;
>>         }
>>
>> It's so trivial to implement that it's hardly worth the effort to
>> implement a class for it.
>>
>> Your mileage may vary, though.
>>
>>
>> T
>
> The cool thing about that implementation is that, by using slices, you
> generally avoid allocation, unless its neccessary.

As far the queue is concerned. The stack implementation misses an assumeSafeAppend and will reallocate unnecessarily.

D as in Development Hell.

On Mon, Feb 20, 2012 at 09:33:51AM +0100, a wrote:
> >here's a stack:
> >
> >	T[] stack;
> >	void push(elem) {
> >		stack ~= elem;
> >	}
> >	T pop() {
> >		T elem = stack[$-1];
> >		stack = stack[0..$-1];
> >		return elem;
> >	}
> 
> 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.


T

-- 
If you want to solve a problem, you need to address its root cause, not just its symptoms. Otherwise it's like treating cancer with Tylenol...

"H. S. Teoh" <hsteoh@quickfur.ath.cx> wrote in message news:mailman.666.1329752861.20196.digitalmars-d@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.

> 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.

Yes, it does. When you take a slice of an array and then append
an element to it, the slice has to be reallocated or the element
in the original array after the end of the slice would be
modified. For example:

auto a = [1,2,3,4,5];
auto b = a[0..3];
b ~= 0;
writeln(a);

If b was not reallocated, the code above would print [1, 2, 3, 0, 5],
which is probably not what one would expect. This would cause problems
if a function took array as a parameter and then appended to it. If
you passed an array slice to such function you would have a
non-deterministic bug - when the appending would cause reallocation,
everything would be okay, but when it wouldn't, the function would
modifiy the array outside of the slice that was passed to it. Arrays
in D used to work like that IIRC. Someone in this thread mentioned
that you should use assumeSafeAppend for stack implementation (I did
not know about assumeSafeAppend before that). The following code:

auto a = [1,2,3,4,5];
auto b = a[0..3];
assumeSafeAppend(b);
b ~= 0;
writeln(a);

prints [1, 2, 3, 0, 5], so b is not reallocated in this case.

> auto a = [1,2,3,4,5];
> auto b = a[0..3];
> assumeSafeAppend(b);
> b ~= 0;
> writeln(a);
>
> prints [1, 2, 3, 0, 5], so b is not reallocated in this case.

Just to clarify: this is not guaranteed to print [1, 2, 3, 0, 5], it only does
if there is still enough memory in a block allocated to b and it doesn't have
to be reallocated.

On 2/20/12 10:13 AM, Daniel Murphy wrote:
> "H. S. Teoh"<hsteoh@quickfur.ath.cx>  wrote in message
> news:mailman.666.1329752861.20196.digitalmars-d@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.

Andrei

On Mon, Feb 20, 2012 at 05:16:17PM +0100, a wrote:
> >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.
> 
> Yes, it does. When you take a slice of an array and then append an element to it, the slice has to be reallocated or the element in the original array after the end of the slice would be modified.

I know that. But we're implementing a stack here. The stack slice is the only thing that refers to that part of the memory. The reallocation only happens if you start making external references to elements/slices on the stack. But if you only access it via push() and pop(), then there are no other references to the stack, so why should the GC reallocate it on append?


T

-- 
Государство делает вид, что платит нам зарплату, а мы делаем вид, что работаем.

> But if you only access it via push() and pop(), then there are no other references to the stack, so why should the GC reallocate it on append?

Because the GC doesn't know there aren't any other references to it unless you tell it with assumeSafeAppend.

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@quickfur.ath.cx> wrote in message news:mailman.666.1329752861.20196.digitalmars-d@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