Change AllocRef to take &self

[Amanieu]

This has several advantages:

• AllocRef can now be used by concurrent (lock-free) data structures which only have &self operations. Currently the allocator would need to be wrapped in a mutex even if the allocator is thread-safe.
• Allocators can directly expose whether they are thread-safe or not with Sync. This bound is inherited by data structures using an allocator: a lock-free queue would only be Sync if its allocator is Sync.
• We can define a blanket implementation of AllocRef for all types implementing GlobalAlloc. This would allow us to change #[global_allocator] to require AllocRef instead of GlobalAlloc. This is not possible if AllocRef methods take &mut self.

[TimDiekmann]

I find the first point in particular very important. I see the second point as a side effect, because data structures that accept &mut self are not affected by it, but together with point 1 it is still very interesting! I'm sure we could get #[global_allocator] work somehow with AllocRef but implementing it this way is by far the most intuitive and easiest solution.

How does the last point plays together with #43? System and GlobalAlloc are stable, impl<A: GlobalAlloc> AllocRef for A would prohibit impl AllocRef for System. Is specialization an option here?

[Amanieu]

We remove the existing impl GlobalAlloc for System. We add impl AllocRef for System. The blanket impl will take care of providing GlobalAlloc for System via the AllocRef impl.

[TimDiekmann]

The blanket impl will take care of providing GlobalAlloc for System via the AllocRef impl.

I thought we impl<A: GlobalAlloc> AllocRef for A, not impl<A: AllocRef> GlobalAlloc for A?

[Amanieu]

Ah, you're right, I got mixed up. I think we can make this work with specialization, but I'll need to double-check.

[TimDiekmann]

#![feature(specialization)]

trait GlobalAlloc {
    fn global_alloc(&self) {}
}
trait AllocRef {
    fn alloc_ref(&self) {}
}

impl<A: GlobalAlloc> AllocRef for A {}

struct System;
impl GlobalAlloc for System {}

impl AllocRef for System {}

fn main() {
    System.global_alloc();
    System.alloc_ref();
}

This works, even without the default keyword, but I'm not that deep into specialization. However it fails to compile without #![feature(specialization]

EDIT: Actually this is very nice, as we can "specialize" System implementation if there is a performance gain, otherwise we can rely on the blanket implementation.

[RustyYato]

This works because there is a default implementation in the trait, it doesn't forward the from AllocRef to GlobalAlloc.

However, this works even with the sound sub-set of specialization. (min_specialization)

#![feature(min_specialization)]

trait GlobalAlloc {
    fn global_alloc(&self); // no default implementation in the trait
}
trait AllocRef {
    fn alloc_ref(&self); // no default implementation in the trait
}

impl<A: GlobalAlloc> AllocRef for A {
    default fn alloc_ref(&self) { A::global_alloc(self) }
}

struct System;
impl GlobalAlloc for System {
    fn global_alloc(&self) {}
}

impl AllocRef for System {}

fn main() {
    System.global_alloc();
    System.alloc_ref();
}

[TimDiekmann]

• We can define a blanket implementation of AllocRef for all types implementing GlobalAlloc. This would allow us to change #[global_allocator] to require AllocRef instead of GlobalAlloc. This is not possible if AllocRef methods take &mut self.

I think you mixed this up as well, as we call &self from &mut self:

unsafe impl<A: GlobalAlloc> AllocRef for A {
    fn alloc(&mut self, layout: Layout, init: AllocInit) -> Result<MemoryBlock, AllocErr> {
         // ZST checks etc.
        let raw_ptr = match init {
            AllocInit::Uninitialized => GlobalAlloc::alloc(self, layout), // Takes &self
            AllocInit::Zeroed => GlobalAlloc::alloc_zeroed(self, layout), // Takes &self
        };
        // error handling
    }
   // ...
}

However, this works even with the sound sub-set of specialization. (min_specialization)

Good to know it's working somehow 🙂

[TimDiekmann]

• AllocRef can now be used by concurrent (lock-free) data structures which only have &self operations. Currently the allocator would need to be wrapped in a mutex even if the allocator is thread-safe.

This is not the most elegant solution, but it's working:

struct MyAlloc;
unsafe impl AllocRef for &MyAlloc {
    fn alloc(&mut self, _: Layout, _: AllocInit) -> Result<MemoryBlock, AllocErr> {
        println!("alloc");
        Err(AllocErr)
    }
    unsafe fn dealloc(&mut self, _: NonNull<u8>, _: Layout) {}
}

struct DataStructure<A> {
    alloc: A,
}

impl<A> DataStructure<A>
where
    for<'a> &'a A: AllocRef,
{
    fn use_alloc(&self) {
        (&self.alloc).alloc(Layout::new::<u32>(), AllocInit::Zeroed);
    }
}

fn main() {
    let s = DataStructure { alloc: MyAlloc };
    s.use_alloc();
}

Playground

[Wodann]

I remembered a prior discussion about moving away from &mut self that resulted in the conclusion that &mut self is required

[TimDiekmann]

I remembered a prior discussion about moving away from &mut self that resulted in the conclusion that &mut self is required

At least it is required to stay at a reference level, it's not necessarily required to stick the mut.

---

I like to summarize the (dis)advantages for &self and &mut self to have a full list at one place (no specific order, non-exhaustive).

	&self	&mut self
Changing the internal state	requires some sort of internal mutability (either Sync or !Sync), atomic ordering may be tricky	trivial
Multithreading	Depends on internal mutability type	implicit possible
Usage on data structures taking &self	trivial	requires AllocRef to be implemented on &MyAlloc and a for<'a> &'a A bound
Sharing (e.g. via Rc and Arc)	implicit and explicit (by_ref) possible	requires AllocRef to be implemented on &MyAlloc
Performance of unshared allocators used repeatedly in a linear fashion	May introduce overhead due to internal mutability	No impact for unshared allocators

I think both types are more or less equal. For &self one have to choose the type of internal mutability in any case, which might be tricky. This probably results in a version using Cell for !Sync and in a version using atomics for Sync. For sharing &mut self allocators this also applies, but for unshared allocators the &mut self variant implementation is straight forward. However the ergonomic of &MyAlloc might be unintuitive.

To conclude: We need internal mutability, we only have to decide when it is required:

• &self: Required when internal states is modified
• &mut self: Required when sharing

[SimonSapin]

• AllocRef can now be used by concurrent (lock-free) data structures which only have &self operations.

Isn’t this already possibly through impl AllocRef for &MyLockFreeAllocator, impl AllocRef for Arc<MyLockFreeAllocator> etc?

I thought that was the point of naming the trait AllocRef rather than Alloc.