Array length & allocation question

Chris Nicholson-Sauls ibisbasenji at gmail.com
Thu Jun 8 12:33:33 PDT 2006


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



More information about the Digitalmars-d-learn mailing list