Is custom allocators the right abstraction?

libs
88

I was experimenting with my own PoC for the storage API and I found some things I wanted to share, mention and discuss here.

As I'm not a native english speaker, fell free to ask me if you can't understand some parts! :wink:

So these are what I have thought about:

  • The distinction between Single* and Multi* storage isn't really needed. In general, Storage stores information (or inline storage) shared across all allocations and Handle stores information about one specific allocation. But for Single* storages, this distinction is unnecessary because there is no shared information (or shared inline storage) at all. We can actually store everything in handle which would allow that there are many alive handles at any time - which would in turn erase the need for Single* storage.

    For better understanding: Inline Single* storages are implemented like this:

    Storage: inline storage
Handle: some metadata

    And there is no reason why this cannot be implemented this way:

    Storage: ()
Handle: inline storage + some metadata

    This way, the storage can allocate many handles and there is no additional overhead when compared to the original.

    You can see an example of this here (Ignore that the trait definition is somewhat different from the traits in storage-poc).

  • There are some problems with the current typed Storage API:

    • compatibility with future custom DST proposals: To allocate DST using the typed API, one of the following conditions must be true:

      • There must be a Sized counterpart of the DST type (which you can CoerceUnsized).
      • You must be able to get both a valid pointer metadata (before initialising the memory) and the layout from the pointer metadata.

      Both conditions can be violated when custom DSTs comes in.

    • dynamic allocations: There are some cases where you want to allocate runtime-sized memory for example like language interpreter, game engines, data driven systems, etc. This is not possible when the API is typed.

    So the underlying problem is that the current typed Storage does not allow runtime-sized allocations. Using Allocator instead of Storage is also not a real solution because Allocator is less powerful than Storage (you can't implement things like shared-memory allocations, auto-defragmentations or inlined allocations with current Allocator).

    Currently, I can see two options to solve this problem:

    • Using Layout for the Storage API instead of type parameter T

      This way, you can allocate runtime-sized memories at cost of more error-prone API (because it is untyped) and slightly worse performance (because you have to pass Layout around every time).

    • Building the Allocator API also around custom handles

      This way, Allocator trait becomes as powerful as Storage trait at cost of less ergonomic API.

    Edit: When I think about it now, there are actually no real differences between this two options as "untyped Storage" is essentially the same as "handle based Allocator". I'm even not sure whether there must be two separate traits for this.

    Indeed, we could just have one untyped, handle based allocation trait and maybe additionally a fully-typed, more ergonomic and less error-prone API implemented on top of that if we want to.

  • Currently, we can do nothing with an allocated handle; we need to first acquire the underlying pointer (which may change at any time) to do operations with the memory itself.

    One problem arises with this approach: We can't use storages in const context.

    We can't use pointers in const context and it is unlikely that this will change. This means that we can't do things like const MAP: HashMap<String, u32, InlineStorage> = { ... } although it can be done in compile-time.

    (This point isn't really problematic right now as "const collections" are not the main focus of this proposal. But we will have to decide whether to use pointers or some other approach before stabilisation; because after that, we cannot change it anymore.)

Maybe these questions were not needed right now because the current storage proposal is only at the PoC stage; but I think the earlier we raise up unresolved questions, the better we can answer those.

@matthieum: What do you think about this?

As a side note, thanks for this awesome proposal and working on this kind of stuffs!

3 Likes