Combining the allocator and storages APIs

libs
1

I've been thinking about whether there's a happy medium between the typed and highly monomorphized storages api that was proposed in this post: Is custom allocators the right abstraction? and the existing Allocator trait currently in nightly.

I think I've come up with an elegant solution that sticks with being byte-focused yet allows for a very compact inline Vec (as well as other collections).

The main idea is to add an associated type "handle" to the Allocator trait along with a function that extracts a pointer + length out of that handle.

pub unsafe trait Allocator {
    // In most cases, this will just be `NonNull<[u8]>`.
    type Handle: Clone;
    
    fn get(&self, handle: &Self::Handle) -> NonNull<[u8]>;
    fn default_handle(&self) -> Self::Handle;
    
    fn allocate(&self, layout: Layout) -> Result<Self::Handle, AllocError>;
    unsafe fn deallocate(&self, handle: &Self::Handle, layout: Layout);

    // ...
}

In the majority of cases, Allocator::Handle will just be NonNull<[u8]>, so the usage doesn't change except that the collection must only store the handle and reacquire the pointer every time it's used.

I've implemented a proof-of-concept InlineAlloc along with a simple Vec that can use this new Allocator trait.

This is what the usage ends up looking like:

let mut v: Vec<i32, InlineAlloc<{ 4 * 4 }>> = Vec::new_in(InlineAlloc::default());

assert_eq!(mem::size_of_val(&v), 24);
assert_eq!(v.capacity(), 4);
    
v.try_push(1).unwrap();
v.try_push(2).unwrap();
v.try_push(3).unwrap();
v.try_push(4).unwrap();
v.try_push(5).unwrap_err();

assert_eq!(&[1, 2, 3, 4] as &[_], v.as_slice());
println!("{:?}", v.as_slice());

Here's a link to a playground containing all the relevant code: Rust Playground.

2

A major trick here (that I think was mentioned previously?) is that instead of having Allocator(Buffer); Handle(()), you have Allocator(()); Handle(Buffer). This prevents the previous need to have "single storages," which were required so the storage didn't have to remember if it's given out a handle to it's singular slot. Instead, just make the handle the slot.

The one thing I do worry about, though, is that this breaks most containers. Consider a trie; rebalancing shuffles a lot of owning handles around. A trie rebalance could be written to never persist a pointer over a handle move, but I'm sure there are more complicated containers where there isn't a single owning handle, but there still is a point where the allocation is jointly owned (think arenas). Along those lines, Arc<T, InlineAlloc> obviously doesn't work. How do we make it not compile?

Perhaps the graph/arena/owning-handle issue can be solved by moving ownership back into the home allocator and just reintroducing the "oneshot" supertrait to avoid bookkeeping overhead, while keeping the type agnostic API. I don't know if the previous storage API ever dealt with making Arc<T, InlineAlloc> not compile (while allowing Arc<T, GlobalAlloc>), so I'm not holding it against this variant.

Cc @TimDiekmann ; I don't see any immediate shortcoming compared to "full" storages, but I'm also not fully aware of the intricacies.

I think I'm weakly in favor of the allocator/storage API dealing exclusively in "give me a place matching Layout", i.e. this byte dealing API rather than the typed one. The typed layer of the abstraction comes in at a later point, with Box, Vec, or other containers.

1 Like
3

Is there a reason this has to be Clone?

I think this needs a mutable version, otherwise you're forced to use UnsafeCell like in your example and lose aliasing optimizations.

Is this supposed to be something like a dangling pointer for niche optimizations?

I guess introduce another marker trait? The question is probably what should it be.

4

@CAD97 touched on this, but I want to elaborate: you cannot both store the memory in the handle and have multiple handles to the same memory at the same time.

For Vec, this is not an issue, but how do you plan on implementing a LinkedList? Or any form of tree with a pointer to the parent in every child?

This is why I am afraid that there is no choice but for Handle to be a "pointer" to the memory area, and not the memory area itself.

5

@CAD97 The solution is to have two traits, Allocator and DistantAllocator: Allocator (bikeshedding necessary). DistantAllocator would assert that pointers retrieved from an allocation do not point to within the allocator or any handles it creates. That does not, however, mean that the allocation does not move—a compacting allocator would be implementable in this proposal. Another way would be that the collection could assert that mem::size_of::<A::Handle>() is smaller than the size of the allocated space.

In reply to @SkiFire13: I guess it's not necessary. I'm not sure if get should take a mutable handle or not. An yes default_handle would return NonNull::dangling() in most cases.

EDIT: I thought of another way to disallow things like Arc. Since the handle would have to be Clone for Arc to work, the handle of an inline allocator would simply not be Clone. Also, storing a handle within an inline handle won't be an issue, since the collection would have to request an allocation with space for the handle + other stuff, which would always fail in that case.

6

CoerceUnsized is still an issue, unfortunately. There needs to be some way to insert code into the coercion operations because the handle is untyped.

There might be another way around this issue by making <T as Pointee>::Metadata implement CoerceUnsized in some way as suggested in this post: Should Pointee Metadata be CoerceUnsized?

7

Thinking more deeply about this case, I think that many collections will indeed require that the handle and buffer be absolutely separate.

Even a cons-list such as struct List<T>(T, Option<Box<Self>>) or a binary tree without parent pointer such as struct Tree<T>(T, Option<Box<Self>>, Option<Box<Self>>) cannot be implemented with a buffer contained in a handle. The reason is simple, it would mean the buffer contains something larger than its own size, which is of course impossible.

So any kind of recursive data-structure -- lists, trees, graphs -- cannot be implemented on top of handles containing their own buffer.

This leaves at least Box and Vec (and Vec-like such as VecDeque or open-access hash-tables), which is a non-empty set, but it's unclear if it's worth having a different concept just for those, rather than a more universal concept of pointer-like handles.

8

I think having it work merely for Vec is enough for it to be useful. That being said, there are other use-cases: for example, you could implement a compacting allocator with this, where there's one level of indirection between a handle and a pointer to the allocation.

I went ahead and implemented simplified versions of Vec, Box, LinkedList (singly), and Rc in this Rust Playground using the proposed allocator trait.

I had to add an additional Size associated type that lets things like Box be the same size as a pointer. LinkedList is successfully prevented from allocating when using an inline allocator, and Rc::clone fails to compile if it's using an allocator which doesn't have a Cloneable Handle.

I think this proposal can be used for everything that the current Allocator can (as long as the CoerceUnsized issue is sorted out) plus it's more flexible and allows for exotic allocator types, like compacting and inline allocators.

9

I need to (and plan on) playing with it some, but I think we can get away with some trickery here. Say that semantically Clone/Copy on a Handle type must copy the handle, but not the backing memory. Place a similar bound on Copy/Cone for the Allocator. Then, things like graphs and Arc require Handle: Copy, but Box doesn't, so can use inline storage.

1 Like
10

Yeah, take a look at the Allocator trait and Rc implementation in the most recent playground (Rust Playground).

11

With some hacking around to make the alignment of the inline allocator a const generic parameter, InlineVec<T, N> can be implemented as this:

pub type InlineVec<T, const N: usize> = Vec<T, InlineAlloc<{mem::size_of::<T>() * N}, {mem::align_of::<T>()}>>;

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=c813ccb387eefdabe945965d9b6f03d2

12

I am not quite sure how to read that:

  • Having it work for Vec is enough to prove it's a better Allocator API.
  • Having it work for Vec is enough, we don't need the Storage API.

I do agree that I do think that reifying the Handle, rather than relying on NonNull, is worth it in general. It unlocks a number of usecases: you mentioned compacting allocators, but there's also shared memory, possibly GPU memory, etc...

I do not think that handles should contain the memory they refer to.

It works only for a narrow set of usecases, so you need the Storage API regardless, and once you have the Storage API then there's no point in "fat" handles.

I do think that having typed handles is useful.

Much like NonNull<T> is typed, I do think it is useful to have Handle<T>. It provides a place for meta-data to be stored, and it assists users in writing correct code.

13

One problem of having typed handles (but not the storage/allocator itself) is that they need full GATs. I'm not sure the advantages offset having to wait that much

14

That is true; I'm not sure how close/far GATs are.

On the other hand, I don't think you can get CoerceUnsized for untyped handles, and I presume we'd want Box<T, A/S> to implement CoerceUnsized.

15

Since the Rust team decided to postpone the allocator API until after 1.0.0, we already ended up at a point where several possible solutions became infeasible. However, there are also still so many new ideas being presented, that even though I'd love to have a stable, more powerful API, right now, I don't think rushing will get us anywhere. IMO, the WG should explore all possibillities and if it turns out, that the best possible allocator API requires waiting on another unstable feature being stabilized, then I'd rather wait another year than end up with a sub-optimal solution, that will bring us one step closer to Rust 2.0.0, Rust++ or <insert new language name> that does everything Rust does, but better. Editions can fix a lot of stuff, but not everything.

2 Likes
16

I think typed handles add a huge amount of complexity and lack of flexibility that could be avoided by modifying CoerceUnsized.

17

I think I need to clarify.

The idea of the Storage API was to supplement the Allocator API, by providing a more convenient API for writing collections -- and especially unlocking "inline" collections.

Since the Storage API supplemented the Allocator API, there was no need to redo what the Allocator API was doing, and notably I saw no need to worry about untyped handles because that's already what the Allocator API provides.

If we are discussing the_entire_ context of memory allocation -- a mix of both Allocator and Storage APIs -- then we need to discuss both untyped memory (NonNull<[u8]> today) and typed memory (NonNull<T> today).

It's notable that typed handles, just liked NonNull, can express both typed and untyped, and therefore it would have my preference, but we could also argue towards splitting typed and untyped.

From experience CoerceUnsized doesn't work very well with typed handles today -- this seems relatively easy to fix, unlike making it work for untyped handles, though.

18

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.