On 12-Jul-2015 18:08, Jacob Carlborg wrote:
> On 2015-06-12 13:06, Dicebot wrote:
>> The legendary allocator package by Andrei Alexandrescu has arrived at
>> your doorsteps and kindly asks to let it into Phobos
>>
>> http://wiki.dlang.org/Review/std.experimental.allocator
>>
>> Docs:
>> http://erdani.com/d/phobos-prerelease/std_experimental_allocator.html
>> Code:
>> https://github.com/andralex/phobos/tree/allocator/std/experimental/allocator
>>
>
> I just looked at Andrei's dconf talk and started to look at the source
> code how this "hasMember" is used. To me it looks like in most cases the
> optional methods, like "deallocate", "owns", "expand" and so on, could
> instead be required methods. Allocators that don't support these methods
> would need to have dummy implementations. But at the same time it would
> be easier for the user of the allocators, doesn't need to use all these
> "static if".

But then a Parent allocator would like to know if the child actually doesn't support reallocate vs say failing to reallocate. In the former case a lot of extra logic is simply removed at compile-time.


-- 
Dmitry Olshansky

On 7/12/15 11:08 AM, Jacob Carlborg wrote:
> On 2015-06-12 13:06, Dicebot wrote:
>> The legendary allocator package by Andrei Alexandrescu has arrived at
>> your doorsteps and kindly asks to let it into Phobos
>>
>> http://wiki.dlang.org/Review/std.experimental.allocator
>>
>> Docs:
>> http://erdani.com/d/phobos-prerelease/std_experimental_allocator.html
>> Code:
>> https://github.com/andralex/phobos/tree/allocator/std/experimental/allocator
>>
>
> I just looked at Andrei's dconf talk and started to look at the source
> code how this "hasMember" is used. To me it looks like in most cases the
> optional methods, like "deallocate", "owns", "expand" and so on, could
> instead be required methods. Allocators that don't support these methods
> would need to have dummy implementations. But at the same time it would
> be easier for the user of the allocators, doesn't need to use all these
> "static if".

That design would have been possible, e.g. have deallocate return false, owns return Ternary.unknown, expand return false, alignedAllocate return null etc.

I see the following issues with that design:

1. Many incorrect or grossly unfit allocators can be statically defined, for example a FallbackAllocator putting in the front an allocator that has a dummy implementation of owns. Unittesting could be expected to reasonably get rid of most.

But there are many byzantine failure modes that are likely to escape even thorough unittesting. Consider, for example, building a Segregator out of several allocators, most of which support alignedAllocate, but some that don't (i.e. return null). During testing, if only the supported size ranges are tested, it all works. In production, if the wrong size is asked for in alignedAllocate, the allocator will return null as if the system ran out of memory.

2. Efficiency becomes increasingly tenuous. Simple cases of calls to do-nothing functions can be reasonably expected to be handled by the optimizer, but e.g. AllocatorList does significant work in owns, deallocate, deallocateAll, etc. - all under the assumption that the parent does implement the expected functionality.

Emery Berger told me this was a constant source of concern with HeapLayers; he'd need to look at disassembly and tweak code in various ways to obtain the desired inlining, which when absent would cause dramatic slowdowns. Compiler technology has improved since that work, but also Heap Building Blocks go quite a longer distance than HeapLayers.

With the DbI approach, the performance profile of a composite allocator is immediate and obvious.

3. Layout decisions cannot be made with dummy implementations.

Currently there are no layout decisions in std.allocator that depend on presence of members, but ScopedAllocator came very closed to such. (There are many layout decisions that depend on instance size.) Going with a dynamic approach would preclude data layout decisions.


Andrei

On 2015-07-12 18:10, Dmitry Olshansky wrote:

> But then a Parent allocator would like to know if the child actually
> doesn't support reallocate vs say failing to reallocate. In the former
> case a lot of extra logic is simply removed at compile-time.

Perhaps this is a simplified view, but most cases there were no difference between failing to reallocate or does not support reallocate.

"deallocate", for example, was used like this:

static if (hasMember!("deallocate"))
    deallocate();

No "else", no action was taken when it didn't support "deallocate". I haven't look through the whole source code.

-- 
/Jacob Carlborg

On 2015-07-13 20:52, Andrei Alexandrescu wrote:

> That design would have been possible, e.g. have deallocate return false,
> owns return Ternary.unknown, expand return false, alignedAllocate return
> null etc.

Perhaps it's a simplified view, but for all examples in the talk it seems it would work without changing the API. The branch which was executed for "does not support this operation" was the same for "this operation failed". Example:

static if (hasMember!("deallocate"))
    deallocate();

There was no "else", no action when "deallocate" was not supported. Or:

static if (hasMember!("reallocate"))
    return reallocate();
else
    return false;

Of course I haven't look through the whole source code.

> I see the following issues with that design:
>
> 1. Many incorrect or grossly unfit allocators can be statically defined,
> for example a FallbackAllocator putting in the front an allocator that
> has a dummy implementation of owns. Unittesting could be expected to
> reasonably get rid of most.
>
> But there are many byzantine failure modes that are likely to escape
> even thorough unittesting. Consider, for example, building a Segregator
> out of several allocators, most of which support alignedAllocate, but
> some that don't (i.e. return null). During testing, if only the
> supported size ranges are tested, it all works. In production, if the
> wrong size is asked for in alignedAllocate, the allocator will return
> null as if the system ran out of memory.
>
> 2. Efficiency becomes increasingly tenuous. Simple cases of calls to
> do-nothing functions can be reasonably expected to be handled by the
> optimizer, but e.g. AllocatorList does significant work in owns,
> deallocate, deallocateAll, etc. - all under the assumption that the
> parent does implement the expected functionality.
>
> Emery Berger told me this was a constant source of concern with
> HeapLayers; he'd need to look at disassembly and tweak code in various
> ways to obtain the desired inlining, which when absent would cause
> dramatic slowdowns. Compiler technology has improved since that work,
> but also Heap Building Blocks go quite a longer distance than HeapLayers.
>
> With the DbI approach, the performance profile of a composite allocator
> is immediate and obvious.

Yeah, my suggestion assumes the compiler can optimize away all these dummy functions.

-- 
/Jacob Carlborg

On 7/14/15 7:35 AM, Jacob Carlborg wrote:
> On 2015-07-13 20:52, Andrei Alexandrescu wrote:
>
>> That design would have been possible, e.g. have deallocate return false,
>> owns return Ternary.unknown, expand return false, alignedAllocate return
>> null etc.
>
> Perhaps it's a simplified view, but for all examples in the talk it
> seems it would work without changing the API. The branch which was
> executed for "does not support this operation" was the same for "this
> operation failed". Example:
>
> static if (hasMember!("deallocate"))
>      deallocate();
>
> There was no "else", no action when "deallocate" was not supported. Or:
>
> static if (hasMember!("reallocate"))
>      return reallocate();
> else
>      return false;

I explained matters at length in the post you're replying to, and from what I can tell this reply is a reiteration of your same point. I don't know what to add - you may want to pay some more mind to that post.

> Of course I haven't look through the whole source code.

One easy way to take a look at things is to clone the branch and then:

git grep --context=5 hasMember

or however many lines you need.

> Yeah, my suggestion assumes the compiler can optimize away all these
> dummy functions.

There were two other considerations.


Andrei

Something I thought about today, if a class or struct is allocated by an allocator(say a malloc based allocator) and one of its fields is populated with a reference to GCed memory, will the GC know to scan the allocator memory to keep that GCed memory alive?

On Thursday, 13 August 2015 at 20:56:36 UTC, Tofu Ninja wrote:
> Something I thought about today, if a class or struct is allocated by an allocator(say a malloc based allocator) and one of its fields is populated with a reference to GCed memory, will the GC know to scan the allocator memory to keep that GCed memory alive?

http://dlang.org/phobos/core_memory.html#.GC.addRange

On Thursday, 13 August 2015 at 21:05:28 UTC, rsw0x wrote:
> On Thursday, 13 August 2015 at 20:56:36 UTC, Tofu Ninja wrote:
>> Something I thought about today, if a class or struct is allocated by an allocator(say a malloc based allocator) and one of its fields is populated with a reference to GCed memory, will the GC know to scan the allocator memory to keep that GCed memory alive?
>
> http://dlang.org/phobos/core_memory.html#.GC.addRange

Yeah I know about that, I was just asking if all the allocators would be marked to be scanned by default. Or if they might try to only mark as needing to be scanned if they contain types that could contain references.

The information of which types have internal references seems to be available at least to the GC. Theoretically an allocator could use that information to mark its allocations as needing to be scanned as well.

Or it could be a wrapper allocator that simply marks things as needing to be scanned when they need to be, that way it would be an opt-in type deal.

just some thoughts...