Awesome

zee_alloc — zig wee allocator

A tiny general purpose allocator targeting WebAssembly.

This allocator has not been well tested. Use at your own peril.

Getting Started

In zig:

const zee_alloc = @import("zee_alloc");

pub fn foo() void {
    var mem = zee_alloc.ZeeAllocDefaults.wasm_allocator.alloc(u8, 1000);
    defer zee_alloc.ZeeAllocDefaults.wasm_allocator.free(mem);
}

Exporting into wasm:

const zee_alloc = @import("zee_alloc");

comptime {
    (zee_alloc.ExportC{
        .allocator = zee_alloc.ZeeAllocDefaults.wasm_allocator,
        .malloc = true,
        .free = true,
        .realloc = false,
        .calloc = false,
    }).run();
  }

Goals

(inspired by Rust's wee_alloc)

1. Tiny compiled output
2. Tiny compiled output x2
3. Malloc/free compatibility
4. Avoid long-term fragmentation
5. Reasonably fast alloc and free
6. Code simplicity — probably goes in hand with tiny output

Non-goals

• Debugging — this library probably will never do a good job identifying errors. Zig has a great debug allocator in the works, and zig programs should be able to easily swap allocators.
• Compact memory — fixed allocation frames are used for speed and simplicity. Memory usage will never be optimum unless the underlying algorithm completely changes
• Thread performance — wasm is single-threaded

Benchmarks

Benchmark                                   Mean(ns)
----------------------------------------------------
DirectAllocator.0                              50842
DirectAllocator.1                              98343
DirectAllocator.2                             203980
DirectAllocator.3                              49908
DirectAllocator.4                             103635
DirectAllocator.5                             195941
DirectAllocator.6                              47367
DirectAllocator.7                             101733
DirectAllocator.8                             202697
Arena_DirectAllocator.0                        11837
Arena_DirectAllocator.1                        19591
Arena_DirectAllocator.2                        30689
Arena_DirectAllocator.3                        30916
Arena_DirectAllocator.4                        52425
Arena_DirectAllocator.5                        75673
Arena_DirectAllocator.6                        44874
Arena_DirectAllocator.7                        67557
Arena_DirectAllocator.8                        96276
ZeeAlloc_DirectAllocator.0                     15892
ZeeAlloc_DirectAllocator.1                     24435
ZeeAlloc_DirectAllocator.2                     49564
ZeeAlloc_DirectAllocator.3                     26656
ZeeAlloc_DirectAllocator.4                     52462
ZeeAlloc_DirectAllocator.5                     93854
ZeeAlloc_DirectAllocator.6                     51493
ZeeAlloc_DirectAllocator.7                     95223
ZeeAlloc_DirectAllocator.8                    250187
FixedBufferAllocator.0                           177
FixedBufferAllocator.1                           412
FixedBufferAllocator.2                          1006
FixedBufferAllocator.3                           296
FixedBufferAllocator.4                           785
FixedBufferAllocator.5                          1721
FixedBufferAllocator.6                           848
FixedBufferAllocator.7                          1546
FixedBufferAllocator.8                          3331
Arena_FixedBufferAllocator.0                     299
Arena_FixedBufferAllocator.1                     573
Arena_FixedBufferAllocator.2                    1624
Arena_FixedBufferAllocator.3                    1115
Arena_FixedBufferAllocator.4                    1868
Arena_FixedBufferAllocator.5                    4422
Arena_FixedBufferAllocator.6                    1706
Arena_FixedBufferAllocator.7                    3389
Arena_FixedBufferAllocator.8                    8430
ZeeAlloc_FixedBufferAllocator.0                  232
ZeeAlloc_FixedBufferAllocator.1                  577
ZeeAlloc_FixedBufferAllocator.2                 1165
ZeeAlloc_FixedBufferAllocator.3                  443
ZeeAlloc_FixedBufferAllocator.4                  907
ZeeAlloc_FixedBufferAllocator.5                 1848
ZeeAlloc_FixedBufferAllocator.6                  907
ZeeAlloc_FixedBufferAllocator.7                 1721
ZeeAlloc_FixedBufferAllocator.8                 3836

Architecture — Buddy memory allocation

Caveat: I knew nothing about memory allocation when starting this project. Any semblence of competence is merely a coincidence.

idx frame_size
 0  >65536  jumbo
 1   65536  wasm page size
 2   32768
 3   16384
 4    8192
 5    4096
 6    2048
 7    1024
 8     512
 9     256
10     128
11      64
12      32
13      16  smallest frame

Size order is reversed because 0 and 1 are special. I believe counting down had slightly better semantics than counting up but I haven't actually tested it.

Wasm only allows for allocating entire pages (64K) at a time. Current architecture is heavily influenced by this behavior. In a real OS, the page size is much smaller at 4K. Everything should work as expected even if it does not run as efficient as possible.

Each allocation frame consists of 2 usizes of metadata: the frame size and a pointer to the next free node. This enables some rudimentary debugging as well as a simple lookup when we only have the allocated data-block (especially important for C compatibility).

For allocations <=64K in size, we find the smallest usable free frame. If it's bigger than necessary, we grab the smallest power of 2 we need and resize the rest to toss back as free nodes. This is O(log k) which is O(1).

For allocations >64K, we iterate through list 0 to find a matching size, O(n). Free jumbo frames are never divided into smaller allocations.

ZeeAlloc only supports pointer alignment at 2x usize — 8 bytes in wasm. There are a few ideas to expand this to up-to half page_size but nothing concrete yet.