In Go, we rarely think about where our data lives. When we call new(T) or use a composite literal like &T{}, the Go runtime handles the complexities of finding space, managing lifecycle, and eventually reclaiming that space via garbage collection. For most programs (including some games), this is more than fast enough. The runtime is fast, and always getting faster e.g. https://go.dev/blog/size-specialized-allocations.

But there are times when the standard allocator is just not fast enough, or you create so much garbage that you start to notice the GC overhead. If you are building a high-performance system where you need to create millions of small, short-lived objects, or if you want to represent certain values in a way that avoids the overhead of heap allocation entirely, you might find yourself looking for something more "exotic", like an arena.

What is an Arena?

The concept of an arena (often called a bump allocator) is quite simple. Instead of asking the runtime for memory every time you need an object, you reserve a large, contiguous block of memory upfront. You then maintain two pointers: a start pointer (the beginning of the arena) and a current pointer (the next available address).

To allocate memory from this arena, you simply return the current pointer and increment it by the size of the requested object. When you are done with all the objects in the arena, you can reclaim the entire block at once.

This is a bit abstract. Let's look at how we can implement a specialized version of this idea in Go.

Reserving the Address Space with mmap

On Unix-like systems, mmap allows us to request pages of memory directly, bypassing the Go allocator. Here is a simplified version of how we might implement a mmap function:

//go:build unix

package uniquenumber

import (
	"unsafe"
	"golang.org/x/sys/unix"
)

func mmap(size int) (unsafe.Pointer, error) {
	// MAP_ANON: not backed by any file
	// MAP_PRIVATE: changes are private to this process
	// PROT_READ: we want to be able to read this memory
	s, err := unix.Mmap(-1, 0, size, unix.PROT_READ, unix.MAP_PRIVATE|unix.MAP_ANON)
	if err != nil {
		return nil, err
	}
	return unsafe.Pointer(unsafe.SliceData(s)), nil
}

By using MAP_ANON and PROT_READ, we are telling the kernel: "Give me a huge, empty chunk of virtual address space that I can read from." On a 64-bit system, this space is vast, allowing us to be quite ambitious with our request. We can usually mmap 45+ bits / 32 TiB without issue.

Playing with Pointers and unsafe

Once we have this raw block of memory, we can't use it with standard Go types directly. We need to bridge the gap between the world of types and the world of raw memory addresses. This is where the unsafe package comes in and it allows us to do exactly what the name says: play games with the Go type system.

To do any meaningful work, we have to treat our pointers as uintptr values, which allows us to perform pointer arithmetic. In modern Go, we use unsafe.Add to move through our arena instead of doing arithmetic direct with + or - like in C.

Conceptually, an arena might look like this:

type Arena struct {
    start   unsafe.Pointer
    current unsafe.Pointer
    end     unsafe.Pointer
}

func (a *Arena) Alloc(size uintptr) (unsafe.Pointer, error) {
    if uintptr(a.current) + size > uintptr(a.end) {
        return nil, ErrOutOfMemory
    }
    ptr := a.current
    a.current = unsafe.Add(a.current, size)
    return ptr, nil
}

Or maybe clearer as an allocator of integers, using a slice:

type Arena struct {
		reserve []int
    current   int
}

func (a *Arena) Alloc() (*int, error) {
    if a.current >= len(a.reserve) {
        return nil, ErrOutOfMemory
    }
    ptr := &a.reserve[a.current]
    a.current++
    return ptr, nil
}

You might have noticed that all we've done is implemented what's effectively a stack, so let's try something a little more interesting.

An allocator of unsigned integers

Usually, an allocator takes a size and returns a pointer to a location where you can store a value. But what if the value is the pointer?

Consider the problem of allocating integers e.g. for a virtual machine. If we have a massive, contiguous block of memory, we can map every integer in a certain range to a specific, unique address within that block.

Instead of allocating a piece of memory to hold the number 42, we simply calculate the address that represents 42 and return it.

var (
	arenaStart, arenaEnd = newArena()
	maxUint              = uint(uintptr(arenaEnd) - uintptr(arenaStart))
)

func newArena() (start, end unsafe.Pointer) {
	// try to mmap space for all 32-bits ints
	size := 1 << 32
	slice, err := unix.Mmap(-1, 0, 1<<32, unix.PROT_READ, unix.MAP_PRIVATE|unix.MAP_ANON)
	if err != nil {
		// if that fails, allocate space for all 16-bit ints
		// it's only a cheap 16k allocation and can cover 65536 ints, so it's a good fallback
		size = 1 << 16
		slice = make([]byte, size)
	}
	start = unsafe.Pointer(unsafe.SliceData(slice))
	end = unsafe.Add(start, size)
	return start, end
}

type Uint struct {
		p unsafe.Pointer
}

func NewUint(v uint) Uint {
    // if v is within our pre-allocated range
    // we offset the base address by the value itself.
    if v <= maxUint {
        return Uint{p: unsafe.Add(arenaStart, v)}
    }
    // otherwise, fallback to standard heap-allocation
    return Uint{p: unsafe.Pointer(&v)}
}

func (u Uint) Value() uint {
    // if the ptr is in our pre-allocated range
    // to get the value back, we just subtract the base address
    p := uintptr(u.p)
    if uintptr(arenaStart) <= p && p <= uintptr(arenaEnd) {
        return uint(p - uintptr(arenaStart))
    }
    // otherwise, we stored a uint pointer
    // just cast it back to a *uint and dereference to get the value
    return *(*uint)(u.p)
}

Interning: What if I want a stable value

For values allocated from our arena, the pointer is stable. Given the same number, you always get back the same pointer, so comparisons can be done with == without needing to call .Value() and you can use it directly as map keys, etc.

But for values out of the range, we fall back to allocating a new pointer.

To solve this and similar issues, we can use a technique commonly know as interning. Go added weak maps and specifically the unique package for this.

You might have wondering how we're going integrate a unique.Handle package into our Uint type without increasing the size (and thus causing an allocation if we assign it to an interface)...

The type for type unique.Handle is:

type Handle[T comparable] struct {
	value *T
}

Does it look familiar? The struct has the same layout as Uint i.e. a single pointer.

That means we can "safely" cast it to another type with the same layout... and yes, you can use the same technique to access unexported members of a type in another package xD.

var (
	arenaStart, arenaEnd = newArena()
	maxUint              = uint(uintptr(arenaEnd) - uintptr(arenaStart))
)

func newArena() (start, end unsafe.Pointer) {
	// try to mmap space for all 32-bits ints
	size := 1 << 32
	slice, err := unix.Mmap(-1, 0, 1<<32, unix.PROT_READ, unix.MAP_PRIVATE|unix.MAP_ANON)
	if err != nil {
		// if that fails, allocate space for all 16-bit ints
		// it's only a cheap 16k allocation and can cover 65536 ints, so it's a good fallback
		size = 1 << 16
		slice = make([]byte, size)
	}
	start = unsafe.Pointer(unsafe.SliceData(slice))
	end = unsafe.Add(start, size)
	return start, end
}

// unique.Handle is designed to be comparable (e.g. used as map keys) so the layout will never change...
// but to make sure, we can use this hack to make sure it remains the same as our Uint type.
// if the size changes, the code will fail to compile
var (
	_ [unsafe.Sizeof(Uint{})]struct{} = [unsafe.Sizeof(unique.Handle[any]{})]struct{}{}
)

type Uint struct {
		p unsafe.Pointer
}

func NewUint(v uint) Uint {
    // if v is within our pre-allocated range
    // we offset the base address by the value itself.
    if v <= maxUint {
        return Uint{p: unsafe.Add(arenaStart, v)}
    }
    // otherwise, fallback to a unique.Handle
   	h := unique.Make(v)
    return *(*Uint)(unsafe.Pointer(&h))
}

func (u Uint) Value() uint {
    // if the ptr is in our pre-allocated range
    // to get the value back, we just subtract the base address
    p := uintptr(u.p)
    if uintptr(arenaStart) <= p && p <= uintptr(arenaEnd) {
        return uint(p - uintptr(arenaStart))
    }
    // otherwise, we stored a unique.Hande; just cast it back to get the value
    return (*(*unique.Handle[uint])(u.p)).Value()
}

In this pattern, the allocation cost for any value within our range is effectively zero. We are simply performing a 1 comparison and 1 addition to generate a pointer.

Additionally, because we don't write to any of the pointers (or read from any, for that matter), it's concurrency safe by design.

What's the catch?

An allocator that allocates numbers in ~1-2ns, zero heap zero allocations and provides stable handles/pointers... it seems too good to be true...

This approach is incredibly fast. In our benchmarks, MakeUint and MakeInt show zero allocations per operation. We have turned a potentially expensive heap operation into a simple bit of pointer arithmetic.

Of course, there is a cost. We are consuming a significant amount of virtual address space, which can lead to crashes or failure to start the app, but this is usually an OS configuration problem (esp. in containers).

We are also stepping outside the safety guarantees of the Go language by using unsafe. A mistake in our arithmetic could lead to a segmentation fault or, worse, silent data corruption. But we never read or write anything in the virtual address space and it's a very small amount of code, so it should be no concern in a real implementation.

A complete implementation

A complete implementation that supports ints, uints and floats can be found here https://github.com/amitybell/uniquenumber