Array append performance 2

[Denis Koroskin]

On Mon, 01 Sep 2008 01:11:46 +0400, bearophile <bearophileHUGS at lycos.com>  
wrote:

> Fawzi Mohamed:
>> I had not thought about an important thing: the content of the array
>> can change... so copying is safer.
>
> Yes, and there are other problems, that make the situation/code a mess,  
> so I copy all items now, keeping code simpler. I'm  
> debugging/benchmarking it now...
>
> Later,
> bearophile

Please, test my version, too!
While it is slighly slower, it allows appending invariant arrays (i.e.  
strings) without copying data (although it is currently not implemented).

An idea is to store an array (or a list) of invariant elements.
Current buffer is mutable until it is completely full. It then casted to  
invariant and appended to the list and an new mutable buffer (of a higher  
size) created.

struct ArrayBuilder(T) {
     //private BearophileArrayBuilder!(invariant(T[])) subArrays;
     private invariant(T[])[] subArrays;
     private int lengthSoFar;
	
     private T[] tmpArray;
     private int curOffset = 0;

     void opCatAssign(T x) {
         int capacity = tmpArray.length;
         if (curOffset >= capacity) {
             int old_capacity = capacity;

             if (capacity == 0)
                 capacity = 4; // starting point not too much small
             else if (capacity < (1 << 26)) // 67_108_864
                 capacity *= 2; // for amortized O(1) and less RAM  
fragmentation
             else
                 capacity *= 1.3; // slower growing rate to save RAM

             if (old_capacity != 0) {
                 subArrays ~= cast(invariant(T[]))tmpArray;
             }

             tmpArray = new T[capacity];
			curOffset = 0;
         }

         tmpArray[curOffset] = x;
         assert(tmpArray[curOffset] == x);
         ++curOffset;
         ++lengthSoFar;
     }

     ///
     T[] toarray() {
         T[] array = new T[lengthSoFar];
         int offset = 0;
         foreach (subArray; subArrays) {
             int newOffset = offset+subArray.length;
             array[offset..newOffset] = subArray[];
             offset = newOffset;
         }
         array[offset..$] = tmpArray[0..curOffset];
         return array;
     }
}