I’m doing Advent of Code again this year; so far I’ve been very pleasantly surprised that my facility for solving the problems has improved. (Of course, I’m well aware that the difficulty is likely to ramp up soon, so I may end up eating my words.) Previously, I did the 2023 Advent of Code as it happened in Zig. Pace Loris Cro, who wrote a great blog post on the subject, I think that despite the way Advent of Code problems are at odds with the kinds of software problems that Zig aims itself at solving, doing Advent of Code is a great way to gain familiarity with Zig. Over this past summer I also did the 2022 Advent of Code problems as a way of learning Rust. Today, solving the 5th problem for 2024, it occurred to me that Rust had taught me something surprisingly useful for my Zig solution. The purpose of this post is to talk about what I learned—this post does not contain spoilers for any Advent of Code problems, and indeed is not really “about” Advent of Code at all: as I was writing it, it became clear that part of this blog post actually belongs on the Zig issue tracker.

All I know is eat hot chip and Impl Iterator

In my opinion, both Rust and Zig have (very different!) hard edges that ultimately lead you towards writing better programs. The “obvious” hard edge that Rust has is the borrow checker, which other people have beaten to death. The borrow checker is a beautiful piece of software; I’m not interested in discussing it here.

No, with Rust i was so immediately taken with the Iterator trait and the ease of creating Vecs and HashSets and so forth with .collect() that i spent a large amount of thought while ramping up with the first several problems so that my processing of the input could go something like

fn process(input: &str) -> u32 {
	input.lines()
	    .map(|line| { ... })
	    // ...
	    .fold(...)
}

I write more procedurally in Zig (which doesn't have first-class support for "generic" iteration processing like map or fold or first-class closures), which I think is an instance of a Zig hard edge that improves correctness (more on this another time, I guess), but Rust's affordance for it taught me a lot in terms of rigorous thinking about scope and clarity of purpose: each iterator chain exists to transform an input to an output—it doesn't have access the full input or other context unless you correctly make that available to it. (Correctly in the sense of the borrow checker.) Paradoxically, even though process is provided the full file as input, this impl Iterator code structure also promotes a "streaming" mentality for processing the data; I find I don't create more than is actually necessary.

By the way, I’d argue that passing the entire file contents to this function is always correct: Advent of Code text files are small, even when they stretch into the kilobytes—that's a small number in comparison to my total RAM, I try to keep in mind. Additionally, the input parameter introduces the correct “code seam” (thanks Nicole Watts for a beautiful new-to-me metaphor!) for testing your solution.

Containers? Use ’em

That's kind of the high-minded thing Rust taught me. The other thing I learned via doing Advent of Code in Rust is feeling comfortable using the containers it provides. Rust makes this easier than Zig as of 0.13 on a name level—if you want a growable array of objects, all of type T, what you want is a Vec<T>. If you want to start with a collection of objects, you can construct one with the vec! macro. If you want to deduplicate a list, what you want is a HashSet<T>, or if you want to associate keys to values, you want a HashMap<K,V>. The Vec type is so common it's imported into every Rust scope, but making HashSet and HashMap available to you is not difficult.

Zig does great on this front, actually; it has great default implementations of all of these container types. They're just named poorly. One instance of poor name choices is already being corrected for Zig 0.14. I'll save discussing that for later. First, I'd like to argue for another change towards better defaults.

In Zig, here is the signature of std.HashMap:

pub fn HashMap(comptime K: type, 
	comptime V: type, 
	comptime Context: type, 
	comptime max_load_percentage: u64,
) type { ... }

(Yes, that's a function. In Zig, to create a type that depends on another type, y ou write a function which takes in a parameter like comptime T: type and returns a type. This saves you from having to write generics using a thornier sublanguage instead of regular Zig.)

The Context type is responsible for actually hashing keys of type K and determining when two keys are the same. You can write a Context type yourself without crying too much; for Advent of Code 2023, I did—for the simple and sad reason that this type has the best name, while the type that actually deserves the best name does not.

As of Zig 0.13, I will confidently assert that the type you want maybe 90% of the time you reach for a std.HashMap is actually one of std.AutoHashMapUnmanaged(K, V), std.AutoArrayHashMapUnmanaged(K, V), or in the particular case of string keys, std.StringHashMapUnmanaged or std.StringArrayHashMapUnmanaged.

The Unmanaged issue, as I alluded to earlier, is being fixed already. If the issue of the Auto prefix is not already being changed, I'd like to propose that it should be.

Here Auto means "use a best guess at a default hashing function". (Array means store keys and values contiguously so that iterating over them is fast and ergonomic. I read somewhere that even iterating once is enough to justify reaching for this type.) It's great that Zig allows you to swap out the default (or even std-provided) methods for hashing with your own. The "ground" types HashMapUnmanaged and ArrayHashMapUnmanaged are well thought through in terms of API design. My issue with them is that for a beginner, they shadow the correct type to reach for first.

I propose that current std.HashMap should become std.HashMapWithContext and that std.AutoHashMap should become std.HashMap. I'm happy to defer to the core team's expertise on how to manage the transition period.

Now, to be sure, the core of this proposal could be summarily dismissed as a "skill issue". On the one hand, reading documentation or the std library code quickly reveals the existence of the Auto... types. And on the other, learning to write reasonably useful hashing functions is a skill that will serve a budding programmer well.

I think this dismissal is a mistake. In my personal experience, Zig's extremely legible standard library code and thoughtful approach to default implementations has helped me grow as a programmer in ways I never anticipated. By providing friction in the right places, the language has steered me towards better design and more correct code. In this particular instance, I think juice, while worth an eventual squeeze, might come at an off-putting price for a beginner. To wit, I didn't learn to comfortably reach for hash maps from Zig; I learned it from Rust.

This is more of an addendum, but I'd like to also propose the addition of std.HashSet(T) as well, as in #6919. My reason for doing so, though, is different. For example, I would be happy to see a simple implementation like

pub fn std.HashSet(K) type {
    return std.ArrayAutoHashMapUnmanaged(K, void);
}

The reason I would like to ask for this addition to the standard library is not functional but pedagogical: again, realizing that you can implement a HashSet type by creating a HashMap type with a zero-sized value type is a beautiful realization that I don't want to deny a beginner Zig programmer; the challenge is that coming to that realization on one's own is nontrivial.

Managed vs. Unmanaged and ArrayLists

You could be forgiven for thinking that Vec<T> translates to Zig's @Vector—that's Rust's (really C++'s) fault; choosing the name Vec for this data structure was an awful mistake. It's also such an old one that I can't hold it against Rust. Zig's current answer is std.ArrayList(T). I don't mind it as a name: "Array" to me signals contiguity, while "List" suggests that you can grow it. The problem is that actually you really want std.ArrayListUnmanaged(T). There's room for difference of opinions on this, but here are three reasons that convinced me of this:

Initialization

You can default-initialize std.ArrayListUnmanaged(T), as in

var list: std.ArrayListUnmanaged(T) = .{};

Actually, with Zig's upcoming "decl literal" syntax, it becomes preferred to write something like .empty instead of .{}. The reason to prefer this over .{} is that making it possible to initialize a struct of type S with .{} requires you to set default values for all of the fields of S; but std.ArrayListUnmanaged(T) has two fields, items and capacity, and it is a mistake to override one default value without also setting the other.

Since Zig has no "default" allocator, std.ArrayList(T) must either be initialized completely by hand or by calling init(allocator). If you compose a larger struct by including a std.ArrayList(T), that means you cannot default-init your larger struct either and must write an init function.

Size

@sizeOf(std.ArrayList(T) == 5 * @sizeOf(usize), while @sizeOf(std.ArrayListUnmanaged(T)) == 3 * @sizeOf(usize). This is because std.ArrayList(T) takes possession of a std.mem.Allocator object, which it uses to manage its allocation as you interact with the ArrayList, while std.ArrayListUnmanaged does not, instead requiring you to pass the same Allocator as an argument each time you execute a call which could allocate or deallocate memory.

I mistakenly thought that in Rust, which uses the borrow checker to manage memory for you, Vec<T> has size equal to only 2 * @sizeOf(usize), which would be ideal for a type you'd like to pass around a lot. It appears that actually by default it has the same size as std.ArrayListUnmanaged. Some other Rust containers like those in the ecow crate do manage this by hiding both the capacity field (and the Allocator, when you're using one with positive size) inside its heap allocation. I don’t think Zig should adopt this sleight of hand for the standard container type.

Optimizability

I've read—although here I have to joyfully confess my lack of expertise—that making the Allocator a parameter as opposed to a field allows the LLVM backend (which as of 0.13 is the main way Zig produces machine code) to "devirtualize" the allocation calls.

Here's my understanding of what that means: in Zig, a std.mem.Allocator is a type-erased interface for a number of different approaches to allocation, in much the same way that objects in an object-oriented programming language like C++ or Java might conform to an "interface" (or the way the Rust compiler will generate code for you if you pass something as Box<dyn Trait>).

Zig doesn't have first-class interfaces or traits; instead std.mem.Allocator follows a "pointer + vtable" pattern (making std.mem.Allocator a type that sometimes goes by the name "fat pointer"). If you open Allocator.zig in Zig's standard library, you'll see that the definition of an Allocator type has two fields, which I'll summarize as:

pub const Allocator = struct {
	ptr: *anyopaque,
	vtable: *const VTable,

	pub const VTable = struct {
	    alloc: *const fn // …,
	    resize: *const fn // …,
	    free: *const fn // …,
    };
};

That is, Allocator has two fields: ptr and vtable. Both of these are pointers; ptr to an unspecified type (anyopaque) and vtable to a const VTable. If you look at the definition of VTable, which I've abridged above, you'll see that it contains only function pointers; the methods on the Allocator struct call through these function pointers to actually do the allocation work. When you set up an Allocator in Zig, it's typically a two-step process. For example, most of my Advent of Code solutions (actually, most of my Zig programs full stop) begin with the following lines:

var gpa: std.heap.GeneralPurposeAllocator(.{}) = .{};
defer _ = gpa.deinit();
const allocator = gpa.allocator();

The gpa variable must be var rather than const because allocator() captures a mutable pointer to it—under the hood, the allocator() function looks something like this

pub fn allocator(self: *@This()) std.mem.Allocator {
	return .{
		.ptr = self,
		// yes, we are returning a pointer 
		// to what appears to be a local variable!
		// this is fine because the contents of the literal
		// are completely known at compile time,
		// so the literal actually has a static lifetime.
		.vtable = &.{
			// these are functions implemented in 
			// general_purpose_allocator.zig
			.alloc = alloc,
			.resize = resize,
			.free = free,
		},
	};
}

I'm told (although I have to continue to joyfully confess that I am not an expert!) that calling functions through function pointers can be expensive. This makes sense—you have to prepare the computer to jump to an essentially arbitrary section of code to run, whereas with a "normal" function call, you know where you're going already.

Now, there are ways to mitigate this expense: one of them is "devirtualization", which as far as I understand means that if the compiler knows that the function pointer is always pointing to the same place in code, when it optimizes, it can replace the "virtual" function call with a "normal" one.

The point is that for std.ArrayListUnmanaged(T), the compiler is far more likely to be able to come to this conclusion: because the Allocator only ever appears as a function parameter (and function parameters are always const in Zig), the chances of the compiler realizing that it never changes are much higher, since you cannot change fields of a const struct, and you cannot reach through and change values on the other side of the *const VTable either. But for std.ArrayList(T), if you take (as you must) a mutable pointer to the ArrayList, suddenly, while it is not possible for you to change values on the other side of *const VTable, you can change out that *const VTable for another one wholesale. There's no reason you would, and I doubt that anyone does, but the possibility is more likely to make the compiler go "nah, too risky, I can't devirtualize that".