voroskoi/skiplist.zig - Change LVNADDHM446QNUHG3VTNBOHNJGCDROOFBVGO4WXMUUAN6Y4LNCNAC

messy commit

Created by voroskoi on December 26, 2024

LVNADDHM446QNUHG3VTNBOHNJGCDROOFBVGO4WXMUUAN6Y4LNCNAC

Dependencies

In channels

main

Change contents

Insertion in src/main.zig at line 7 [4.33]

[3.1346]

const BENCH_LIMIT_FACTOR = 20; // make 50% of removes (1%) actually hit

Replacement in src/main.zig at line 12 [4.33]
B:BD[3.1396] → [5.345:371]
```
    try benchSkipQueue();
```
[3.1396]
[5.371]
```
    // try benchSkipQueue();
```
Replacement in src/main.zig at line 14 [4.33]
B:BD[5.395] → [5.395:418]
```
    try benchLazyST();
```
[5.395]
[5.418]
```
    // try benchLazyST();
```

Replacement in src/main.zig at line 16 [4.33]

∅:D[6.29] → [7.45:71]

∅:D[5.441] → [7.45:71]

∅:D[8.2349] → [7.45:71]

B:BD[7.45] → [7.45:71]

B:BD[3.1541] → [3.1541:1634]

B:BD[3.1634] → [5.442:512]

∅:D[5.512] → [4.317:341]

∅:D[3.1698] → [4.317:341]

B:BD[4.317] → [4.317:341]

B:BD[4.341] → [9.1445:1524]

∅:D[9.1524] → [3.1783:1814]

B:BD[3.1783] → [3.1783:1814]

∅:D[3.1814] → [4.768:769]

B:BD[4.768] → [4.768:769]

B:BD[4.769] → [3.1815:1859]

∅:D[3.1859] → [4.787:788]

B:BD[4.787] → [4.787:788]

B:BD[4.788] → [3.1860:1923]

B:BD[3.1923] → [5.513:989]

∅:D[5.989] → [3.2076:2082]

B:BD[3.2076] → [3.2076:2082]

∅:D[3.2082] → [4.1124:1125]

B:BD[4.1124] → [4.1124:1125]

B:BD[4.1125] → [9.1525:1602]

}
fn benchPugh() !void {
    var sl = try SkipList.Pugh(BENCH_KEY, BENCH_VALUE, {}, comptime std.sort.asc(BENCH_KEY))
        .init(std.heap.page_allocator, BENCH_SKIP_SIZE, BENCH_ITEMS);
    defer sl.deinit();
    var rand = std.rand.DefaultPrng.init(@intCast(std.time.milliTimestamp()));
    const rnd = rand.random();
    var timer = try std.time.Timer.start();
    var i: usize = 0;
    while (i < BENCH_ITEMS) : (i += 1) {
        const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), BENCH_ITEMS / 2);
        const query_type = rnd.intRangeAtMostBiased(u8, 0, 99);
        switch (query_type) {
            0 => { // 1% remove
                _ = try sl.remove(key);
            },
            1...9 => { // 9% insert
                _ = try sl.insert(key, {});
            },
            else => { // 90% search
                _ = sl.search(key);
            },
        }
    }
    std.debug.print("Pugh: {d} ms\n", .{timer.read() / std.time.ns_per_ms});

[5.441]

[4.1174]

    // try benchXev();

Insertion in src/main.zig at line 30 [4.33]

[7.454]

[5.1129]


    for (0..BENCH_ITEMS) |_| {
        const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), std.math.maxInt(BENCH_KEY));
        _ = try sl.insert(key, {});
    }
    std.debug.print("Prepared skiplist with {d} elements...\n", .{BENCH_ITEMS});

Replacement in src/main.zig at line 41 [4.33]

B:BD[5.1198] → [5.1198:1453]

    var i: usize = 0;
    while (i < BENCH_ITEMS) : (i += 1) {
        // BENCH_ITEMS/20 means 50% of each call (remove, insert, search) hits a target
        const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), BENCH_ITEMS / 20);

[5.1198]

[5.1453]

    for (0..BENCH_ITEMS) |_| {

Replacement in src/main.zig at line 44 [4.33]

B:BD[5.1547] → [5.1547:1579]

            0 => { // 1% remove

[5.1547]

[5.1579]

            0...1 => { // 2% remove
                const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), BENCH_ITEMS / BENCH_LIMIT_FACTOR);

Replacement in src/main.zig at line 49 [4.33]

B:BD[5.1704] → [5.1704:1740]

            1...9 => { // 9% insert

[5.1704]

[5.1740]

            2...10 => { // 9% insert
                const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), BENCH_ITEMS / BENCH_LIMIT_FACTOR);

Replacement in src/main.zig at line 54 [4.33]

B:BD[5.1873] → [5.1873:1909]

            else => { // 90% search

[5.1873]

[5.1909]

            else => { // 89% search
                const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), BENCH_ITEMS / BENCH_LIMIT_FACTOR);

Replacement in src/main.zig at line 63 [4.33]

B:BD[5.2145] → [5.2145:2259]

    std.debug.print("Total items: {d}, remove {d}/{d}, insert {d}/{d}, search {d}/{d}\n", .{
        BENCH_ITEMS,

[5.2145]

[5.2259]

    std.debug.print("Stats: remove {d}/{d}, insert {d}/{d}, search {d}/{d}\n", .{

Insertion in src/main.zig at line 74 [4.33]
[5.2415]
[5.2415]
```
    const BATCH_SIZE = 100;
```

Replacement in src/main.zig at line 77 [4.33]

B:BD[5.2446] → [5.2446:2627]

        fn insert(skiplist: SL, key: BENCH_KEY, val: BENCH_VALUE) void {
            _ = @call(std.builtin.CallModifier.auto, SL.insert, .{ skiplist, key, val }) catch unreachable;

[5.2446]

[5.2627]

        fn insert(skiplist: SL, rnd: std.Random) void {
            for (0..BATCH_SIZE) |_| {
                const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), BENCH_ITEMS / BENCH_LIMIT_FACTOR);
                _ = @call(std.builtin.CallModifier.auto, SL.insert, .{ skiplist, key, {} }) catch unreachable;
            }

Replacement in src/main.zig at line 83 [4.33]

B:BD[5.2637] → [5.2637:2777]

        fn remove(skiplist: SL, key: BENCH_KEY) void {
            _ = @call(std.builtin.CallModifier.auto, SL.remove, .{ skiplist, key });

[5.2637]

[5.2777]

        fn remove(skiplist: SL, rnd: std.Random) void {
            for (0..BATCH_SIZE) |_| {
                const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), BENCH_ITEMS / BENCH_LIMIT_FACTOR);
                _ = @call(std.builtin.CallModifier.auto, SL.remove, .{ skiplist, key });
            }

Replacement in src/main.zig at line 89 [4.33]

B:BD[5.2787] → [5.2787:2927]

        fn search(skiplist: SL, key: BENCH_KEY) void {
            _ = @call(std.builtin.CallModifier.auto, SL.search, .{ skiplist, key });

[5.2787]

[5.2927]

        fn search(skiplist: SL, rnd: std.Random) void {
            for (0..BATCH_SIZE) |_| {
                const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), BENCH_ITEMS / BENCH_LIMIT_FACTOR);
                _ = @call(std.builtin.CallModifier.auto, SL.search, .{ skiplist, key });
            }

Replacement in src/main.zig at line 104 [4.33]

B:BD[5.3174] → [5.3174:3271]

    try pool.init(std.Thread.Pool.Options{
        .allocator = std.heap.page_allocator,
    });

[5.3174]

[5.3271]

    try pool.init(std.Thread.Pool.Options{ .allocator = std.heap.page_allocator });

Replacement in src/main.zig at line 109 [4.33]

B:BD[5.3365] → [5.3365:3468]

        const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), BENCH_ITEMS / 20);

[5.3365]

[10.950]

        const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), std.math.maxInt(BENCH_KEY));
        _ = try sl.insert(key, {});
    }
    std.debug.print("Prepared skiplist with {d} elements...\n", .{BENCH_ITEMS});
    for (0..BENCH_ITEMS / BATCH_SIZE) |_| {
        const query_type = rnd.intRangeAtMostBiased(u8, 0, 99);
        switch (query_type) {
            0...1 => { // 2% remove
                pool.spawnWg(&wg, Functions.remove, .{ sl, rnd });
            },
            2...10 => { // 9% insert
                pool.spawnWg(&wg, Functions.insert, .{ sl, rnd });
            },
            else => { // 89% search
                pool.spawnWg(&wg, Functions.search, .{ sl, rnd });
            },
        }
    }
    var timer = try std.time.Timer.start();
    pool.waitAndWork(&wg);
    std.debug.print("Lazy {d} threads: {d} ms\n", .{
        try std.Thread.getCpuCount(),
        timer.read() / std.time.ns_per_ms,
    });
}
fn benchLazyXev() !void {
    const xev = @import("xev");
    var sl = try SL.init(std.heap.page_allocator);
    defer sl.deinit();
    var rand = std.rand.DefaultPrng.init(@intCast(std.time.milliTimestamp()));
    const rnd = rand.random();
    var pool = xev.ThreadPool.init(xev.ThreadPool.Config{});
    defer {
        pool.shutdown();
        pool.deinit();
    }
    const wg = std.Thread.WaitGroup{};
    for (0..BENCH_ITEMS) |_| {
        // const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), BENCH_ITEMS / 20);

Replacement in src/main.zig at line 162 [4.33]

B:BD[5.3595] → [5.3595:3662]

                pool.spawnWg(&wg, Functions.remove, .{ sl, key });

[5.3595]

[5.3662]

                // pool.spawnWg(&wg, Functions.remove, .{ sl, key });

Replacement in src/main.zig at line 165 [4.33]

B:BD[5.3713] → [5.3713:3784]

                pool.spawnWg(&wg, Functions.insert, .{ sl, key, {} });

[5.3713]

[5.3784]

                // pool.spawnWg(&wg, Functions.insert, .{ sl, key, {} });

Replacement in src/main.zig at line 168 [4.33]

B:BD[5.3835] → [5.3835:3902]

                pool.spawnWg(&wg, Functions.search, .{ sl, key });

[5.3835]

[5.3902]

                const task = xev.ThreadPool.Task{
                    .callback = struct {
                        fn callback(_: *xev.ThreadPool.Task) void {
                            defer wg.finish();
                            // _ = sl.search(key);
                        }
                    }.callback,
                };
                const batch = xev.ThreadPool.Batch.from(task);
                wg.start();
                xev.ThreadPool.schedule(batch);

Replacement in src/main.zig at line 185 [4.33]
B:BD[10.1423] → [5.3970:3997]
```
    pool.waitAndWork(&wg);
```
[10.1423]
[10.1514]
```
    wg.wait();
```

Insertion in src/main.zig at line 191 [4.33]

[5.4140]

[8.2350]

}
fn benchXev() !void {
    const xev = @import("xev").IO_Uring;
    var rand = std.rand.DefaultPrng.init(@intCast(std.time.milliTimestamp()));
    const rnd = rand.random();
    const Callbacks = struct {
        fn search(
            sl: ?*SL,
            _: *xev.Loop,
            c: *xev.Completion,
            result: xev.Timer.RunError!void,
        ) xev.CallbackAction {
            _ = result catch unreachable;
            const key: usize = @intFromPtr(c.userdata);
            _ = sl.?.search(key);
            std.log.debug("searched for {d}", .{c.userdata.?});
            return .disarm;
        }
    };
    var sl = try SL.init(std.heap.page_allocator);
    defer sl.deinit();
    var loop = try xev.Loop.init(xev.Options{});
    defer loop.deinit();
    var keys = try std.ArrayList(usize).initCapacity(std.heap.page_allocator, BENCH_ITEMS);
    var comps = try std.ArrayList(xev.Completion).initCapacity(std.heap.page_allocator, BENCH_ITEMS);
    for (0..BENCH_ITEMS) |i| {
        const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), BENCH_ITEMS / 20);
        keys.appendAssumeCapacity(key);
        const query_type = rnd.intRangeAtMostBiased(u8, 0, 99);
        switch (query_type) {
            0 => { // 1% remove
                // pool.spawnWg(&wg, Functions.remove, .{ sl, key });
            },
            1...9 => { // 9% insert
                // pool.spawnWg(&wg, Functions.insert, .{ sl, key, {} });
            },
            else => { // 90% search
                comps.appendAssumeCapacity(xev.Completion{
                    .userdata = &keys.items[i],
                });
                var timer = try xev.Timer.init();
                defer timer.deinit();
                timer.run(&loop, &comps.items[i], 0, SL, &sl, Callbacks.search);
            },
        }
    }
    try loop.run(.until_done);

Insertion in src/main.zig at line 251 [4.33]

[8.2353]

fn benchPugh() !void {
    var sl = try SkipList.Pugh(BENCH_KEY, BENCH_VALUE, {}, comptime std.sort.asc(BENCH_KEY))
        .init(std.heap.page_allocator, BENCH_SKIP_SIZE, BENCH_ITEMS);
    defer sl.deinit();
    var rand = std.rand.DefaultPrng.init(@intCast(std.time.milliTimestamp()));
    const rnd = rand.random();
    var timer = try std.time.Timer.start();
    var i: usize = 0;
    while (i < BENCH_ITEMS) : (i += 1) {
        const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), BENCH_ITEMS / 2);
        const query_type = rnd.intRangeAtMostBiased(u8, 0, 99);
        switch (query_type) {
            0 => { // 1% remove
                _ = try sl.remove(key);
            },
            1...9 => { // 9% insert
                _ = try sl.insert(key, {});
            },
            else => { // 90% search
                _ = sl.search(key);
            },
        }
    }
    std.debug.print("Pugh: {d} ms\n", .{timer.read() / std.time.ns_per_ms});
}

Insertion in src/lazy.zig at line 2 [11.108]
[11.137]
[12.0]
```
const builtin = @import("builtin");
```

Insertion in src/lazy.zig at line 58 [11.108]

[9.4933]

[11.1434]


                std.debug.assert(n.key == key);

Insertion in src/lazy.zig at line 126 [11.108]

[11.4215]

                std.debug.assert(pred.nexts.len > level - 1);

Replacement in src/lazy.zig at line 128 [11.108]

B:BD[11.4273] → [11.4273:4353]

                while (curr != null and lessThan(context, curr.?.key.?, key)) {

[11.4273]

[11.4353]

                while (curr != null and curr.?.key != null and lessThan(context, curr.?.key.?, key)) {

Insertion in src/lazy.zig at line 155 [11.108]

[11.5291]

[6.1416]

            // const preds = self.allocator.alloc(?*Node, max_level) catch unreachable;
            // @memset(preds, null);
            // defer self.allocator.free(preds);
            // const succs = self.allocator.alloc(?*Node, max_level) catch unreachable;
            // @memset(succs, null);
            // defer self.allocator.free(succs);

Replacement in src/lazy.zig at line 244 [11.108]

B:BD[11.8670] → [2.966:1020]

                    for (0..node.nexts.len) |level| {

[11.8670]

[9.9519]

                    NEXT: for (0..node.nexts.len) |level| {

Insertion in src/lazy.zig at line 247 [11.108]

[9.9678]


                        if (builtin.mode == .Debug) {
                            var lit = locks.iterator(.{});
                            while (lit.next()) |lvl| {
                                if (preds[lvl].? == preds[level].?) continue :NEXT;
                            }
                            @panic("level is not locked...");
                        }
                    }
                    if (builtin.mode == .Debug) {
                        for (node.nexts) |item| {
                            std.debug.assert(node.nexts.len == rlevel + 1);
                            if (item != null) {
                                std.debug.assert(item.?.key != null);
                                continue;
                            }
                            std.debug.assert(item == null);
                        }

Insertion in src/lazy.zig at line 267 [11.108]
[9.9700]
[9.9700]

Replacement in src/lazy.zig at line 340 [11.108]

∅:D[2.1408] → [13.1855:1914]

∅:D[12.2239] → [13.1855:1914]

B:BD[13.1855] → [13.1855:1914]

                        while (level > 0) : (level -= 1) {

[2.1408]

[13.1914]

                        NEXT: while (level > 0) : (level -= 1) {

Insertion in src/lazy.zig at line 342 [11.108]

[13.2010]


                            if (builtin.mode == .Debug) {
                                var lit = locks.iterator(.{});
                                while (lit.next()) |lvl| {
                                    if (preds[lvl].? == preds[level - 1].?) continue :NEXT;
                                }
                                @panic("level is not locked...");
                            }

File addition: build.zig.zon (----------)

[14.1]

.{
    .name = "skiplist",
    .version = "0.0.0",
    .minimum_zig_version = "0.13.0",
    // This field is optional.
    // Each dependency must either provide a `url` and `hash`, or a `path`.
    // `zig build --fetch` can be used to fetch all dependencies of a package, recursively.
    // Once all dependencies are fetched, `zig build` no longer requires
    // internet connectivity.
    .dependencies = .{
        // See `zig fetch --save <url>` for a command-line interface for adding dependencies.
        //.example = .{
        //    // When updating this field to a new URL, be sure to delete the corresponding
        //    // `hash`, otherwise you are communicating that you expect to find the old hash at
        //    // the new URL.
        //    .url = "https://example.com/foo.tar.gz",
        //
        //    // This is computed from the file contents of the directory of files that is
        //    // obtained after fetching `url` and applying the inclusion rules given by
        //    // `paths`.
        //    //
        //    // This field is the source of truth; packages do not come from a `url`; they
        //    // come from a `hash`. `url` is just one of many possible mirrors for how to
        //    // obtain a package matching this `hash`.
        //    //
        //    // Uses the [multihash](https://multiformats.io/multihash/) format.
        //    .hash = "...",
        //
        //    // When this is provided, the package is found in a directory relative to the
        //    // build root. In this case the package's hash is irrelevant and therefore not
        //    // computed. This field and `url` are mutually exclusive.
        //    .path = "foo",
        //    // When this is set to `true`, a package is declared to be lazily
        //    // fetched. This makes the dependency only get fetched if it is
        //    // actually used.
        //    .lazy = false,
        //},
        .libxev = .{
            .url = "https://github.com/mitchellh/libxev/archive/db6a52bafadf00360e675fefa7926e8e6c0e9931.tar.gz",
            .hash = "12206029de146b685739f69b10a6f08baee86b3d0a5f9a659fa2b2b66c9602078bbf",
        },
    },
    // Specifies the set of files and directories that are included in this package.
    // Only files and directories listed here are included in the `hash` that
    // is computed for this package. Only files listed here will remain on disk
    // when using the zig package manager. As a rule of thumb, one should list
    // files required for compilation plus any license(s).
    // Paths are relative to the build root. Use the empty string (`""`) to refer to
    // the build root itself.
    // A directory listed here means that all files within, recursively, are included.
    .paths = .{
        "build.zig",
        "build.zig.zon",
        "src",
    },
}

Insertion in build.zig at line 14 [15.8644]

[15.8908]

[9.13463]

    const xev = b.dependency("libxev", .{ .target = target, .optimize = optimize });
    exe.root_module.addImport("xev", xev.module("xev"));