Quick question concerning Array lengths and memory allocations.

When an array.length = array.length + 1 (or length - 1) happens, does the system only increase (decrease) the memory allocation by 1 [unit] or does it internally mantain a buffer and try to minimise the resizing of the array?

I think I can remember seeing posts saying to maintain the buffer yourself and other posts saying it was done automatically behind the scenes.

Robert Atkinson wrote:
> Quick question concerning Array lengths and memory allocations.
> 
> When an array.length = array.length + 1 (or length - 1) happens, does the system
> only increase (decrease) the memory allocation by 1 [unit] or does it internally
> mantain a buffer and try to minimise the resizing of the array?
> 
> I think I can remember seeing posts saying to maintain the buffer yourself and
> other posts saying it was done automatically behind the scenes.
> 
> 
> 
> 
Even if the buffer is there I would think that it would be faster to do it your self because you have more information to decide how to do it


char[] first = "foo bar"

func(first[0..3]);


char[] func(char[] inp)
{
		// first time around can't extend in place
		// logic to check this would be costly
	while(go())
		inp.length = inp.length+1;

	return inp;		
}

Robert Atkinson wrote:
> Quick question concerning Array lengths and memory allocations.
> 
> When an array.length = array.length + 1 (or length - 1) happens, does the system
> only increase (decrease) the memory allocation by 1 [unit] or does it internally
> mantain a buffer and try to minimise the resizing of the array?

The latter.

> I think I can remember seeing posts saying to maintain the buffer yourself and
> other posts saying it was done automatically behind the scenes.

In most cases it's not worth it to try and maintain the buffer yourself.  At the very least, you should test both methods and see which is faster.


Sean

Sean Kelly wrote:

> Robert Atkinson wrote:
>> Quick question concerning Array lengths and memory allocations.
>> 
>> When an array.length = array.length + 1 (or length - 1) happens, does the system only increase (decrease) the memory allocation by 1 [unit] or does it internally mantain a buffer and try to minimise the resizing of the array?
> 
> The latter.
> 
>> I think I can remember seeing posts saying to maintain the buffer yourself and other posts saying it was done automatically behind the scenes.
> 
> In most cases it's not worth it to try and maintain the buffer yourself.
>   At the very least, you should test both methods and see which is faster.
> 
> 
> Sean

I think the "double-the-size-when-more-is-needed" strategy is used, and afaik, it is the one that performs best in the general case.

-- 
Lars Ivar Igesund
blog at http://larsivi.net
DSource & #D: larsivi

Robert Atkinson wrote:
> Quick question concerning Array lengths and memory allocations.
> 
> When an array.length = array.length + 1 (or length - 1) happens, does the system
> only increase (decrease) the memory allocation by 1 [unit] or does it internally
> mantain a buffer and try to minimise the resizing of the array?
> 
> I think I can remember seeing posts saying to maintain the buffer yourself and
> other posts saying it was done automatically behind the scenes.
> 
> 

Setting the array length does just that and nothing more or less. But using the the array concatenation operator (~) will preallocate some space.

time this:

    int[] arr;
    for(int i = 0; i < 1000000; i++)
    {
        arr.length = arr.length + 1;
        arr[i] = i;
    }

vs this:

    int[] arr;
    for(int i = 0; i < 1000000; i++)
    {
        arr ~= i;
    }

Dave wrote:
> Setting the array length does just that and nothing more or less. But using the the array concatenation operator (~) will preallocate some space.
> 
> time this:
> 
>     int[] arr;
>     for(int i = 0; i < 1000000; i++)
>     {
>         arr.length = arr.length + 1;
>         arr[i] = i;
>     }
> 
> vs this:
> 
>     int[] arr;
>     for(int i = 0; i < 1000000; i++)
>     {
>         arr ~= i;
>     }

So I did.  :)  My test program:

# module array_alloc;
#
# import cashew .utils .Benchmark ;
# import mango  .io    .Stdout    ;
#
# void main () {
#   auto bench = new BaselineBenchmark ("Index Assign"c);
#
#   for (int i; i < 10; i++) {
#     bench .begin   ();
#     viaIndexAssign ();
#     bench .end     ();
#   }
#
#   Stdout(CR);
#   bench.reset("Cat Assign");
#   for (int i; i < 10; i++) {
#     bench .begin ();
#     viaCatAssign ();
#     bench .end   ();
#   }
# }
#
# void viaIndexAssign () {
#   int[] arr ;
#
#   for(int i; i < 1_000_000; i++) {
#     arr.length = arr.length + 1;
#     arr[i] = i;
#   }
# }
#
# void viaCatAssign () {
#   int[] arr ;
#
#   for(int i; i < 1_000_000; i++)
#     arr ~= i;
# }

And my results, compiling with "-release -O -inline", were:
<Benchmark Index Assign> Baseline 79.090000
<Benchmark Index Assign> 43.830000 & 1.804472 versus baseline
<Benchmark Index Assign> 42.570000 & 1.857881 versus baseline
<Benchmark Index Assign> 42.560000 & 1.858318 versus baseline
<Benchmark Index Assign> 42.410000 & 1.864890 versus baseline
<Benchmark Index Assign> 41.680000 & 1.897553 versus baseline
<Benchmark Index Assign> 41.640000 & 1.899376 versus baseline
<Benchmark Index Assign> 41.580000 & 1.902116 versus baseline
<Benchmark Index Assign> 41.580000 & 1.902116 versus baseline
<Benchmark Index Assign> 41.680000 & 1.897553 versus baseline

<Benchmark Cat Assign> Baseline 0.720000
<Benchmark Cat Assign> 0.600000 & 1.200000 versus baseline
<Benchmark Cat Assign> 0.550000 & 1.309091 versus baseline
<Benchmark Cat Assign> 0.610000 & 1.180328 versus baseline
<Benchmark Cat Assign> 0.600000 & 1.200000 versus baseline
<Benchmark Cat Assign> 0.550000 & 1.309091 versus baseline
<Benchmark Cat Assign> 0.600000 & 1.200000 versus baseline
<Benchmark Cat Assign> 0.610000 & 1.180328 versus baseline
<Benchmark Cat Assign> 0.600000 & 1.200000 versus baseline
<Benchmark Cat Assign> 0.550000 & 1.309091 versus baseline


DMD 0.160, Win32.
That's a rather disturbing disparity, if you ask me.  Now, what I didn't test but probably should have, was the effect of "pre-allocating" the array by setting the .length to a large value and then back to zero, expanding the behind-the-scenes capacity of the array.  I'm betting in that case the IndexAssign would be the faster.

-- Chris Nicholson-Sauls

On Fri, 09 Jun 2006 05:33:33 +1000, Chris Nicholson-Sauls <ibisbasenji@gmail.com> wrote:

> Now, what I didn't test but probably should have, was the effect of "pre-allocating" the array by setting the .length to a large value and then back to zero, expanding the behind-the-scenes capacity of the array.   I'm betting in that case the IndexAssign would be the faster.

Not if you set it back to zero. If you do that, D also deallocates the RAM. Setting its length back to 1 however is okay it that the allocated RAM stays allocated to the array. This means that the first element is just a dummy to get around the 'bug'.


-- 
Derek Parnell
Melbourne, Australia

Lars Ivar Igesund wrote:
> Sean Kelly wrote:
> 
>> Robert Atkinson wrote:
>>> Quick question concerning Array lengths and memory allocations.
>>>
>>> When an array.length = array.length + 1 (or length - 1) happens, does the
>>> system only increase (decrease) the memory allocation by 1 [unit] or does
>>> it internally mantain a buffer and try to minimise the resizing of the
>>> array?
>> The latter.
>>
>>> I think I can remember seeing posts saying to maintain the buffer
>>> yourself and other posts saying it was done automatically behind the
>>> scenes.
>> In most cases it's not worth it to try and maintain the buffer yourself.
>>   At the very least, you should test both methods and see which is faster.
>>
>>
>> Sean
> 
> I think the "double-the-size-when-more-is-needed" strategy is used, and
> afaik, it is the one that performs best in the general case.
> 

Hum, and happens when one shortens the length of the array? The Memory Manager "back" buffer size remains the same?

-- 
Bruno Medeiros - CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D

On Mon, 12 Jun 2006 09:11:04 +1000, Bruno Medeiros <brunodomedeirosATgmail@SPAM.com> wrote:

> Hum, and happens when one shortens the length of the array? The Memory Manager "back" buffer size remains the same?

Yes. However there is a bug (oops - an issue) in which if the length is set to zero the RAM is released back to the the system.

-- 
Derek Parnell
Melbourne, Australia

Derek Parnell wrote:
> On Mon, 12 Jun 2006 09:11:04 +1000, Bruno Medeiros <brunodomedeirosATgmail@SPAM.com> wrote:
> 
>> Hum, and happens when one shortens the length of the array? The Memory Manager "back" buffer size remains the same?
> 
> Yes. However there is a bug (oops - an issue) in which if the length is set to zero the RAM is released back to the the system.
> 
> --Derek Parnell
> Melbourne, Australia

That makes perfect sense, why would it be a bug?

-- 
Bruno Medeiros - CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D