Array append performance 2

[bearophile]

Until some more basic solution is found (and/or answers from Walter regarding how to solve this append performance problem and regarding the idea of adding a third capacity field to dynamical arrays), someone has suggested to create an array builder class, like the string builder of Java. So I have created one, the code is in the attach. Note that code is raw still, not commented, and it does the bare minimum (append one item and extract the array, I'd like to add generic extend methods, and tye possibility to change the capacity/length), its tests are messy still, etc, once I know it's correct I'll improve it and I'll add it to my libs (of course, I can offer a version of this code to Phobos/Tango too).

It's not easy for me to write such GC-based code, so my questions are:
Is ArrayBuilder!() correct in every situation?
Why are the performance of the benchmark3 so low (a bit worse than normal array append)? Can it be improved?


Extra note: while creating it I have found another bug in DMD I didn't know about:

import std.stdio: writefln;
void main() {
    alias int[2] T;
    writefln(T.init);
}

This program has to print [0,0] instead of 0.


Timings, on a Core Duo @ 2 GHz, 2 GB RAM:

benchmark 1, N=2_000_000:
  Array append: 0.160 s
  ArrayBuilder: 0.026 s
benchmark 1, N=20_000_000:
  Array append: 1.837 s
  ArrayBuilder: 0.325 s
benchmark 1, N=50_000_000:
  Array append: 4.489 s
  ArrayBuilder: 0.731 s
benchmark 1, N=200_000_000:
  Array append: 32.293 s
  ArrayBuilder: Out of memory

benchmark 2, N=200_000:
  Array append: 0.099 s
  ArrayBuilder: 0.004 s
benchmark 2, N=2_000_000:
  Array append: 6.896 s
  ArrayBuilder: 0.050 s

benchmark 3, N=200_000:
  Array append: 0.090 s
  ArrayBuilder: 0.076 s
benchmark 3, N=2_000_000:
  Array append: 1.014 s
  ArrayBuilder: 0.923 s (why is this so slow?)
benchmark 3, N=6_000_000:
  Array append: 5.295 s
  ArrayBuilder: 4.431 s

benchmark 4, N=500_000:
  Array append: 1.109 s
  ArrayBuilder: 0.414 s
benchmark 4, N=1_000_000:
  Array append: 3.103 s

Bye,
bearophile
-------------- next part --------------
A non-text attachment was scrubbed...
Name: arraybuilder4.d
Type: text/x-dsrc
Size: 14008 bytes
Desc: not available
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20080830/83b91999/attachment.d>