MTB::Entity: An address-stable, interior-mutable Slab allocator

中文版请见: README-zh.md

⚠️ Notes

This allocator is experimental; its API may change significantly.
It has not been thoroughly tested and may contain memory-safety issues. Use with care.
It currently supports single-threaded use only, with no plans for multithreading support.
The recommended alternative is the slab crate — it’s superior in both performance and safety in general. If you don’t specifically need interior mutability, prefer slab.

Introduction

The motivation for this allocator came while building Remusys. The slab crate’s Slab requires a mutable reference to allocate elements, which complicated some of my optimizations. This chunked, address-stable allocator lets you allocate new elements while reading existing ones:

use mtb_entity_slab::{EntityAlloc, PtrID, IEntityAllocatable, EntityAllocPolicy256};

#[derive(Debug, Clone, PartialEq, Eq)]
struct Inst {
    pub opcode: u32,
    pub operands: [u64; 4],
    pub heap_data: String,
}
/// Not every type can be stored in this allocator. You need to implement the
/// `IEntityAllocatable` trait for your type.
impl IEntityAllocatable for Inst {
    type AllocatePolicyT = EntityAllocPolicy256<Self>;

    /// You should implement your own pointer ID wrapper.
    type PtrID = PtrID<Inst>;
}

impl Inst {
    fn new(opcode: u32) -> Self {
        Self {
            opcode,
            operands: [0; 4],
            heap_data: format!("InstData{}", opcode),
        }
    }
}

fn main() {
    let mut alloc = EntityAlloc::with_capacity(1024);
    let ptrs = {
        let mut v = Vec::new();
        for i in 0..1000 {
            let ptr = alloc.allocate(Inst::new(i));
            v.push(ptr);
        }
        v
    };

    let inst = ptrs[500].deref(&alloc);

    // Allocate a new element while concurrently reading existing ones
    let new_id = alloc.allocate(Inst::new(2000));
    assert_eq!(inst.opcode, 500);
    assert_eq!(new_id.deref(&alloc).opcode, 2000);
}

Basic type hierarchy

EntityAlloc — The allocator itself; manages all chunks and the allocation/freeing of elements.
IEntityAllocID<E> — A trait for converting between PtrID and IndexedID.
PtrID<E> — An ID pointing to an element inside the allocator, internally a raw pointer. Fast but unsafe.
IndexedID<E> — An ID pointing to an element, represented by a pair of chunk index and in-chunk index. Safe but much slower.
IDProxy<'alloc, E> — A proxy used for two-phase initialization of a target element.

Allocation policies

The allocator supports multiple allocation strategies to fit different scenarios. Not every type can be stored in the allocator; your type must implement IEntityAllocatable and specify a policy. Available policies:

EntityAllocPolicy128<E> — 128 elements per chunk (medium/small chunks, single-level bitmap).
EntityAllocPolicy256<E> — 256 elements per chunk (medium/small chunks, single-level bitmap).
EntityAllocPolicy512<E> — 512 elements per chunk (medium/small chunks, single-level bitmap).
EntityAllocPolicy1024<E> — 1024 elements per chunk (large chunks, two-level bitmap).
EntityAllocPolicy2048<E> — 2048 elements per chunk (large chunks, two-level bitmap).
EntityAllocPolicy4096<E> — 4096 elements per chunk (large chunks, two-level bitmap).

Here’s the boilerplate for making a type allocatable, as in the example above:

use mtb_entity_slab::{IEntityAllocatable, EntityAllocPolicyXXX};

struct MyType {
    // ...
}
impl IEntityAllocatable for MyType {
    type AllocatePolicyT = EntityAllocPolicyXXX<Self>;
}

Containers

Some container types are built on top of EntityAlloc for convenience: