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.
