Design document for a lighter alternative to Vec<Box<T>> for building persistent data structures

Vox.md

Vox: A Vectorised Box

Vox<T> is intended to provide a more performant alternative to constructs such as Vec<Box<T>> where it is desirable to maintain a growable collection of fixed-location heap allocated immutable objects.

The core design decisions for Vox are:

• Owns all of the allocations of type T stored within it.

• Append-only; new T instances can only be appended to the end of a Vox<T>, not inserted at an arbitrary position, moved, or removed.

• Preallocates [NonNull<*mut T>; n] space for the pointers when growing.

• Preallocates [T; n] space for the stored instances of T when growing, where n is max(CACHE_LINE_SIZE / size_of::<T>(), 1) instances.

Optimisation

The use of a custom data type based on the above design decisions allows for a number of low-level optimisations to be made:

• Vox only needs to drop the owned instances of T when it is dropped itself.

• Actual memory storing T instances is stored in contiguous blocks in multiples of the system cache line size.

• No concern is needed for any rearranging or removing contents.

Public API

Listed here is the minimum required set of operations that need to be publicly exposed for a working Vox<T>. Other operations may be provided purely for convenience.

Vox<T>::new() -> Vox<T>

Create and return a new Vox<T> which is ready to appended to.

len() -> usize

Return the current number of T instances in the Vox<T>.

push(T) -> &T

The primary operation for read & write access; appends an instance of T to the end of the Vox<T>, returning an immutable reference to it's persistent location in memory.

Internal API

While there are likely to be further implementation details, those listed here are the minimal set of logical operations which will need to be implemented.

append(T) -> &T

Actual logic to append a new T to the Vox<T>; used along with ensure_free() to implement push(T).

cap() -> usize

Return the total current capacity of the Vox<T>.

drop()

Implementation of Drop trait that correctly drops both the memory used by each T, and the memory used by the array of pointers.

ensure_free()

Ensure that there is free space available to actually append a new T to the Vox<T>.

rem() -> usize

Return the number of new T instances that can be stored at the current capacity of the Vox<T>.