On Tue, Apr 22, 2014 at 02:24:41PM -0400, Steven Schveighoffer via Digitalmars-d wrote:
> On Tue, 22 Apr 2014 14:10:30 -0400, H. S. Teoh via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
> 
> >I'm going through some code and thinking of ways to reduce GC pressure, and came across a bit that needed to append some items to an array:
> >
> >	T[] args;
> >	lex.expect("(");
> >	args ~= parseSingleItem(lex);
> >	while (!lex.empty) {
> >		lex.expect(",");
> >		args ~= parseSingleItem(lex);
> >	}
> >	lex.expect(")");
> >	return computeResult(args);
> >
> >Now obviously, in the general case (with arbitrarily many number of items) some GC allocations will be needed, but the most common use-cases are actually only 1 or 2 items each time. Allocating lots of small arrays seem to be rather wasteful, so I thought to use a static array as a buffer instead.
> >
> >The question is, is there a way to take a slice of the static array, set the length to zero, and append to it with ~= such that when it runs out of space in the static buffer, it will reallocate a longer array on the GC heap? Or is this a bad idea?
> 
> TL;DR: Yes, use Appender :)
> 
> The reason appending even works is because of the metadata stored in the heap. Obviously, stack frames and fixed-length arrays do not have this data.
> 
> When that metadata cannot be found, it reallocates because that's the only option.
> 
> However, Appender, initialized with a static buffer, knows the length of its data, and stores its own capacity, separate from the heap.
[...]

Unfortunately, the whole point of this exercise was to eliminate GC allocations for small arrays -- but since Appender's implementation allocates a private Data struct in its ctor, that kinda defeats the purpose. For the common case of 1 or 2 items only, it doesn't seem like Appender will perform any better, and it will introduce extra GC allocations to boot.

:-(


T

-- 
What are you when you run out of Monet? Baroque.

On Tue, 22 Apr 2014 14:31:07 -0400, H. S. Teoh via Digitalmars-d <digitalmars-d@puremagic.com> wrote:

> On Tue, Apr 22, 2014 at 02:24:41PM -0400, Steven Schveighoffer via Digitalmars-d wrote:
>> On Tue, 22 Apr 2014 14:10:30 -0400, H. S. Teoh via Digitalmars-d
>> <digitalmars-d@puremagic.com> wrote:
>>
>> >I'm going through some code and thinking of ways to reduce GC
>> >pressure, and came across a bit that needed to append some items to
>> >an array:
>> >
>> >	T[] args;
>> >	lex.expect("(");
>> >	args ~= parseSingleItem(lex);
>> >	while (!lex.empty) {
>> >		lex.expect(",");
>> >		args ~= parseSingleItem(lex);
>> >	}
>> >	lex.expect(")");
>> >	return computeResult(args);
>> >
>> >Now obviously, in the general case (with arbitrarily many number of
>> >items) some GC allocations will be needed, but the most common
>> >use-cases are actually only 1 or 2 items each time. Allocating lots
>> >of small arrays seem to be rather wasteful, so I thought to use a
>> >static array as a buffer instead.
>> >
>> >The question is, is there a way to take a slice of the static array,
>> >set the length to zero, and append to it with ~= such that when it
>> >runs out of space in the static buffer, it will reallocate a longer
>> >array on the GC heap? Or is this a bad idea?
>>
>> TL;DR: Yes, use Appender :)
>>
>> The reason appending even works is because of the metadata stored in
>> the heap. Obviously, stack frames and fixed-length arrays do not have
>> this data.
>>
>> When that metadata cannot be found, it reallocates because that's the
>> only option.
>>
>> However, Appender, initialized with a static buffer, knows the length
>> of its data, and stores its own capacity, separate from the heap.
> [...]
>
> Unfortunately, the whole point of this exercise was to eliminate GC
> allocations for small arrays -- but since Appender's implementation
> allocates a private Data struct in its ctor, that kinda defeats the
> purpose. For the common case of 1 or 2 items only, it doesn't seem like
> Appender will perform any better, and it will introduce extra GC
> allocations to boot.
>
> :-(

I advocated a long time ago that Appender should have a stack-based version.

I still think that's the case. Because really what Appender has as an advantage over builtin slices is that it keeps a local copy of the capacity, so no heap metadata lookups need to occur. It's not conceptually that much added.

Of course, back then, I'm not sure we had @disable this(this), which such an appender should have.

-Steve

On Tuesday, 22 April 2014 at 18:52:44 UTC, Steven Schveighoffer wrote:
> On Tue, 22 Apr 2014 14:31:07 -0400, H. S. Teoh via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>
>> On Tue, Apr 22, 2014 at 02:24:41PM -0400, Steven Schveighoffer via Digitalmars-d wrote:
>>> On Tue, 22 Apr 2014 14:10:30 -0400, H. S. Teoh via Digitalmars-d
>>> <digitalmars-d@puremagic.com> wrote:
>>>
>>> >I'm going through some code and thinking of ways to reduce GC
>>> >pressure, and came across a bit that needed to append some items to
>>> >an array:
>>> >
>>> >	T[] args;
>>> >	lex.expect("(");
>>> >	args ~= parseSingleItem(lex);
>>> >	while (!lex.empty) {
>>> >		lex.expect(",");
>>> >		args ~= parseSingleItem(lex);
>>> >	}
>>> >	lex.expect(")");
>>> >	return computeResult(args);
>>> >
>>> >Now obviously, in the general case (with arbitrarily many number of
>>> >items) some GC allocations will be needed, but the most common
>>> >use-cases are actually only 1 or 2 items each time. Allocating lots
>>> >of small arrays seem to be rather wasteful, so I thought to use a
>>> >static array as a buffer instead.
>>> >
>>> >The question is, is there a way to take a slice of the static array,
>>> >set the length to zero, and append to it with ~= such that when it
>>> >runs out of space in the static buffer, it will reallocate a longer
>>> >array on the GC heap? Or is this a bad idea?
>>>
>>> TL;DR: Yes, use Appender :)
>>>
>>> The reason appending even works is because of the metadata stored in
>>> the heap. Obviously, stack frames and fixed-length arrays do not have
>>> this data.
>>>
>>> When that metadata cannot be found, it reallocates because that's the
>>> only option.
>>>
>>> However, Appender, initialized with a static buffer, knows the length
>>> of its data, and stores its own capacity, separate from the heap.
>> [...]
>>
>> Unfortunately, the whole point of this exercise was to eliminate GC
>> allocations for small arrays -- but since Appender's implementation
>> allocates a private Data struct in its ctor, that kinda defeats the
>> purpose. For the common case of 1 or 2 items only, it doesn't seem like
>> Appender will perform any better, and it will introduce extra GC
>> allocations to boot.
>>
>> :-(
>
> I advocated a long time ago that Appender should have a stack-based version.
>
> I still think that's the case. Because really what Appender has as an advantage over builtin slices is that it keeps a local copy of the capacity, so no heap metadata lookups need to occur. It's not conceptually that much added.
>
> Of course, back then, I'm not sure we had @disable this(this), which such an appender should have.
>
> -Steve

What I said in the other thread, my ScopeAppender is stack based. Very soon to being finished :)

On Tuesday, 22 April 2014 at 18:52:44 UTC, Steven Schveighoffer wrote:
> On Tue, 22 Apr 2014 14:31:07 -0400, H. S. Teoh via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>
>> On Tue, Apr 22, 2014 at 02:24:41PM -0400, Steven Schveighoffer via Digitalmars-d wrote:
>>> On Tue, 22 Apr 2014 14:10:30 -0400, H. S. Teoh via Digitalmars-d
>>> <digitalmars-d@puremagic.com> wrote:
>>>
>>> >I'm going through some code and thinking of ways to reduce GC
>>> >pressure, and came across a bit that needed to append some items to
>>> >an array:
>>> >
>>> >	T[] args;
>>> >	lex.expect("(");
>>> >	args ~= parseSingleItem(lex);
>>> >	while (!lex.empty) {
>>> >		lex.expect(",");
>>> >		args ~= parseSingleItem(lex);
>>> >	}
>>> >	lex.expect(")");
>>> >	return computeResult(args);
>>> >
>>> >Now obviously, in the general case (with arbitrarily many number of
>>> >items) some GC allocations will be needed, but the most common
>>> >use-cases are actually only 1 or 2 items each time. Allocating lots
>>> >of small arrays seem to be rather wasteful, so I thought to use a
>>> >static array as a buffer instead.
>>> >
>>> >The question is, is there a way to take a slice of the static array,
>>> >set the length to zero, and append to it with ~= such that when it
>>> >runs out of space in the static buffer, it will reallocate a longer
>>> >array on the GC heap? Or is this a bad idea?
>>>
>>> TL;DR: Yes, use Appender :)
>>>
>>> The reason appending even works is because of the metadata stored in
>>> the heap. Obviously, stack frames and fixed-length arrays do not have
>>> this data.
>>>
>>> When that metadata cannot be found, it reallocates because that's the
>>> only option.
>>>
>>> However, Appender, initialized with a static buffer, knows the length
>>> of its data, and stores its own capacity, separate from the heap.
>> [...]
>>
>> Unfortunately, the whole point of this exercise was to eliminate GC
>> allocations for small arrays -- but since Appender's implementation
>> allocates a private Data struct in its ctor, that kinda defeats the
>> purpose. For the common case of 1 or 2 items only, it doesn't seem like
>> Appender will perform any better, and it will introduce extra GC
>> allocations to boot.
>>
>> :-(
>
> I advocated a long time ago that Appender should have a stack-based version.
>
> I still think that's the case. Because really what Appender has as an advantage over builtin slices is that it keeps a local copy of the capacity, so no heap metadata lookups need to occur. It's not conceptually that much added.
>
> Of course, back then, I'm not sure we had @disable this(this), which such an appender should have.
>
> -Steve

This old thread is still relevant. Today I was in the same quest as H. S. Teoh here, and I assumed that Appender would work well, but alas. Fortunately, there is a package that does the job: https://code.dlang.org/packages/stringbuffer. Thank you Robert!

-- Bastiaan.