Thread overview | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
June 08, 2006 Array length & allocation question | ||||
---|---|---|---|---|
| ||||
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. |
June 08, 2006 Re: Array length & allocation question | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert Atkinson | 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;
}
|
June 08, 2006 Re: Array length & allocation question | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert Atkinson | 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 |
June 08, 2006 Re: Array length & allocation question | ||||
---|---|---|---|---|
| ||||
Posted in reply to Sean Kelly | 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 |
June 08, 2006 Re: Array length & allocation question | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert Atkinson | 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;
}
|
June 08, 2006 Re: Array length & allocation question | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dave | 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
|
June 08, 2006 Re: Array length & allocation question | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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 |
June 11, 2006 Re: Array length & allocation question | ||||
---|---|---|---|---|
| ||||
Posted in reply to Lars Ivar Igesund | 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 |
June 12, 2006 Re: Array length & allocation question | ||||
---|---|---|---|---|
| ||||
Posted in reply to Bruno Medeiros | 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 |
June 12, 2006 Re: Array length & allocation question | ||||
---|---|---|---|---|
| ||||
Posted in reply to Derek Parnell | 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 |
Copyright © 1999-2021 by the D Language Foundation