How would you support custom allocators?

[johnrrowe]

This is a similar question to https://github.com/orgs/hylo-lang/discussions/736 but specifically about custom allocators. The general pattern in languages like C++ and Rust is to store a pointer/reference to the allocator, but that breaks MVS. I also don't think it always makes sense for a collection to own its allocator. For example, you might want to use a bump allocator to pack a bunch of heterogeneous objects together in memory. Is there an ergonomic solution to this that doesn't sacrifice MVS? I really like the design of Hylo, so I'm hoping there is. An obvious but undesirable solution would be an array of union objects, but that has multiple inefficiencies.

[dabrahams]

Thanks for asking!

Except for global threadsafe shared resources like the system's malloc allocator, an allocator is a container, a whole, and the things allocated within it are its parts. They can be projected out of the allocator. That's the only way to maintain MVS. It many not even make sense to think of the allocator as an allocator; you might think of it as a heterogeneous container. The exact way that memory is acquired by the allocator and apportioned to the allocator's parts is of course dependent on the allocation strategy (arrays of raw bytes can work, with some bookkeeping). The illusion presented by C++ that there is no whole-part relationship between the allocator and things stored in it cannot be upheld, so the ergonomics will be different. And that's about as much as I know for sure at this point.

Whether it's reasonable for vocabulary collection types to be able to expose borrowed memory, or whether you need a separate family of collection types that can be projected out of allocators, is an open question. Implicits (implicit function arguments) may have a role to play in keeping usage ergonomic also; they can help hide the passing-around of context. But knowing more is going to take some experimentation, so I encourage you to dig into the problems yourself and see what you come up with.

[johnrrowe]

Thanks for your response. What you said makes sense, and I think I agree that the usual idea of an allocator implies a "references" relationship, not a whole-part. I haven't taken the time to use Hylo myself, but I definitely plan to explore these ideas further. The most straightforward translation of an allocator API I thought of looks like this (using Rust because I'm not very familiar with Hylo syntax). An allocator would be a heterogeneous container that gives access to its parts through a handle, where project would be a subscript in Hylo.

trait Allocator {
    // This probably needs to be opaque to users. Wouldn't want the internals of it to be modifiable
    type Handle<T>;

    fn alloc<T, F: FnOnce() -> T>(&mut self, construct: F) -> Self::Handle<T>;

    // SAFETY: Handle must have been allocated by the same instance. Value being projected must still be valid.
    unsafe fn project<'s, T>(&'s self, h: &Self::Handle<T>) -> &'s T;
    
    // SAFETY: Handle must have been allocated by the same instance. Handle must not have been copied
    // otherwise potential double free/use after free. Nothing is forcing the handle to be freed, so potential leaks.  
    unsafe fn free<T>(&mut self, h: Self::Handle<T>);
}

I don't like that this API is inherently unsafe. Some improvements that I think are theoretically possible:

1. Require Handle to be non-copyable (not sure if that's expressible in Rust traits). I'm not sure if Hylo has support for "true" linear types in the sense that the compiler can force you to sink a value for "final destruction". Not sure what destructors look like in Hylo, if they exist, but I don't think that would be viable because Handle's destructor would need access to the allocator.
2. A way for the compiler to associate a Handle to a particular instance of an allocator. I came across an interesting Rust proposal based on static path-dependent types, which I think is inspired by Scala. I've never used them, so I don't fully understand how they work. But I think this API needs something like this to be safe. Here's the paper | Here's a video by the author

All these hoops feel like I'm trying to reinvent reference semantics with extra steps, but at least things are more explicit than they would be with first class references, i.e. no spooky action. But to some extent, I think this is kind of required in MVS?

I think statically enforced path-dependent types are an interesting concept, but I'm not sure if Hylo would find their complexity/ergonomics acceptable. I could imagine them being as complicated as Rust's lifetime annotations. However, I think they're worth considering because they would be useful beyond allocators. Anytime you have a context that produces handles that are tied to a specific instance of said context, I think you could use path-dependent types to ensure that at compile time. For example, when using the adjacency list representation of a graph, you could ensure your node indices are used with the correct graph.

Edit: Looks like people have actually implemented a similar idea in Rust by encoding things with lifetime parameters Crate | Video

[kyouko-taiga]

Require Handle to be non-copyable

Hylo has a true linear type system so you can make the handles non-copyable. You can also require that the only type knowing how to destroy a handle is the allocator. That's because a "destructor" is simply a method that sinks an object and can consume its contents.

You would need to gather and collect all handles before you destroy the allocator itself, though.

A way for the compiler to associate a handle with a particular instance of the allocator

We would need Scala-like path-dependent types for that, indeed. However, we have concluded they didn't justify the complexity they bring to the language the last time we discussed them.

Having handles coming from multiple allocators of the same type in scope sounds like a very particular setup, though. I haven't personally encountered realistic examples of the kind. Further I became used to deal with positions into collections that do not "know" the collection instance from which they come (and neither does the compiler). That is essentially the same setup as the one you describe with allocators, except that the "handles" can be destroyed anywhere.

I think that in general we should strive for situations where the positions/handles of type T.X we use in one scope all come from a single instance of a container/allocator of type T. That way we can write simpler APIs and even use Scala-like implicit parameters to provide the familiar dotted property access.

[johnrrowe]

Thanks for filling me in. I think I agree that it's a niche scenario, so path-dependent types seem like overkill. I was just thinking out loud and exploring how things do or don't translate to MVS is helping me understand it more. My question about linear types in Hylo was more about whether it's a compile error not to consume certain types.

[dabrahams]

I'm having trouble understanding this:

I don't like that this API is inherently unsafe.

I guess one way to understand it is that the API can be implemented by a model having only safe operations. But in a generic context, it seems to me it's obviously unsafe, because project and free can be implemented by unsafe operations. What am I missing?

[johnrrowe]

I didn't phrase that well. What I meant is that there are certain allocators where it would be UB to use a handle created by one instance with another instance. So you either have to make this API unsafe or exclude the allocators where the API would be unsafe. For example

struct BumpAllocator {
    bytes: Vec<u8>
}

struct BumpHandle<T> {
    offset: usize,
    m: std::marker::PhantomData<T>, // just here because generic param must be used, 0 size
}

impl Allocator for BumpAllocator {
    type Handle<T> = BumpHandle<T>;

    // ignoring alignment
    fn alloc<T, F: FnOnce() -> T>(&mut self, construct: F) -> Self::Handle<T> {
        let final_len = self.bytes.len() + std::mem::size_of::<T>();

        if final_len >= self.bytes.capacity() {
            self.bytes.reserve(final_len - self.bytes.capacity())
        }

        unsafe {
            let object_start = self.bytes.as_mut_ptr().add(final_len);
            std::ptr::write(object_start.cast::<T>(), construct());
            self.bytes.set_len(final_len)
        }

        Handle {
            offset: final_len,
            p: Default::default(),
        }
    }

    unsafe fn project<'s, T>(&'s self, h: &Self::Handle<T>) -> &'s T {
        unsafe { &*self.bytes.as_ptr().add(h.offset).cast::<T>() }
    }

    // Only deallocates memory at the end of the allocator's life, i.e. calling free only drops the object
    unsafe fn free<T>(&mut self, h: Self::Handle<T>) {
        unsafe { self.bytes.as_mut_ptr().add(h.offset).cast::<T>().drop_in_place() }
    }
}

A handle created by instance A likely does not refer to a valid object of the same type in instance B, so using project and free would be unsafe. With extra bookkeeping, you could probably make it safe if you're allowed to throw. With path-dependent types, this usage would be a compile error, making BumpAllocator safe to use even without extra bookkeeping (assuming BumpHandle is a linear type)

[dabrahams]

You don't need permission to throw to make something safe, if throwing is possible. That means there's a suitable dynamic check for the precondition violation, and you can terminate. Throwing on precondition violations is inappropriate anyway. Yes, path-dependent types can solve the particular problem that values are paired up inappropriately, but I think there are lots of other potential safety problems in the area of allocators.

[johnrrowe]

My fault. I meant something more like terminating or panicking rather than throwing an error that would be handled. I think you can eliminate (almost?) all unsafe client usage with linear, path-dependent types, but there would still be safety concerns when implementing. I think this API breaks down when considering what an inout projection would need to do. If you alloc'd a collection and inside the inout projection you appended to the collection, you might have to realloc, but I don't know how the append function would know what allocator to realloc with.