Implement allocators, integrate with box, smart pointers, containers

[brson]

RELATED WORK

• http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html
• https://github.com/bloomberg/bde/wiki/BDE-Allocator-Model

BLOCKING BUGS

• ICE if generic destructor invokes a method on self ("vtables missing where they are needed") #4252 (?)

[huonw]

#4252 is required for allocators (to be able to call .free in Drop impls).

[pnkfelix]

Assigning 1.0 (at least to put a spec in, if nothing else, though we probably should have an implementation as well).

Depending on how allocators integrate with box as well as std libraries, could be P-backcompat-libs (but a case could be made for lang)...

[brson]

We at least need to have high-confidence that we can do it post-1.0.

[thestinger]

If it's done with default parameters, it would be backwards compatible.

Vec<T> -> Vec<T, A = Heap>
Rc<T> -> Rc<T, A = Heap>
HashMap<K, V> -> Vec<K, V, A = Heap>

Functions like new would then be defined only for A = Heap and a with_alloc function taking an allocator parameter would be available for passing a custom allocator instance:

// this becomes a TreeSet<int, Heap> and will still print in errors as TreeSet<int>
let mut xs = TreeSet::new();
xs.insert(5);
channel.send(xs);

// this is a TreeSet<int, CacheAlignedAllocator>
let mut xs = TreeSet::with_alloc(CACHE_ALIGNED_ALLOCATOR);
xs.insert(5);
channel.send(xs);

[nikomatsakis]

cc me

[cgaebel]

I was at Bloomberg last year, and I found https://github.com/bloomberg/bde/wiki/BDE-Allocator-Model to be extremely powerful, and potentially something to model Rust's allocators after.

Pros: Where your memory comes from is very explicit. It makes it very easy to do things such as hierarchical allocators. For example, having a bump allocator allocate its memory out of an arena of bump allocators which allocates its memory out of the stack. Writing code that only uses stack in inner-loops becomes possible, and I've seen very little code like it outside of that company.

Cons: Where your memory comes from is very explicit. Basically every struct that can allocate memory gains a new Allocator pointer. It works pretty well in large, homogeneous C++ codebases, but maybe rust can do something smarter here. I don't like having to add that field myself, every time, but I also wouldn't like for my structs to gain implicit fields. There is a relatively large design space here to explore.

[huonw]

Basically every struct that can allocate memory gains a new Allocator pointer

The precise details of this isn't quite true. Every struct that can allocate memory would gain a new field like (for illustration purposes):

struct Foo<A: Allocator> {
    // ...

    alloc: A
}

i.e. not required to be a pointer. Also, Rust has well-defined zero-sized types, so one can substitute in something like struct CAlloc;that just calls malloc/free, and struct Jemalloc; calling jemalloc's routines. If someone does have an allocator that needs to be behind a pointer (for size or for shared data), they're free to do that as part of the implementation details of it.

(Just glancing at the BDE API now, it seems like it would be preferable for Rust to expose an API like jemalloc's experimental API, where e.g. malloc returns the true usable size of the allocations, and you can request some optional extra size for reallocs, etc.)

---

FWIW, #4252 is now closed, so it's probably possible to start experimenting with this seriously.

[cgaebel]

The way BDE does it, is that every struct/class which allocates gets an Allocator*. When you create one of these objects, you pass it one. You could also pass null (which the parameter defaults to), in which case it uses the global allocator. But either way, it doesn't store the allocator itself - only a pointer to it. This might be hard to replicate in rust (with memory safety and all), but using a reference counted pointer might be appropriate for this.

[huonw]

If some allocator needs shared state, the Allocator struct can use something like

struct MyCoolAllocator {
     priv inner: Rc<MyCoolSharedState>
}

impl Allocator for MyCoolAllocator { ... }

We definitely don't need to force every struct taking an allocator to be a word larger (since we have zero-sized types, unlike C++), or force the entirety of each allocators to be behind a pointer.

[cgaebel]

The allocators are designed as honest to goodness classes in BDE, with pure virtual allocate() and deallocate() methods. I've seen traditional C++ template-based allocators in use and BDE allocators in practice, and I much preferred BDEs. The semantics were extremely clean, and the vtable dispatches were entirely worth it.

[huonw]

Why not have

impl Allocator for ~Allocator { ... }
// etc

(would be just impl Allocator for Allocator { ... } with DST.)

so one can choose between extra words & virtual calls, and static dispatch (and no extra words) seamlessly? (I guess this might not be quite so clean.)