Top 5

[Andrei Alexandrescu]

dsimcha wrote:
> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
> 
>> If anyone wants to try it, I'm pasting the draft version of Appender
>> from std.array below.
>> Andrei
> 
> One comment:  Part of the reason why ~= is slow is that for anything other than a
> tiny array, the array doesn't expand geometrically.  It expands a memory page at a
> time.  You can see this by printing the capacity of an array as it is expanded,
> using this trivial program:
> 
> import std.stdio, std.gc;
> 
> void main () {
>     uint[] foo;
>     size_t oldCapacity;
>     foreach(i; 0..100_000) {
>         foo ~= 1;
>         if(capacity(foo.ptr) != oldCapacity) {
>             writeln(capacity(foo.ptr));
>             oldCapacity = capacity(foo.ptr);
>         }
>     }
> }
> 
> This means that, even with cached capacity, appends are worse than amortized O(1).
>  On the other hand, sometimes space is more important than speed.  Maybe how this
> memory allocation is done could be a ctor parameter, with the default being geometric.

That test is misleading. A while ago Walter added in-place expansion; 
whenever a non-in-place expansion occurs, he does grow size geometrically.

Andrei