https://github.com/D-Programming-Language/phobos/pull/1911

This adds a package std.buffer, and the first entry in that package, std.buffer.scopebuffer.

ScopeBuffer is an OutputRange that sits on the stack, and overflows to malloc/free. It's designed to help in eliminating gc allocation by lower level functions that return buffers, such as std.path.buildPath(). With some judicious user tuning of the initial stack size, it can virtually eliminate storage allocation.

Using it is @system, but the user of ScopeBuffer can be @trusted.

An output range like this is a precursor to eliminating the excessive gc use by functions such as buildPath().

On Friday, 7 February 2014 at 08:24:39 UTC, Walter Bright wrote:
> https://github.com/D-Programming-Language/phobos/pull/1911
>
> This adds a package std.buffer, and the first entry in that package, std.buffer.scopebuffer.

About to go to bed so just a couple of quick thoughts.

Why not just stick the stack array in ScopeBuffer itself (the
size could be a template parameter)? Escaping a ScopeBuffer is
rarely safe when it takes an external static array but if it
packed its own static array you could safely return it safely.

Also, if it did embed the static array in the ScopeBuffer I
wonder if it could just use the pointer as the buffer if the
length is less than size_t (short string optimization).

(Just thinking aloud, I wonder if std.allocators could be used to
implement this more generically (hypothetically: alias
ScopeBuffer =
CustomAllocOutputRange!(StaticWithMallocFallbackAllocator!10)))

It's a welcome addition and will go a long way toward cutting
down GC allocations once Phobos is output-range-ified. This technique is probably the first thing I'd reach for when choosing an output range.

On 2/7/2014 12:46 AM, Brad Anderson wrote:
> On Friday, 7 February 2014 at 08:24:39 UTC, Walter Bright wrote:
>> https://github.com/D-Programming-Language/phobos/pull/1911
>>
>> This adds a package std.buffer, and the first entry in that package,
>> std.buffer.scopebuffer.
>
> About to go to bed so just a couple of quick thoughts.
>
> Why not just stick the stack array in ScopeBuffer itself (the
> size could be a template parameter)?

1. It's set up to fit into two registers on 64 bit code. This means it can be passed/returned from functions in registers. When I used this in my own code, high speed was the top priority, and this made a difference.

2. It needs to avoid the default initialization of the array, because it's both
unnecessary and it kills the speed. Currently, this
cannot be avoided for part of a struct.

3. I wanted it to be usable for any block of memory the user wished to dedicate to be a buffer.

4. Having an internal reference like that would mean a postblit is required for copying/moving the range, another source of speed degradation.


The design of ScopeBuffer is based on a fair amount of trial and error on my part trying to wring as much speed as possible out of it.


> Also, if it did embed the static array in the ScopeBuffer I
> wonder if it could just use the pointer as the buffer if the
> length is less than size_t (short string optimization).

I almost never needed a buffer that small, and the extra tests for it killed performance (I had tried it at one point).


> (Just thinking aloud, I wonder if std.allocators could be used to
> implement this more generically (hypothetically: alias
> ScopeBuffer =
> CustomAllocOutputRange!(StaticWithMallocFallbackAllocator!10)))

The custom allocator design is a long way from being realized. I don't know if it would help or not.


> It's a welcome addition and will go a long way toward cutting
> down GC allocations once Phobos is output-range-ified. This technique is
> probably the first thing I'd reach for when choosing an output range.

Once the buffer package is accepted, I want to add others I've been using like circular buffers (the one from the compressor proposal), fixed buffers, and even move std.outbuffer to it. I also want it to be one buffer design per module, not the usual grab-bag modules.

On Friday, 7 February 2014 at 08:24:39 UTC, Walter Bright wrote:
> [...]
>
> An output range like this is a precursor to eliminating the excessive gc use by functions such as buildPath().

Somewhat OT, but I think you should pick some other function than buildPath() for your examples.  It *used* to allocate east and west, yes, but that was a holdover from the old std.path.join().  I made some improvements to it about half a year ago, and now it virtually never allocates more than once(*).

Note, this is not an argument against ScopeBuffer, which may well be very useful.  (I haven't looked properly at it yet.)

Lars


(*) Specifically, it will allocate more than once iff the list of path segments is an input range, and not a forward range, and the resulting path is longer than 255 characters.

On 2/7/2014 1:13 AM, Lars T. Kyllingstad wrote:
> On Friday, 7 February 2014 at 08:24:39 UTC, Walter Bright wrote:
>> An output range like this is a precursor to eliminating the excessive gc use
>> by functions such as buildPath().
>
> Somewhat OT, but I think you should pick some other function than buildPath()
> for your examples.  It *used* to allocate east and west, yes, but that was a
> holdover from the old std.path.join(). I made some improvements to it about half
> a year ago, and now it virtually never allocates more than once(*).

I picked on buildPath() for a reason. The program I was writing did a lot of searching for files along a path, and by a lot I mean tens of thousands of times (!).

That one little 'ole allocation was murdering performance and generating vast amounts of garbage.

I wound up rewriting it to use ScopeBuffer, problem solved.

(Also, one of the lovely things about ScopeBuffer is it moves the action to the stack, which is hot in the cache.)

On 2/7/2014 1:38 AM, Walter Bright wrote:
> I picked on buildPath() for a reason.

Sorry :-)

Anyhow, I think buildPath() is a good example of why even an innocuous allocation can cause problems.

On Friday, 7 February 2014 at 09:38:56 UTC, Walter Bright wrote:
> I picked on buildPath() for a reason. The program I was writing did a lot of searching for files along a path, and by a lot I mean tens of thousands of times (!).
>
> That one little 'ole allocation was murdering performance and generating vast amounts of garbage.

I don't understand.  Even if your workspace is stack-based or malloc-ed, you still need that one GC allocation for the return value, no?

Lars

On Friday, 7 February 2014 at 09:44:07 UTC, Walter Bright wrote:
> On 2/7/2014 1:38 AM, Walter Bright wrote:
>> I picked on buildPath() for a reason.
>
> Sorry :-)

No worries. :)  I'm not being defensive here; I just want to understand, and I also don't want newbies to needlessly avoid buildPath() because they think it is a performance killer.

Am 07.02.2014 10:13, schrieb Walter Bright:
> 1. It's set up to fit into two registers on 64 bit code. This means it can be
> passed/returned from functions in registers. When I used this in my own code,
> high speed was the top priority, and this made a difference.

did you also test the codegen of ldc and gdc - or is this optimization
only "working" for dmd?

On 2/7/2014 2:02 AM, Lars T. Kyllingstad wrote:
> On Friday, 7 February 2014 at 09:38:56 UTC, Walter Bright wrote:
>> I picked on buildPath() for a reason. The program I was writing did a lot of
>> searching for files along a path, and by a lot I mean tens of thousands of
>> times (!).
>>
>> That one little 'ole allocation was murdering performance and generating vast
>> amounts of garbage.
>
> I don't understand.  Even if your workspace is stack-based or malloc-ed, you
> still need that one GC allocation for the return value, no?

If you have a path with 20 entries in it, and don't find the file, you do zero allocations instead of 20. If you find the file, that's do one allocation instead of 20/2 (on average), and you might be able to avoid that by passing it upwards, too :-)