Thread overview | |||||||||
---|---|---|---|---|---|---|---|---|---|
|
April 22, 2014 assumeSafeAppend on slice of static array? | ||||
---|---|---|---|---|
| ||||
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
|
April 22, 2014 Re: assumeSafeAppend on slice of static array? | ||||
---|---|---|---|---|
| ||||
Posted in reply to H. S. Teoh | 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
|
April 22, 2014 Re: assumeSafeAppend on slice of static array? | ||||
---|---|---|---|---|
| ||||
Posted in reply to H. S. Teoh | 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 |
April 22, 2014 Re: assumeSafeAppend on slice of static array? | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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.
|
April 22, 2014 Re: assumeSafeAppend on slice of static array? | ||||
---|---|---|---|---|
| ||||
Posted in reply to monarch_dodra | 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 |
April 22, 2014 Re: assumeSafeAppend on slice of static array? | ||||
---|---|---|---|---|
| ||||
Posted in reply to H. S. Teoh | 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 |
April 22, 2014 Re: assumeSafeAppend on slice of static array? | ||||
---|---|---|---|---|
| ||||
Posted in reply to H. S. Teoh | 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 |
Copyright © 1999-2021 by the D Language Foundation