Arena swapping pattern in Zig

There’s this curious pattern with using arena, which I can’t fully wrap my head around:

The idea there is that you several scratch arenas, so that, when a call allocates into caller’s scratch, and uses its own arena, they don’t conflict.

I’ve recently saw a curious variation of that which claims that just two arenas is all you need:

(I think I’ve seen the two arenas trick somewhere else, but don’t recall there).

Is there some larger pieces of Zig software that use this pattern? I don’t fully understand it, and would love to get another example besides that Microsoft editor.

2 Likes

Two arenas, “permanent” and “scratch”. The former is for objects that will be returned to the caller. The latter is for temporary objects whose lifetime ends when the function returns. They have stack lifetimes just like local variables.

from https://nullprogram.com/blog/2023/09/27/

I feel like in zig this is slightly less relevant as you can create arena from arena in the function itself for a “scratch” allocator. Though the implementation detail that std arenas only free the last allocation may cause a problem with memory fragmentation.

It is infact pretty intresting pattern. Here is my best attempt at explaining it. Most common pattern in functions is like so

pub fn getFullNameFromJsonString(arena: Allocator, str: []const u8) []const u8 {
    // do some work which uses temporal allocationes
    const temp = std.json.parseFromSlice(
        struct { name: []const u8, surname: []const u8 },
        gpa,
        str,
        .{},
    ) catch @panic("OOM");


    // compute final result
    const result = std.fmt.allocPrint(arena, "{s} {s}", .{ temp.value.name, res.value.surname }) catch @panic("OOM");

    // free temporary allocations (not using defer for clarity)
    temp.deinit();

    return result;
}

If we imagine how values are placed on arena we would get this.


Final step requieres us to free temp value but we can’t since its not last.

So idea is to have 2 arenas.


This way on function exit we can clear Scratch arena and result will still be returnable.

Here is more full fledged version using 2 arenas:

const std = @import("std");
const Allocator = std.mem.Allocator;
const Arena = std.heap.ArenaAllocator;

pub fn getFullNameFromJson(scratch: Allocator, result_arena: Allocator, config: []const u8) ![]const u8 {
    var scratch_scope = Arena.init(scratch);
    defer scratch_scope.deinit();

    const res = try std.json.parseFromSliceLeaky(
        struct { name: []const u8, surname: []const u8 },
        scratch_scope.allocator(),
        config,
        .{ .ignore_unknown_fields = true },
    );

    return try std.fmt.allocPrint(result_arena, "{s} {s}", .{ res.name, res.surname });
}

pub fn userScoreString(scratch: Allocator, result_arena: Allocator, config: []const u8, points: usize) ![]const u8 {
    var scratch_scope = Arena.init(scratch);
    defer scratch_scope.deinit();

    const name = try getFullNameFromJson(scratch_scope.allocator(), result_arena, config);

    return try std.fmt.allocPrint(result_arena, "{s}, your score is {d}", .{ name, points });
}

pub fn main() !void {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    defer _ = gpa.deinit();

    var scratch = Arena.init(gpa.allocator());
    defer scratch.deinit();
    var result = Arena.init(gpa.allocator());
    defer result.deinit();

    std.debug.print("{s}\n", .{try userScoreString(
        scratch.allocator(),
        result.allocator(),
        \\{
        \\"name": "Andrew",
        \\"surname": "Kraevskii"
        \\}
        \\ 
    ,
        10,
    )});
}

There is one problem with that version: we are not freeing name in userScoreString. This happens because we asked getFullNameFromJson to allocate the value on the result arena, and we never free it. If we pass the arenas swapped, it will solve this issue.

This makes sense if we consider that, for getFullNameFromJson, the result value is a scratch value for userScoreString.

const std = @import("std");
const Allocator = std.mem.Allocator;
const Arena = std.heap.ArenaAllocator;

pub fn getFullNameFromJson(scratch: Allocator, result_arena: Allocator, config: []const u8) ![]const u8 {
    var scratch_scope = Arena.init(scratch);
    defer scratch_scope.deinit();

    const parsed_json = try std.json.parseFromSliceLeaky(
        struct { name: []const u8, surname: []const u8 },
        scratch_scope.allocator(),
        config,
        .{ .ignore_unknown_fields = true },
    );

    const name_surname = try std.fmt.allocPrint(result_arena, "{s} {s}", .{ parsed_json.name, parsed_json.surname });
    return name_surname;
}

pub fn userScoreString(scratch: Allocator, result_arena: Allocator, config: []const u8, points: usize) ![]const u8 {
    var scratch_scope = Arena.init(scratch);
    defer scratch_scope.deinit();

    // swaped arenas here when passing
    const name_surname = try getFullNameFromJson(result_arena, scratch_scope.allocator(), config);

    const score_string = try std.fmt.allocPrint(result_arena, "{s}, your score is {d}", .{ name_surname, points });
    return score_string;
}

pub fn main() !void {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    defer _ = gpa.deinit();

    var scratch = Arena.init(gpa.allocator());
    defer scratch.deinit();
    var result = Arena.init(gpa.allocator());
    defer result.deinit();

    std.debug.print("{s}\n", .{try userScoreString(
        scratch.allocator(),
        result.allocator(),
        \\{
        \\"name": "Andrew",
        \\"surname": "Kraevskii"
        \\}
        \\ 
    ,
        10,
    )});
}

It will look kinda like this. We can see how some values leave as both scratch and result (they cross function boundry).

6 Likes

That’s a neat post, and it is quoted in the edit source, but it isn’t the pattern actually used there! It’s a next-level idea that your scratch is your caller’s perm!

As an example, consider this C pseudo-code (sorry for an extremely fake example):

char* hello_world(arena* perm, arena scratch) char* {
    char* hello = fmt(&scratch, "hello");
    char* who = world(&scratch, *perm); //!! Swap the order here
    return fmt(perm, "%s%s", hello, who)
}

char* world(arena* perm, arena scratch) char* {
     char* wo = fmt(&scratch, "wo");
     char* rld = fmt(&scratch, "rld");
     return fmt(perm, "%s%s", wo, rld);
}

char* fmt(arena* perm, char* fmt, ...) {
    // ...
}

If you take a perm/scratch pair, and you need to call a helper that also takes perm/scratch, you can use your scratch for their perm. The galaxy brain idea is that you can also use your perm as their scratch! So you actually flip the arguments at every level, and it all works out.

Which is super-error prone, as it is the opposite of how it is usually done, and also requires threading arenas throughout. So there’s an extra twist, where you have get_me_arena function which gives you a global arena, but it also takes an argument which it uses to give you the other arena.

Super cursed, would love to study some Zig project using this on a larger scale.

The flip/flop’ing indeed seems extremely brittle, wonder if it’s possible to introduce some safeguards in debug builds

Hmm thats actually neat. Since you pass the flip flopped perm into scratch argument as a copy, there wont be fragmentation either.

You probably could make a safer interface for this using destructuring in zig and have separate struct keep track of the flip flops.

var perm, var scratch = flip_arenas.take();
defer scratch.deinit(); // can be omitted if using fbas instead
// ...

Kinda reminds me of double buffering.

My attempt at pretty directly translating the pattern, without globals/threadlocals (it really is not a pain to pass a single ctx argument with whatever global state you need), and without copy-by-value-on-function-call trick:

const std = @import("std");
const assert = std.debug.assert;
const Allocator = std.mem.Allocator;
const ArenaAllocator = std.heap.ArenaAllocator;

const Context = struct {
    arenas: [2]ArenaAllocator,

    pub const SubArena = struct {
        arena: *ArenaAllocator,
        end_index: usize,

        pub fn allocator(arena: *const SubArena) Allocator {
            return arena.arena.allocator();
        }

        pub fn deinit(arena: *const SubArena) void {
            assert(arena.arena.state.end_index >= arena.end_index);
            arena.arena.state.end_index = arena.end_index;
        }
    };

    pub fn init(gpa: Allocator) Context {
        return .{ .arenas = .{
            ArenaAllocator.init(gpa),
            ArenaAllocator.init(gpa),
        } };
    }

    pub fn deinit(ctx: *Context) void {
        for (&ctx.arenas) |*arena| arena.deinit();
        ctx.* = undefined;
    }

    pub fn scratch(ctx: *Context, conflict: ?Allocator) SubArena {
        const index = if (conflict) |allocator|
            for (&ctx.arenas, 0..) |*arena, index| {
                if (allocator.ptr == @as(*anyopaque, arena)) break index ^ 1;
            } else unreachable
        else
            0;

        return .{
            .arena = &ctx.arenas[index],
            .end_index = ctx.arenas[index].state.end_index,
        };
    }
};

pub fn main() !void {
    var gpa_instance: std.heap.GeneralPurposeAllocator(.{}) = .{};
    defer switch (gpa_instance.deinit()) {
        .leak => @panic("leaked"),
        .ok => {},
    };
    const gpa = gpa_instance.allocator();

    var ctx = Context.init(gpa);
    defer ctx.deinit();

    try top(&ctx);
}

fn top(ctx: *Context) !void {
    const scratch = ctx.scratch(null);
    const hello = try hello_world(ctx, scratch.allocator());
    std.debug.print("{s}\n", .{hello});
}

fn hello_world(ctx: *Context, perm: Allocator) ![]const u8 {
    const scratch = ctx.scratch(perm);
    defer scratch.deinit();

    const hello = try std.fmt.allocPrint(scratch.allocator(), "hello", .{});
    const who = try world(ctx, scratch.allocator());

    return try std.mem.concat(perm, u8, &.{ hello, who });
}

fn world(ctx: *Context, perm: Allocator) ![]const u8 {
    const scratch = ctx.scratch(perm);
    defer scratch.deinit();

    const wo = try std.fmt.allocPrint(scratch.allocator(), "wo", .{});
    const rld = try std.fmt.allocPrint(scratch.allocator(), "rld", .{});
    return try std.mem.concat(perm, u8, &.{ wo, rld });
}

I think there isn’t any way to get rid of sub-arena’s defers here, though I’d love to be proven wrong!

2 Likes

It’s only possible if you use fbas for both perm and scratch

I did a stream with Andrew about implementing subarenas in std.heap.ArenaAllocator and concluded that it’s an inferior choice to simply creating a nested arena, especially if the outer arena has been created over page_allocator.

Another consideration I came out with from that experience is that it’s generally not worth it trying to retain a value in an arena and then shrink it (instead of fully resetting it) and that in the general case you’re better off copying the value out of the arena (or even better directly allocating it with a gpa) instead.

4 Likes