The power and complexity of **Comptime** in Zig

Ed Yu (@edyu on Github and

@edyu on Twitter)

January.17.2024

## Introduction

**Zig** is a modern systems programming language and although it claims to a be a **better C**, many people who initially didn't need systems programming were attracted to it due to the simplicity of its syntax compared to alternatives such as **C++** or **Rust**.

However, due to the power of the language, some of the syntaxes are not obvious for those first coming into the language. I was actually one such person.

Today we will explore a unique aspect of metaprogramming in **Zig** that sets it apart from other similarly low-level languages -- `comptime`

.

I've already written an earlier article on `comptime`

but today I want to explore an example using a simplified version of erasure coding that I've implemented using **Zig** with extensive use of `comptime`

.

Due to the length of the code example, I'll explain the code in a series of articles and eventually even compare it to an Odin implementation.

## WTF is Comptime

I gave an overview of **Zig** `comptime`

in WTF Zig Comptime. In short, `comptime`

is a way to designate either a variable or a piece of code such as a block or a function as something to be run at compile time as opposed to runtime.

The first benefit of running a these `comptime`

code at `comptime`

is so that the results of `comptime`

are essentially constants that can be used directly by the compiled program. As a result, `comptime`

does not use runtime resources for these any results.

One example is the same `factorial`

code I showed in WTF Zig Comptime. In such a case, even if I pass in a large number *n*, which takes a long time to calculate at `comptime`

, during runtime it's just another constant.

By using a `comptime`

variable, I still have the flexibility to change the number anytime and just recompile the program to recalculate the correct result.

```
pub fn factorial(comptime n: u8) comptime_int {
var r = 1; // no need to write it as comptime var r = 1
for (1..(n + 1)) |i| {
r *= i;
}
return r;
}
const v = comptime factorial(120);
```

The other benefit is actually due to necessity of metaprogramming. One of the primary reasons to use metaprogramming is to allow for different behaviors for different types.

Because you have to know precisely how much memory to allocate at compile time, **Zig** types must be complete at compile type. What it means is that if you want to use a *type function* (once again, see WTF Zig Comptime) to create different types based on some variable you pass, that variable must be comptime.

One example is say you want to create a matrix type and that a matrix type of *3 x 3* should be completely separate from a matrix type of *4 x 4* in that you cannot simply treat them in the same way. However, you do want to use the same *type function* to create both matrices, then you must declare the *n* in *n x n* matrix as a `comptime`

variable that you pass in.

```
// a square matrix is a matrix where number_of_rows == number_of_cols
pub fn SquareMatrix(comptime n: comptime_int) type {
return struct {
allocator: std.mem.Allocator,
comptime numRows: u8 = n,
comptime numCols: u8 = n,
const Self = @This();
pub fn init(allocator: std.mem.Allocator) Self {
return .{
.allocator = allocator,
}
}
// other methods
}
}
```

## WTF is Erasure Coding

Now, with the introduction out of the way, let's talk about Erasure Coding.

Erasure Coding is a way to split up your data in multiple pieces (shards) so that if you lose one or more of the pieces, you can still retrieve the original data. If you think this sounds like duplication or replication, or even RAID, then you are somewhat correct. The difference is that in a simple replication (or RAID 1), you make complete copies of the data so that if you make 2 copies of the data, you have a total of 3 copies (including the original copy) and that as long as you don't lose all 3 copies, you can get the data back. In a more complex RAID setup such as RAID 5, data is split across (stripe) multiple disks and then additional parity blocks are added to tolerate disk loss. However, in the case of RAID 5, you can tolerate 1 disk loss, whereas RAID 6 can tolerate up to 2 disk failures.

In Erasure Coding, you transform the data while you split the data so that the copies are not necessarily the same. You still need a minimum number of copies to reconstruct the original data and as long as you don't lose more than such minimal number, you can reconstruct the data.

We typically describe Erasure Coding with 2 numbers of N and K where N is the total number of shards, and K is the minimum number of shards you need in order to reconstruct the data. For instance, in a (5, 3) Erasure Coding, N is 5 and K is 3, you need 3 of the 5 shards in order to reconstruct the data. In other words, you can tolerate the loss of up to (N - K) = 2 shards.

What makes Erasure Coding better than a simple replication is that you save more disk spaces by using Erasure Coding compared to simple replication.

In a quick test, using a file of 680 bytes, if I make 2 additional copies, the total storage needed is 680 * 3 = 2040 bytes. If instead I use my **Zig** Erasure Coding, I need 5 copies of 240 bytes each which means the total storage needed is 240 * 5 = 1020 bytes. The total saving in storage comparing the two is (2040 - 1020) / 2040 = 50%.

Of course the storage saving is not free as there is extra computation involved both in encoding (splitting the original data to shards) and decoding (reconstruct the data from shards).

## Erasure Code Example

The example Erasure Coding is based upon Erasure Coding For The Masses by Dr. Vishesh Khemani.

The method described is not the most efficient Erasure Coding but it's easy to understand and I really liked how Dr. Vishesh Khemani used simple finite field arithmetic to describe Erasure Coding. finite field arithmetic to describe Erasure Coding.

## Finite (Binary) Field Arithmetic

If you are mathmetically inclined, you are certainly welcome to read the Wikipedia article or in particular binary fields. I'm not but I'll try my best to give a simple explanation of binary fields from a programmer's perspective.

When you have a finite field, you are basically doing modular maths, which basically means that you have to take the modulo of the modulus (usually 1 more than then largest allowed number). For example, for a finite field of 3, you only have `[0, 1, 2]`

as valid numbers, the **modulus** is 3 (1 more than the largest number which is 2). So if you add 1 and 2 together, you normally would get 3 without modular arithmetic but because it's modulo maths, you have to modulo 3 which is `3 mod 3 = 0`

. For us programmers, this is very similar to how a ring buffer works.

In the case of binary fields, the maths is even easier as you only have `[0, 1]`

as valid numbers and addition is really just `XOR`

because *1 + 1 = 2 mod 2 = 0 = 1 XOR 1*. What's even cooler is that because *-1 = 1 mod 2* (try going counter-clockwise on your ring buffer), we can do subtraction just as we do addition because *n - 1 = n + (-1) = n + 1*.

## Code: matrix.zig

Ok, that's probably too much maths already. Let's go back to the code example.

The first code I want to describe is an implementation of *m x n* matrix where *m* is the number of rows and *n* is the number of columns.

I decided to use *type function* to return the matrix type because I wanted to make sure the compiler can enforce that a *3 x 2* matrix is different from a *2 x 3* matrix.

The way to do so is to pass in both *m* and *n* as `comptime`

variables to the *type function*.

```
pub fn Matrix(comptime m: comptime_int, comptime n: comptime_int) type {
return struct {
allocator: std.mem.Allocator = undefined,
mdata: std.ArrayList(u8) = undefined,
mtype: DataOrder = undefined,
comptime numRows: u8 = m,
comptime numCols: u8 = n,
const Self = @This();
// followed by type methods
}
}
```

Do note that I ended up saving *m* and *n* as fields inside the `Matrix(m, n)`

type as `numRows`

and `numCols`

. **Zig** doesn't require you to only access fields as methods and by exposing them as fields, I can use `mat.numRow`

and `mat.numCols`

directly if `mat`

is a `Matrix(m, n)`

. I do have to designate both `numRows`

and `numCols`

as `comptime`

in order to store *m* and *n*.

The code should be fairly straightforward but I do want to explain why I have an `enum`

called `DataOrder`

. The internal data format is an array using `ArrayList`

called `mdata`

. Typically, you can store a 2D matrix as 1D vector (or `ArrayList`

in **Zig**) either in row-major or column-major order. The original reason to have `DataOrder`

is so that I can have the flexibility to store the matrix data in either order and then `transpose`

is really just changing the `mtype`

from one to the other.

In the end, not only I ended up not needing such flexibiltiy, but it made my code much more complicated. I kept it there mostly as a reminder to myself to not do premature optimization.

```
Premature Optimization is the root of all evil
-- Donald Knuth
```

One artifact of such *complication* is that `getSlice()`

returns a vector based on whether the matrix is stored internally in row-major or colume-major. The burden is on the caller to keep track of of the `DataOrder`

because the caller is the one that initialized the matrix. Of course, `getRow()`

and `getCol()`

are exposed and preferred.

```
// return eithers a row or a column based on matrix data order
// use getRow() or getCol() if you want row/col regardless of data order
pub fn getSlice(self: *const Self, rc: usize) []u8 {
switch (self.mtype) {
.row => {
std.debug.assert(rc < m);
const i = rc * n;
return self.mdata.items[i .. i + n];
},
.col => {
std.debug.assert(rc < n);
const i = rc * m;
return self.mdata.items[i .. i + m];
},
}
}
```

The reverse `setSlice()`

has similar logic and in the end, I'm not sure whether the *optimization* is ever needed. Once again, it's probably better to not go through such complication and just expose `setRow()`

and `setCol()`

instead.

```
fn setSlice(self: *Self, rc: usize, new_rc: []const u8) void {
switch (self.mtype) {
.row => {
std.debug.assert(rc < m and new_rc.len >= n);
const i = rc * n;
self.mdata.replaceRange(i, n, new_rc[0..n]) catch return;
},
.col => {
std.debug.assert(rc < n and new_rc.len >= m);
const i = rc * m;
self.mdata.replaceRange(i, m, new_rc[0..m]) catch return;
},
}
}
```

## Code: finite_field.zig

Finally, we can look at the code for binary fields. The finite_field.zig exposes the n of finite field p^n^ as `n`

using `comptime`

: Because we only care about binary finite fields, `p`

is always 2 and doesn't needed to specifically passed in.

```
pub fn BinaryFiniteField(comptime n: comptime_int) type {
return struct {
exp: u8 = undefined,
order: u8 = undefined,
divisor: u8 = undefined,
// more code
}
}
```

The `init()`

method mostly initializes the 3 numbers needed later. The `exp`

is just the `n`

passed in. Note that because of the use case and my lack of advanced mathematics knowledge, I only care about `n >= 1 and n <= 7`

. This also made it easier for calculating the `order`

because `u8`

is enough to left shift 1 based on the `n`

. The `divisor`

are primes that are results of using 2 as `x`

in the comments. Leave in the comments if you know the maths and want to explain to other readers why that's the case.

```
pub fn init() ValueError!Self {
var d: u8 = undefined;
// Irreducible polynomial for mod multiplication
d = switch (n) {
1 => 3, // 1 + x ? undef shift(0b11)=2
2 => 7, // 1 + x + x^2 shift(0b111)=3
3 => 11, // 1 + x + x^3 shift(0b1011)=4
4 => 19, // 1 + x + x^4 shift(0b10011)=5
5 => 37, // 1 + x^2 + x^5 shift(0b100101)=6
6 => 67, // 1 + x + x^6 shift(0b1000011)=7
7 => 131, // 1 + x + x^7 shift(0b10000011)=8
else => return ValueError.InvalidExponentError,
};
return .{
.exp = @intCast(n),
.divisor = d,
.order = @as(u8, 1) << @intCast(n),
};
}
```

The number `order`

is the 1 + the maximum allowed number in the fields. For example, if *n* is 3, the field cannot contain any number greater than 10.

```
pub fn validated(self: *const Self, a: usize) ValueError!u8 {
if (a < self.order) {
return @intCast(a);
} else {
return ValueError.InvalidNumberError;
}
}
```

## Addition and Subtraction

Recall that for binary fields, addition is just `exclusive OR`

.

```
pub fn add(self: *const Self, a: usize, b: usize) ValueError!u8 {
return try self.validated((try self.validated(a)) ^ (try self.validated(b)));
}
```

Also, negation is simply the number itself and subtraction is just addition of the negation.

```
pub fn neg(self: *const Self, a: usize) ValueError!u8 {
return try self.validated(a);
}
pub fn sub(self: *const Self, a: usize, b: usize) ValueError!u8 {
return try self.add(a, try self.neg(b));
}
```

## Multiplication

Multiplication is probably the most complicated of all the methods except in the case of *n* is 1.

```
pub fn mul(self: *const Self, a: usize, b: usize) ValueError!u8 {
if (self.exp == 1) {
return self.validated(try self.validated(a) * try self.validated(b));
}
// n > 1
const x = try self.validated(a);
const y = try self.validated(b);
var result: u16 = 0;
for (0..8) |i| {
const j = 7 - i;
if (((y >> @intCast(j)) & 1) == 1) {
result ^= @as(u16, x) << @intCast(j);
}
}
while (result >= self.order) {
// count how many binary digits result has
var j = countBits(result);
j -= self.exp + 1;
result ^= @as(u16, self.divisor) << @intCast(j);
}
return try self.validated(result);
}
```

It requires a function to count the number of binary digits of a number. There is probably a much better way to figure this out in **Zig** but since I don't know, I just implemented a naive solution. Leave a comment if you know a better way.

```
fn countBits(num: usize) u8 {
var v = num;
var c: u8 = 0;
while (v != 0) {
v >>= 1;
c += 1;
}
return c;
}
```

## Division

Division is simply the multiplication of the inverse.

```
pub fn div(self: *const Self, a: usize, b: usize) ValueError!u8 {
return try self.mul(a, try self.invert(b));
}
```

However, finding the inverse of a number is more complicated than negation. We do have to check whether the number is 0 first, hence no inverse. We then find the inverse using brute force by trying every number within the `order`

to see whether the result is 1 because `b`

is the inverse of `a`

if and only if `a * b == 1`

. Once again, if you have a better way, leave a comment.

```
pub fn invert(self: *const Self, a: usize) ValueError!u8 {
if (try self.validated(a) == 0) {
return ValueError.NoInverseError;
}
for (0..self.order) |b| {
if (try self.mul(a, b) == 1) {
return try self.validated(b);
}
}
return ValueError.NoInverseError;
}
```

## Matrix Representation

The final 3 methods are used to find the *n x n* matrix representation for a number in the field. This is also the primary reason why we had to implement a matrix. The main idea is to separate the number into its basis based on the polynormials mentioned in the comments of `init()`

.

```
fn setCol(m: *mat.Matrix(n, n), c: usize, a: u8) void {
for (0..n) |r| {
const v = (a >> @intCast(r)) & 1;
m.set(r, c, v);
}
}
fn setAllCols(self: *const Self, m: *mat.Matrix(n, n), a: usize) !void {
var basis: u8 = 1;
for (0..n) |c| {
const p = try self.mul(a, basis);
basis <<= 1;
setCol(m, c, p);
}
}
// n x n binary matrix representation
pub fn toMatrix(self: *const Self, allocator: std.mem.Allocator, a: usize) !mat.Matrix(n, n) {
var m = try mat.Matrix(n, n).init(allocator, mat.DataOrder.row);
try self.setAllCols(&m, a);
return m;
}
```

## Bonus

By adding a function called `format`

to matrix.zig, it's much easier to print out the matrix in debugging calls such as `std.debug.print`

because **Zig** would implicitly check whether such method exists for the `struct`

and use it to format the output. As such I can just call `std.debug.print("{}", mat)`

if `mat`

is of type `Matrix(m, n)`

.

```
pub fn format(self: *const Self, comptime _: []const u8, _: std.fmt.FormatOptions, stream: anytype) !void {
switch (self.mtype) {
.row => {
try stream.print("\n{d}x{d} row ->\n", .{ m, n });
for (0..m) |r| {
for (0..n) |c| {
try stream.print("{d} ", .{self.get(r, c)});
}
try stream.print("\n", .{});
}
},
.col => {
try stream.print("\n{d}x{d} col ->\n", .{ m, n });
for (0..n) |c| {
for (0..m) |r| {
try stream.print("{d} ", .{self.get(r, c)});
}
try stream.print("\n", .{});
}
},
}
}
```

## The End

You can read my part 1 at WTF Zig Comptime.

The inspiration of the code is from Erasure Coding For The Masses.

You can find the code for the article here.

The full erasure coding code is here.

## Latest comments (0)