I know official support for custom allocators for containers in Rust isn't there yet, but I was implementing my own container and got me thinking about the most efficient way to do it.
One thing that has always bothered me about allocators is needing to have the extra pointer to the allocator that is bloating your containers. If you're in a situation where you are using custom allocators in the first place there is a good chance that you will care about this. From what I've been reading, when Rust allocator support lands it will support ZSTs for allocators, which will solve this problem when your allocator is actually a global resource.
However, what if your allocator is not a global resource? I have run into this situation:
struct Foo<T> {
allocator: A,
outer: OuterContainer<InnerContainer<T, A>, A>
}
In a perfect world, somehow we would only store one reference to A that was somehow shared amongst all of the instances of InnerContainer, instead of each individual instance having their own separate reference. Somehow InnerContainer would crawl back up the object hierarchy and find Foo's allocator instance, and we'd save a bunch of memory/cache.
The best alternative I have come up with is making it so that all of the methods of OuterContainer and InnerContainer that need an allocator take an allocator argument and never actually store a reference to the allocator. Methods on Foo explicitly pass the allocator into methods on OuterContainer, which explicitly pass the allocator into the methods on InnerContainer.
This creates two new problems:
-
How do you write your containers such that they support both types of allocators?: allocators where it is expected they store of reference to the allocator and can't count on callers to give them the allocator every time, and allocators where they are specifically not supposed to store a reference to the allocator and require callers to give them the allocator every time.
-
What if callers don't consistently pass in the same allocator?
For #1, I figure you could have a trait that looks something like this:
unsafe trait Allocator {
type StoredReference;
type PassedByCallers;
fn allocate(stored: &StoredReference, passed: &PassedByCallers) -> *mut u8;
//...
}
Implementers of the trait would arrange it it so one of StoredReference or PassedByCallers is a ZST (or both if the allocator is truly a global resource). You would implement your containers to store an instance of StoredReference, and for all of their allocating methods to take a reference to an instance of PassedByCallers. Because the allocate method requires you to provide both, the container is oblivious to which was actually important. Callers that know the real allocator being used and expect each container to store its own reference to the allocator know they can pass in some trivially constructible object of the PassedByCallers type.
It's not pretty per se but I believe it at least works. Is there a better approach? Has anyone else done this?
For #2, things seem less clear. Typically rust considers allocation to be safe and deallocation to be unsafe. In this case because there is the risk that callers could call allocating functions with different allocators for the same container, so I'm not sure if allocation is technically safe. The problems I can imagine are still deallocation specific, but I'm not sure if there is some safe way to write an allocator or container such that the container triggers UB if the same allocator isn't used consistently. It doesn't seem observable to me without making assumptions about pointer values that would be inherently allocator specific but maybe somebody has a counter example?
Edit: there is a third problem which is that container methods that would usually be innocent but are expected to deallocate like pop_back have to be unsafe assuming that deallocating with the wrong allocator triggers UB. It is possible to write allocators that detect this and panic instead, then needing implementations to do that becomes part of the safety contract for the trait.