Zig Coding Adventures: ripgrep rip-off

One tool I rely on heavily in my day-to-day is ripgrep. The main way I use it is to search for a string in Dialpad's repositories to find where a function, class, etc. is declared or implemented. It's much faster than relying on the poor language server in a multi-million-line codebase. In my journey to learn Zig and complete the Ziglings exercises, I decided to have a go at creating a simpler version of ripgrep: all it will do is recursively search directories and return which files contain a search term. The simplest possible version of this program is quite quick to implement:

const std = @import("std");

pub fn main(init: std.process.Init) !void {
    const io = init.io;
    const args = try init.minimal.args.toSlice(init.arena.allocator());
    if (args.len != 3) {
        std.debug.print("Usage: {s} <needle> <directory>\n", .{args[0]});
        return;
    }
    const needle = args[1];
    if (needle.len == 0) return;
    const dir_path = args[2];
    var dir = std.Io.Dir.cwd().openDir(init.io, dir_path, .{
        .iterate = true,
    }) catch |err| {
        std.debug.print("Error: cannot open directory '{s}': {s}\n", .{ dir_path, @errorName(err) });
        return;
    };
    defer dir.close(io);

    var walker = try dir.walk(init.gpa);
    defer walker.deinit();

    var output_buffer: [4096]u8 = undefined;
    var output = std.Io.File.stdout().writerStreaming(io, &output_buffer);

    while (try walker.next(io)) |entry| {
        if (entry.kind != .file) continue;

        const haystack = entry.dir.readFileAlloc(
            io,
            entry.basename,
            init.gpa,
            .unlimited,
        ) catch |err| {
            std.debug.print("Error: cannot open file '{s}': {s}\n", .{ entry.path, @errorName(err) });
            return;
        };
        defer init.gpa.free(haystack);

        if (std.mem.indexOf(u8, haystack, needle) != null) {
            const path = try std.Io.Dir.path.join(
                init.gpa,
                &.{ args[2], entry.path },
            );
            defer init.gpa.free(path);

            try output.interface.print("{s}\n", .{path});
            try output.interface.flush();
        }
    }

}

To benchmark this code (and the ones below), I ran the built binary using ReleaseFast on the Zig library tree. My system is an AMD Ryzen 9 5950X, running Linux kernel 7.2.9, with Zig 0.16.0. I used three warmup runs followed by 20 measured runs per command, shuffling the command order each round and redirecting stdout to /dev/null. Elapsed time is the mean $\pm$ one standard deviation, including process startup. CPU time is the mean user plus system time across all threads. Peak RSS is the largest resident-memory peak observed across the 20 runs.

For the baseline:

The performance of this is quite bad, as we are walking a directory tree and when we reach a file we synchronously allocate memory onto the heap and copy the file contents into the buffer, then scan said buffer using the Boyer-Moore-Horspool algorithm. This workload is a great candidate for an asynchronous architecture and a search optimization: using SIMD instructions. Zig makes this easy as both are part of the wonderful standard library!

We will use two sets of workers: TraversalWorkers, which feed a WorkQueue (a custom queue implementation that enables parallel directory traversal; we'll get into this later) and a FileQueue, which will contain paths of files for our SearchWorkers, which will perform streaming reads into their own internal buffers and run our search implementation. Let's start by parallelizing our previous implementation:

const std = @import("std");

const jobs = 4;
const chunk_size = 1 << 20;
const max_needle_len = 128;
const paths_per_batch = 8;
const queued_batches = 64;
const DirectoryQueue = WorkQueue([]const u8);
// std.Io.Queue is thread safe!
const FileQueue = std.Io.Queue(PathBatch);

pub fn main(init: std.process.Init) !void {
    const io = init.io;
    const allocator = init.gpa;
    const args = try init.minimal.args.toSlice(init.arena.allocator());
    if (args.len != 3) {
        std.debug.print("Usage: {s} <needle> <directory>\n", .{args[0]});
        return;
    }
    if (args[1].len == 0) return;
    if (args[1].len > max_needle_len) return error.NeedleTooLong;

    // Each worker reuses its own 1 MiB buffer, plus space for a partial match.
    // Workers finish or are canceled before this allocation is freed.
    const buffer_size = chunk_size + max_needle_len - 1;
    const buffers = try allocator.alloc(u8, jobs * buffer_size);
    defer allocator.free(buffers);

    var output_buffer: [4096]u8 = undefined;
    var output: Output = .{
        .writer = std.Io.File.stdout().writerStreaming(io, &output_buffer),
    };

    // Initialize both queues and free any remaining paths during cleanup.
    var directory_queue = DirectoryQueue.init(allocator);
    defer {
        while (directory_queue.drain()) |path| allocator.free(path);
        directory_queue.deinit();
    }
    var file_storage: [queued_batches]PathBatch = undefined;
    var file_queue: FileQueue = .init(&file_storage);
    defer {
        file_queue.close(io);
        while (file_queue.getOneUncancelable(io)) |batch| {
            batch.deinit(allocator);
        } else |_| {}
    }
    var state: State = .{
        .allocator = allocator,
        .directories = &directory_queue,
        .files = &file_queue,
    };
    {
        // Give the directory queue its own copy of the root path.
        const root = try allocator.dupe(u8, args[2]);
        errdefer allocator.free(root);
        try directory_queue.submit(io, root);
    }

    // A Group tracks tasks that we await or cancel together.
    // cancel requests cancellation and waits for workers to finish before
    // cleanup frees their shared state. See the async Ziglings exercises
    var search_workers: std.Io.Group = .init;
    defer search_workers.cancel(io);
    {
        // After traversal finishes, close the file queue. Searches can drain
        // its remaining batches before getOne returns error.Closed.
        defer file_queue.close(io);
        var traversal_workers: std.Io.Group = .init;
        defer traversal_workers.cancel(io);
        // Group.concurrent starts a task in the group. Unlike async, it guarantees concurrency
        // or returns error.ConcurrencyUnavailable. Consumers can therefore make
        // progress while producers wait for queue space.
        for (0..jobs) |i| {
            try search_workers.concurrent(io, SearchWorker.run, .{SearchWorker{
                .io = io,
                .state = &state,
                .needle = args[1],
                .buffer = buffers[i * buffer_size ..][0..buffer_size],
                .output = &output,
            }});
        }
        for (0..jobs) |_| {
            try traversal_workers.concurrent(io, TraversalWorker.run, .{TraversalWorker{
                .io = io,
                .state = &state,
            }});
        }
        // await waits for every task in the group to finish.
        try traversal_workers.await(io);
    }
    try search_workers.await(io);
    if (state.failure) |err| return err;
}

The workers share the queues, failure state, and output writer:

// Bundle up to eight paths per queue item to reduce queue operations and
// internal mutex acquisitions per file, reducing opportunities for contention.
// The consumer frees the batch's paths after processing.
const PathBatch = struct {
    paths: [paths_per_batch][]const u8 = undefined,
    len: usize = 0,

    fn deinit(self: *const PathBatch, allocator: std.mem.Allocator) void {
        for (self.paths[0..self.len]) |path| allocator.free(path);
    }
};

// Share the queues and record the first failure under a mutex.
const State = struct {
    allocator: std.mem.Allocator,
    directories: *DirectoryQueue,
    files: *FileQueue,
    // Release stores and acquire loads synchronize the stop flag across workers.
    stopped: std.atomic.Value(bool) = .init(false),
    failure_mutex: std.Io.Mutex = .init,
    failure: ?anyerror = null,

    fn fail(self: *State, io: std.Io, err: anyerror) void {
        self.failure_mutex.lockUncancelable(io);
        if (self.failure == null) self.failure = err;
        self.stopped.store(true, .release);
        self.failure_mutex.unlock(io);
        // Wake blocked workers so they can stop on failure.
        self.directories.close(io);
        self.files.close(io);
    }
};

// Protect the shared writer with a mutex so complete lines stay together.
const Output = struct {
    mutex: std.Io.Mutex = .init,
    writer: std.Io.File.Writer,
    failed: bool = false,

    fn print(output: *Output, io: std.Io, comptime format: []const u8, args: anytype) !void {
        try output.mutex.lock(io);
        defer output.mutex.unlock(io);
        if (output.failed) return error.WriteFailed;
        errdefer output.failed = true;
        try output.writer.interface.print(format, args);
        try output.writer.interface.flush();
    }
};

The search workers consume file batches and reuse their buffers across files. This uses the streaming loop from zwhere, with std.mem.indexOf for now and the example's existing error propagation:

// Consume file batches and perform the search
const SearchWorker = struct {
    io: std.Io,
    needle: []const u8,
    buffer: []u8,
    output: *Output,
    state: *State,

    fn run(self: SearchWorker) std.Io.Cancelable!void {
        self.runTasks() catch |err| {
            self.state.fail(self.io, err);
            if (err == error.Canceled) return error.Canceled;
        };
    }

    fn runTasks(self: SearchWorker) !void {
        while (!self.state.stopped.load(.acquire)) {
            const batch = self.state.files.getOne(self.io) catch |err| switch (err) {
                error.Closed => return,
                else => return err,
            };
            defer batch.deinit(self.state.allocator);
            for (batch.paths[0..batch.len]) |path| {
                if (self.state.stopped.load(.acquire)) return;
                try self.searchFile(path);
            }
        }
    }

    fn searchFile(self: SearchWorker, file_path: []const u8) !void {
        const io = self.io;
        const overlap = self.needle.len - 1;
        const file = try std.Io.Dir.cwd().openFile(io, file_path, .{
            .mode = .read_only,
        });
        defer file.close(io);

        var carry: usize = 0;
        while (!self.state.stopped.load(.acquire)) {
            // Read after any bytes retained from the previous chunk.
            const n = file.readStreaming(io, &.{self.buffer[carry .. carry + chunk_size]}) catch |err| switch (err) {
                error.EndOfStream => return,
                else => return err,
            };
            // A zero-byte read is not necessarily EOF in std.Io.
            if (n == 0) continue;

            const haystack = self.buffer[0 .. carry + n];
            if (std.mem.indexOf(u8, haystack, self.needle) != null) {
                try self.output.print(io, "{s}\n", .{file_path});
                return;
            }

            // Keep up to needle.len - 1 bytes so matches spanning reads are found.
            // copyForwards also handles overlapping source and destination slices.
            carry = @min(overlap, haystack.len);
            std.mem.copyForwards(u8, self.buffer[0..carry], haystack[haystack.len - carry ..]);
        }
    }
};

The traversal workers supply those batches and submit any subdirectories to the directory queue:

// Queue discovered subdirectories and send batches of file paths to searches.
const TraversalWorker = struct {
    io: std.Io,
    state: *State,

    fn run(self: TraversalWorker) std.Io.Cancelable!void {
        self.runTasks() catch |err| {
            self.state.fail(self.io, err);
            if (err == error.Canceled) return error.Canceled;
        };
    }

    fn runTasks(self: TraversalWorker) !void {
        while (try self.state.directories.next(self.io)) |path| {
            defer self.state.directories.done(self.io);
            defer self.state.allocator.free(path);
            try self.walkDirectory(path);
        }
    }

    fn flush(self: TraversalWorker, batch: *PathBatch) !void {
        if (batch.len == 0) return;
        try self.state.files.putOne(self.io, batch.*);
        batch.len = 0;
    }

    fn walkDirectory(self: TraversalWorker, dir_path: []const u8) !void {
        const io = self.io;
        const allocator = self.state.allocator;
        var dir = try std.Io.Dir.cwd().openDir(io, dir_path, .{
            .iterate = true,
        });
        defer dir.close(io);

        var iterator = dir.iterateAssumeFirstIteration();

        var batch: PathBatch = .{};
        defer batch.deinit(allocator);
        while (!self.state.stopped.load(.acquire)) {
            const entry = (try iterator.next(io)) orelse break;
            if (entry.kind != .directory and entry.kind != .file) continue;

            const full_path = try std.Io.Dir.path.join(allocator, &.{ dir_path, entry.name });
            if (entry.kind == .directory) {
                errdefer allocator.free(full_path);
                try self.state.directories.submit(io, full_path);
            } else {
                batch.paths[batch.len] = full_path;
                batch.len += 1;
                if (batch.len == paths_per_batch) try self.flush(&batch);
            }
        }
        if (!self.state.stopped.load(.acquire)) try self.flush(&batch);
    }
};

The directory queue tracks both queued and active tasks so workers know when traversal is finished:

// Use a growing deque for directories as a bounded queue could deadlock if every
// traversal worker were waiting to enqueue more directories. We also track queued plus
// active tasks because an empty queue does not mean traversal is finished
fn WorkQueue(comptime Task: type) type {
    return struct {
        const Self = @This();
        allocator: std.mem.Allocator,
        tasks: std.Deque(Task) = .empty,
        // Protect the deque, pending count, and closed flag.
        mutex: std.Io.Mutex = .init,
        // Let idle workers wait without polling.
        // https://ziglang.org/documentation/0.16.0/std/#std.Io.Condition
        available: std.Io.Condition = .init,
        pending: usize = 0, // Queued plus currently executing tasks.
        closed: bool = false,

        pub fn init(allocator: std.mem.Allocator) Self {
            return .{ .allocator = allocator };
        }

        pub fn deinit(self: *Self) void {
            self.tasks.deinit(self.allocator);
        }

        pub fn drain(self: *Self) ?Task {
            return self.tasks.popFront();
        }

        pub fn submit(self: *Self, io: std.Io, task: Task) !void {
            try self.mutex.lock(io);
            defer self.mutex.unlock(io);
            if (self.closed) return error.Closed;
            try self.tasks.pushBack(self.allocator, task);
            self.pending += 1;
            // Wake one worker to handle the new task.
            self.available.signal(io);
        }

        pub fn next(self: *Self, io: std.Io) !?Task {
            try self.mutex.lock(io);
            defer self.mutex.unlock(io);
            while (!self.closed) {
                if (self.tasks.popFront()) |task| return task;
                if (self.pending == 0) return null;
                // Release the mutex while waiting; reacquire it before returning.
                try self.available.wait(io, &self.mutex);
            }
            return null;
        }

        // Uncancelable locking keeps required bookkeeping from being skipped
        // during cancellation. Wake all waiters when no work remains.
        pub fn done(self: *Self, io: std.Io) void {
            self.mutex.lockUncancelable(io);
            defer self.mutex.unlock(io);
            std.debug.assert(self.pending != 0);
            self.pending -= 1;
            if (self.pending == 0) self.available.broadcast(io);
        }

        // Close even during cancellation and wake every waiting worker.
        pub fn close(self: *Self, io: std.Io) void {
            self.mutex.lockUncancelable(io);
            defer self.mutex.unlock(io);
            self.closed = true;
            self.available.broadcast(io);
        }
    };
}

With four traversal workers and four search workers, using the same corpus and measurement method:

On these searches, the streaming concurrency version takes about one-fifth to one-sixth of the baseline's elapsed time.

This is much faster, but we can do a bit better. While std.mem.indexOf is quite fast (especially for a single char needle), SIMD instructions can make a substantial improvement, depending on the needles and haystacks (though in general an improvement is expected). I first learned about this algorithm when trying to implement a fast search for terminal emulator buffers in this article by Wojciech Muła. This is a SIMD accelerated substring find function:

pub fn init(needle: []const u8) Searcher {
    const first_offset, const second_offset = common.rarest(needle) orelse .{ 0, 0 };
    return .{
        .needle = needle,
        .first_offset = first_offset,
        .second_offset = second_offset,
        // @splat repeats a scalar in every lane, the field type supplies the width.
        .first = if (needle.len == 0) @splat(0) else @splat(needle[first_offset]),
        .second = if (needle.len == 0) @splat(0) else @splat(needle[second_offset]),
    };
}

pub fn contains(self: *const Searcher, haystack: []const u8) bool {
    const needle = self.needle;
    if (needle.len == 0 or needle.len > haystack.len) return false;
    const candidates = haystack.len - needle.len + 1;
    var i: usize = 0;
    while (candidates - i >= width) : (i += width) {
        // @Vector(width, u8) defines width byte lanes. Zig coerces the loaded
        // array to a vector and uses SIMD instructions where the target supports it.
        const a: @Vector(width, u8) = haystack[i + self.first_offset ..][0..width].*;
        const b: @Vector(width, u8) = haystack[i + self.second_offset ..][0..width].*;
        // @bitCast reinterprets the boolean vector as a width-bit unsigned mask.
        var matches: std.meta.Int(.unsigned, width) = @bitCast((self.first == a) & (self.second == b));
        while (matches != 0) {
            // @ctz counts trailing zero bits, locating the lowest set bit.
            const lane = @ctz(matches);
            if (std.mem.eql(u8, haystack[i + lane ..][0..needle.len], needle)) return true;
            matches &= matches - 1;
        }
    }
    return scalarContains(needle, haystack[i..]);
}

pub fn scalarContains(needle: []const u8, haystack: []const u8) bool {
    if (needle.len == 0 or needle.len > haystack.len) return false;
    const candidates = haystack.len - needle.len + 1;
    for (0..candidates) |i| {
        if (std.mem.eql(u8, haystack[i..][0..needle.len], needle)) return true;
    }
    return false;
}

The idea is to find eligible locations for the needle to be located using the two rarest bytes from the needle. To pick them, our common.rarest helper uses a rarity table from BurntSushi's memchr, which I've copied into common.zig. This gives us a rough idea of which bytes are less likely to show up in the haystack without having to count them ourselves. Why two? Well you can add more, but every extra byte we check adds a vector load, comparison and AND operation in each batch. When using the two rarest occurring characters in the needle, the actual number of candidates is usually quite low, so adding more "filtering" can actually LOWER the performance. Of course, this heavily depends on the search term and the text you are searching. We filter based on the width the CPU can support: AVX2 support implies a width of 32, whereas CPUs with AVX512 support can process 64 bytes at once. Zig has a standard library function, std.simd.suggestVectorLength(u8), which suggests a lane count for the compilation target. We use std.simd.suggestVectorLength(u8) orelse 1 for our width. I've left out the Searcher struct definition above, but it just holds the needle, the two offsets, and two @Vector(width, u8) fields that init fills with our chosen bytes using @splat. For this example, we still assume width=8 for readability. For lazy, the rarest characters are z=152 and y=214 (lower means rarer), selecting offsets 2 and 3. We start checking every 8-byte block in the string The quick brown fox jumps over the lazy dog. The blocks at i=0,8,16,24 produce zero masks. At i=32:

haystack: "The quick brown fox jumps over the lazy dog"
needle:   "lazy"
All indexes are zero-based; SP means a space.

needle offset:       0        1        2        3
needle byte:         l        a        z        y
ASCII binary:     01101100 01100001 01111010 01111001

lane:                0        1        2        3        4        5        6        7
candidate start:     32       33       34       35       36       37       38       39
byte at start:       h        e        SP       l        a        z        y        SP

a loads candidate start + 2: haystack[34..42]
haystack index:      34       35       36       37       38       39       40       41
a chars:             SP       l        a        z        y        SP       d        o
a bytes:          00100000 01101100 01100001 01111010 01111001 00100000 01100100 01101111
compare to 'z':   01111010 01111010 01111010 01111010 01111010 01111010 01111010 01111010

b loads candidate start + 3: haystack[35..43]
haystack index:      35       36       37       38       39       40       41       42
b chars:             l        a        z        y        SP       d        o        g
b bytes:          01101100 01100001 01111010 01111001 00100000 01100100 01101111 01100111
compare to 'y':   01111001 01111001 01111001 01111001 01111001 01111001 01111001 01111001

Vector equality produces one boolean per lane, and & retains lanes passing both checks. Only lane 3 survives: it checks z at byte 37 and y at byte 38, for a candidate starting at byte 35. The mask is 00001000, so @ctz gives 3 and i + 3 = 35. The full match, lazy, occupies bytes 35 through 38; the candidate-start row is separate from each load's byte indexes.

lane order:    0 1 2 3 4 5 6 7
first == a:    0 0 0 1 0 0 0 0
second == b:   0 0 0 1 0 0 0 0
AND:           0 0 0 1 0 0 0 0

On little-endian targets, lane 0 maps to bit 0.
Writing the integer mask with its most significant bit on the left:

bit position:  7 6 5 4 3 2 1 0
matches:       0 0 0 0 1 0 0 0 = 0b00001000
                         ^^^^^
                         3 trailing zeros

@ctz(matches) = 3 -> candidate start = 32 + 3 = 35

haystack index:      35       36       37       38
haystack chars:       l        a        z        y
haystack[35..39]: 01101100 01100001 01111010 01111001
needle "lazy":    01101100 01100001 01111010 01111001 -> match

If verification had failed, clear that bit:
    matches:     00001000
    matches - 1: 00000111
    AND:         00000000 -> no candidates left in this block

The benchmarks for this version:

Compared with the streaming std.mem.indexOf version, elapsed time falls by about 10% for fn, 30% for allocator, and 13% for the absent needle.

Most CPUs have SIMD instructions available, but what if someone wants to run this on one that doesn't? We can use what can be described as a 'poor man's SIMD', SWAR: SIMD Within A Register, processing several bytes with ordinary integer operations. On a 64-bit target, a usize holds eight bytes; on a 32-bit target, it holds four. We keep the same two-byte filter, but replace vector comparisons with XOR and a function that detects zero bytes:

const std = @import("std");

// @sizeOf returns the size of a type in bytes.
const width = @sizeOf(usize);
const ones: usize = std.math.maxInt(usize) / 255;
const low_bits = ones * 0x7f;
const high_bits = ones * 0x80;

fn zeroBytes(word: usize) usize {
    return ~(((word & low_bits) + low_bits) | word | low_bits) & high_bits;
}

On a 64-bit target, ones is 0x0101010101010101. Multiplying it by a byte repeats that byte eight times, so ones * 'z' plays the role of @splat('z'). We load each group with std.mem.readInt(usize, ..., .little), placing its first byte in the least significant eight bits. XORing the loaded word with the repeated byte produces 00000000 wherever the bytes match. zeroBytes then produces 10000000 for each zero byte and 00000000 elsewhere. To do this, word & low_bits clears each byte's high bit, and adding 01111111 sets that bit whenever the remaining seven bits are nonzero. Each byte's sum is at most 11111110, so there is no carry into its neighbor. ORing with word also catches bytes whose original high bit was set; ORing with low_bits, inverting, and masking with high_bits leaves only the high bits of zero bytes:

One byte of zeroBytes:     zero byte    nonzero byte   high bit set
word                        00000000     00000011       10000000
word & 01111111             00000000     00000011       00000000
+ 01111111                  01111111     10000010       01111111
| word | 01111111           01111111     11111111       11111111
invert (~)                  10000000     00000000       00000000
& 10000000                  10000000     00000000       00000000

For the same lazy search, we again select z at offset 2 and y at offset 3. Assume a 64-bit target, so width=8. The blocks at i=0,8,16,24 produce zero masks. At i=32, we load a from bytes 34–41 and b from bytes 35–42. Each column below corresponds to one byte inside the integer; the XOR, addition, and bitwise operations act on the whole word at once:

haystack: "The quick brown fox jumps over the lazy dog"
needle:   "lazy"
Columns run from least to most significant byte (lane 0 to lane 7).

lane:                  0        1        2        3        4        5        6        7
candidate start:       32       33       34       35       36       37       38       39
byte at start:         h        e        SP       l        a        z        y        SP

a = readInt(usize, haystack[34..42], .little)
haystack index:        34       35       36       37       38       39       40       41
a chars:               SP       l        a        z        y        SP       d        o
a bytes:            00100000 01101100 01100001 01111010 01111001 00100000 01100100 01101111
repeat 'z':         01111010 01111010 01111010 01111010 01111010 01111010 01111010 01111010
a XOR repeat 'z':   01011010 00010110 00011011 00000000 00000011 01011010 00011110 00010101
zeroBytes:          00000000 00000000 00000000 10000000 00000000 00000000 00000000 00000000

b = readInt(usize, haystack[35..43], .little)
haystack index:        35       36       37       38       39       40       41       42
b chars:               l        a        z        y        SP       d        o        g
b bytes:            01101100 01100001 01111010 01111001 00100000 01100100 01101111 01100111
repeat 'y':         01111001 01111001 01111001 01111001 01111001 01111001 01111001 01111001
b XOR repeat 'y':   00010101 00011000 00000011 00000000 01011001 00011101 00010110 00011110
zeroBytes:          00000000 00000000 00000000 10000000 00000000 00000000 00000000 00000000

mask (AND):         00000000 00000000 00000000 10000000 00000000 00000000 00000000 00000000

ANDing the two zero-byte masks leaves only lane 3. This mask still occupies a full usize: each matching lane sets bit 8 * lane + 7, the high bit of its byte. Here the set bit is at position 31, so @ctz(mask) / 8 gives 31 / 8 = 3 using integer division. The candidate starts at 32 + 3 = 35; comparing the complete needle confirms lazy at bytes 35–38. If verification fails, mask &= mask - 1 clears that candidate's bit. Any remaining starting positions that do not fill a whole word are checked by scalarContains, as in the SIMD version.

Same combined mask, now written as an integer with the most significant bit first:

byte lane:             7        6        5        4        3        2        1        0
mask:               00000000 00000000 00000000 00000000 10000000 00000000 00000000 00000000
                                                        ^
                                                        bit 31: 31 zero bits to its right

mask = 0x0000000080000000
@ctz(mask) / 8 = 31 / 8 = 3
candidate start = 32 + 3 = 35

haystack index:      35       36       37       38
haystack chars:       l        a        z        y
haystack[35..39]: 01101100 01100001 01111010 01111001
needle "lazy":    01101100 01100001 01111010 01111001 -> match

Here is the SWAR implementation from zwhere:

const std = @import("std");
const common = @import("common.zig");

const width = @sizeOf(usize);
const ones: usize = std.math.maxInt(usize) / 255;
const low_bits = ones * 0x7f;
const high_bits = ones * 0x80;

fn zeroBytes(word: usize) usize {
    return ~(((word & low_bits) + low_bits) | word | low_bits) & high_bits;
}

pub const Searcher = struct {
    needle: []const u8,
    first_offset: usize,
    second_offset: usize,
    first: usize,
    second: usize,

    pub fn init(needle: []const u8) Searcher {
        const first_offset, const second_offset = common.rarest(needle) orelse .{ 0, 0 };
        return .{
            .needle = needle,
            .first_offset = first_offset,
            .second_offset = second_offset,
            .first = if (needle.len == 0) 0 else ones * needle[first_offset],
            .second = if (needle.len == 0) 0 else ones * needle[second_offset],
        };
    }

    pub fn contains(self: *const Searcher, haystack: []const u8) bool {
        const needle = self.needle;
        if (needle.len == 0 or needle.len > haystack.len) return false;
        const candidates = haystack.len - needle.len + 1;
        var i: usize = 0;
        while (candidates - i >= width) : (i += width) {
            const a = std.mem.readInt(usize, haystack[i + self.first_offset ..][0..width], .little);
            const b = std.mem.readInt(usize, haystack[i + self.second_offset ..][0..width], .little);
            var mask = zeroBytes(a ^ self.first) & zeroBytes(b ^ self.second);
            while (mask != 0) {
                const lane = @ctz(mask) / 8;
                if (std.mem.eql(u8, haystack[i + lane ..][0..needle.len], needle)) return true;
                mask &= mask - 1;
            }
        }
        return common.scalarContains(needle, haystack[i..]);
    }
};

pub fn contains(needle: []const u8, haystack: []const u8) bool {
    return Searcher.init(needle).contains(haystack);
}

The benchmarks results using SWAR:

SWAR is close to SIMD for fn here, but takes about 17% longer for allocator and 20% longer for the absent needle.

You can find a full implementation of the zwhere program here

Some potential followups:

• Using MemoryMap on particularly large files (might improve performance?)
• Supporting regular expressions (this would involve building a regex library or using an off the shelf solution)
• Supporting fuzzy finding
• support not searching files/paths specified by .gitignore
• Unicode awareness