RFC on range design for D2

[bearophile]

Few benchmarks, appending ints, note this is a worst-case situation (other benchmarks are less dramatic). Just many appends, followed by the "release":

benchmark 10, N=10_000_000:
  Array append:  0.813 s
  ArrayBuilder:  0.159 s
  ArrayAppender: 1.056 s

benchmark 10, N=100_000_000:
  Array append:  10.887 s
  ArrayBuilder:   1.477 s
  ArrayAppender: 13.305 s

-----------------

Chunk of the code I have used:

struct ArrayAppender(T)
{
     private T* _buffer;
     private size_t _length;
     private size_t _capacity;

     void build(T[] array)
     {
         _buffer = array.ptr;
         _length = array.length;
         //if (_buffer) _capacity = .capacity(array.ptr) / T.sizeof;
     }

     size_t capacity() /* const */ { return _capacity; }

     void putNext(T item)
     {
         /* invariant */ int desiredLength = _length + 1;
         if (desiredLength <= _capacity)
         {
             // Should do in-place construction here
             _buffer[_length] = item;
         }
         else
         {
             // Time to reallocate, do it and cache capacity
             auto tmp = _buffer[0 .. _length];
             tmp ~= item;
             _buffer = tmp.ptr;
             _capacity = this.capacity() / T.sizeof;
         }
         _length = desiredLength;
     }

     T[] release()
     {
         // Shrink-to-fit
         //auto result = cast(T[]) realloc(_buffer, _length * T.sizeof);
         auto result = cast(T[]) gcrealloc(_buffer, _length * T.sizeof);
         // Relinquish state
         _buffer = null;
         _length = _capacity = 0;
         return result;
     }
}

unittest
{
     auto app = arrayAppender(new char[0]);
     string b = "abcdefg";
     foreach (char c; b) app.putNext(c);
     assert(app.release == "abcdefg");
}


    void benchmark10(int ntest, int N) {
        putr("\nbenchmark 10, N=", thousands(N), ":");

        if (ntest == 0) {
            auto t0 = clock();
            int[] a1;
            for (int i; i < N; i++)
                a1 ~= i;
            auto last1 = a1[$ - 1];
            auto t2 = clock() - t0;
            putr("  Array append: %.3f", t2, " s   ", last1);
        } else if (ntest == 1) {
            auto t0 = clock();
            ArrayBuilder!(int) a2;
            for (int i; i < N; i++)
                a2 ~= i;
            auto last2 = a2.toarray[$ - 1];
            auto t2 = clock() - t0;
            putr("  ArrayBuilder: %.3f", t2, " s   ", last2);
        } else {
            auto t0 = clock();
            ArrayAppender!(int) a3;
            a3.build(null);
            for (int i; i < N; i++)
                a3.putNext(i);
            auto last3 = a3.release()[$ - 1];
            auto t2 = clock() - t0;
            putr("  ArrayAppender: %.3f", t2, " s   ", last3);
        }
    }

Bye,
bearophile