D-Programming-Language/phobos — pull request #502 by sandford (2012-03-19 21:01:22+00:00)
Title: Fix Issue 5813, Fix Issue 7215, Fix Issue 6641, Fix Issue 4287 - Appender rewrite

This pull request addresses:

[patch] std.array.Appender has severe performance and memory leak problems
http://d.puremagic.com/issues/show_bug.cgi?id=5813

Issue 7215 - array.Appender.put should work on its own type
http://d.puremagic.com/issues/show_bug.cgi?id=7215

Issue 6641 - RefAppender!(T[]) should be OutputRange.
http://d.puremagic.com/issues/show_bug.cgi?id=6641

Issue 4287 - opOpAssign!("~=") for std.array.Appender
http://d.puremagic.com/issues/show_bug.cgi?id=4287

Appender has been rewritten to improve memory usage and performance, both at small and large scales. Algorithmically, Appender is implemented using a sealed rope, a linked-list of arrays, with the first node being cached in a thread local free list. It provides strict computational and memory performance bounds: for most users data will be copied exactly twice, there will be less than 4k of wasted space and a maximum memory usage of o(2N). For small arrays, this results in a 40% performance increase. For large arrays, the lack of memory/GC churn and false pointers eliminates a source of memory leaks that prevented very large arrays.

The implementation change is reflected in the API; .data has been soft-deprecated and the conventions of std.container have been employed were applicable. Phobos has been reviewed for usages of .data. The vast majority of uses involve de novo array creation and have been migrated to using .dup. Two uses involved using appender as a stack (std.file and std.regex). std.file was migrated to the appropriate container APIs. std.regex required an un-sealed container. A simple, array based stack was written to fulfill this need. std.stdio used appender to wrap a buffer as part of readlnImpl. A zero-overhead method of wrapping a buffer (wrappedBuffer) was added to efficiently support this use case and is available to @system methods. As discussed in issue 6641, RefAppender has been removed; wrappedBuffer provides similar functionality with no extra overhead. Unittestsand documentation were added for all new functionality.

Unittests have been verified on DMD 2.058, 32-bit windows.