Storage Abstraction Redesign #2

[teryror]

The Storage trait and surrounding machinery, as it exists today, works reasonably well for what it was meant to do: enable the implementation of many of the data structures introduced in coca version 0.3, which the old design just couldn't support. There are several avenues for improvement, though, which I would like to at least explore before the next major release:

• Add support for reallocation.

  • Add an associated method try_with_capacity(cap: usize) -> Result<Self>. This needn't even be a breaking change (though everything else on this list probably will be) - just add a default implementation that always returns Err.

  • Go through all the existing data structures, and make sure they actually try calling that when their storage space runs out.

  • Add two new storage types to make use of this feature: GrowableStorage (or StdStorage?), which should make data structures act like the standard implementations, and SmallStorage (or SsoStorage?), which should be a union of InlineStorage and GrowableStorage, switching between the two as needed. Then add corresponding type aliases for all the data structures. It should be possible to implement both generically over the LayoutSpec.

  • With two new storage types, both of which could support both with_capacity-style constructors (like AllocStorage) and parameterless new constructors (like InlineStorage), it's worth thinking about how to implement these constructors for data structures in a way that's generic over the storage type. It's probably easiest to use the Default trait for the latter, but it'll likely require a new trait to make that work for the former (a marker trait should suffice, given the new Storage::try_with_capacity method).

    This will be nice to have on the implementation side, but will make it even less obvious which constructors are available for which types, which has already been a point of confusion for potential users, even with the current design. It'll be important to document this thoroughly.

• Unify ArenaStorage and SliceStorage.

  There's no real reason for these to actually be different types, both are just unowned memory, binding the client data structure to a given lifetime (so maybe BorrowedStorage or RefStorage?). Combining the two would allow methods like SliceVec::split_and_shrink_to to just work for arena storage, and would also allow us to get rid of a few type aliases. Shrinking the API surface seems good, but it should be thoroughly documented that the combined type isn't just for arena-allocated memory, and can also be constructed from an arbitrary slice.

• Generalize the option_group::Compound trait.

  • The main goal here should be to introduce an equivalent to Vec, with a structure-of-arrays memory layout, which users should be able to operate on like a Vec of tuples, minus the ability to get a slice of tuples, but with the added ability to get columnar slices of the tuple fields. Call this MultiVec, or maybe just SoA.
  • Currently, all non-ArrayLayout storage types use an SoA layout. There's no code abstracting over this, so each data structure using such a layout defines some number of helper functions to get the base pointers of the various arrays, including a lot of duplicate code calculating address offsets. Improving on this shouldn't change anything for users of the crate, but remove some boilerplate code, and make my life slightly easier in the future. If we introduce a new SoALayout or some such, we could provide generic helper methods on that, and replace the existing LayoutSpec implementations with wrappers around it (so as to not bake this layout requirement into the public API).
  • It would be extremely nice to have the ability to derive the Compound trait on structs, so that users could have vectors switch between SoA and AoS layout just by changing the type name; obviously, this would require a separate crate, but would probably be worth it. One minor drawback with this approach: any methods on the Vec-equivalent that refer to any individual column would have to have the column index suffixed to their name, like OptionGroup does; maybe it's better over all to offer a macro (which users should be able to just wrap a struct declaration with) that instead creates a newtype wrapping the Vec-equivalent, but with more readable method names.

• Generalize the alignment markers in the object module.

  It's not clear to me that this would really be needed elsewhere, but for SIMD, it would be nice to at least have vectors with custom alignment guarantees for the array base. This could then be used to provide specialized iterators that are more ergonomic than even the ones offered by most cross-platform SIMD crates. Bonus points if this works for each column in the SoA vectors from the previous point.