View mode: basic / threaded / horizontal-split · Log in · Help
February 20, 2012
Re: std.collection lets rename it into std,ridiculous.
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.
February 20, 2012
Re: std.collection lets rename it into std,ridiculous.
D as in Development Hell.
February 20, 2012
Re: std.collection lets rename it into std,ridiculous.
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...
February 20, 2012
Re: std.collection lets rename it into std,ridiculous.
"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.
February 20, 2012
Re: std.collection lets rename it into std,ridiculous.
> 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.
February 20, 2012
Re: std.collection lets rename it into std,ridiculous.
> 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.
February 20, 2012
Re: std.collection lets rename it into std,ridiculous.
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
February 20, 2012
Re: std.collection lets rename it into std,ridiculous.
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

-- 
Государство делает вид, что платит нам зарплату, а мы делаем вид, что работаем.
February 20, 2012
Re: std.collection lets rename it into std,ridiculous.
> 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.
February 20, 2012
Re: std.collection lets rename it into std,ridiculous.
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
1 2 3 4 5
Top | Discussion index | About this forum | D home