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?


T

-- 
Without geometry, life would be pointless. -- VS

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.

I'm not sure if it will fit your needs, give it a look.

-Steve

22-Apr-2014 22:10, H. S. Teoh via Digitalmars-d пишет:
> 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?
>

Should be a canonical use case for ScopeBuffer
https://github.com/D-Programming-Language/phobos/blob/master/std/internal/scopebuffer.d

Except that it has crippled usability e.g. you need to call free manually.

-- 
Dmitry Olshansky

On Tuesday, 22 April 2014 at 18:47:16 UTC, Dmitry Olshansky wrote:
> 22-Apr-2014 22:10, H. S. Teoh via Digitalmars-d пишет:
>> 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?
>>
>
> Should be a canonical use case for ScopeBuffer
> https://github.com/D-Programming-Language/phobos/blob/master/std/internal/scopebuffer.d
>
> Except that it has crippled usability e.g. you need to call free manually.

I've been working on a "ScopedAppender" that is *bit* slower than ScopeBuffer, but can be used on any generic types, and is nothrow/ctfe/pure/"sometimes safe". I'm giving it the "finishing touches".

But in the meantime, normal appender+clear can work:

int[50] buf;
auto app = appender(buf[]);
app.clear();
//app is ready for use.

The "issue" though is that appender itself as a reference type, so just declaring it allocates, which kind of gets in the way of setting up a local scratch space to begin with.

On Tue, Apr 22, 2014 at 06:59:05PM +0000, monarch_dodra via Digitalmars-d wrote:
> On Tuesday, 22 April 2014 at 18:47:16 UTC, Dmitry Olshansky wrote:
> >22-Apr-2014 22:10, H. S. Teoh via Digitalmars-d пишет:
[...]
> >>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?
> >>
> >
> >Should be a canonical use case for ScopeBuffer https://github.com/D-Programming-Language/phobos/blob/master/std/internal/scopebuffer.d
> >
> >Except that it has crippled usability e.g. you need to call free manually.
> 
> I've been working on a "ScopedAppender" that is *bit* slower than ScopeBuffer, but can be used on any generic types, and is nothrow/ctfe/pure/"sometimes safe". I'm giving it the "finishing touches".
> 
> But in the meantime, normal appender+clear can work:
> 
> int[50] buf;
> auto app = appender(buf[]);
> app.clear();
> //app is ready for use.
> 
> The "issue" though is that appender itself as a reference type, so just declaring it allocates, which kind of gets in the way of setting up a local scratch space to begin with.

Yeah, I'm already using appender for the general case of n items; right now I'm just trying to optimize for the very common case where there are only 1 or two items in the list by eliminating GC allocations for that case. The fact that appender allocates defeats the whole purpose. :-/


T

-- 
BREAKFAST.COM halted...Cereal Port Not Responding. -- YHL

H. S. Teoh:

> 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?

I suggested to add this to Phobos:
https://d.puremagic.com/issues/show_bug.cgi?id=8550

Bye,
bearophile

On 04/22/2014 11:10 AM, H. S. Teoh via Digitalmars-d wrote:

> is there a way to take a slice of the static array, set the
> length to zero,

Currently, instead of setting the length to zero, you should start with the whole slice.

> and append to it with ~=

Instead, you can use the output range primitive put().

> such that when it runs out of space in the static buffer

When slice.empty, it would have covered the static array completely:

import std.range;

void foo()
{
    int[2] buffer;
    int[] slice = buffer[];

    foreach (int i, _; slice) {
        slice.put(i);
    }

    assert(buffer == [ 0, 1 ]);
}

void main()
{
    foo();
}

Ali