Columned: Single, Contiguous, Allocation for Multiple Objects

A single, contiguous allocation for multiple objects that live the same lifetimes. This reduces multiple allocations to a single one. This may improve performance, as multiple memory allocations may require multiple slow system calls. Further, this may alleviate memory fragmentation.

Working Principle

Guard manages a contiguous allocation of memory. Each object has a pointer to this contiguous allocation. The following figure illustrates the working principle.

       Guard
       +--------+--------+
       | 0x0123 |   ...  |
       +--------+--------+
        ptr
         |
         V
Heap   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
       |           0.1 |           3.2 |     5 |     7 |    20 |     6 |
       +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
         ^                               ^
         |                               |
        ptr      len                    ptr      len
       +--------+--------+             +--------+--------+
       | 0x0123 |      2 |             | 0x012b |      4 |
       +--------+--------+             +--------+--------+
       Guarded<[f32]>                  Guarded<[u16]>

The lifetimes of the type system will ensure that the Guard will outlive any slice.

Examples

Simple Example

use std::mem::MaybeUninit;
use columned::{Guard, GuardedBuilder};

fn main() {
    //Declare size and initialization of the slices.
    let mut xs = GuardedBuilder::<[u64]>::new_slice(10);
    let mut ys = GuardedBuilder::<[u64]>::new_slice(10);
    let mut sums = GuardedBuilder::<[MaybeUninit<u64>]>::new_slice(10);

    //Initialize a "Guard", which will manage the allocation.
    let mut guard: Guard = Guard::default();

    guard
        .subscriber()
        .subscribe(&mut xs)
        .subscribe(&mut ys)
        .subscribe(&mut sums)
        .allocate()
        .unwrap();

    let xs = xs.build_from_fn(|i| i as u64);
    let ys = ys.build_from_fn(|i| i as u64);
    let mut sums = sums.build_uninit();

    //drop(guard); // This would cause a compilation error

    for ((mut sum, x), y) in sums.iter_mut().zip(xs.iter()).zip(ys.iter()) {
        sum.write(x + y);
    }

    let sums = unsafe { sums.assume_init() };

    for (i, sum) in sums.iter().enumerate() {
        assert_eq!(*sum, 2 * i as u64);
    }
}

Structure of Array Example

use std::mem::MaybeUninit;
use columned::{Guard, Guarded, GuardedBuilder, Subscriber};

// The structure-of-array
struct Bodies<'a> {
    //Position
    position: Vec3<'a>,
    //Velocity
    velocity: Vec3<'a>,
    //Mass
    mass: &'a mut [f32],
}

impl <'a> Bodies<'a> {
    fn new(n: usize, subscriber: Subscriber<'a, '_>, f: impl FnOnce(Subscriber<'a, '_>)) -> Self {
        let mut mass = GuardedBuilder::<[f32]>::new_slice(n);

        let subscriber = subscriber
            .subscribe(&mut mass);
        
        let mut position = Vec3::default();
        let mut velocity = Vec3::new(n, subscriber, |subscriber| {
            position = Vec3::new(n, subscriber, f);
        });

        let mass = mass.build_default().into_mut();

        Self {
            position,
            velocity,
            mass
        }
    }
}

#[derive(Default)]
struct Vec3<'a> {
    x: &'a mut [f32],
    y: &'a mut [f32],
    z: &'a mut [f32],
}

impl <'a> Vec3<'a> {
    fn new(n: usize, subscriber: Subscriber<'a, '_>, f: impl FnOnce(Subscriber<'a, '_>)) -> Self {
        let mut x = GuardedBuilder::<[f32]>::new_slice(n);
        let mut y = GuardedBuilder::<[f32]>::new_slice(n);
        let mut z = GuardedBuilder::<[f32]>::new_slice(n);

        let subscriber = subscriber
        .subscribe(&mut x)
        .subscribe(&mut y)
        .subscribe(&mut z);

        f(subscriber);

        let x = x.build_default().into_mut();
        let y = y.build_default().into_mut();
        let z = z.build_default().into_mut();

        Vec3 {
            x,
            y,
            z,
        }
    }
}

fn main() {
    let mut guard = Guard::new();
    let bodies = Bodies::new(100, guard.subscriber(), |subscriber| {
        subscriber.allocate().unwrap()
    });
    
    //drop(guard); // would cause a compile error
    
    // use bodies here ...
}

Why Would I Not Use ... Instead?

• Arena: They require re-allocation for allocating more than one object.
• Memory-Pool: They are fixed in allocation size, “wasting” memory if over-provisioned or failing if under-provisioned. Columned dynamically allocates once depending on the required memory.
• Dynamic Allocation: They risk fragmentation for multiple objects, and risk multiple slow system calls.
• nested: Nested<T> can lump allocations of a singular type T. Columned can lump allocations of different types into a single allocation.