Comptime is funtime: Per-Span State Without a Hash Map David Bach<br>About Ideas Talks<br>Comptime is funtime: Per-Span State Without a Hash Map<br>In my free time, I have been following Casey Muratori's excellent Performance-Aware Programming Series. In Part 2: Basic Profiling, the task is to build a simple profiler. While doing so, I discovered a neat feature of Zig's comptime and generics.<br>The profiler is supposed to be easy to use, accurate, and, crucially, have low overhead. It has the three global variables shown below. These are not thread-safe, as we intentionally only want to profile single-threaded programs:<br>A buffer of spans with a fixed capacity holding the timings for each profiling block.<br>The current index.<br>The current parent index.<br>The fixed size means we can only have up to that number of unique spans. That is fine because we are instrumenting our code and it is unlikely we want to time more than 4096unique functions or blocks.<br>var spans: [4096]Span = undefined;<br>var current_index: SpanIndex = .reserved;<br>var current_parent_index: ?SpanIndex = null;

pub const Span = struct {<br>name: []const u8,<br>elapsed: u64,<br>elapsed_children: u64,<br>hit_count: u64,<br>};

const SpanIndex = enum(u32) {<br>reserved = 0,<br>_,<br>}; Each span is identified by its name, and it tracks how much time has elapsed, how much time its children took, and how many times it has been called. When we instrument our code, spans will be written into the spans buffer in the order of invocation. If a function that we profile is called twice, we don't add another span, we increment the existing span's values.<br>The API has two functions, beginBlock and endBlock, and can be used in the following way:<br>pub fn beginBlock(comptime name: []const u8) SpanBlock {}

pub fn endBlock(block: SpanBlock) void {}

fn readFile() !void {<br>const block = profile.beginBlock("readFile");<br>defer profile.endBlock(block);

// ... implementation ...<br>} Note: We could use @src() instead but I opted for the string variant for now.<br>When endBlock(block) runs, we store the elapsed time for this span in the spans buffer.<br>The question is: How do we compute the index of a particular span in the spans buffer without maintaining a HashMap between block name and index?<br>In the course, Casey uses __COUNTER__ from C++, which "gives an increasing non-negative integral value each time it is used." At each call site, the beginBlock function would get a unique index for it span at compile time . We don't have this in Zig. Actually, we could have done this a while ago, but since #19414, global mutable comptime state is no longer allowed.<br>In Zig, containers are namespaces that can contain top-level mutable declarations. spans, current_index, and current_parent_index are the three mutable top-level declarations of the profile.zig container (files are structs themselves). In Zig, generics are implemented via comptime: we write a function that returns a type. If we combine the two, we get the following:<br>fn SpanSlot(comptime name: []const u8) type {<br>return struct {<br>const span_name = name;<br>// This is a mutable top-level declaration in this specialized<br>// struct, storing the index the span will have in the<br>// `spans` buffer.<br>var index: ?SpanIndex = null;<br>};<br>} Each time we call beginBlock, we call SpanSlot to get the unique container for the given name. Then we look up the index variable in the container, and if it does not exist, we increment the index counter and store it.<br>pub fn beginBlock(comptime name: []const u8) SpanBlock {<br>const Slot = SpanSlot(name);

const span_index: SpanIndex = Slot.index orelse blk: {<br>// This is the first time we see a block with this<br>// `name`. Increment the index and store it in the container.<br>const next: SpanIndex = @enumFromInt(@intFromEnum(current_index) + 1);

Slot.index = next;

current_index = next;

// Initialize the span.<br>var span_ptr = &spans[@intFromEnum(next)];<br>span_ptr.name = name;<br>span_ptr.hit_count = 0;<br>span_ptr.elapsed = 0;<br>span_ptr.elapsed_children = 0;

break :blk next;<br>};

/// ...<br>} When we do const Slot = SpanSlot(name), we get back a type, not a local instance of this type. This gives us global mutable state per span without needing to explicitly track all possible spans we have, at the expense of compilation time.<br>Our solution is not entirely identical to using __COUNTER__. We still increment the index and store it at runtime. But at least this way we don't need to keep a hash map around.<br>Bonus 1<br>What are the effects on compilation time when we have a non-trivial number of spans? To simulate this I generate a Zig program that contains increasing number of functions that are timed with unique names and compiled it using ReleaseFast:<br>0 spans : 5 secs<br>100 spans: 5.2 secs<br>1000 spans: 6.8 secs<br>4032 spans: 13.3 secs<br>To further compare this I edited the 4032 spans version and used the same span name:<br>4032 spans (identical): 7.3 secs<br>Profiling lots of functions does have an effect on compilation time but gets only really noticeable from 1000 spans onward.<br>Bonus 2<br>If...