voroskoi/skiplist.zig - Change XKMEZUFTLVXL65G6JWQQ6I7HRDHZDUSM3KQQVZ6RVIKOW2OLUKBAC

Remove libxev

Created by voroskoi on January 11, 2025

XKMEZUFTLVXL65G6JWQQ6I7HRDHZDUSM3KQQVZ6RVIKOW2OLUKBAC

Dependencies

In channels

main

Change contents

Replacement in src/main.zig at line 12 [4.33]
B:BD[3.1396] → [2.73:102]
∅:D[2.102] → [5.371:395]
B:BD[5.371] → [5.371:395]
B:BD[5.395] → [2.103:129]
```
    // try benchSkipQueue();
    // try benchPugh();
    // try benchLazyST();
```
[3.1396]
[5.418]
```
    try benchSkipQueue();
    try benchPugh();
    try benchLazyST();
```
Deletion in src/main.zig at line 16 [4.33]
B:BD[5.441] → [2.130:153]
```
    // try benchXev();
```

Deletion in src/main.zig at line 140 [4.33]

B:BD[2.3107] → [2.3107:3658]

∅:D[6.770] → [7.950:951]

∅:D[8.2736] → [7.950:951]

∅:D[5.3468] → [7.950:951]

∅:D[2.3658] → [7.950:951]

B:BD[7.950] → [7.950:951]

B:BD[7.951] → [5.3469:3595]

B:BD[5.3595] → [2.3659:3729]

∅:D[2.3729] → [5.3662:3713]

B:BD[5.3662] → [5.3662:3713]

B:BD[5.3713] → [2.3730:3804]

∅:D[2.3804] → [5.3784:3835]

B:BD[5.3784] → [5.3784:3835]

B:BD[5.3835] → [2.3805:4278]

∅:D[2.4278] → [5.3902:3917]

B:BD[5.3902] → [5.3902:3917]

∅:D[9.215] → [8.3036:3046]

∅:D[5.3917] → [8.3036:3046]

B:BD[8.3036] → [8.3036:3046]

B:BD[8.3046] → [5.3918:3924]

∅:D[6.1236] → [7.1396:1397]

∅:D[8.3046] → [7.1396:1397]

∅:D[5.3924] → [7.1396:1397]

B:BD[7.1396] → [7.1396:1397]

B:BD[7.1397] → [5.3925:3969]


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);
        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
                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);
            },
        }
    }
    var timer = try std.time.Timer.start();

Deletion in src/main.zig at line 141 [4.33]

B:BD[7.1423] → [2.4279:4294]

∅:D[6.1345] → [7.1514:1515]

∅:D[5.3997] → [7.1514:1515]

∅:D[2.4294] → [7.1514:1515]

B:BD[7.1514] → [7.1514:1515]

B:BD[7.1515] → [5.3998:4140]

B:BD[5.4140] → [2.4295:6174]

∅:D[9.383] → [10.2350:2353]

∅:D[8.3398] → [10.2350:2353]

∅:D[5.4140] → [10.2350:2353]

∅:D[2.6174] → [10.2350:2353]

B:BD[7.1751] → [10.2350:2353]

    wg.wait();
    std.debug.print("Lazy {d} threads: {d} ms\n", .{
        try std.Thread.getCpuCount(),
        timer.read() / std.time.ns_per_ms,
    });
}
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);
}

Deletion in build.zig.zon at line 40 [2.9191]

B:BD[2.11129] → [2.11129:11367]

        .libxev = .{
            .url = "https://github.com/mitchellh/libxev/archive/db6a52bafadf00360e675fefa7926e8e6c0e9931.tar.gz",
            .hash = "12206029de146b685739f69b10a6f08baee86b3d0a5f9a659fa2b2b66c9602078bbf",
        },

Deletion in build.zig at line 14 [11.8644]

B:BD[11.8908] → [2.12045:12188]

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