Why "bring your own allocator" APIs are not more popular in Rust?

It's probably just me, but what is allocation golfing?

Why can't a (custom) allocator return a ZST error on allocation failure, e.g. enum AllocError { OutOfMemory }? Or even a non-ZST error that derives Copy¹?

¹The reason I believe that an allocation error should be able to derive Copy even if it isn't ZST is because I assume it's specifically the heap space that's under control of the allocator that is exhausted on OOM. But not call stack space, or at least it seems exceedingly unlikely to me that that would happen at the exact same time.

2 Likes

Please correct me if I’m wrong, but AFAIU this means doing the strict minimum of allocation. For example if you want to create a dynamically sized n × m matrix (with both n and m runtime values), but where the dimensions don’t change during the lifetime of the matrix, you can either

  • Create a Vec<Vec<T>>. There is n inner Vec (one for each column). That simpler because you you get my_matrix[y][x] for free, but you will have a total of n + 1 allocation.
  • Or you can allocate a single Vec<T> for a total of 1 allocation. When implementing Index, accessing my_matrix[y][x] is in reality accessing data[y * n + x].

Note: I really hope I didn’t inverted column / rows, x / y or m / n, but you should get the general idea.

2 Likes

I think that the concept of “golfing” something, as e.g. in “code golfing”, refers to reducing the number of something as much as possible. Possibly even by taking it as far that it’s just an end in itself, and not necessarily practically useful or worth it anymore. Just like in the actual sports where the goal is to use as few strokes as possible. So in this sense, “allocation golfing” is referring to reducing the number of allocations as much as possible.

10 Likes

As for runtime injection rather than type parametrization, the problem is Drop . The type has to know how to dealloc itself at an arbitrary timing, without outside input. Also, providing the wrong de/alloc to an allocating method would be super quick UB.

I know this is a bit off topic, but I would love for the ability to have a Drop (or a required consuming self method) with custom parameters that had to be explicitly called or would be a compile error. This would allow something like the following to be a compile error:

fn do_a_thing(device: &mut Device)
{
  let mut command_buffer = CommandBuffer::new();
  command_buffer.push(Command::A);
  command_buffer.push(Command::B);
  command_buffer.push(Command::C);
  // ERROR: oops forgot to call `command_buffer.execute(device);`.
}

This would be a compile error because the following couldn't be automatically called due to requiring more than just &mut self.

impl Drop for CommandBuffer
{
  fn drop(&mut self, device: &mut Device)
  {
    // ...
  }
}

Back to the allocation subject, if this functionality existed, then you could require the allocator be passed to Drop instead of storing it on the instance. At the same time, a type that stores the allocator wouldn't require that and could just use the implicit Drop call.

The problem with that is the problem with all linear types. The big one is how do you handle panics, since those unwind and call Drop::drop, if you have to consume the value.

Gankra's The Pain Of Real Linear Types In Rust should be mandatory reading for anyone wanting to add linear-esque types to Rust, and they should have a real purposeful answer (even if it's just "deal with the described fallout") to each of the issues described in that post.

9 Likes

I think the main reason is that Rust picked the option of using a single global allocator early on in its existance and basically stuck with it. It can be easily seen, why they choose this approach given that no-std was yet to be invented and C++ (from which Rust has taken a lot of concepts) has a similar approach in its standard library.

Zig is a different example as "bring your own allocator and use it with standard containers" seems to be a core concept of the language (I think it might have even been invented there) and it has been taken into account in the entire design early on.

The reason why "bring your own allocator" is not used in Rust is because the standard libaries don't really support it. There is the Allocator trait alloc. But not only is it nightly only, but it also is limited by the fact, that it must fit into the preexisting structures. For example you cannot really use it to implement a failable allocator or for many kinds of area allocation, because of the way it is used e.g. in String and Vec. This makes it not that usefull. It is also questionable if custom allocators are the right abstractions, see Is custom allocators the right abstraction?.

My personal guess is that the proper solution would require a redesign of the api of the container types currently defined to alloc to overcome this limitations. This can be done in a backward compatible fashion. This might become more relevant due to the inclusion of Rust in the Linux kernel.

2 Likes

The Allocator trait easily supports failable allocations.

3 Likes

Yes but most of its users do not (currently)

It's a nightly-only trait at the moment. There are very few users. Whether the Global and System allocators support it is up to the platform, not Rust.

1 Like

I don't konw if it is relevant, but seems the linux kernel require a custom allocator to actually embrace rust? https://lkml.org/lkml/2021/4/14/1099

Yeah, this is highly relevant to what I am getting at with this inquiry. To me, it seems that kernel requires not so much a custom std::alloc::Allocator, as completely custom allocation strategy (as far as I understand, kernel usually allocates pages, rather than blobs of bytes, and there are several flags controlling which flavor of pages you want exactly).

So it's not the question of "how I override malloc/free" (which Rust has a good story for), but rather a question of "I have this chunk of memory, it''s all mine, how do I use in the most convenient way?", which I don't see explored in Rust a lot.

1 Like

Wouldn't that be solved by Storage (a concept that was brought up in the "Are Allocators the correct abstraction" ?

1 Like

I recently tried implementing a container in this style (every method on the container that would possibly allocate took an allocator and every method that would possibly deallocate took an allocator). I did it this way because I needed custom allocation but I also didn't want to pay the cost of storing a pointer to the allocator in every instance of my container because I was also going to have many many container instances.

  • When you deallocate how do you know the user is passing in the same allocator instance that they used when they allocated? If you don't have a way to guarantee this any methods on your container that deallocate have to be unsafe. (Workaround: All of my allocations are fixed size so I change the deallocation methods to take a free list that they push back on to instead of actually freeing. Caller becomes responsible for using the free list instead of the allocator for future allocations as long as the free list has entries in it.)

  • How do you pass in the allocator explicitly on drop? (Workaround: require the user to explicitly call a clear method on the container that takes the allocator before the container gets dropped. Have a drop implementation that panics if the container is not empty.)

I doubt everyone would find these workarounds acceptable in the general case.

2 Likes

I think both of those are generally why having the type be generic over the allocator instead is better. That way drop still works and deallocation is safe

I wouldn't say it's necessarily better, but it's definitely easier. I really care about performance, so in a perfect world I would be able to pass in the allocator instead of having to store it and somehow be able to statically guarantee that I pass in the same object consistently to both the allocation and the deallocation methods. I find in trying to write fast safe Rust code I frequently run into the problem of not being able to guarantee that one object came from another object.

You can kind of get this now, if you are willing to have your allocator be a singleton with a unique type, where you actually enforce the property that there is only one instance, but at that point you can just directly refer to the singleton instead of passing it in every time... unless you want to be generic over regular allocators and allocators that you pass in every time, in which case you store a type that is either an allocator reference or a ZST, and all of your methods take a type that is either an allocator reference or a ZST, and in the regular allocator case the member is actually a reference and the argument is the ZST and in the singleton case it's reversed.

1 Like

One interesting option here is to just not free memory in Drop. That is, if you pass-in a bump allocator / arena, you need only at the allocation points, as deallocation happens en-mass outside of your library. That seems to have an interesting implications perf-wise, as you get rid of drop glue everywhere.

1 Like

Half baked idea: Allocators get their own address ranges - i.e. there's a global singleton for allocators, and deallocation dispatches based on the pointer address? I think most malloc systems do something like this internally for different size buckets, etc.

1 Like

So want to be able to have an arbitrary amount of allocators? I don't know if it is possible to have both that and have a compiler make sure that you pass the correct one to each call.

Though as it should be generally known types that must be called by a non-drop (but drop like) function are not panic safe. So I guess you would be okay with (in your performance sensitive code) memory leaks.

I think the qcell crate does some good exploration of different ways to achieve dependency between objects. It presents runtime-ids, singletons, and another approach involving unique invariant lifetimes. (Read the LCellOwner docs.) I wouldn't be surprised if the lifetimes approach could be useful for allocators, too.

1 Like

I think that the storage type itself must in some way precisely encode which allocator is used. A heap storage would likely have to look like this.

struct AllocatorStorage<T, A> {
    ptr: *const T,
    len: usize,
    allocator: A // Might be a zero sized object
}

impl<T: Sized, A: Allocator> Storage for AllocatorStorage<T, A> {
    // ommited
}

If we somebody wants to do this range based allocator, this is in fact doable with Storages, but not with Allocators only. Just build your own storage, that knows how to drop itself.

Regarding drop: A Storage does never drop its content, nor does it provide direct access to its data. For a fixed size storage you could not use [T; N] but only something like [Slot<T>, N]. The Storage will be always be owned by the container type, which is responsible for dropping / moving out the stored data before releasing the storage itself.