www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - assumeSafeAppend on slice of static array?

reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
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
Apr 22 2014
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Apr 22 2014
prev sibling next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Apr 22 2014
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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.
Apr 22 2014
prev sibling next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
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
Apr 22 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Apr 22 2014
prev sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Apr 22 2014