Home

Awesome

Arenas: Arena allocators for C#/CSharp

This is a .NET Standard 2.0 library that provides access to arena allocators along with the ability to use unmanaged references with natural C# syntax and safe-guards, as well as the ability for arena-allocated items to reference managed C# objects. It is NativeAOT compatible.

Use by creating a new Arena() and calling Allocate with blittable structs or AllocCount to allocate arrays of items. Types that implement IArenaContents will automatically have Free called and ArenaID set where appropriate (without boxing.)

Features

Samples

Do some stuff with arenas:

UnmanagedRef<Person> staleRefTest;

using (var arena = new Arena()) {
    // allocate some people in the arena
    var john = arena.Allocate(new Person());
    john.Value->FirstName = "John";
    john.Value->LastName = "Doe";

    var jack = arena.Allocate(new Person());
    jack.Value->FirstName = "Jack";
    jack.Value->LastName = "Black";

    Console.WriteLine($"Size of UnmanagedRef: {sizeof(UnmanagedRef)}");

    Console.WriteLine(john);
    Console.WriteLine(jack);

    // make a list of integers in the arena
    var list = new ArenaList<int>(arena) { 1, 2, 3 };
    for (int i = 10; i < 22; i++) {
        list.Add(i);
    }

    Console.WriteLine("Values in list:");
    foreach (var i in list) {
        Console.WriteLine(i);
    }

    // make a dictionary of integers in the arena
    var dict = new ArenaDict<int, int>(arena);
    var random = new Random(12345);
    for (int i = 0; i < 20; i++) {
        dict[random.Next(1000)] = random.Next(1000);
    }

    Console.WriteLine("Values in dictionary (sorted by key ascending):");
    foreach (var kvp in from entry in dict orderby entry.Key ascending select entry) {
        Console.WriteLine(kvp);
    }

    Console.WriteLine("Items in arena:");
    foreach (var item in arena) {
        Console.WriteLine(item);
    }

    // free an item
    arena.Free(jack);
    
    Console.WriteLine("Items in arena after freeing:");
    foreach (var item in arena) {
        Console.WriteLine(item);
    }

    // free the rest and show that our references are stale
    arena.Clear();
    Console.WriteLine($"Does stale reference have a value? {john.HasValue}");

    // make some random bytes using a Guid
    var guid = Guid.NewGuid();
    var guidBytes = guid.ToByteArray();

    // allocate a buffer for the bytes in the arena and copy them
    var unmanagedBytes = arena.AllocCount<byte>(guidBytes.Length);
    Marshal.Copy(guidBytes, 0, (IntPtr)unmanagedBytes.Value, guidBytes.Length);

    // check if the bytes are the same
    var isSame = true;
    for (int i = 0; i < guidBytes.Length; i++) {
        if (guidBytes[i] != *unmanagedBytes[i]) {
            isSame = false;
            break;
        }
    }
    Console.WriteLine(isSame ? "ArenaID bytes match" : "ArenaID bytes don't match");

    // split a string into a bunch of ArenaString instances
    using (var splitResults = ArenaString.Split(arena, "Lorem ipsum dolor sit amet", ' ')) {
        for (int i = 0; i < splitResults.Count; i++) {
            var str = splitResults[i];
            Console.WriteLine(str);
            str.Free();
        }
    }

    // final stale reference test for disposal
    staleRefTest = arena.Allocate(new Person());
    staleRefTest.Value->FirstName = "Stale";
    staleRefTest.Value->LastName = "Reference";
}

Console.WriteLine($"Does stale reference have a value after disposal? {staleRefTest.HasValue}");

Create a blittable struct with managed references:

[StructLayout(LayoutKind.Sequential)]
unsafe public struct Person : IArenaContents {
    // these two lines are boilerplate for IArenaContents structs
    ArenaID IArenaContents.ArenaID { get; set; }
    IArenaMethods IArenaContents.ArenaMethods { get => ArenaMethods<Person>.Instance; }

    private ManagedRef firstName;
    private ManagedRef lastName;

    public override string ToString() {
        return $"{FirstName} {LastName}";
    }

    public void Free() {
        // free managed references by setting to null
        FirstName = null;
        LastName = null;
    }

    public string FirstName {
        get { return firstName.Get<string>(); }
        set { firstName = firstName.Set(ref this, value); }
    }
    public string LastName {
        get { return lastName.Get<string>(); }
        set { lastName = lastName.Set(ref this, value); }
    }
}

Store references to items in arena in ArenaList:

using (var arena = new Arena()) {
    // allocate a list
    var people = new ArenaList<UnsafeRef>(arena);

    // allocate some people references
    var john = arena.Allocate(new Person());
    john.Value->FirstName = "John";
    john.Value->LastName = "Doe";

    var jack = arena.Allocate(new Person());
    jack.Value->FirstName = "Jack";
    jack.Value->LastName = "Black";

    // store references inside the list
    people.Add(john);
    people.Add(jack);

    // iterate over unmanaged list and write out all the people
    foreach (var item in people) {
        var person = item.As<Person>();
        Console.WriteLine(*person);
    }
}

Zero-allocation string splitting via arenas (requires .NET Core):

This sample was made before the ArenaString type existed as an example of interaction between arenas and the .NET Core Span type. For zero-allocation string splitting please use ArenaString.Split

class Program {
    unsafe static void Main(string[] args) {
        using (var arena = new Arena()) {
            Console.WriteLine($"Original string: {sourceText}");

            // contrived example to split a string into words using an arena
            // in order to avoid allocations
            var words = new ArenaList<Word>(arena);

            var index = 0;
            var startIndex = 0;

            void addWord() {
                var length = index - startIndex;
                if (length > 0) {
                    var chars = arena.AllocCount<char>(length);
                    var source = sourceText.AsSpan(startIndex, length);
                    var dest = new Span<char>(chars.Value, length);
                    source.CopyTo(dest);
                    words.Add(new Word(length, chars.Value));
                }

                startIndex = index + 1;
            };

            while (index < sourceText.Length) {
                var c = sourceText[index];
                if (c == ' ') {
                    addWord();
                }
                index++;
            }

            addWord();

            Console.Write("Split string: ");
            foreach (var word in words) {
                var s = new Span<char>(word.Data, word.Length);
                foreach (var c in s) {
                    Console.Write(c);
                }
                Console.Write(' ');
            }
            Console.WriteLine();

            Console.WriteLine("Arena contents after splitting:");
            foreach (var item in arena) {
                Console.WriteLine($"0x{item.Value:x16}: {item}");
            }
        }
    }

    private static string sourceText = @"Lorem ipsum dolor sit amet, consectetur adipiscing elit. Aliquam sodales elit rutrum iaculis dictum.";

    [StructLayout(LayoutKind.Sequential)]
    private unsafe struct Word {
        public int Length;
        public char* Data;

        public Word(int length, char* data) {
            Length = length;
            Data = data;
        }

        public override string ToString() => Data is null || Length <= 0 ? "" : new string(Data, 0, Length);
    }
}

"yo dawg i herd u liek arena allocators so i put some arena allocators in ur arena allocators":

private static Arena parentArena = new Arena();

private unsafe class ArenaAllocator : IMemoryAllocator {
    public MemoryAllocation Allocate(int sizeBytes) {
        var alloc = parentArena.AllocCount<byte>(sizeBytes);
        return new MemoryAllocation((IntPtr)alloc.Value, alloc.Size);
    }

    public void Free(IntPtr ptr) => parentArena.Free(ptr);
}

static unsafe void ArenaArenas() {
    // by using a page size of 2048 we're actually guaranteeing this allocator
    // will use pages of ~4k, because the size is rounded to the next power of
    // two after adding the item header size
    using (var childArena = new Arena(new ArenaAllocator(), 2048)) {
        var john = childArena.Allocate(new Person());
        john.Value->FirstName = "John";
        john.Value->LastName = "Doe";

        var jack = childArena.Allocate(new Person());
        jack.Value->FirstName = "Jack";
        jack.Value->LastName = "Black";

        Console.WriteLine("Child arena:");
        foreach (var item in childArena) Console.WriteLine(item);
        Console.WriteLine("Parent arena:");
        foreach (var item in parentArena) Console.WriteLine(item);
    }
}

Potential future work

Should I use this in production?

Eh, maybe? I feel like the library is pretty mature, so for small projects I think it'd be okay. Probably not for big dang enterprise stuff though. Unless you really want to, I'm not your dad. I'd definitely use it myself at this point, but I'm a game developer, what do I know?