markcsaving/drop_arena

A single-type allocator which permits dropping and reclaiming of individual elements.

drop_arena

Introduction

A DropArena<T> can allocate or deallocate individual elements of type T. Only allocating elements of a fixed size ! and alignment allows the allocator to be extremely efficient compared to an ordinary implementation of malloc and free. Think of DropArena as providing a combination of the functionality of an Arena and the allocator that makes Boxes.

The DropArena can return a DropBox<T>, which functions very much like a Box<T> except for being tied to the DropArena that allocated it. A DropBox can be used exactly like a &mut T; in fact, it is a repr(transparent) wrapper around a &mut T.

When it comes to getting rid of a DropBox<T>, there are several options. First, you may use drop (or let the DropBox go out of scope). This will call drop on the underlying T, but it will not reclaim the memory needed to allocate the T. Similarly, you may use DropBox::into_inner, which extracts the underlying T but does not reclaim the memory the T formerly occupied. This memory will eventually be reclaimed when the DropArena<T> is itself dropped. Finally, you may call DropBox::leak, which produces a &mut T. This means that unless unsafe code is used, the T will never be droped. However, when the DropArena which allocated the DropBox is dropped, the memory will be reclaimed.

In order to reclaim the memory allocated to a DropBox<T>, we need a reference to the DropArena<T> which allocated it. We can use the DropArena::drop_box method on a DropBox to drop the underlying value and reclaim the memory. We can also use the DropArena::box_into_inner method to retrieve the underlying T from a DropBox<T> and reclaim the memory it used.

To guarantee that an arena can only reclaim memory from DropBoxes it allocated (or one allocated by a drop arena with exactly the same lifetime), we need to use lifetime magic. A DropArena is tagged with the lifetime it will live, and it has an invariant relationship with this lifetime. DropBoxes have an invariant relationship with the lifetime of the DropArena that created them.

It is not recommended to have multiple DropArena<T>s with the same lifetime. In particular, if arena 1 keeps allocating DropBox<T>s which arena 2 keeps consuming, you won't get any benefit out of reclaiming the memory. However, it is perfectly safe to do this.

Complexity

Calling DropArena::box_into_inner() or DropBox::into_inner() is O(1) with very small constants (except if the size of T is large - then copying the T dominates). The corresponding drop functions are also O(1) + the time the call to Drop::drop takes with small constants.

Allocating is also very fast. There are three possible paths for an allocation. First, the arena has a free space where something was previously allocated. In this case, allocation is O(1) with small constants. Second, the pre-allocated capacity of the Arena is large enough to fit one more element. In this case, allocation is O(1) with small constants. Third, the arena has genuinely run out of space (this is the most uncommon case, even when we are only doing allocations and no drops). In this case, we must allocate more space using the system allocator. We follow the same guidelines as typed_arena, making a single allocation with enough space for many more Ts (in fact, we actually implement DropArena using typed_arena).

Recursive owning data structures

We can write some basic owning data structures using our arena as follows. The list implementation below is inspired by Learning Rust With Entirely Too Many Linked Lists.

use drop_arena::{DropArena, DropBox};
struct Node<'arena, T> {
    item: T,
    rest: Link<'arena, T>,
}

type Link<'arena, T> = Option<DropBox<'arena, Node<'arena, T>>>;

struct List<'arena, T> {
    arena: &'arena DropArena<'arena, Node<'arena, T>>,
    ptr: Link<'arena, T>,
}

impl<'arena, T> Drop for List<'arena, T> {
    fn drop(&mut self) {
        while let Some(mut nxt) = self.ptr.take() {
            self.ptr = nxt.rest.take();
            self.arena.drop_box(nxt);
        }
    }
}

impl<'d, T> List<'d, T> {
    fn push(&mut self, val: T) {
        self.ptr = Some(self.arena.alloc(Node {
            item: val,
            rest: self.ptr.take(),
        }))
    }

    fn pop(&mut self) -> Option<T> {
        let first = self.ptr.take()?;
        let node = self.arena.box_into_inner(first);
        self.ptr = node.rest;
        Some(node.item)
    }

    fn new(arena: &'d DropArena<'d, Node<'d, T>>) -> Self {
        Self { arena, ptr: None }
    }
}


let arena = DropArena::new();
let mut list = List::new(&arena);

for i in 0..100 {
    list.push(i);
}

for i in (0..100).rev() {
    assert_eq!(list.pop().unwrap(), i);
}

Areas of Improvement

This allocator works for zero-sized types, but it is not efficient in this case. I plan to address this in the future using conditional types. The issue is that keeping a free block list requires pointers. However, in theory, when we are dealing with ZSTs, we could just choose not to have a free list at all. I would like to separately implement a special arena for ZSTs using CondType, but this crate is still limited. In order for it to be usable here, we need this issue to be resolved.

Much more testing is required to ensure that DropArenas are safe. I've done some elementary experimentation with Miri, but exhaustive fuzzing is needed. This code uses a fair amount of unsafe, and that means there are plenty of chances for serious bugs to appear. I think I've caught most of them, but it's not impossible I neglected one.

Making sure that a DropBox<T> implements all the traits that a Box<T> does seems desirable.

Maintenance

This is my first open-source project, so I may not be able to find time to properly maintain it. That said, I will do my best, time-permitting, especially for serious bugs. Please be patient.

License: MIT