RFC on range design for D2

[Andrei Alexandrescu]

Sean Kelly wrote:
> Andrei Alexandrescu wrote:
>>
>> I gave it some more thought and I have a theory for the root of the 
>> issue. My implementation assumes there's exponential (multiplicative) 
>> increase of capacity in the built-in ~=. I hope Walter wouldn't do 
>> anything else. If there are differences in growth strategies between 
>> D1 and D2, that could explain the difference between bearophile's 
>> benchmarks and mine.
> 
> Arrays larger than 4k grow logarithmically, smaller than 4k they grow 
> exponentially.  This is certainly true of D1 and Tango, and I'd assume 
> D2 is no different.

Yes, but with in-place expansion, effective growth stays exponential 
even beyond 4k. So I'm not that worried that it could become quadratic, 
unless there are some really wicked workloads.

I modified my putNext to print what's happening:

     void putNext(T item)
     {
         if (_end < _eos)
         {
             // Should do in-place construction here
             *_end++ = item;
         }
         else
         {
             // Time to reallocate, do it and cache capacity
             auto tmp = _begin[0 .. _end - _begin];
             tmp ~= item;
             if (_begin != tmp.ptr)
             {
                 _begin = tmp.ptr;
                 _end = _begin + tmp.length;
                 writeln(_end - _begin);
             }
             else
             {
                 ++_end;
             }
             _eos = _begin + .capacity(_begin) / T.sizeof;
         }
     }

Notice the writeln. On my system the console reads:

benchmark 10, N=75000000:
1
5
9
17
33
65
129
257
513
253953
1155073
4743169
18505729
68861953

That's exponential alright. On the other hand, if you move the writeln 
after the if, indeed:

1
5
9
17
33
65
129
257
513
1025
2049
3073
4097
5121
6145
7169
8193
9217
10241
11265
12289

But it's the former column that matters, because moving chinks is where 
real work is being done. In-place block expansion should take constant time.

With this behavior in place, my code amortizes calls to capacity() by a 
factor of 1024, and keeps amortized append complexity constant.


Andrei