Orphan ranges

[Steven Schveighoffer]

On Sun, 15 Apr 2012 12:34:11 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> I'm making good progress on an allocator design. If things come together  
> as I hope, it'll kick some serious ass.
>
> I'm currently looking at four allocation models:
>
> * straight GC, safe (no deallocation)
> * GC + the ability to free memory
> * malloc/free, unsafe, buyer beware (STL-level safety)
> * reference counted (based on either malloc or GC+free)
> * region (scoped)

* pool/freelist based.  Dcollections has such an allocator (Called a chunk  
allocator), which I hope would be applicable.  It's in fact the default  
allocator.

I saw you responded later that it will be a generic parameter.  While I  
support that, and it is the same model in dcollections, it leaves a lot to  
be desired.  For instance, if I have a RedBlackTree of SList!int, will  
each SList have it's own copy of an allocator?  Sure you could use a  
singleton allocator to avoid overhead, but what if I simply want only the  
SLists in my RedBlackTree to share an allocator, and not with all  
SList!int?

I've been occasionally putting some thought into that for dcollections,  
and I haven't really come up with a good solution yet, but it feels  
withink reach with some dedicated effort.  I'm interested if you have a  
solution for this in mind.

> I need to kink out a few details, most important being - is safety part  
> of the allocator or an extricable property that's a different policy?  
> For now I have a related question about orphan ranges.

It's definitely an allocator property.  For example, malloc/free is  
unsafe, there is no way to make it safe.

> Consider this motivating example:
>
> void main()
> {
>      int[] x;
>      {
>          auto b = new int[20];
>          x = b[5 .. $ - 5];
>      }
>      ... use x ...
> }
>
> The range x is a 10-elements range that originates in a 20-element  
> array. There is no safe way to access the original array again, so in a  
> sense the other 10 elements are "lost". That's why I call x an orphan  
> range - a range of which original container is gone.
>
> Built-in arrays work routinely like that, and in fact the originating  
> arrays are not distinguished by type in any way from their ranges (be  
> they orphan or not). The question is, what should std.container do about  
> orphan ranges in general? Should it allow them, disallow them, or leave  
> the decision open (e.g. to be made by the allocator)? Depending on what  
> way we go, the low-level design would be quite different.

I'd like to slightly correct your statement ;)  b is a 20-element range  
that originates in a 31-element array (b.capacity is 31).  The GC is the  
allocator and owner of the array type, which has no formal type.

But I understand the question.  and I think the situation is somewhat  
different -- most ranges will not be able to be attached spontaneously to  
different container instances.  Nor will they rely on the allocator to  
generate extra instances at will to appease the requests.  Built-in  
arrays/slices are like that.

However, I think absolutely we need orphan range support.  I think it's  
really a property of the allocator, not the container, as to whether  
orphan ranges exist.  For proof, look no further than your list of  
possible allocators at the malloc/free version.  Clearly orphan ranges are  
not implementable using that back-end, since once you lose your original  
container reference, the memory is leaked.

If we make it container policy, any container would have to disallow that  
allocator.  I think that's too restrictive, and makes the malloc/free  
allocator somewhat useless.

In terms of "allowance", I don't see how you disallow them.  All I think  
you can do is make using orphaned ranges defined behavior or not.

-Steve