Is custom allocators the right abstraction?

Preface: I renamed acquire/release to allocate/deallocate, to be closer to the Allocator API.


@CAD97 I tried adding support for converting from Box<T, StorageA> to Box<T, StorageB>, and given that T can be !Sized at that point, this required me to add an allocate method to ElementStorage that only takes the meta-data, not the T, so you were spot on regarding this comment.

With regard to the exact hierarchy of traits; I am not sure.

At some point in the discussion I was afraid that each data-structure would require a unique trait API. I'm very happy that I managed to distill down the requirements to end up with the 2x2 matrix (Single vs Multi and Element vs Range). It's entirely possible that further simplification is still available... but I am not sure if it's possible, or even desirable:

  • I don't think that Single vs Multi should be erased:
    • There's a strong semantic difference since Single doesn't keep track of whether it's "occupied" or not. I am slightly uncomfortable smoothing it out.
    • This difference has repercussions on the implementation: Multi requires extra tracking which is just overhead for Single, so a given storage is generally specialized for one or the other anyway -- the only exception being the allocators.
  • Unification of Element vs Range is even more complicated. Differences are:
    • T: ?Sized + Pointee vs T: yet, if considering the range as a single Element, this should work.
    • MaybeUninit: in the case of Range storage. If we change the signature of resolve (gonna steal that name...) to going from Handle<T> to NonNull<MaybeUninit<T>>, then it would be smoothed.
    • type Capacity. This latter is critical, it's how a Vec<u8, inline::SingleRangeStorage<u8, [u8; 31]>> can take only 32 bytes. At the same time, there's no Capacity for Element Storage; it's meaningless.

I can see building a hierarchy like:

  • Storage: Handle<T>, deallocate, and resolve.
    • ElementStorage: destroy convenience method.
      • SingleElementStorage: allocate, and create convenience method.
      • MultiElementStorage: allocate, and create convenience method.
    • RangeStorage: Capacity, try_grow, and try_shrink.
      • SingleRangeStorage: allocate.
      • MultiRangeStorage: allocate.

However I find the Storage trait rather... pointless, on its own? I don't have any usecase that would require it right now, though at a guess resolve may be useful on its own?

Imagining that we paper over the difference between Single and Multi, as uncomfortable as this makes me:

  • Storage: Handle<T>, deallocate, and resolve.
    • ElementStorage: allocate, and for convenience create and destroy.
    • RangeStorage: Capacity, allocate, try_grow, and try_shrink.

And imagining that we're okay asking the user to synthetize a SliceMeta<T> out of thin air just to call allocate:

  • Storage: Handle<T>, allocate, deallocate, and resolve.
    • ElementStorage: convenience create and destroy.
    • RangeStorage: Capacity, try_grow, and try_shrink.

But to reiterate, this seems like shoehorning to me considering that:

  • A given container has very specific requirements on the Single/Multi and Element/Range axes, and only requires one combination.
  • A given storage is tailored to a very specific case on the Single/Multi axis.

So I could see an advantage in carving out a Storage with Handle<T> and resolve. But any further attempt at simplification seems rather artificial for now.


@RustyYato I don't see how to provide Drop:

  1. The storage doesn't keep track of which element is initialized, or not, so doesn't know what to Drop.
  2. The handles would need a mutable reference to the storage to be able to drop, which we can't have if we have multiple handles.
  3. In the case of ranges, only the user knows which elements in the range are initialized or not.

So, I don't see any way to call the destructor of elements because of (3), hence the user would be responsible for that regardless. And I don't see any way to release the memory without extra tracking.

I would say that the Drop wrapper you ask for is going to be called Box, Vec, ... I am not sure there's a good opportunity for an intermediate layer.

1 Like

It doesn't need to Drop the elements, just deallocate the storage if necessary. See RawVec in std for an example.

2 Likes

I am glad we agree that calling Drop on the elements is not possible.

How do you plan on solving the MultiStorage issue that it does not track the multiple allocations?

I only mentioned using Drop for Single*, not Multi*. But given @CAD97's comments I think it would be fine to not use Drop in this case either.