Module mem

Memory management internals for the bucket array

The solver needs sparse arrays of sorting buckets as temporary space. To minimize peak memory usage, we need to dynamically reallocate portions of that space between usages. A naive solution could use a separate Vec for each array of bucket keys/values. A quick benchmark confirms that this is between 2% and 10% worse than if the solver could use a single block of memory with predetermined packed layout.

Using a static layout presents some challenges in initialization, since the entire struct is now too large to fit on the stack reliably. Creating an instance using Box::new() would cause a stack overflow.

We can solve several of these problems by orienting the data structure around MaybeUninit memory: No initialization needed, we can easily switch between space layouts using a union without risk of transmuting live values, and we avoid an additional redundant zeroing of memory.

This module provides a trait, Uninit, for memory that we can safely treat as uninitialized when it isn’t being used. We track that use via a mutable reference, so that gives us mutually exclusive access enforced at compile-time.

That uninitialized memory can be used to build backing layouts that are made from instances of BucketArrayMemory. The whole backing layout is then instantiated using freshly allocated uninitialized memory.

A BucketArrayMemory can be temporarily, using a mutable reference, wrapped into a BucketArray or half of a BucketArrayPair. Internally, a BucketState tracks how many items are in each bucket. The only supported write operation is appending to an underfull bucket. Once initialized by such a write, bucket items may be randomly accessed via the methods on the BucketArray or BucketArrayPair.

It’s critical for memory safety that we only read from a MaybeUninit that has definitely been initialized. The static lifetimes of the mutable reference and our counts array ensure we always start out with zeroed counts and fully assumed-uninitialized memory. Our write method must be certain to never increment the counter without actually writing to the MaybeUninit. See BucketState::insert.

Structs

BucketArray

Concrete binding between one BucketState and one BucketArrayMemory

BucketArrayMemory

Backing memory for a single key or value bucket array

BucketArrayPair

Concrete binding between one BucketState and a pair of BucketArrayMemory

BucketState 🔒

Common implementation for key/value and value-only bucket arrays

Traits

Count

Types that can be used as a count of items in a bucket

Uninit

Marker trait for types that are normally assumed uninitialized