Phobos addition formal review: std.experimental.allocator

[Andrei Alexandrescu via Digitalmars-d]

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