Trie representation benchmarks

trie_bench.zig

const std = @import("std");
const Allocator = std.mem.Allocator;
const builtin = @import("builtin");

const PtrRange = struct {
    min: usize,
    max: usize,
};

const Trie = struct {
    root: *Node,
    allocator: Allocator,

    pub fn init(allocator: Allocator) !Trie {
        const root = try allocator.create(Node);
        root.* = .{};
        return Trie{
            .root = root,
            .allocator = allocator,
        };
    }

    pub fn deinit(self: *Trie) void {
        self.root.destroyRecursive(self.allocator);
        self.* = undefined;
    }

    const Node = struct {
        children: [256]?*Node = [_]?*Node{null} ** 256,
        end_of_word: bool = false,

        pub fn numDirectChildren(self: *const Node) u8 {
            var num: u8 = 0;
            for (self.children) |child| {
                if (child != null) num += 1;
            }
            return num;
        }

        fn destroyRecursive(self: *const Node, allocator: Allocator) void {
            for (self.children) |maybe_child| {
                if (maybe_child) |child| {
                    child.destroyRecursive(allocator);
                }
            }
            allocator.destroy(self);
        }

        /// Includes self
        fn numNodesRecursive(self: *const Node) usize {
            var num: usize = 1;
            for (self.children) |maybe_child| {
                if (maybe_child) |child| {
                    num += child.numNodesRecursive();
                }
            }
            return num;
        }

        fn getPtrRangeRecursive(self: *const Node) PtrRange {
            var range = PtrRange{ .min = @intFromPtr(self), .max = @intFromPtr(self) };
            for (self.children) |maybe_child| {
                if (maybe_child) |child| {
                    const child_range = child.getPtrRangeRecursive();
                    range.min = @min(child_range.min, range.min);
                    range.max = @max(child_range.max, range.max);
                }
            }
            return range;
        }
    };

    pub fn insert(self: *Trie, str: []const u8) !void {
        var node = self.root;

        for (str) |c| {
            if (node.children[c] == null) {
                const child = try self.allocator.create(Node);

                child.* = .{};
                node.children[c] = child;
            }
            node = node.children[c].?;
        }
        node.end_of_word = true;
    }

    fn totalNodeCount(self: *const Trie) usize {
        return self.root.numNodesRecursive();
    }

    pub fn contains(self: *const Trie, str: []const u8) bool {
        var node = self.root;
        for (str) |c| {
            node = node.children[c] orelse return false;
        }
        return node.end_of_word;
    }
};

const TrieWithLinkedListChildren = struct {
    root: *Node,
    allocator: Allocator,

    const Node = struct {
        char: u8,
        first_child: ?*Node = null,
        next_sibling: ?*Node = null,
        end_of_word: bool = false,

        fn destroyRecursive(self: *const Node, allocator: Allocator) void {
            defer allocator.destroy(self);
            var node = self.first_child orelse return;
            while (true) {
                const maybe_next_node = node.next_sibling;
                node.destroyRecursive(allocator);
                node = maybe_next_node orelse break;
            }
        }

        fn getPtrRangeRecursive(self: *const Node) PtrRange {
            var range = PtrRange{ .min = @intFromPtr(self), .max = @intFromPtr(self) };
            var node = self.first_child orelse return range;
            while (true) {
                const child_range = node.getPtrRangeRecursive();
                range.min = @min(child_range.min, range.min);
                range.max = @max(child_range.max, range.max);
                node = node.next_sibling orelse break;
            }
            return range;
        }
    };

    pub fn init(allocator: Allocator) !TrieWithLinkedListChildren {
        const root = try allocator.create(Node);
        root.* = .{ .char = 0, .end_of_word = false };
        return TrieWithLinkedListChildren{
            .root = root,
            .allocator = allocator,
        };
    }

    pub fn deinit(self: *TrieWithLinkedListChildren) void {
        self.root.destroyRecursive(self.allocator);
        self.* = undefined;
    }

    pub fn insert(self: *TrieWithLinkedListChildren, str: []const u8) !void {
        var node = self.root;

        for (str) |c| {
            if (node.first_child == null) {
                const child = try self.allocator.create(Node);
                child.* = .{ .char = c };
                node.first_child = child;
                node = child;
            } else {
                const match_or_insertion_point = searchSiblings(node.first_child.?, c);
                if (match_or_insertion_point.char == c) {
                    node = match_or_insertion_point;
                } else {
                    const sibling = try self.allocator.create(Node);
                    sibling.* = .{ .char = c };
                    match_or_insertion_point.next_sibling = sibling;
                    node = sibling;
                }
            }
        }
        node.end_of_word = true;
    }

    /// Returns the matching sibling, if found. Otherwise, returns
    /// the last sibling.
    fn searchSiblings(first_child: *Node, c: u8) *Node {
        var node = first_child;
        while (true) {
            if (node.char == c) return node;
            node = node.next_sibling orelse return node;
        }
    }

    fn totalNodeCount(self: *const TrieWithLinkedListChildren) usize {
        return self.root.numNodesRecursive();
    }

    fn contains(self: *const TrieWithLinkedListChildren, str: []const u8) bool {
        var node = self.root;
        for (str) |c| {
            node = node.first_child orelse return false;
            while (true) {
                if (node.char == c) break;
                node = node.next_sibling orelse return false;
            }
        }
        return node.end_of_word;
    }
};

const TrieAsArray = struct {
    nodes: []Node,
    allocator: Allocator,

    const Node = packed struct(u32) {
        char: u8,
        end_of_word: bool,
        last_sibling: bool,
        _: u6 = 0,
        first_child_index: u16,
    };

    pub fn deinit(self: TrieAsArray) void {
        self.allocator.free(self.nodes);
    }

    pub fn fromTrie(trie: Trie, allocator: Allocator) !TrieAsArray {
        const num_nodes = trie.totalNodeCount();
        var nodes = try allocator.alloc(Node, num_nodes);

        var node_i: u16 = 0;

        // write root
        nodes[node_i] = .{ .char = 0, .end_of_word = false, .last_sibling = true, .first_child_index = 1 };
        node_i += 1;

        var queue = std.fifo.LinearFifo(*Trie.Node, .Dynamic).init(allocator);
        defer queue.deinit();

        var first_available_index: u16 = 1 + trie.root.numDirectChildren();
        first_available_index = try populateChildren(trie.root, nodes, &queue, &node_i, first_available_index);

        while (queue.readItem()) |node| {
            first_available_index = try populateChildren(node, nodes, &queue, &node_i, first_available_index);
        }

        return .{
            .nodes = nodes,
            .allocator = allocator,
        };
    }

    fn populateChildren(
        node: *Trie.Node,
        nodes: []Node,
        queue: *std.fifo.LinearFifo(*Trie.Node, .Dynamic),
        node_i: *u16,
        first_available_index: u16,
    ) !u16 {
        var cur_available_index = first_available_index;
        const num_children = node.numDirectChildren();
        var child_i: u16 = 0;
        for (node.children, 0..) |maybe_child, c_usize| {
            const child = maybe_child orelse continue;
            const c: u7 = @intCast(c_usize);
            const child_num_children = child.numDirectChildren();
            const is_last_child = child_i == num_children - 1;

            const first_child_index = if (child_num_children > 0) cur_available_index else 0;
            cur_available_index += child_num_children;
            try queue.writeItem(child);

            nodes[node_i.*] = .{
                .char = c,
                .end_of_word = child.end_of_word,
                .last_sibling = is_last_child,
                .first_child_index = first_child_index,
            };

            node_i.* += 1;
            child_i += 1;
        }
        return cur_available_index;
    }

    fn contains(self: *const TrieAsArray, str: []const u8) bool {
        var node_i: u16 = 0;
        for (str) |c| {
            node_i = self.nodes[node_i].first_child_index;
            if (node_i == 0) return false;
            while (true) {
                const node = self.nodes[node_i];
                if (node.char == c) break;
                if (node.last_sibling) return false;
                node_i += 1;
            }
        }
        return self.nodes[node_i].end_of_word;
    }
};

var debug_allocator = std.heap.DebugAllocator(.{}){};

pub fn main() !void {
    // An arena for non-trie related allocations
    var arena_state = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena_state.deinit();
    const arena = arena_state.allocator();

    // Allocator specifically for the tries
    var trie_arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer trie_arena.deinit();
    const allocator = trie_arena.allocator();

    const args = try std.process.argsAlloc(arena);
    defer std.process.argsFree(arena, args);

    const BenchToRun = enum {
        all,
        trie,
        trie_ll,
        trie_array,
    };
    const bench_to_run: BenchToRun = blk: {
        if (args.len >= 2) {
            break :blk std.meta.stringToEnum(BenchToRun, args[1]) orelse {
                std.debug.print("invalid arg: {s}\n", .{args[1]});
                return error.InvalidArg;
            };
        }
        break :blk .all;
    };

    const json_contents = try std.fs.cwd().readFileAlloc(arena, "entities.json", std.math.maxInt(usize));
    defer arena.free(json_contents);

    var parsed = try std.json.parseFromSlice(std.json.Value, arena, json_contents, .{});
    defer parsed.deinit();

    var to_run_buf: [3]BenchToRun = undefined;
    const to_run = blk: {
        switch (bench_to_run) {
            .all => {
                to_run_buf = [_]BenchToRun{ .trie, .trie_ll, .trie_array };
                break :blk to_run_buf[0..];
            },
            else => |v| {
                to_run_buf[0] = v;
                break :blk to_run_buf[0..1];
            },
        }
    };

    for (to_run) |b| {
        switch (b) {
            .all => unreachable,
            .trie => {
                var trie = try Trie.init(allocator);
                defer trie.deinit();
                for (parsed.value.object.keys()) |str| {
                    std.debug.assert(str[0] == '&');
                    try trie.insert(str[1..]);
                }

                const trie_ns = try bench(&trie);
                std.debug.print("      trie: {} ({} per iteration)\n", .{
                    std.fmt.fmtDuration(trie_ns),
                    std.fmt.fmtDuration(trie_ns / bench_iterations),
                });
            },
            .trie_ll => {
                var trie_ll = try TrieWithLinkedListChildren.init(allocator);
                defer trie_ll.deinit();
                for (parsed.value.object.keys()) |str| {
                    std.debug.assert(str[0] == '&');
                    try trie_ll.insert(str[1..]);
                }

                const trie_ll_ns = try bench(&trie_ll);
                std.debug.print("   trie_ll: {} ({} per iteration)\n", .{
                    std.fmt.fmtDuration(trie_ll_ns),
                    std.fmt.fmtDuration(trie_ll_ns / bench_iterations),
                });
            },
            .trie_array => {
                var trie = try Trie.init(allocator);
                defer trie.deinit();
                for (parsed.value.object.keys()) |str| {
                    std.debug.assert(str[0] == '&');
                    try trie.insert(str[1..]);
                }

                var flattened = try TrieAsArray.fromTrie(trie, allocator);
                defer flattened.deinit();

                const flattened_ns = try bench(&flattened);
                std.debug.print("trie_array: {} ({} per iteration)\n", .{
                    std.fmt.fmtDuration(flattened_ns),
                    std.fmt.fmtDuration(flattened_ns / bench_iterations),
                });
            },
        }
    }
}

const named_character_references: []const []const u8 = &.{ "AElig", "AElig;", "AMP", "AMP;", "Aacute", "Aacute;", "Abreve;", "Acirc", "Acirc;", "Acy;", "Afr;", "Agrave", "Agrave;", "Alpha;", "Amacr;", "And;", "Aogon;", "Aopf;", "ApplyFunction;", "Aring", "Aring;", "Ascr;", "Assign;", "Atilde", "Atilde;", "Auml", "Auml;", "Backslash;", "Barv;", "Barwed;", "Bcy;", "Because;", "Bernoullis;", "Beta;", "Bfr;", "Bopf;", "Breve;", "Bscr;", "Bumpeq;", "CHcy;", "COPY", "COPY;", "Cacute;", "Cap;", "CapitalDifferentialD;", "Cayleys;", "Ccaron;", "Ccedil", "Ccedil;", "Ccirc;", "Cconint;", "Cdot;", "Cedilla;", "CenterDot;", "Cfr;", "Chi;", "CircleDot;", "CircleMinus;", "CirclePlus;", "CircleTimes;", "ClockwiseContourIntegral;", "CloseCurlyDoubleQuote;", "CloseCurlyQuote;", "Colon;", "Colone;", "Congruent;", "Conint;", "ContourIntegral;", "Copf;", "Coproduct;", "CounterClockwiseContourIntegral;", "Cross;", "Cscr;", "Cup;", "CupCap;", "DD;", "DDotrahd;", "DJcy;", "DScy;", "DZcy;", "Dagger;", "Darr;", "Dashv;", "Dcaron;", "Dcy;", "Del;", "Delta;", "Dfr;", "DiacriticalAcute;", "DiacriticalDot;", "DiacriticalDoubleAcute;", "DiacriticalGrave;", "DiacriticalTilde;", "Diamond;", "DifferentialD;", "Dopf;", "Dot;", "DotDot;", "DotEqual;", "DoubleContourIntegral;", "DoubleDot;", "DoubleDownArrow;", "DoubleLeftArrow;", "DoubleLeftRightArrow;", "DoubleLeftTee;", "DoubleLongLeftArrow;", "DoubleLongLeftRightArrow;", "DoubleLongRightArrow;", "DoubleRightArrow;", "DoubleRightTee;", "DoubleUpArrow;", "DoubleUpDownArrow;", "DoubleVerticalBar;", "DownArrow;", "DownArrowBar;", "DownArrowUpArrow;", "DownBreve;", "DownLeftRightVector;", "DownLeftTeeVector;", "DownLeftVector;", "DownLeftVectorBar;", "DownRightTeeVector;", "DownRightVector;", "DownRightVectorBar;", "DownTee;", "DownTeeArrow;", "Downarrow;", "Dscr;", "Dstrok;", "ENG;", "ETH", "ETH;", "Eacute", "Eacute;", "Ecaron;", "Ecirc", "Ecirc;", "Ecy;", "Edot;", "Efr;", "Egrave", "Egrave;", "Element;", "Emacr;", "EmptySmallSquare;", "EmptyVerySmallSquare;", "Eogon;", "Eopf;", "Epsilon;", "Equal;", "EqualTilde;", "Equilibrium;", "Escr;", "Esim;", "Eta;", "Euml", "Euml;", "Exists;", "ExponentialE;", "Fcy;", "Ffr;", "FilledSmallSquare;", "FilledVerySmallSquare;", "Fopf;", "ForAll;", "Fouriertrf;", "Fscr;", "GJcy;", "GT", "GT;", "Gamma;", "Gammad;", "Gbreve;", "Gcedil;", "Gcirc;", "Gcy;", "Gdot;", "Gfr;", "Gg;", "Gopf;", "GreaterEqual;", "GreaterEqualLess;", "GreaterFullEqual;", "GreaterGreater;", "GreaterLess;", "GreaterSlantEqual;", "GreaterTilde;", "Gscr;", "Gt;", "HARDcy;", "Hacek;", "Hat;", "Hcirc;", "Hfr;", "HilbertSpace;", "Hopf;", "HorizontalLine;", "Hscr;", "Hstrok;", "HumpDownHump;", "HumpEqual;", "IEcy;", "IJlig;", "IOcy;", "Iacute", "Iacute;", "Icirc", "Icirc;", "Icy;", "Idot;", "Ifr;", "Igrave", "Igrave;", "Im;", "Imacr;", "ImaginaryI;", "Implies;", "Int;", "Integral;", "Intersection;", "InvisibleComma;", "InvisibleTimes;", "Iogon;", "Iopf;", "Iota;", "Iscr;", "Itilde;", "Iukcy;", "Iuml", "Iuml;", "Jcirc;", "Jcy;", "Jfr;", "Jopf;", "Jscr;", "Jsercy;", "Jukcy;", "KHcy;", "KJcy;", "Kappa;", "Kcedil;", "Kcy;", "Kfr;", "Kopf;", "Kscr;", "LJcy;", "LT", "LT;", "Lacute;", "Lambda;", "Lang;", "Laplacetrf;", "Larr;", "Lcaron;", "Lcedil;", "Lcy;", "LeftAngleBracket;", "LeftArrow;", "LeftArrowBar;", "LeftArrowRightArrow;", "LeftCeiling;", "LeftDoubleBracket;", "LeftDownTeeVector;", "LeftDownVector;", "LeftDownVectorBar;", "LeftFloor;", "LeftRightArrow;", "LeftRightVector;", "LeftTee;", "LeftTeeArrow;", "LeftTeeVector;", "LeftTriangle;", "LeftTriangleBar;", "LeftTriangleEqual;", "LeftUpDownVector;", "LeftUpTeeVector;", "LeftUpVector;", "LeftUpVectorBar;", "LeftVector;", "LeftVectorBar;", "Leftarrow;", "Leftrightarrow;", "LessEqualGreater;", "LessFullEqual;", "LessGreater;", "LessLess;", "LessSlantEqual;", "LessTilde;", "Lfr;", "Ll;", "Lleftarrow;", "Lmidot;", "LongLeftArrow;", "LongLeftRightArrow;", "LongRightArrow;", "Longleftarrow;", "Longleftrightarrow;", "Longrightarrow;", "Lopf;", "LowerLeftArrow;", "LowerRightArrow;", "Lscr;", "Lsh;", "Lstrok;", "Lt;", "Map;", "Mcy;", "MediumSpace;", "Mellintrf;", "Mfr;", "MinusPlus;", "Mopf;", "Mscr;", "Mu;", "NJcy;", "Nacute;", "Ncaron;", "Ncedil;", "Ncy;", "NegativeMediumSpace;", "NegativeThickSpace;", "NegativeThinSpace;", "NegativeVeryThinSpace;", "NestedGreaterGreater;", "NestedLessLess;", "NewLine;", "Nfr;", "NoBreak;", "NonBreakingSpace;", "Nopf;", "Not;", "NotCongruent;", "NotCupCap;", "NotDoubleVerticalBar;", "NotElement;", "NotEqual;", "NotEqualTilde;", "NotExists;", "NotGreater;", "NotGreaterEqual;", "NotGreaterFullEqual;", "NotGreaterGreater;", "NotGreaterLess;", "NotGreaterSlantEqual;", "NotGreaterTilde;", "NotHumpDownHump;", "NotHumpEqual;", "NotLeftTriangle;", "NotLeftTriangleBar;", "NotLeftTriangleEqual;", "NotLess;", "NotLessEqual;", "NotLessGreater;", "NotLessLess;", "NotLessSlantEqual;", "NotLessTilde;", "NotNestedGreaterGreater;", "NotNestedLessLess;", "NotPrecedes;", "NotPrecedesEqual;", "NotPrecedesSlantEqual;", "NotReverseElement;", "NotRightTriangle;", "NotRightTriangleBar;", "NotRightTriangleEqual;", "NotSquareSubset;", "NotSquareSubsetEqual;", "NotSquareSuperset;", "NotSquareSupersetEqual;", "NotSubset;", "NotSubsetEqual;", "NotSucceeds;", "NotSucceedsEqual;", "NotSucceedsSlantEqual;", "NotSucceedsTilde;", "NotSuperset;", "NotSupersetEqual;", "NotTilde;", "NotTildeEqual;", "NotTildeFullEqual;", "NotTildeTilde;", "NotVerticalBar;", "Nscr;", "Ntilde", "Ntilde;", "Nu;", "OElig;", "Oacute", "Oacute;", "Ocirc", "Ocirc;", "Ocy;", "Odblac;", "Ofr;", "Ograve", "Ograve;", "Omacr;", "Omega;", "Omicron;", "Oopf;", "OpenCurlyDoubleQuote;", "OpenCurlyQuote;", "Or;", "Oscr;", "Oslash", "Oslash;", "Otilde", "Otilde;", "Otimes;", "Ouml", "Ouml;", "OverBar;", "OverBrace;", "OverBracket;", "OverParenthesis;", "PartialD;", "Pcy;", "Pfr;", "Phi;", "Pi;", "PlusMinus;", "Poincareplane;", "Popf;", "Pr;", "Precedes;", "PrecedesEqual;", "PrecedesSlantEqual;", "PrecedesTilde;", "Prime;", "Product;", "Proportion;", "Proportional;", "Pscr;", "Psi;", "QUOT", "QUOT;", "Qfr;", "Qopf;", "Qscr;", "RBarr;", "REG", "REG;", "Racute;", "Rang;", "Rarr;", "Rarrtl;", "Rcaron;", "Rcedil;", "Rcy;", "Re;", "ReverseElement;", "ReverseEquilibrium;", "ReverseUpEquilibrium;", "Rfr;", "Rho;", "RightAngleBracket;", "RightArrow;", "RightArrowBar;", "RightArrowLeftArrow;", "RightCeiling;", "RightDoubleBracket;", "RightDownTeeVector;", "RightDownVector;", "RightDownVectorBar;", "RightFloor;", "RightTee;", "RightTeeArrow;", "RightTeeVector;", "RightTriangle;", "RightTriangleBar;", "RightTriangleEqual;", "RightUpDownVector;", "RightUpTeeVector;", "RightUpVector;", "RightUpVectorBar;", "RightVector;", "RightVectorBar;", "Rightarrow;", "Ropf;", "RoundImplies;", "Rrightarrow;", "Rscr;", "Rsh;", "RuleDelayed;", "SHCHcy;", "SHcy;", "SOFTcy;", "Sacute;", "Sc;", "Scaron;", "Scedil;", "Scirc;", "Scy;", "Sfr;", "ShortDownArrow;", "ShortLeftArrow;", "ShortRightArrow;", "ShortUpArrow;", "Sigma;", "SmallCircle;", "Sopf;", "Sqrt;", "Square;", "SquareIntersection;", "SquareSubset;", "SquareSubsetEqual;", "SquareSuperset;", "SquareSupersetEqual;", "SquareUnion;", "Sscr;", "Star;", "Sub;", "Subset;", "SubsetEqual;", "Succeeds;", "SucceedsEqual;", "SucceedsSlantEqual;", "SucceedsTilde;", "SuchThat;", "Sum;", "Sup;", "Superset;", "SupersetEqual;", "Supset;", "THORN", "THORN;", "TRADE;", "TSHcy;", "TScy;", "Tab;", "Tau;", "Tcaron;", "Tcedil;", "Tcy;", "Tfr;", "Therefore;", "Theta;", "ThickSpace;", "ThinSpace;", "Tilde;", "TildeEqual;", "TildeFullEqual;", "TildeTilde;", "Topf;", "TripleDot;", "Tscr;", "Tstrok;", "Uacute", "Uacute;", "Uarr;", "Uarrocir;", "Ubrcy;", "Ubreve;", "Ucirc", "Ucirc;", "Ucy;", "Udblac;", "Ufr;", "Ugrave", "Ugrave;", "Umacr;", "UnderBar;", "UnderBrace;", "UnderBracket;", "UnderParenthesis;", "Union;", "UnionPlus;", "Uogon;", "Uopf;", "UpArrow;", "UpArrowBar;", "UpArrowDownArrow;", "UpDownArrow;", "UpEquilibrium;", "UpTee;", "UpTeeArrow;", "Uparrow;", "Updownarrow;", "UpperLeftArrow;", "UpperRightArrow;", "Upsi;", "Upsilon;", "Uring;", "Uscr;", "Utilde;", "Uuml", "Uuml;", "VDash;", "Vbar;", "Vcy;", "Vdash;", "Vdashl;", "Vee;", "Verbar;", "Vert;", "VerticalBar;", "VerticalLine;", "VerticalSeparator;", "VerticalTilde;", "VeryThinSpace;", "Vfr;", "Vopf;", "Vscr;", "Vvdash;", "Wcirc;", "Wedge;", "Wfr;", "Wopf;", "Wscr;", "Xfr;", "Xi;", "Xopf;", "Xscr;", "YAcy;", "YIcy;", "YUcy;", "Yacute", "Yacute;", "Ycirc;", "Ycy;", "Yfr;", "Yopf;", "Yscr;", "Yuml;", "ZHcy;", "Zacute;", "Zcaron;", "Zcy;", "Zdot;", "ZeroWidthSpace;", "Zeta;", "Zfr;", "Zopf;", "Zscr;", "aacute", "aacute;", "abreve;", "ac;", "acE;", "acd;", "acirc", "acirc;", "acute", "acute;", "acy;", "aelig", "aelig;", "af;", "afr;", "agrave", "agrave;", "alefsym;", "aleph;", "alpha;", "amacr;", "amalg;", "amp", "amp;", "and;", "andand;", "andd;", "andslope;", "andv;", "ang;", "ange;", "angle;", "angmsd;", "angmsdaa;", "angmsdab;", "angmsdac;", "angmsdad;", "angmsdae;", "angmsdaf;", "angmsdag;", "angmsdah;", "angrt;", "angrtvb;", "angrtvbd;", "angsph;", "angst;", "angzarr;", "aogon;", "aopf;", "ap;", "apE;", "apacir;", "ape;", "apid;", "apos;", "approx;", "approxeq;", "aring", "aring;", "ascr;", "ast;", "asymp;", "asympeq;", "atilde", "atilde;", "auml", "auml;", "awconint;", "awint;", "bNot;", "backcong;", "backepsilon;", "backprime;", "backsim;", "backsimeq;", "barvee;", "barwed;", "barwedge;", "bbrk;", "bbrktbrk;", "bcong;", "bcy;", "bdquo;", "becaus;", "because;", "bemptyv;", "bepsi;", "bernou;", "beta;", "beth;", "between;", "bfr;", "bigcap;", "bigcirc;", "bigcup;", "bigodot;", "bigoplus;", "bigotimes;", "bigsqcup;", "bigstar;", "bigtriangledown;", "bigtriangleup;", "biguplus;", "bigvee;", "bigwedge;", "bkarow;", "blacklozenge;", "blacksquare;", "blacktriangle;", "blacktriangledown;", "blacktriangleleft;", "blacktriangleright;", "blank;", "blk12;", "blk14;", "blk34;", "block;", "bne;", "bnequiv;", "bnot;", "bopf;", "bot;", "bottom;", "bowtie;", "boxDL;", "boxDR;", "boxDl;", "boxDr;", "boxH;", "boxHD;", "boxHU;", "boxHd;", "boxHu;", "boxUL;", "boxUR;", "boxUl;", "boxUr;", "boxV;", "boxVH;", "boxVL;", "boxVR;", "boxVh;", "boxVl;", "boxVr;", "boxbox;", "boxdL;", "boxdR;", "boxdl;", "boxdr;", "boxh;", "boxhD;", "boxhU;", "boxhd;", "boxhu;", "boxminus;", "boxplus;", "boxtimes;", "boxuL;", "boxuR;", "boxul;", "boxur;", "boxv;", "boxvH;", "boxvL;", "boxvR;", "boxvh;", "boxvl;", "boxvr;", "bprime;", "breve;", "brvbar", "brvbar;", "bscr;", "bsemi;", "bsim;", "bsime;", "bsol;", "bsolb;", "bsolhsub;", "bull;", "bullet;", "bump;", "bumpE;", "bumpe;", "bumpeq;", "cacute;", "cap;", "capand;", "capbrcup;", "capcap;", "capcup;", "capdot;", "caps;", "caret;", "caron;", "ccaps;", "ccaron;", "ccedil", "ccedil;", "ccirc;", "ccups;", "ccupssm;", "cdot;", "cedil", "cedil;", "cemptyv;", "cent", "cent;", "centerdot;", "cfr;", "chcy;", "check;", "checkmark;", "chi;", "cir;", "cirE;", "circ;", "circeq;", "circlearrowleft;", "circlearrowright;", "circledR;", "circledS;", "circledast;", "circledcirc;", "circleddash;", "cire;", "cirfnint;", "cirmid;", "cirscir;", "clubs;", "clubsuit;", "colon;", "colone;", "coloneq;", "comma;", "commat;", "comp;", "compfn;", "complement;", "complexes;", "cong;", "congdot;", "conint;", "copf;", "coprod;", "copy", "copy;", "copysr;", "crarr;", "cross;", "cscr;", "csub;", "csube;", "csup;", "csupe;", "ctdot;", "cudarrl;", "cudarrr;", "cuepr;", "cuesc;", "cularr;", "cularrp;", "cup;", "cupbrcap;", "cupcap;", "cupcup;", "cupdot;", "cupor;", "cups;", "curarr;", "curarrm;", "curlyeqprec;", "curlyeqsucc;", "curlyvee;", "curlywedge;", "curren", "curren;", "curvearrowleft;", "curvearrowright;", "cuvee;", "cuwed;", "cwconint;", "cwint;", "cylcty;", "dArr;", "dHar;", "dagger;", "daleth;", "darr;", "dash;", "dashv;", "dbkarow;", "dblac;", "dcaron;", "dcy;", "dd;", "ddagger;", "ddarr;", "ddotseq;", "deg", "deg;", "delta;", "demptyv;", "dfisht;", "dfr;", "dharl;", "dharr;", "diam;", "diamond;", "diamondsuit;", "diams;", "die;", "digamma;", "disin;", "div;", "divide", "divide;", "divideontimes;", "divonx;", "djcy;", "dlcorn;", "dlcrop;", "dollar;", "dopf;", "dot;", "doteq;", "doteqdot;", "dotminus;", "dotplus;", "dotsquare;", "doublebarwedge;", "downarrow;", "downdownarrows;", "downharpoonleft;", "downharpoonright;", "drbkarow;", "drcorn;", "drcrop;", "dscr;", "dscy;", "dsol;", "dstrok;", "dtdot;", "dtri;", "dtrif;", "duarr;", "duhar;", "dwangle;", "dzcy;", "dzigrarr;", "eDDot;", "eDot;", "eacute", "eacute;", "easter;", "ecaron;", "ecir;", "ecirc", "ecirc;", "ecolon;", "ecy;", "edot;", "ee;", "efDot;", "efr;", "eg;", "egrave", "egrave;", "egs;", "egsdot;", "el;", "elinters;", "ell;", "els;", "elsdot;", "emacr;", "empty;", "emptyset;", "emptyv;", "emsp13;", "emsp14;", "emsp;", "eng;", "ensp;", "eogon;", "eopf;", "epar;", "eparsl;", "eplus;", "epsi;", "epsilon;", "epsiv;", "eqcirc;", "eqcolon;", "eqsim;", "eqslantgtr;", "eqslantless;", "equals;", "equest;", "equiv;", "equivDD;", "eqvparsl;", "erDot;", "erarr;", "escr;", "esdot;", "esim;", "eta;", "eth", "eth;", "euml", "euml;", "euro;", "excl;", "exist;", "expectation;", "exponentiale;", "fallingdotseq;", "fcy;", "female;", "ffilig;", "fflig;", "ffllig;", "ffr;", "filig;", "fjlig;", "flat;", "fllig;", "fltns;", "fnof;", "fopf;", "forall;", "fork;", "forkv;", "fpartint;", "frac12", "frac12;", "frac13;", "frac14", "frac14;", "frac15;", "frac16;", "frac18;", "frac23;", "frac25;", "frac34", "frac34;", "frac35;", "frac38;", "frac45;", "frac56;", "frac58;", "frac78;", "frasl;", "frown;", "fscr;", "gE;", "gEl;", "gacute;", "gamma;", "gammad;", "gap;", "gbreve;", "gcirc;", "gcy;", "gdot;", "ge;", "gel;", "geq;", "geqq;", "geqslant;", "ges;", "gescc;", "gesdot;", "gesdoto;", "gesdotol;", "gesl;", "gesles;", "gfr;", "gg;", "ggg;", "gimel;", "gjcy;", "gl;", "glE;", "gla;", "glj;", "gnE;", "gnap;", "gnapprox;", "gne;", "gneq;", "gneqq;", "gnsim;", "gopf;", "grave;", "gscr;", "gsim;", "gsime;", "gsiml;", "gt", "gt;", "gtcc;", "gtcir;", "gtdot;", "gtlPar;", "gtquest;", "gtrapprox;", "gtrarr;", "gtrdot;", "gtreqless;", "gtreqqless;", "gtrless;", "gtrsim;", "gvertneqq;", "gvnE;", "hArr;", "hairsp;", "half;", "hamilt;", "hardcy;", "harr;", "harrcir;", "harrw;", "hbar;", "hcirc;", "hearts;", "heartsuit;", "hellip;", "hercon;", "hfr;", "hksearow;", "hkswarow;", "hoarr;", "homtht;", "hookleftarrow;", "hookrightarrow;", "hopf;", "horbar;", "hscr;", "hslash;", "hstrok;", "hybull;", "hyphen;", "iacute", "iacute;", "ic;", "icirc", "icirc;", "icy;", "iecy;", "iexcl", "iexcl;", "iff;", "ifr;", "igrave", "igrave;", "ii;", "iiiint;", "iiint;", "iinfin;", "iiota;", "ijlig;", "imacr;", "image;", "imagline;", "imagpart;", "imath;", "imof;", "imped;", "in;", "incare;", "infin;", "infintie;", "inodot;", "int;", "intcal;", "integers;", "intercal;", "intlarhk;", "intprod;", "iocy;", "iogon;", "iopf;", "iota;", "iprod;", "iquest", "iquest;", "iscr;", "isin;", "isinE;", "isindot;", "isins;", "isinsv;", "isinv;", "it;", "itilde;", "iukcy;", "iuml", "iuml;", "jcirc;", "jcy;", "jfr;", "jmath;", "jopf;", "jscr;", "jsercy;", "jukcy;", "kappa;", "kappav;", "kcedil;", "kcy;", "kfr;", "kgreen;", "khcy;", "kjcy;", "kopf;", "kscr;", "lAarr;", "lArr;", "lAtail;", "lBarr;", "lE;", "lEg;", "lHar;", "lacute;", "laemptyv;", "lagran;", "lambda;", "lang;", "langd;", "langle;", "lap;", "laquo", "laquo;", "larr;", "larrb;", "larrbfs;", "larrfs;", "larrhk;", "larrlp;", "larrpl;", "larrsim;", "larrtl;", "lat;", "latail;", "late;", "lates;", "lbarr;", "lbbrk;", "lbrace;", "lbrack;", "lbrke;", "lbrksld;", "lbrkslu;", "lcaron;", "lcedil;", "lceil;", "lcub;", "lcy;", "ldca;", "ldquo;", "ldquor;", "ldrdhar;", "ldrushar;", "ldsh;", "le;", "leftarrow;", "leftarrowtail;", "leftharpoondown;", "leftharpoonup;", "leftleftarrows;", "leftrightarrow;", "leftrightarrows;", "leftrightharpoons;", "leftrightsquigarrow;", "leftthreetimes;", "leg;", "leq;", "leqq;", "leqslant;", "les;", "lescc;", "lesdot;", "lesdoto;", "lesdotor;", "lesg;", "lesges;", "lessapprox;", "lessdot;", "lesseqgtr;", "lesseqqgtr;", "lessgtr;", "lesssim;", "lfisht;", "lfloor;", "lfr;", "lg;", "lgE;", "lhard;", "lharu;", "lharul;", "lhblk;", "ljcy;", "ll;", "llarr;", "llcorner;", "llhard;", "lltri;", "lmidot;", "lmoust;", "lmoustache;", "lnE;", "lnap;", "lnapprox;", "lne;", "lneq;", "lneqq;", "lnsim;", "loang;", "loarr;", "lobrk;", "longleftarrow;", "longleftrightarrow;", "longmapsto;", "longrightarrow;", "looparrowleft;", "looparrowright;", "lopar;", "lopf;", "loplus;", "lotimes;", "lowast;", "lowbar;", "loz;", "lozenge;", "lozf;", "lpar;", "lparlt;", "lrarr;", "lrcorner;", "lrhar;", "lrhard;", "lrm;", "lrtri;", "lsaquo;", "lscr;", "lsh;", "lsim;", "lsime;", "lsimg;", "lsqb;", "lsquo;", "lsquor;", "lstrok;", "lt", "lt;", "ltcc;", "ltcir;", "ltdot;", "lthree;", "ltimes;", "ltlarr;", "ltquest;", "ltrPar;", "ltri;", "ltrie;", "ltrif;", "lurdshar;", "luruhar;", "lvertneqq;", "lvnE;", "mDDot;", "macr", "macr;", "male;", "malt;", "maltese;", "map;", "mapsto;", "mapstodown;", "mapstoleft;", "mapstoup;", "marker;", "mcomma;", "mcy;", "mdash;", "measuredangle;", "mfr;", "mho;", "micro", "micro;", "mid;", "midast;", "midcir;", "middot", "middot;", "minus;", "minusb;", "minusd;", "minusdu;", "mlcp;", "mldr;", "mnplus;", "models;", "mopf;", "mp;", "mscr;", "mstpos;", "mu;", "multimap;", "mumap;", "nGg;", "nGt;", "nGtv;", "nLeftarrow;", "nLeftrightarrow;", "nLl;", "nLt;", "nLtv;", "nRightarrow;", "nVDash;", "nVdash;", "nabla;", "nacute;", "nang;", "nap;", "napE;", "napid;", "napos;", "napprox;", "natur;", "natural;", "naturals;", "nbsp", "nbsp;", "nbump;", "nbumpe;", "ncap;", "ncaron;", "ncedil;", "ncong;", "ncongdot;", "ncup;", "ncy;", "ndash;", "ne;", "neArr;", "nearhk;", "nearr;", "nearrow;", "nedot;", "nequiv;", "nesear;", "nesim;", "nexist;", "nexists;", "nfr;", "ngE;", "nge;", "ngeq;", "ngeqq;", "ngeqslant;", "nges;", "ngsim;", "ngt;", "ngtr;", "nhArr;", "nharr;", "nhpar;", "ni;", "nis;", "nisd;", "niv;", "njcy;", "nlArr;", "nlE;", "nlarr;", "nldr;", "nle;", "nleftarrow;", "nleftrightarrow;", "nleq;", "nleqq;", "nleqslant;", "nles;", "nless;", "nlsim;", "nlt;", "nltri;", "nltrie;", "nmid;", "nopf;", "not", "not;", "notin;", "notinE;", "notindot;", "notinva;", "notinvb;", "notinvc;", "notni;", "notniva;", "notnivb;", "notnivc;", "npar;", "nparallel;", "nparsl;", "npart;", "npolint;", "npr;", "nprcue;", "npre;", "nprec;", "npreceq;", "nrArr;", "nrarr;", "nrarrc;", "nrarrw;", "nrightarrow;", "nrtri;", "nrtrie;", "nsc;", "nsccue;", "nsce;", "nscr;", "nshortmid;", "nshortparallel;", "nsim;", "nsime;", "nsimeq;", "nsmid;", "nspar;", "nsqsube;", "nsqsupe;", "nsub;", "nsubE;", "nsube;", "nsubset;", "nsubseteq;", "nsubseteqq;", "nsucc;", "nsucceq;", "nsup;", "nsupE;", "nsupe;", "nsupset;", "nsupseteq;", "nsupseteqq;", "ntgl;", "ntilde", "ntilde;", "ntlg;", "ntriangleleft;", "ntrianglelefteq;", "ntriangleright;", "ntrianglerighteq;", "nu;", "num;", "numero;", "numsp;", "nvDash;", "nvHarr;", "nvap;", "nvdash;", "nvge;", "nvgt;", "nvinfin;", "nvlArr;", "nvle;", "nvlt;", "nvltrie;", "nvrArr;", "nvrtrie;", "nvsim;", "nwArr;", "nwarhk;", "nwarr;", "nwarrow;", "nwnear;", "oS;", "oacute", "oacute;", "oast;", "ocir;", "ocirc", "ocirc;", "ocy;", "odash;", "odblac;", "odiv;", "odot;", "odsold;", "oelig;", "ofcir;", "ofr;", "ogon;", "ograve", "ograve;", "ogt;", "ohbar;", "ohm;", "oint;", "olarr;", "olcir;", "olcross;", "oline;", "olt;", "omacr;", "omega;", "omicron;", "omid;", "ominus;", "oopf;", "opar;", "operp;", "oplus;", "or;", "orarr;", "ord;", "order;", "orderof;", "ordf", "ordf;", "ordm", "ordm;", "origof;", "oror;", "orslope;", "orv;", "oscr;", "oslash", "oslash;", "osol;", "otilde", "otilde;", "otimes;", "otimesas;", "ouml", "ouml;", "ovbar;", "par;", "para", "para;", "parallel;", "parsim;", "parsl;", "part;", "pcy;", "percnt;", "period;", "permil;", "perp;", "pertenk;", "pfr;", "phi;", "phiv;", "phmmat;", "phone;", "pi;", "pitchfork;", "piv;", "planck;", "planckh;", "plankv;", "plus;", "plusacir;", "plusb;", "pluscir;", "plusdo;", "plusdu;", "pluse;", "plusmn", "plusmn;", "plussim;", "plustwo;", "pm;", "pointint;", "popf;", "pound", "pound;", "pr;", "prE;", "prap;", "prcue;", "pre;", "prec;", "precapprox;", "preccurlyeq;", "preceq;", "precnapprox;", "precneqq;", "precnsim;", "precsim;", "prime;", "primes;", "prnE;", "prnap;", "prnsim;", "prod;", "profalar;", "profline;", "profsurf;", "prop;", "propto;", "prsim;", "prurel;", "pscr;", "psi;", "puncsp;", "qfr;", "qint;", "qopf;", "qprime;", "qscr;", "quaternions;", "quatint;", "quest;", "questeq;", "quot", "quot;", "rAarr;", "rArr;", "rAtail;", "rBarr;", "rHar;", "race;", "racute;", "radic;", "raemptyv;", "rang;", "rangd;", "range;", "rangle;", "raquo", "raquo;", "rarr;", "rarrap;", "rarrb;", "rarrbfs;", "rarrc;", "rarrfs;", "rarrhk;", "rarrlp;", "rarrpl;", "rarrsim;", "rarrtl;", "rarrw;", "ratail;", "ratio;", "rationals;", "rbarr;", "rbbrk;", "rbrace;", "rbrack;", "rbrke;", "rbrksld;", "rbrkslu;", "rcaron;", "rcedil;", "rceil;", "rcub;", "rcy;", "rdca;", "rdldhar;", "rdquo;", "rdquor;", "rdsh;", "real;", "realine;", "realpart;", "reals;", "rect;", "reg", "reg;", "rfisht;", "rfloor;", "rfr;", "rhard;", "rharu;", "rharul;", "rho;", "rhov;", "rightarrow;", "rightarrowtail;", "rightharpoondown;", "rightharpoonup;", "rightleftarrows;", "rightleftharpoons;", "rightrightarrows;", "rightsquigarrow;", "rightthreetimes;", "ring;", "risingdotseq;", "rlarr;", "rlhar;", "rlm;", "rmoust;", "rmoustache;", "rnmid;", "roang;", "roarr;", "robrk;", "ropar;", "ropf;", "roplus;", "rotimes;", "rpar;", "rpargt;", "rppolint;", "rrarr;", "rsaquo;", "rscr;", "rsh;", "rsqb;", "rsquo;", "rsquor;", "rthree;", "rtimes;", "rtri;", "rtrie;", "rtrif;", "rtriltri;", "ruluhar;", "rx;", "sacute;", "sbquo;", "sc;", "scE;", "scap;", "scaron;", "sccue;", "sce;", "scedil;", "scirc;", "scnE;", "scnap;", "scnsim;", "scpolint;", "scsim;", "scy;", "sdot;", "sdotb;", "sdote;", "seArr;", "searhk;", "searr;", "searrow;", "sect", "sect;", "semi;", "seswar;", "setminus;", "setmn;", "sext;", "sfr;", "sfrown;", "sharp;", "shchcy;", "shcy;", "shortmid;", "shortparallel;", "shy", "shy;", "sigma;", "sigmaf;", "sigmav;", "sim;", "simdot;", "sime;", "simeq;", "simg;", "simgE;", "siml;", "simlE;", "simne;", "simplus;", "simrarr;", "slarr;", "smallsetminus;", "smashp;", "smeparsl;", "smid;", "smile;", "smt;", "smte;", "smtes;", "softcy;", "sol;", "solb;", "solbar;", "sopf;", "spades;", "spadesuit;", "spar;", "sqcap;", "sqcaps;", "sqcup;", "sqcups;", "sqsub;", "sqsube;", "sqsubset;", "sqsubseteq;", "sqsup;", "sqsupe;", "sqsupset;", "sqsupseteq;", "squ;", "square;", "squarf;", "squf;", "srarr;", "sscr;", "ssetmn;", "ssmile;", "sstarf;", "star;", "starf;", "straightepsilon;", "straightphi;", "strns;", "sub;", "subE;", "subdot;", "sube;", "subedot;", "submult;", "subnE;", "subne;", "subplus;", "subrarr;", "subset;", "subseteq;", "subseteqq;", "subsetneq;", "subsetneqq;", "subsim;", "subsub;", "subsup;", "succ;", "succapprox;", "succcurlyeq;", "succeq;", "succnapprox;", "succneqq;", "succnsim;", "succsim;", "sum;", "sung;", "sup1", "sup1;", "sup2", "sup2;", "sup3", "sup3;", "sup;", "supE;", "supdot;", "supdsub;", "supe;", "supedot;", "suphsol;", "suphsub;", "suplarr;", "supmult;", "supnE;", "supne;", "supplus;", "supset;", "supseteq;", "supseteqq;", "supsetneq;", "supsetneqq;", "supsim;", "supsub;", "supsup;", "swArr;", "swarhk;", "swarr;", "swarrow;", "swnwar;", "szlig", "szlig;", "target;", "tau;", "tbrk;", "tcaron;", "tcedil;", "tcy;", "tdot;", "telrec;", "tfr;", "there4;", "therefore;", "theta;", "thetasym;", "thetav;", "thickapprox;", "thicksim;", "thinsp;", "thkap;", "thksim;", "thorn", "thorn;", "tilde;", "times", "times;", "timesb;", "timesbar;", "timesd;", "tint;", "toea;", "top;", "topbot;", "topcir;", "topf;", "topfork;", "tosa;", "tprime;", "trade;", "triangle;", "triangledown;", "triangleleft;", "trianglelefteq;", "triangleq;", "triangleright;", "trianglerighteq;", "tridot;", "trie;", "triminus;", "triplus;", "trisb;", "tritime;", "trpezium;", "tscr;", "tscy;", "tshcy;", "tstrok;", "twixt;", "twoheadleftarrow;", "twoheadrightarrow;", "uArr;", "uHar;", "uacute", "uacute;", "uarr;", "ubrcy;", "ubreve;", "ucirc", "ucirc;", "ucy;", "udarr;", "udblac;", "udhar;", "ufisht;", "ufr;", "ugrave", "ugrave;", "uharl;", "uharr;", "uhblk;", "ulcorn;", "ulcorner;", "ulcrop;", "ultri;", "umacr;", "uml", "uml;", "uogon;", "uopf;", "uparrow;", "updownarrow;", "upharpoonleft;", "upharpoonright;", "uplus;", "upsi;", "upsih;", "upsilon;", "upuparrows;", "urcorn;", "urcorner;", "urcrop;", "uring;", "urtri;", "uscr;", "utdot;", "utilde;", "utri;", "utrif;", "uuarr;", "uuml", "uuml;", "uwangle;", "vArr;", "vBar;", "vBarv;", "vDash;", "vangrt;", "varepsilon;", "varkappa;", "varnothing;", "varphi;", "varpi;", "varpropto;", "varr;", "varrho;", "varsigma;", "varsubsetneq;", "varsubsetneqq;", "varsupsetneq;", "varsupsetneqq;", "vartheta;", "vartriangleleft;", "vartriangleright;", "vcy;", "vdash;", "vee;", "veebar;", "veeeq;", "vellip;", "verbar;", "vert;", "vfr;", "vltri;", "vnsub;", "vnsup;", "vopf;", "vprop;", "vrtri;", "vscr;", "vsubnE;", "vsubne;", "vsupnE;", "vsupne;", "vzigzag;", "wcirc;", "wedbar;", "wedge;", "wedgeq;", "weierp;", "wfr;", "wopf;", "wp;", "wr;", "wreath;", "wscr;", "xcap;", "xcirc;", "xcup;", "xdtri;", "xfr;", "xhArr;", "xharr;", "xi;", "xlArr;", "xlarr;", "xmap;", "xnis;", "xodot;", "xopf;", "xoplus;", "xotime;", "xrArr;", "xrarr;", "xscr;", "xsqcup;", "xuplus;", "xutri;", "xvee;", "xwedge;", "yacute", "yacute;", "yacy;", "ycirc;", "ycy;", "yen", "yen;", "yfr;", "yicy;", "yopf;", "yscr;", "yucy;", "yuml", "yuml;", "zacute;", "zcaron;", "zcy;", "zdot;", "zeetrf;", "zeta;", "zfr;", "zhcy;", "zigrarr;", "zopf;", "zscr;", "zwj;", "zwnj;" };

fn randAlphabeticAscii(rand: std.Random) u8 {
    var val = rand.uintAtMost(u8, 'Z' - 'A') + 'A';
    if (rand.boolean()) val += 'a' - 'A';
    std.debug.assert(std.ascii.isAlphabetic(val));
    return val;
}

const bench_iterations = 10_000_000;

fn bench(trie: anytype) !u64 {
    var timer = try std.time.Timer.start();

    var rng = std.Random.DefaultPrng.init(0);
    const rand = rng.random();

    var num: usize = 0;

    var buf: std.BoundedArray(u8, 64) = .{};
    for (0..bench_iterations) |_| {
        buf.clear();
        const ref = named_character_references[rand.uintLessThan(usize, named_character_references.len)];
        buf.appendSlice(ref) catch unreachable;

        const choice = rand.enumValue(enum {
            valid,
            character_swap,
            truncated,
            insert_character,
            append_character,
            ascii_char_followed_by_random_bytes,
            random_bytes,
        });

        switch (choice) {
            .valid => {},
            .character_swap => {
                buf.set(rand.uintLessThan(usize, buf.len), randAlphabeticAscii(rand));
            },
            .truncated => {
                buf.len -= rand.uintLessThan(usize, buf.len);
            },
            .insert_character => {
                buf.insert(rand.uintLessThan(usize, buf.len), randAlphabeticAscii(rand)) catch unreachable;
            },
            .append_character => {
                buf.append(randAlphabeticAscii(rand)) catch unreachable;
            },
            .ascii_char_followed_by_random_bytes => {
                buf.clear();
                buf.append(randAlphabeticAscii(rand)) catch unreachable;
                for (0..rand.uintLessThan(usize, 10)) |_| {
                    buf.appendAssumeCapacity(rand.int(u8));
                }
            },
            .random_bytes => {
                buf.clear();
                for (0..rand.uintLessThan(usize, 20)) |_| {
                    buf.appendAssumeCapacity(rand.int(u8));
                }
            },
        }

        const contains = trie.contains(buf.slice());
        if (contains) num += 1;
    }

    // The number of expected successful `contains` calls is known in advance
    // since we're using a specific PRNG seed. This just double checks that
    // each implementation gets the same result.
    if (num != 1740941) return error.BrokenImplementation;

    return timer.read();
}

test {
    var trie = try Trie.init(std.testing.allocator);
    defer trie.deinit();

    try trie.insert("hello");
    try trie.insert("jealous");
    try trie.insert("jello");

    try std.testing.expect(trie.contains("hello"));
    try std.testing.expect(trie.contains("jello"));
    try std.testing.expect(trie.contains("jealous"));
    try std.testing.expect(!trie.contains("jeal"));
    try std.testing.expect(!trie.contains("jealousy"));
    try std.testing.expect(!trie.contains("jell"));

    var trie_ll = try TrieWithLinkedListChildren.init(std.testing.allocator);
    defer trie_ll.deinit();

    try trie_ll.insert("hello");
    try trie_ll.insert("jealous");
    try trie_ll.insert("jello");

    try std.testing.expect(trie_ll.contains("hello"));
    try std.testing.expect(trie_ll.contains("jello"));
    try std.testing.expect(trie_ll.contains("jealous"));
    try std.testing.expect(!trie_ll.contains("jeal"));
    try std.testing.expect(!trie_ll.contains("jealousy"));
    try std.testing.expect(!trie_ll.contains("jell"));

    var flattened = try TrieAsArray.fromTrie(trie, std.testing.allocator);
    defer flattened.deinit();

    try std.testing.expect(flattened.contains("hello"));
    try std.testing.expect(flattened.contains("jello"));
    try std.testing.expect(flattened.contains("jealous"));
    try std.testing.expect(!flattened.contains("jeal"));
    try std.testing.expect(!flattened.contains("jealousy"));
    try std.testing.expect(!flattened.contains("jell"));
}