Stream: t-libs/wg-allocators

Topic: Some random thoughts about infallible allocations


Tim Diekmann (Jan 23 2020 at 10:44, on Zulip):

True infallible allocators are not possible!
An allocator is used to... allocate. Each time an allocator allocates, a memory area is returned. So how can an allocator be infallible when memory is finite?

So what does mean infallible in this context?
I can only think of one kind of allocator: You know the memory size from the beginning, either as a parameter in the constructor, or prescribed by the type itself. Then the allocator is basically nothing else but a low-level `Vec'. In such cases, the allocator could panic instead of aborting, since the user theoretically knows how much space is left in the allocator.

How to implement infallibility?
In the current AllocRef trait, we always return AllocErr as error. To mark an allocator as infallible, we need an associated error type. If this is set to !, an allocator is infallible. There may be other possibilities, but I can't think of any right now.

What do we want/need infallible allocators for?
Infallible allocators would return Result<_, !>'. Result<_, !>::unwrap() is a noop while Result<_, AllocErr>::unwrap()` requires a branch. This matters in tight loops, where those allocator could be used (e.g. in game development).

Simon Sapin (Jan 23 2020 at 12:17, on Zulip):

I think this is a false premise. “Infallible” in the context of memory allocation does not mean that failure never happens. (This may be confusing and perhaps it was not a great choice of terminology, but at this point it is somewhat established.) It means that the possibility of failure is not part of the “main” code path. In a fallible API, failure is represented as part of the return value of relevant functions or methods, for example with Result or a nullable pointer. In a so-called infallible API means that a function diverges (panics, aborts, …) on failure.

Simon Sapin (Jan 23 2020 at 12:17, on Zulip):

Vec::try_reserve is fallible, Vec::reserve is infallible

Tim Diekmann (Jan 23 2020 at 12:18, on Zulip):

Thanks for clarifying this!!

Simon Sapin (Jan 23 2020 at 12:20, on Zulip):

My personal opinion is that Result<_, !> is not a good way of designing infallible APIs. The point of infallibility is that you deal with failure early so that downstream callers have the convenience of not worrying about it. Result<T, !> is less convenient than a plain T.

Tim Diekmann (Jan 23 2020 at 12:22, on Zulip):

I always have associated infallible with "no error". This is a game changer :)

Simon Sapin (Jan 23 2020 at 12:22, on Zulip):

Well yeah, Vec::reserve has no error (visible in its signature)

Tim Diekmann (Jan 23 2020 at 12:24, on Zulip):

Yes, but I meant no errors at all, so the allocator cannot error either

Tim Diekmann (Jan 23 2020 at 12:25, on Zulip):

Vec::try_reserve is fallible, Vec::reserve is infallible

This is the game changer for me ;)

Simon Sapin (Jan 23 2020 at 12:26, on Zulip):

Yes, but I meant no errors at all, so the allocator cannot error either

Like you said, that doesn’t exist

Tim Diekmann (Jan 23 2020 at 12:26, on Zulip):

As everyone (in this wg) knows, that reserve may abort on allocation failure.

Tim Diekmann (Jan 23 2020 at 12:27, on Zulip):

So type Error = ! could never exist in AllocRef

Simon Sapin (Jan 23 2020 at 12:28, on Zulip):

https://doc.rust-lang.org/std/alloc/trait.GlobalAlloc.html#tymethod.alloc is fallible through returning a nullable pointer. I think it would be very reasonable to add a convenience infallible API like fn(alloc: &impl GlobalAlloc, layout: Layout) -> NonNull<u8> { NonNull::new(alloc.alloc(layout)).unwrap_or_else(|| std::alloc::handle_alloc_error(layout)) }

Simon Sapin (Jan 23 2020 at 12:28, on Zulip):

And similar for other methods

Simon Sapin (Jan 23 2020 at 12:28, on Zulip):

Or maybe a generic wrapper struct that provides infallible methods

Tim Diekmann (Jan 23 2020 at 12:31, on Zulip):

The problem here is the naming of the function. The term try is already established in the Rust community, but try_alloc matches the fallible one, which we cannot change, as GlobalAlloc is stabilized

Tim Diekmann (Jan 23 2020 at 12:31, on Zulip):

Thinks like alloc_infallible sounds weird IMO

Simon Sapin (Jan 23 2020 at 12:32, on Zulip):

A Result with an associated error type is no the only option, and I feel it’s not a very good one. Encoding fallibility in the type system has a convenience cost (you need that unwrap or into_ok call)

Simon Sapin (Jan 23 2020 at 12:34, on Zulip):

Result<_, !>::unwrap() is a noop while Result<_, AllocErr>::unwrap() requires a branch. This matters in tight loops, where those allocator could be used (e.g. in game development).

I’d also dispute that claim without profiling a real-world program. My guess would be that the cost of that branch is often insignificant compared to everything else for example a game does

Tim Diekmann (Jan 23 2020 at 12:34, on Zulip):

An associated error type could only bubble more error infos to the user, but that wouldn't change the way the errors have to be handled, so I think those issues are not related

Simon Sapin (Jan 23 2020 at 12:36, on Zulip):

For the global allocator (as opposed to adding an allocator type parameter to container types), naming is the least of your worries. std::alloc::Global is “connected” to #[global_allocator] at link-time, so you can’t have an associated type or generics or anything type-level

Tim Diekmann (Jan 23 2020 at 12:36, on Zulip):

I’d also dispute that claim without profiling a real-world program [...]

Well, that isn't a thing anyway then, as I know the terminology of "infallible" and "fallible" in the context of allocations now.

Tim Diekmann (Jan 23 2020 at 12:37, on Zulip):

As literal infallible allocations does not exist.

An allocator implementation should not decide, on how it's errors are handled.

Mike Hommey (Jan 24 2020 at 10:44, on Zulip):

The way I see infallibility in allocators is: "if it returns, it allocated"

Mike Hommey (Jan 24 2020 at 10:44, on Zulip):

as in "if it returns at all"

John Ericson (Jan 24 2020 at 15:35, on Zulip):

"mandatory" vs "discressionary" might be better

John Ericson (Jan 24 2020 at 15:36, on Zulip):

Regardless of the name I do agree with the changes that's been discussed, and yes they do use Result.

Tim Diekmann (Jan 25 2020 at 00:39, on Zulip):

We rename Alloc to AllocRef because types that implement Alloc are a reference, smart pointer, or ZSTs. This question is another reason, why this rename is a good idea

Tim Diekmann (Jan 25 2020 at 00:41, on Zulip):

It is not possible to have an allocator like MyAlloc([u8; N]), that owns the memory and also implements Alloc. That would mean, that moving a Vec<T, MyAlloc> would need to correct the internal pointer, which is not possible. You have to encapsule the lifetime yourself by impl AllocRef for &(mut) MyAllocator

Tim Diekmann (Jan 25 2020 at 00:41, on Zulip):

Wrong topic...

Last update: Feb 25 2020 at 02:05UTC