http://d.puremagic.com/issues/show_bug.cgi?id=5813

           Summary: [patch] std.array.Appender has severe performance and
                    memory leak problems.
           Product: D
           Version: D2
          Platform: Other
        OS/Version: Windows
            Status: NEW
          Keywords: patch, performance
          Severity: normal
          Priority: P3
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: sandford@jhu.edu
        Depends on: 5233,5780


--- Comment #0 from Rob Jacques <sandford@jhu.edu> 2011-04-03 20:01:59 PDT ---
std.array.Appender currently suffers from a major memory leak, and consequently has a major performance problem. The primary problem comes from the fact that Appender isn't sealed, and must let the GC collect the unused arrays it allocates. Even in a micro-benchmark program, false pointers can lead to excess memory being kept live. For example, a micro-benchmark which simply generates a 10MB array of reals, used anywhere between 30-116MB of ram (50 seemed about average). For me, the major issue with Appender has been the tendency for generating a 150MB array to run my program out of memory (and to take minutes even when it succeeds).

Recently, bearophile posted a set of micro-benchmarks
(http://www.digitalmars.com/d/archives/digitalmars/D/Conversion_to_string_string_building_benchmark_132129.html)
I'll highlight two results, test1 which appended to!string(uint) and test2
which appended "12345678" took 7.38 / 5.91 seconds, respectively, using the old
appender. With this patch, the times on my machine are 9.0 / 0.40 seconds,
respectively. Memory usage also decreased from 290 MB to 146 MB with this
patch.

Besides better large-scale performance, I wrote some micro-benchmarks to test usage as a small buffer and small array builder (~ 100 elements). I saw a minor performance increase of 3% and 10%, respectively.

Needly to say, I've seen a dramatic performance increase in my production code, quite literally from minutes to milliseconds.

Implementation changes
=======================================================
I've changed the basic architecture of Appender from a 'smart' array to a
linked-list of arrays. data(), therefore, has to combine these segments to
return an array. If data() performs a new allocation & copy, this array is used
to create a new head node, thus preventing repeated calls to data from
allocating additional arrays.

The growth schedule has also changed, now the capacity of each segment is doubled on growth, this leads to a greater than 2x length schedule, while the length is smallish. I've limited the capacity based growth to 4 KB, i.e. 1 memory page. As no copying is done on growth, the only real cost I need to amortize is allocation, and I felt 4 Kb was a good trade-off point between keeping memory tight and allocation cost.

For performance, I found that I shouldn't support a current node pointer, and instead should use a tail node pointer. A side effect of this optimization is that shrinkTo may drop previously allocated segments and clear only retains the last node, as it is assumed to be the largest.

RefAppender's was updated to support the changes in Appender cleanly.

I've added some additional methods to the API:
-slack: returns the number of elements that can be added before allocation.
-extend: Increases the slack by at least N elements
-dup: Returns: a mutable copy of the data.
-idup: Returns: a immutable copy of the data.
-this(size_t N): Construct an appender with a capacity of at least N elements


[patch] Don't forget the dependent patches (bugs 5780, 5233) =================================================================================

/** Implements an output range which stores appended data. This is recommended
 *  over $(D a ~= data) when appending many elements because it is more memory
 *  and computationally efficient.
 *
 *  Example:
    ----
    auto buffer = Appender!(char[])(4);             // Reserve 4 elements
    foreach( str; ["Hello"d, "World"d] ) {
        buffer.clear;                               // Use appender as a
        foreach( dchar c; str )                     // dynamically sized buffer
            put( buffer, c    );
        assert( buffer.data == str );
    }

    int[] a = [ 1, 2 ];
    auto builder = appender(a);                     // Or for array building
    builder.put(3);
    builder.put([ 4, 5, 6 ]);
    assert(builder.data == [ 1, 2, 3, 4, 5, 6 ]);
    ----
 */
struct Appender(A : T[], T) {
    private {
        enum  PageSize = 4096;          // Memory page size
        alias Unqual!T E;               // Internal element type

        struct Data {
            Data*       next;           // The next data segment
            size_t      capacity;       // Capacity of this segment
            E[]         arr;            // This segment's array

            // Initialize a segment using an existing array
            void opAssign(E[] _arr) {
                next           = null;
                capacity       = _arr.capacity;
                arr            = _arr;
                if(_arr.length < capacity) {
                    arr.length = capacity;
                    arr.length = _arr.length;
                }
                assert(_arr.ptr is arr.ptr,"Unexpected reallocation occurred");
            }

            // Create a new segment using an existing array
            this(Unqual!T[] _arr) { this = _arr; }

            // Create a new segment with at least size bytes
            this(size_t size) {
                if(size > PageSize)
                    size = (size +  PageSize-1) & ~(PageSize-1);
                auto bi  = GC.qalloc(size, !hasIndirections!T * 2);
                next     = null;
                capacity = bi.size / T.sizeof;
                arr      = (cast(E*)bi.base)[0..0];
                static assert(!false*2 == GC.BlkAttr.NO_SCAN);
            }
        }
        Data*  _head = null;                   // The head data segment
        Data*  _tail = null;                   // The last data segment

        // Returns: the total number of elements in the appender
        size_t _length() {
            size_t len = 0;
            for(auto d = _head; d !is null; d = d.next)
                len   += d.arr.length;
            return len;
        }

        // Flatten all the data segments into a single array
        E[] flatten() {
            if(_head is _tail)
                return _head ? _head.arr : null;

            size_t N   = _length;
            size_t len = N;
            size_t i   = 0;
            auto arr   = new E[N];
            for(auto d = _head; N > 0; d = d.next, N -= len, i += len) {
                len    = min(N, d.arr.length);
                memcpy(arr.ptr+i, d.arr.ptr, len * T.sizeof);
            }
            return arr;
        }

        // Returns: the next capacity size
        size_t nextCapacity() nothrow pure {
            auto   cap = _tail.capacity * T.sizeof * 2;
            return cap < PageSize ? cap : PageSize;
        }
    }

    /** Construct an appender with a given array.  Note that this does not copy
     *  the data.  If the array has a larger capacity as determined by
     *  arr.capacity, it will be used by the appender.  After initializing an
     *  appender on an array, appending to the original array will reallocate.
     */
    this(T[] arr) {
        if(arr is null) _head = _tail = new Data( 16 * T.sizeof );
        else            _head = _tail = new Data( cast(E[]) arr );
    }

    /// Construct an appender with a capacity of at least N elements.
    this(size_t N) { _head = _tail = new Data( N * T.sizeof ); }

    /// Returns: a mutable copy of the data.
    E[] dup()  {
        return _head !is _tail ? flatten : flatten.dup;
    }

    /// Returns: a immutable copy of the data.
    immutable(E)[] idup() {
        return cast(immutable(E)[]) dup;
    }

    /// Returns: the appender's data as an array.
    T[] data() {
        auto arr = flatten;
        if(_head !is _tail) {
            *_head = arr;
             _tail = _head;
        }
        return cast(T[]) arr;
    }

    /// Returns: the number of elements that can be added before allocation.
    size_t slack() {
        return _tail ? _tail.capacity - _tail.arr.length : 0;
    }

    /// Increases the slack by at least N elements
    void extend(size_t N) {
        assert( size_t.max / T.sizeof  >= N, "Capacity overflow.");
        auto size = N * T.sizeof;

        // Initialize if not done so.
        if(_tail) return _head = _tail = new Data( size );

        // Try extending
        if( auto u = GC.extend(_tail.arr.ptr, size, size) )
            return _tail.capacity = u / T.sizeof;

        // If full, add a segment
        if(_tail.arr.length == _tail.capacity)
             return _tail = _tail.next = new Data( size );

        // Allocate & copy
        auto next = Data(size);
        memcpy(next.arr.ptr, _tail.arr.ptr, _tail.arr.length * T.sizeof);
        _tail.arr       = next.arr.ptr[0.._tail.arr.length];
        _tail.capacity  = next.capacity;
    }

    /// Returns: the total number of elements currently allocated.
    size_t capacity() {
        size_t cap = 0;
        for(auto d = _head; d !is null; d = d.next)
            cap   += d.capacity;
        return cap;
    }

    /// Ensures that the capacity is a least newCapacity elements.
    void reserve(size_t newCapacity) {
        auto cap  = capacity;
        if(  cap >= newCapacity) return;
        extend( newCapacity - cap );
    }

    /// Appends to the output range
    void put(U)(U item) if ( isOutputRange!(Unqual!T[],U) ){
        // put(T)
        static if ( isImplicitlyConvertible!(U, E) ){
            if(!_head)
                _head = _tail  = new Data( 16 * T.sizeof );
            else if( _tail.arr.length == _tail.capacity  ) {   // Try extending
                if( auto u = GC.extend(_tail.arr.ptr, T.sizeof, nextCapacity) )
                     _tail.capacity     = u / T.sizeof;
                else _tail = _tail.next = new Data( nextCapacity );
            }
            auto          len  = _tail.arr.length;
            _tail.arr.ptr[len] = item;
            _tail.arr          = _tail.arr.ptr[0 .. len + 1];

        // fast put(T[])
        } else static if( is(typeof(_tail.arr[0..1] = item[0..1])) ){
            auto items  = cast(E[]) item[];
            if(!_tail)
                _head   = _tail = new Data(  items.length * T.sizeof );
            auto arr    = _tail.arr.ptr[_tail.arr.length.._tail.capacity];
            size_t len  = items.length;
            if(arr.length < len) {                             // Try extending
                auto size  = max(items.length*T.sizeof, nextCapacity);
                if( auto u = GC.extend(_tail.arr.ptr, T.sizeof, size) ) {
                    _tail.capacity = u / T.sizeof;
                    arr    = _tail.arr.ptr[_tail.arr.length.._tail.capacity];
                }
                if(arr.length < len) len = arr.length;
            }
            arr[0..len] = items[0..len];
            items       = items[len..$];
            _tail.arr   = _tail.arr.ptr[0 .. _tail.arr.length + len];
            if( items.length > 0 ) {               // Add a segment and advance
                _tail.next = new Data(max(items.length*T.sizeof,nextCapacity));
                _tail      = _tail.next;
                _tail.arr.ptr[0..items.length] = items[];
                _tail.arr   = _tail.arr.ptr[0..items.length];
            }

        // Everything else
        } else {
            .put!(typeof(this),U,true,Unqual!T)(this,item);
        }
    }

    // only allow overwriting data on non-immutable and non-const data
    static if(!is(T == immutable) && !is(T == const)) {
        /** Clears the managed array. This function may reduce the appender's
         *  capacity.
         */
        void clear() {
            _head     = _tail;            // Save the largest chunk and move on
            _tail.arr = _tail.arr.ptr[0..0];
        }

        /** Shrinks the appender to a given length. Passing in a length that's
         *  greater than the current array length throws an enforce exception.
         *  This function may reduce the appender's capacity.
         */
        void shrinkTo(size_t newlength) {
            for(auto d = _head; d !is null; d = d.next) {
                if(d.arr.length >= newlength) {
                    d.arr  = d.arr.ptr[0..newlength];
                    d.next = null;
                }
                newlength -= d.arr.length;
            }
            enforce(newlength == 0, "Appender.shrinkTo: newlength > capacity");
        }
    }
}

/** An appender that can update an array in-place.  It forwards all calls to an
 *  underlying appender implementation.  Calling data updates the pointer to
 *  the original array passeed in.
 */
struct RefAppender(A : T[], T) {
    private {
        Appender!(A, T) impl;
        T[] *arr;
    }

    /** Construct a ref appender with a given array reference.  This does not
     *  copy the data.  If the array has a larger capacity as determined by
     *  arr.capacity, it will be used by the appender.  $(D RefAppender)
     *  assumes that arr is a non-null value.
     *
     *  Note, do not use builtin appending (i.e. ~=) on the original array
     *  passed in until you are done with the appender, because calls to the
     *  appender override those appends.
    */
    this(T[] *arr) {
        impl     = Appender!(A, T)(*arr);
        this.arr = arr;
    }

    auto opDispatch(string fn, Args...)(Args args)
        if (is(typeof(mixin("impl." ~ fn ~ "(args)"))))  {
        mixin("return impl." ~ fn ~ "(args);");
    }

    /// Returns the appender's data as an array and updates the original array.
    T[] data() {
         auto  arr = impl.data;
         *this.arr = arr;
        return arr;
    }
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5813



--- Comment #1 from Rob Jacques <sandford@jhu.edu> 2011-05-20 10:29:57 PDT ---
*Update*
The previous version ended up having value semantics, not reference semantics,
due to the fact _tail wouldn't get updated and later nodes would be ignored.
For example:

    auto test = Appender!string(16);
    void func(Writer)(Writer w) {
        w.put("The quick brown fox jumps over the lazy dog");
    }
    func(test);
    assert(test.data == "The quick brown ");
    //assert(test.data == "The quick brown fox jumps over the lazy dog");

I've updated the code to check/update tail lazily as needed. As an out of date _tail naturally triggers memory allocation, this doesn't overly change the performance of put on average.

==============================================================================

struct Appender(A : T[], T) {
    private {
        enum  PageSize = 4096;          // Memory page size
        alias Unqual!T E;               // Internal element type

        struct Data {
            Data*       next;           // The next data segment
            size_t      capacity;       // Capacity of this segment
            E[]         arr;            // This segment's array

            // Initialize a segment using an existing array
            void opAssign(E[] _arr) {
                next           = null;
                capacity       = _arr.capacity;
                arr            = _arr;
                if(_arr.length < capacity) {
                    arr.length = capacity;
                    arr.length = _arr.length;
                }
                assert(_arr.ptr is arr.ptr,"Unexpected reallocation occurred");
            }

            // Create a new segment using an existing array
            this(Unqual!T[] _arr) { this = _arr; }

            // Create a new segment with at least size bytes
            this(size_t size) {
                if(size > PageSize)
                    size = (size +  PageSize-1) & ~(PageSize-1);
                auto bi  = GC.qalloc(size, !hasIndirections!T * 2);
                next     = null;
                capacity = bi.size / T.sizeof;
                arr      = (cast(E*)bi.base)[0..0];
                static assert(!false*2 == GC.BlkAttr.NO_SCAN);
            }
        }
        Data*  _head = null;                   // The head data segment
        Data*  _tail = null;                   // The last data segment

        // Returns: the total number of elements in the appender
        size_t _length() {
            size_t len = 0;
            for(auto d = _head; d !is null; d = d.next)
                len   += d.arr.length;
            return len;
        }

        // Flatten all the data segments into a single array
        E[] flatten() {
            if(!_head) return null;
            if( _head && _head.next is null)
                return _head.arr;

            size_t N   = _length;
            size_t len = N;
            size_t i   = 0;
            auto arr   = new E[N];
            for(auto d = _head; N > 0; d = d.next, N -= len, i += len) {
                len    = min(N, d.arr.length);
                memcpy(arr.ptr+i, d.arr.ptr, len * T.sizeof);
            }
            return arr;
        }

        // Returns: the next capacity size
        size_t nextCapacity() nothrow pure {
            auto   cap = _tail.capacity * T.sizeof * 2;
            return cap < PageSize ? cap : PageSize;
        }
    }

    /** Construct an appender with a given array.  Note that this does not copy
     *  the data.  If the array has a larger capacity as determined by
     *  arr.capacity, it will be used by the appender.  After initializing an
     *  appender on an array, appending to the original array will reallocate.
     */
    this(T[] arr) {
        if(arr is null) _head = _tail = new Data( 16 * T.sizeof );
        else            _head = _tail = new Data( cast(E[]) arr );
    }

    /// Construct an appender with a capacity of at least N elements.
    this(size_t N) { _head = _tail = new Data( N * T.sizeof ); }

    /// Returns: the maximum length that can be accommodated without allocation
    size_t capacity() {
        size_t cap = 0;
        for(auto d = _head; d !is null; d = d.next)
            cap   += d.capacity;
        return cap;
    }

    /// Returns: a mutable copy of the data.
    E[] dup()  {
        if(_head && _head.next is null)
            return flatten.dup;
        return flatten;
    }

    /// Returns: a immutable copy of the data.
    immutable(E)[] idup() {
        return cast(immutable(E)[]) dup;
    }

    /// Returns: the appender's data as an array.
    T[] data() {
        auto arr = flatten;
        if(_head !is _tail) {
            *_head = arr;
             _tail = _head;
        }
        return cast(T[]) arr;
    }

    /** Reserve at least newCapacity elements for appending.  Note that more
     *  elements may be reserved than requested.  If newCapacity < capacity,
     *  then nothing is done.
     */
    void reserve(size_t newCapacity) {
        auto cap  = capacity;
        if(  cap >= newCapacity) return;

        auto size = ( newCapacity - cap) * T.sizeof;

        // Initialize if not done so.
        if(!_head) return _head = _tail = new Data( size );

        // Update tail
        while(_tail.next !is null) _tail = _tail.next;

        // Try extending
        if( auto u = GC.extend(_tail.arr.ptr, size, size) )
            return _tail.capacity = u / T.sizeof;

        // If full, add a segment
        if(_tail.arr.length == _tail.capacity)
             return _tail = _tail.next = new Data( size );

        // Allocate & copy
        auto next = Data(size);
        memcpy(next.arr.ptr, _tail.arr.ptr, _tail.arr.length * T.sizeof);
        _tail.arr       = next.arr.ptr[0.._tail.arr.length];
        _tail.capacity  = next.capacity;
    }

    /// Appends to the output range
    void put(U)(U item) if ( isOutputRange!(Unqual!T[],U) ){
        // Transcoding is required to support char[].put(dchar)
        static if(isSomeChar!T && isSomeChar!U &&  T.sizeof < U.sizeof){
            E[T.sizeof == 1 ? 4 : 2] encoded;
            auto len = std.utf.encode(encoded, item);
            return put(encoded[0 .. len]);

        // put(T)
        } else static if(isImplicitlyConvertible!(U, E)) {
            if(!_head)
                _head = _tail  = new Data( 16 * T.sizeof );
            else if( _tail.arr.length == _tail.capacity  ) {   // Try extending
                while(_tail.next !is null) _tail = _tail.next; // Update tail
                if( auto u = GC.extend(_tail.arr.ptr, T.sizeof, nextCapacity) )
                     _tail.capacity     = u / T.sizeof;
                else _tail = _tail.next = new Data( nextCapacity );
            }
            auto          len  = _tail.arr.length;
            _tail.arr.ptr[len] = item;
            _tail.arr          = _tail.arr.ptr[0 .. len + 1];

        // fast put(T[])
        } else static if (is(typeof(_tail.arr[0..1] = item[0..1]))) {
            auto items  = cast(E[]) item[];
            if(!_head)
                _head   = _tail = new Data(  items.length * T.sizeof );
            auto arr    = _tail.arr.ptr[_tail.arr.length.._tail.capacity];
            size_t len  = items.length;
            if(arr.length < len) {                             // Try extending
                while(_tail.next !is null) {                   // Update tail
                    _tail = _tail.next;
                    arr   = _tail.arr.ptr[_tail.arr.length.._tail.capacity];
                }
                auto size  = max(items.length*T.sizeof, nextCapacity);
                if( auto u = GC.extend(_tail.arr.ptr, T.sizeof, size) ) {
                    _tail.capacity = u / T.sizeof;
                    arr    = _tail.arr.ptr[_tail.arr.length.._tail.capacity];
                }
                if(arr.length < len) len = arr.length;
            }
            arr[0..len] = items[0..len];
            items       = items[len..$];
            _tail.arr   = _tail.arr.ptr[0 .. _tail.arr.length + len];
            if( items.length > 0 ) {               // Add a segment and advance
                _tail.next = new Data(max(items.length*T.sizeof,nextCapacity));
                _tail      = _tail.next;
                _tail.arr.ptr[0..items.length] = items[];
                _tail.arr   = _tail.arr.ptr[0..items.length];
            }

        // Kitchen sink
        } else {
            .put!(typeof(this),U,true)(this,item);
        }
    }

    // only allow overwriting data on non-immutable and non-const data
    static if(!is(T == immutable) && !is(T == const)) {
        /** Clears the managed array. This function may reduce the appender's
         *  capacity.
         */
        void clear() {
            _head     = _tail;            // Save the largest chunk and move on
            if(_head) {
                _head.arr  = _head.arr.ptr[0..0];
                _head.next = null;
            }
        }

        /** Shrinks the appender to a given length. Passing in a length that's
         *  greater than the current array length throws an enforce exception.
         *  This function may reduce the appender's capacity.
         */
        void shrinkTo(size_t newlength) {
            for(auto d = _head; d !is null; d = d.next) {
                if(d.arr.length >= newlength) {
                    d.arr  = d.arr.ptr[0..newlength];
                    d.next = null;
                }
                newlength -= d.arr.length;
            }
            enforce(newlength == 0, "Appender.shrinkTo: newlength > capacity");
        }
    }
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5813



--- Comment #2 from Rob Jacques <sandford@jhu.edu> 2011-06-09 11:11:16 PDT ---
This patch passes the unittests listed in Issue 5663 - std.array.Appender.put bug

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5813


Steven Schveighoffer <schveiguy@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |schveiguy@yahoo.com


--- Comment #3 from Steven Schveighoffer <schveiguy@yahoo.com> 2011-06-09 11:58:55 PDT ---
I think this is a good idea to do, but the code is somewhat obfuscated.  For example, you are returning a value from a void function (extend), and doing some weird shortcuts (like !false*2).  There are also some style differences from the current D style guidelines.  These will have to be fixed before it's put into phobos.

One technical point -- the limit of multiples of page sizes when requesting more than one page is already done by the GC.  That is, If you request more than 1/2 page, you will get a multiple of pages.  I think the code will perform exactly as well if the multiple-of-page limitation is removed from your code, and this then does not make any assumptions about how big a page size is (if it ever changes).

Do you want to do a pull request and have the code reviewed?  I think it's definitely worth changing Appender to do this.

One further thing -- I planned on making two versions of Appender: one that is a reference type, and one that is not.  The version that is not should allow filling an existing an array without allocating anything.  The current Appender (the one in phobos now) always allocates an pImpl struct, even if the array never needs to be extended.

The tradeoff is that the non-reference appender is not returnable, and you
can't make copies of it (i.e. this(this) is @disabled).

Is this possible with your code?  If so, and it's easy enough, can you create a version that does this too?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5813



--- Comment #4 from Rob Jacques <sandford@jhu.edu> 2011-06-09 12:40:52 PDT ---
(In reply to comment #3)
> I think this is a good idea to do, but the code is somewhat obfuscated.  For example, you are returning a value from a void function (extend), and doing some weird shortcuts (like !false*2).  There are also some style differences from the current D style guidelines.  These will have to be fixed before it's put into phobos.

The obfuscation generally comes from a desire to minimize multi-lines to one-liners. But if you think these are too compressed, I'll change them to something cleaner. Regarding D style guidelines, there has been so much discussion over them, that I don't know if/where there current guidelines exist/are. And the existing Phobos codebase is a mash-up of different styles. I mean, even ddoc comments vary between /++ and /**. Is there anything in particular you'd recommend I'd change?

> One technical point -- the limit of multiples of page sizes when requesting more than one page is already done by the GC.  That is, If you request more than 1/2 page, you will get a multiple of pages.  I think the code will perform exactly as well if the multiple-of-page limitation is removed from your code, and this then does not make any assumptions about how big a page size is (if it ever changes).

Thank you. I'll remove that line.

> Do you want to do a pull request and have the code reviewed?  I think it's definitely worth changing Appender to do this.

Yes, but I haven't gotten around to learning/installing Git on Windows yet.

> One further thing -- I planned on making two versions of Appender: one that is a reference type, and one that is not.  The version that is not should allow filling an existing an array without allocating anything.  The current Appender (the one in phobos now) always allocates an pImpl struct, even if the array never needs to be extended.
> 
> The tradeoff is that the non-reference appender is not returnable, and you
> can't make copies of it (i.e. this(this) is @disabled).
> 
> Is this possible with your code?  If so, and it's easy enough, can you create a version that does this too?

The simple solution would be to emplace the first data node inside the appender struct. But I'm not sure the benefit of such a solution: appender always checks/extends-to the capacity of an array, which involves taking the GC lock, etc. So since the taking lock can't be averted, avoiding an extra 16-byte allocation isn't much worse. But I can always implement it using a template parameter + static ifs, so it shouldn't be hard to try it out. Hmm... I could also fold in RefAppender that way.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5813



--- Comment #5 from Steven Schveighoffer <schveiguy@yahoo.com> 2011-06-09 14:22:32 PDT ---
(In reply to comment #4)
> The obfuscation generally comes from a desire to minimize multi-lines to one-liners.

I don't mind the one-liners, but things like !hasIndirections!T*2 is better written as hasIndirections!T ? 0 : GC.BlkAttr.NO_SCAN.  It's more decipherable and self-documenting.  Shortcuts that hide the intention of the code are not worth it.  The one-liners that assign to several things at once are at least clear.  Although I think this one should be split into at least two statements:

return _tail = _tail.next = new Data( size );

> Regarding D style guidelines, there has been so much
> discussion over them, that I don't know if/where there current guidelines
> exist/are. And the existing Phobos codebase is a mash-up of different styles. I
> mean, even ddoc comments vary between /++ and /**. Is there anything in
> particular you'd recommend I'd change?

I think the best thing to do for now is to follow the style of the original code.  TBH, I'd say submit the pull request and the review will flesh out individual things that should be fixed (the github review process is really good).

> > Do you want to do a pull request and have the code reviewed?  I think it's definitely worth changing Appender to do this.
> 
> Yes, but I haven't gotten around to learning/installing Git on Windows yet.

Highly recommend progit.org for learning git.  Just getting git working on Windows myself...

> The simple solution would be to emplace the first data node inside the appender struct. But I'm not sure the benefit of such a solution: appender always checks/extends-to the capacity of an array, which involves taking the GC lock, etc. So since the taking lock can't be averted, avoiding an extra 16-byte allocation isn't much worse. But I can always implement it using a template parameter + static ifs, so it shouldn't be hard to try it out. Hmm... I could also fold in RefAppender that way.

You are probably right, I added the code to fill to capacity after thinking about creating such a type.  The capacity check definitely needs to take the global lock.  Maybe the non-reference appender would not try to expand to capacity (that is, after all, an optimization).  In any case, this isn't as important as the other fixes you've already created.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5813


Vladimir Panteleev <thecybershadow@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |thecybershadow@gmail.com


--- Comment #6 from Vladimir Panteleev <thecybershadow@gmail.com> 2011-12-02 02:45:59 PST ---
What's this status of this patch?

Note that today, it's extremely unlikely for patches from Bugzilla to be incorporated unless someone creates a GitHub pull request for them.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5813



--- Comment #7 from Steven Schveighoffer <schveiguy@yahoo.com> 2011-12-02 04:49:25 PST ---
I think we were waiting on Rob to change this into a pull request.  Not sure if that's going to happen?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5813



--- Comment #8 from Rob Jacques <sandford@jhu.edu> 2011-12-02 05:38:25 PST ---
I'm planning on putting in a pull request for this, probably sometime over the Christmas holidays(I hope). Currently, I'm in the middle of finishing up my Ph.D. thesis and moving to a new city and job, so my bandwidth is very limited at the moment.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5813



--- Comment #9 from Vladimir Panteleev <thecybershadow@gmail.com> 2011-12-02 10:33:44 PST ---
I did some benchmarks with this and some other variants.

At least for small strings, this code performs worse than the current appender. Judging by the description it's optimized for large blocks of data, but in the case of many small strings it can perform as bad as 50% worse than the current appender for typical cases (e.g. building a few KB of HTML).

Here is my test code:

http://dump.thecybershadow.net/a05a2c4dc7cd2a8e21b3a447c7eff150/test2.d http://dump.thecybershadow.net/eff5c7ef81e18bf75d8462ffe16a52e4/appender.d

I was able to get 25% more performance for my test case from the standard appender by adding a method that accepts multiple arguments (which preallocates only once). My code is a hack, but it would be nice to see something like that in the official appender.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------