Git Product home page Git Product logo

storage-poc's Introduction

storage-poc aims at exploring the usage of custom Storages, rather than custom Allocators.

Goals

This is a Proof-of-Concept aiming at:

  • Demonstrating the technical feasibility.
  • Showcasing the usage of storages for various collections, with different requirements.
  • Sketching out a potential API.

This experiment does not intend to provide a production-ready solution.

Why not Allocators?

The currently proposed API for allocators is centered around NonNull, that is a pointer.

Creating a Box based on a custom allocator means storing the pointer within the Box. If the allocator were to ever move, the pointer within the Box would become dangling.

This limitation prevents storing the content of the Box, and other collections, inline. And there are many benefits to doing so:

  • Imagine returning a Box<dyn Future<_>, InlineStorage>: abstract type, dynamically dispatched, without memory allocation.
  • Imagine storing Box<dyn FnOnce(), InlineStorage>: you can build a task queue, with no memory allocation in sight.
  • Imagine creating a const LOOKUP: BTreeMap<K, V, InlineStorage> = /**/;: no memory allocation, hence const able.

Abstracting away pointers may even allow storing those collections in shared memory.

Interested? Continue reading!

How to navigate?

The repository contains 3 parts:

  • traits.rs sketches out the API of the necessary storage traits.
  • collections sketches out how to adapt a few known collections with disparate needs to demonstrate the usage of the traits, in practice.
  • The other modules are implementations of the traits:
    • allocator.rs implementations simply adapt an Allocator.
    • inline.rs implementations store everything inline.
    • alternative.rs combines 2 storages, either of which is active at the moment. It is used to implement the small.rs family of storages.
    • fallback.rs combines 2 storages, using both simultaneously, with a preference for the first -- which should be cheaper.

What is the API?

The traits.rs defines an API around 2 axes:

  • Single vs Multi: whether the storage allocates a single item at a time, or allows juggling multiple items.
  • Element vs Range: whether the storage allocates a single element at a time, or allocates a range of elements.

The API was created to be higher-level than the Allocator API. Being higher-level makes it easier to use, and allows optimizations in the implementation.

The SingleElementStorage is (stripped down):

pub trait SingleElementStorage : ElementStorage {
    fn create<T: Pointee>(&mut self, value: T) -> Result<Self::Handle<T>, T>;

    fn allocate<T: ?Sized + Pointee>(&mut self, meta: T::MetaData) -> Result<Self::Handle<T>, AllocError>;
}

pub trait ElementStorage {
    type Handle<T: ?Sized + Pointee> : Clone + Copy;

    unsafe fn destroy<T: ?Sized + Pointee>(&mut self, handle: Self::Handle<T>);

    unsafe fn deallocate<T: ?Sized + Pointee>(&mut self, handle: Self::Handle<T>);

    unsafe fn get<T: ?Sized + Pointee>(&self, handle: Self::Handle<T>) -> NonNull<T>;
}

The Handle<T> is the magic allowing inline storage: they are something to be converted to an ephemeral pointer via storage.get(handle), but not a pointer themselves, and therefore supports relocations of the underlying storage.

From there, the lifecyle is rather obvious: create, get a few times, and finally destroy.

Note: the Pointee trait comes from RFC2580, as implemented in rfc2580, it's essentially a trait to split a pointer into pointer-to-data and meta-data and put it back together later.

And the SingleRangeStorage is (stripped down):

pub trait SingleRangeStorage : RangeStorage {
    fn allocate<T>(&mut self, capacity: Self::Capacity) -> Result<Self::Handle<T>, AllocError>;
}

pub trait RangeStorage {
    type Handle<T> : Clone + Copy;

    type Capacity : Capacity;

    fn maximum_capacity<T>(&self) -> Self::Capacity;

    unsafe fn deallocate<T>(&mut self, handle: Self::Handle<T>);

    unsafe fn get<T>(&self, handle: Self::Handle<T>) -> NonNull<[MaybeUninit<T>]>;

    unsafe fn try_grow<T>(&mut self, _handle: Self::Handle<T>, _new_capacity: Self::Capacity) -> Result<Self::Handle<T>, AllocError> {
        Err(AllocError)
    }

    unsafe fn try_shrink<T>(&mut self, _handle: Self::Handle<T>, _new_capacity: Self::Capacity) -> Result<Self::Handle<T>, AllocError> {
        Err(AllocError)
    }
}

Once again a Handle<T> to allow inline storage, and this time a Capacity to allow using a smaller type than usize when possible.

The trait is lower-level, as it makes no assumption about which portions of the range are initialized or not, leaving it up to the caller. This is necessary since Vec and VecDeque have different invariants here.

Can we replace the std collections tomorrow?

There is one blocker currently: the custom Box implementation is not coercible.

CoerceUnsized and Unsize are locked-down, and the custom implementation of RFC2580 therefore cannot implement CoerceUnsized to be able to unsize SizedMetadata<[u8; 3]> into SliceMetadata<[u8]>. This in turn prevents Box from being coercible. Oops.

For the purpose of this Proof-of-Concept, a stand-in coerce method has been added to the ElementStorage trait where the implementation is essentially to go from handle to pointer, let the compiler coerce it, and then go back to handle from there. Then a similar coerce method is implemented on Box, and things just work.

Then, there is the issue that the implementation relies on Generic Associated Types, which are quite unstable, though good enough that the code compiles and runs without issues on nightly... as long as one doesn't try to coerce-unsize the Box. It may be prudent to wait for the go-ahead of the compiler developers before switching any collection.

That's all folks!

And thanks for reading.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.