Vote on region allocator

[Andrei Alexandrescu]

On 9/24/11 1:19 CDT, Jonathan M Davis wrote:
> On Saturday, September 24, 2011 01:10:44 Andrei Alexandrescu wrote:
>> On 9/23/11 22:30 CDT, dsimcha wrote:
>>> On 9/23/2011 11:25 PM, Robert Jacques wrote:
>>>> On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
>>>> <jmdavisProg at gmx.com>  wrote:
>>>>
>>>> No. I cannot build an efficient and safe appender on this API.
>>>
>>> The resize() fix you requested is going to get implemented. I just
>>> haven't actually added it yet.
>>
>> Then we might be hasty to vote this in. Ideally Phobos should be
>> integrating tried and true APIs.
>>
>> I wish we voted allocator in once it's used throughout std.container to
>> great effect.
>
> So, do you think that we should cease the vote then?

At the risk of annoying David and others, allow me to vote against 
inclusion of the current proposal. There are three main reasons:

1. The proposal has been changed mid-review.

2. There are hints of further changes post-review.

3. Only the scoped allocator has been used, but not the others.

These threes are basis enough for a negative vote. That being said, this 
is excellent progress towards solving a very difficult problem.

Below are some more thoughts about steps that could be taken to improve 
the design and its implementation.

Fundamentally we want to make sure we cover the following allocators:

1. Classic malloc/realloc/free, unsafe
2. Scoped allocators of various flavors (simple/expanding/etc.)
3. Full-fledged garbage collectors, conservative and not
4. Stacked combinations (e.g. freelist over region over malloc etc.)
(5. It would be awesome if we could somehow catch allocators that use 
reference counting, or at least not prevent their definition. I'm just 
mentioning this because it's been buzzing in my mind forever, but any 
design I can think of is fraught with issues.)

Of these, the garbage-collected allocators need type information about 
the data, so we can only assume that any allocator needs it. There is 
some design in that direction, but it lacks the dynamic component. 
Generally the relationship between the structural/static interface and 
the dynamic interface is tenuous (when should one use one vs. the other? 
how does one pass type information about an allocation through the 
dynamic interface?)

Currently the low-level interface traffics in void* (not even void[] or 
ubyte[] which may be better) and does not offer any way to e.g. set the 
type of a chunk after it's been allocated. This makes e.g. a precise 
garbage collector difficult to integrate (and impossible with the 
dynamic interface).

I think the interface should offer a bool freeAll() that frees all 
memory allocated by the given allocator. That would only work with 
scoped allocators and would return false for the others. Speaking of 
which, there's no property that says "free() is inoperant", which is the 
case for certain region-based allocators.

Finally, it would be great if some validation was available. There's no 
use of the dynamic interface with e.g. containers, which would have 
readily revealed e.g. the fact that a container can't pass type 
information to the allocator through the dynamic interface.

We should also have some more examples of stacked allocators, e.g. that 
use free lists on top of regions etc. The current static design seems to 
be almost adequate. The way I see this all working is that allocators 
define the static interface for maximum performance and are stackable in 
infinite ways. Once the user decides on a stacking configuration, they 
simply wrap the entire stack in the dynamic interface and use that with 
e.g. a container.


Thanks,

Andrei