why does array appending add a page size instead of doubling ?

[Ali Çehreli]

On 02/02/2013 06:22 PM, timotheecour wrote:
 > What's the rationale behind array appending adding a page size to
 > capacity

It is not always the case. The page is added only if the next page 
conveniently free. There is no cost for that "allocation".

 > instead of doubling,

Rather, a better growth factor is 150%. It has been shown that 150% 
growth factor works much better with memory allocators.

 > after the size of the array reaches a
 > certain size (cf what std::vector does) ? That seems like an example of
 > (evil?) early optimization.

Wouldn't you prefer simply increasing the allocation size without 
copying any elements? A growth strategy that always doubled would have 
to give up even if the next page has been free.

 > ----
 > T[]a;
 > int n=some big value;
 > foreach(i;0..n)
 > a~=T.init;
 > ----
 > Depending on T.sizeof or n, the code above will be linear complexity in
 > n (while capacity remains below page size) or quadratic (while capacity
 > increments are one page at a time).

Have you actually tested the performance? You should not see linear 
complexity.

 > Would love some explanations!

The best explanation is this document:

   http://dlang.org/d-array-article.html

Ali