Impressed with Appender - Is there design/implementation description?

[thedeemon via Digitalmars-d-learn]

On Sunday, 4 December 2016 at 20:03:37 UTC, Jon Degenhardt wrote:
> I've been using Appender quite a bit recently, typically when I 
> need append-only arrays with variable and unknown final sizes. 
> I had been prepared to write a custom data structure when I 
> started using it with large amounts of data, but very nicely 
> this has not surfaced as a need. Appender has held up quite 
> well.
>
> I haven't actually benchmarked it against competing data 
> structures, nor have I studied the implementation. I'd be very 
> interested in understanding the design and how it compares to 
> other data structures. Are there any write-ups or articles 
> describing it?
>
> --Jon

It's rather simple, just take a look at its source code in 
std.array.
It's an ordinary linear array partially filled with your data. 
When your data fills it up, it gets resized to make more space. 
Just two interesting points:

1. When it needs to grow it uses a formula like k = 1 + 10 / 
log2(newsize) for the growth factor (but with a limit of k <= 2), 
which means up to 16 KB it doubles the size each time, then tries 
to grow by a factor of 2/3, then by lower and lower factors.

2. Up until 4 KB it reallocates when growing, but after 4 KB the 
array lives in a larger pool of memory where it can often grow a 
lot without reallocating, so in many scenarios where other 
allocations do not interfere, the data array of appender grows in 
place without copying any data, thanks to GC.extend() method.