Tracking issue for custom allocators in standard collections

[alexcrichton]

The new Alloc trait defined in RFC 1398 was added in #42313 but the libs teamdecided to hold off on Vec integration just yet to be conservative.

This issue is intended to track the integration of the Alloc trait into standard collections like Vec, BTreeMap, etc. I'm not personally aware of any current blockers, but what we'll probably want to do as part of this issue includes:

• Develop a set of conventions for collections which support custom allocators
• Ensure no regressions with integration of a custom allocator:
  • error messages should look as they do today
  • no performance regressions at runtime
  • ideally minimal compile-time impact

[Ericson2314]

There are some very interesting issues here:

• "Flat collections" (Vec, VecDec) can easily store a &mut to the allocator they were crated with, indirection-heavy ones would be significantly bloated if every Box also had an allocator reference.

• Ideally all collections would be resilient in the face of allocation failure, but that will take some major algorithms design work. It's better to convert quickly blowing up on OOM as they do today.

• I had the idea of doing trait InfallableAllocator = Allocator<Error=!> to signify an allocator that wouldn't fail (and thus must panick on OOM). If, when we en-mass convert collections, we have them take an InfallableAllocator parameter, it will be clearer to the end-user that the collections are not oom-resilient, and there would be less panics strune about.

  • I'm not up-to-date with all the discussion of invalid Layouts, so I'll need to double-check that ! wouldn't instead need to be some strict Unsupported;. Then again, it isn't like the collections will be able to handle an unsupported layout either...

• Not sure what the ETA on default parameters is, so we're probably best off reexporting collections in std with the allocator parameter specialized to the global allcoator. This will work today, right?

[joshlf]

@Ericson2314

I had the idea of doing trait InfallableAllocator = Allocator<Error=!> to signify an allocator that wouldn't fail (and thus must panick on OOM). If, when we en-mass convert collections, we have them take an InfallableAllocator parameter, it will be clearer to the end-user that the collections are not oom-resilient, and there would be less panics strune about.

I believe that the current design doesn't allow you to parametrize the error, so it must return the concrete error type with two arms - Unsupported and Exhausted - and if you want to panic on OOM, it's your (the client's) responsibility to do that by panicking yourself or by calling the oom method.

[Ericson2314]

@joshlf err yes, this is predicated on us adding an associated error type.

To support the allocator trait in the collection types, the constructors will need to be duplicated.
@pnkfelix has used the _in suffix and appended the allocator to the list of arguments:

impl RawVec<T, A>
    fn with_capacity(n: usize) -> RawVec<T, HeapAlloc>;
    fn with_capacity_in(n: usize, a: A) -> RawVec<T, A>;
}

I personally quite like this approach.

@Ericson2314 mentioned this:

"Flat collections" (Vec, VecDec) can easily store a &mut to the allocator they were crated with, indirection-heavy ones would be significantly bloated if every Box also had an allocator reference.

I am currently implementing a non-trivial allocator myself (for a relocatable heap) and noticed that it don't need to keep anything around for deallocation (the type information is still needed).

This still works when multible allocators are used.

I wonder if this could be integrated somehow? Associated types to indicate what needs to be stored?

[joshlf]

@s3bk

I am currently implementing a non-trivial allocator myself (for a relocatable heap) and noticed that it don't need to keep anything around for deallocation (the type information is still needed).

This still works when multible allocators are used.

I wonder if this could be integrated somehow? Associated types to indicate what needs to be stored?

So the idea is that, for allocators where all instances of the type refer to the same global singleton, you wouldn't actually need to store a reference? Presumably that wouldn't work for allocators that could actually have multiple distinct instances, right?

This motivates a follow-up: if you were implementing a global singleton, couldn't you just make the actual Alloc type that you expose to users be a ZST that delegates to some private instance under the hood?

@joshlf

So the idea is that, for allocators where all instances of the type refer to the same global singleton, you wouldn't actually need to store a reference? Presumably that wouldn't work for allocators that could actually have multiple distinct instances, right?

Yes, for allocators with multiple instances the allocation function would benefit from non-zero knowledge.
(Mine needs to know the base address for instance. And working with more than one allocator is perfectly reasonable.)
What I was trying to point at, is that the pointer passed to dealloc is enough information to recover the actual instance used to allocate the memory.

[hanna-kruppe]

@s3bk How common is the case where you will only ever need to deallocate? All the standard collections and smart pointers have methods that allocate new memory from the same allocator (usually clone; Rc and Arc have make_mut).

Hm, now that I think about it, those methods already need to clone the allocator, so that would potentially offer a way out. Although it's unclear to me if we can switch between storing A and A::DeallocInfo in the collection depending on whether A: Clone, and it's also not clear to me if that would be a good design (it seems to work out mostly by chance, assuming it works out at all).

@rkruppe there could be

trait Alloc {
    type DeallocInfo;
    fn dealloc(&self, ptr: *mut T, layout: Layout);
    fn dealloc_with(info: Self::DeallocInfo, ptr: *mut T, layout: Layout);
    // snip
}
struct Rc<T, A: Alloc> {
  dealloc: A::DeallocInfo;
  // snip
}
impl<T> Rc<T, HeapAlloc> {
    fn make_mut(&mut self) -> &mut T { 
         // use HeapAlloc to potentially clone T
    }
}
impl<T, A: Alloc> Rc<T, A> {
    fn make_mut_in(&mut self, a: A) -> &mut T { 
         // use A to potentially clone T
    }
}

This would keep Rc as thin as possible, not break existing code and allow to use make_mut_in for code that is generic over Alloc

edit: The case for only dealloc: Box, and many non-std types that only provide a minimal api.
edit 2: completely wrong.

[hanna-kruppe]

@s3bk make_mut_in makes HeapAlloc a special case for no good reason, granting it better ergonomics than other allocators that can support make_mut just as well.

edit: The case for only dealloc: Box, and many non-std types that only provide a minimal api.

Box::clone allocates. Do you have examples of such non-std types?

@rkruppe It looks like I was completely wrong here. Most cases are covered by Box and the others reallocate.
Not sure how the the ergonomics could be solved, apart from adding another trait.