Add default implementation for allocating zero-sized types (or ZSTs)

[Wodann]

After discussion in issue #16, I propose:

1. Adding a default implementation for allocation of ZSTs
2. Splitting alloc into two separate functions for allocating ZSTs and sized types.

The former design decision is inspired by a well-defined approach to allocating ZSTs, that reduces the workload for trait implementors.

The latter design decision is grounded in Rust's philosophy of providing zero-cost abstractions. The if layout.size() == 0 branch in alloc would impose a performance penalty for runtime variable allocations. Hence, we offer the ability to make bare metal calls to alloc_sized and alloc_zero_sized_type for performant use cases.

trait AllocRef {
    fn alloc_sized_type(self, layout: NonZeroLayout) -> Result<NonNull<u8>, AllocErr>;

    #[inline(always)]
    fn alloc(self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
        if layout.size() == 0 {
             // We want to use NonNull::dangling here, but that function uses mem::align_of::<T>
             // internally. For our use-case we cannot call dangling::<T>, since we are not generic
             // over T; we only have access to the Layout of T. Instead we re-implement the
             // functionality here.
             //
             // See https://github.com/rust-lang/rust/blob/9966af3/src/libcore/ptr/non_null.rs#L70
             // for the reference implementation.
             let ptr = align as *mut u8;
             Ok(unsafe { NonNull::new_unchecked(ptr) })
        } else {
             self.alloc_sized_type(unsafe { NonZeroLayout::from_layout_unchecked(layout) })
        }
    }
}

Design questions
If we want to make a data-driven decision, we could run benchmarks to determine the actual cost of the additional branch on runtime variable allocations.

[TimDiekmann]

Thanks for summing this up!
NonZeroLayout will then be defined as in alloc-wg + from_layout_unchecked?

[JelteF]

Looks great overal. Some small remarks/bikeshedding:

1. alloc should return a Result (or do something with the errors)
2. alloc_zero_sized_type naming should be consistent in some way with alloc_sized, i.e. both should have type or none should have type.
3. Maybe it makes more sense to give alloc_zero_sized_type a Layout too for consistency between the different methods.
4. alloc_zero_sized_type could be made safe if we add a ZeroLayout type or an Alignment type (which is always power of 2). If we don't do this, it's probably best to suffix it with _unchecked for consistency with Layout and the possibility to add a checked version.
5. NonNull::new_unchecked(ptr) should be wrapped in Ok(...)

[Wodann]

Thanks for summing this up!
NonZeroLayout will then be defined as in alloc-wg + from_layout_unchecked?

Indeed

[Wodann]

@JelteF thanks for pointing those out. I fixed 1, 2, and 5.

3. alloc_zero_sized_type naming should be consistent in some way with alloc_sized, i.e. both should have type or none should have type.

It seems redundant to pass unnecessary information. I'd go for the minimal API.

4. alloc_zero_sized_type could be made safe if we add a ZeroLayout type or an Alignment type (which is always power of 2). If we don't do this, it's probably best to suffix it with _unchecked for consistency with Layout and the possibility to add a checked version.

We could propose a change to Layout to store the power of two k, but then you'd always need to calculate the alignment on retrieval (i.e. 2^k)

[JelteF]

After considering some more names of the methods I think I prefer alloc_zero and alloc_non_zero. Since there's no type in the API, and a ZST is a Sized type the size is simply 0.

It seems redundant to pass unnecessary information. I'd go for the minimal API.

Yeah that makes sense indeed.

We could propose a change to Layout to store the power of two k, but then you'd always need to calculate the alignment on retrieval (i.e. 2^k)

I think that's not worth it indeed. So in that case I think it makes sense to rename the method to alloc_zero_unchecked, to stay consistent with layout. And possibly add alloc_zero, which checks align.is_power_of_two() before calling alloc_zero_unchecked.

[Amanieu]

I would prefer if the "default" alloc method supports every type of input, and you have to specifically opt-in to an unsafe alloc_nonempty variant when you are sure that you are not allocating a ZST.

Also for the naming, I feel that anything with zero in the name is a bad idea, since it is likely to be confused with zero-initialized allocation. Hence my choice of nonempty.

Finally, I'm still a bit hesitant on this change. While this does help allocators that don't support ZST allocation by providing a default implementation of that methods, it doubles the work for allocators that do support ZST allocation: now they will need to implement both alloc and alloc_nonempty and have one call the other.

[JelteF]

I would prefer if the "default" alloc method supports every type of input, and you have to specifically opt-in to an unsafe alloc_nonempty variant when you are sure that you are not allocating a ZST.

This is the case in this proposal "alloc" supports both. The only difference in what you describe is that alloc_nonempty is also safe.

Also for the naming, I feel that anything with zero in the name is a bad idea, since it is likely to be confused with zero-initialized allocation. Hence my choice of nonempty.

Good catch, completely agree.

Finally, I'm still a bit hesitant on this change. While this does help allocators that don't support ZST allocation by providing a default implementation of that methods, it doubles the work for allocators that do support ZST allocation: now they will need to implement both alloc and alloc_nonempty and have one call the other.

I think "doubling" effort is a bit of exaggeration when talking about forwarding a call. I understand what you mean though. However, I don't really see a way around it, which also avoids the problem of requiring a branch when allocating using an allocator that does not support it empty allocations.

[JelteF]

I have one other question. Do we really need the alloc_zero_sized_type method. I don't really see a reason why anyone would call that instead of the normal alloc. If so, we can simply inline it in the default alloc implementation.

[Wodann]

Also for the naming, I feel that anything with zero in the name is a bad idea, since it is likely to be confused with zero-initialized allocation. Hence my choice of nonempty.

That's a good point. I am still thinking of other potential names, because empty types also exist in Rust..

Finally, I'm still a bit hesitant on this change. While this does help allocators that don't support ZST allocation by providing a default implementation of that methods, it doubles the work for allocators that do support ZST allocation: now they will need to implement both alloc and alloc_nonempty and have one call the other.

I see what you are getting at. I'm not sure at present whether a better solution that would minimize workload in both cases is possible. As I mentioned, in Rust there is only really one requirement for allocating a ZST (i.e. it must be aligned). As such, it is unlikely that someone would want to provide an alternative implementation for alloc_zst, even if the allocator does support allocation of ZSTs. The only cases where this might be, is for external APIs (e.g. a system allocator). If we cannot provide a cleaner solution, then the question becomes "which use case is more common/takes priority?"

I have one other question. Do we really need the alloc_zero_sized_type method. I don't really see a reason why anyone would call that instead of the normal alloc. If so, we can simply inline it in the default alloc implementation.

Yes, I think it could actually be incorporated into alloc, as you said.

[TimDiekmann]

How would you implement realloc and dealloc, if the allocator is not supporting ZSTs? align_of<T>() may return a valid address to an allocated memory block.

[CAD97]

I have another potential proposal:

alloc handles any Layout input (including zero sized allocations). But rather than be the default implemented method that forwards to alloc_[non]empty, those methods are defaulted to forward to alloc.

This means that the minimum work for allocators that do inherently support zero sized allocation is just to implement alloc. For handles to allocators that don't transparently handle zero sized allocation, they do need to handle the zero sized case (but this is to be expected). We can even provide, say, Layout::dangling<T>() -> ptr::NonNull<T> to make this just a call to that function after the check for zero size.

For allocators that have an extra cost associated with checking for zero sized layouts, we can still provide a version that doesn't allow zero size to omit that check. It would just default to calling the version that allows zero sized layouts, but allow for the more optimizable path to be used.

So to be somewhat concrete, my proposal would be roughly

unsafe trait AllocRef {
    type Error;
    fn alloc(self, layout: Layout) -> Result<ptr::NonNull<u8>, Self::Error>;

    fn alloc_nonzero(self, layout: NonZeroLayout) -> Result<ptr::NonNull<u8>, Self::Error> {
        self.alloc(layout.into())
    }

    // all the other provided methods
}

(Modulo exact naming ofc)

Though I definitely am sympathetic to the need to make allocation as cheap/predictable as possible, I think we can do so while still providing a simpler edge-case-handling default API for when it's not needed. The pattern of providing specialized methods that default are impled as the generally applicable one, but then optimized implementations impl the generally applicable one by delegating to the specialized ones is already a decently common pattern that we can use here.

I definitely need to take some time to catch up on wg-alloc though because I have developed some Opinions that apparently aren't represented yet.

[CAD97]

@TimDiekmann as for r/dealloc, remember that these take Layout arguments. So you'd do the same thing there as for alloc: check to see if the size is 0 and handle it if the underlying allocator doesn't. We'd probably want to provide the same NonZeroLayout variants of these methods to allow cases to avoid the cost of that check on those methods as well.