voroskoi/skiplist.zig - Change 5WBYLJAC3MP52G4F5KHVTXOGCBYS7RFACMFQEAAA2D2TON4OBAGQC

benchmark rework

Created by voroskoi on December 22, 2024

5WBYLJAC3MP52G4F5KHVTXOGCBYS7RFACMFQEAAA2D2TON4OBAGQC

Dependencies

In channels

main

Change contents

Replacement in src/skipqueue.zig at line 44 [3.38]

B:BD[3.1410] → [4.318:437]

        pub fn deinit(self: @This(), allocator: std.mem.Allocator) void {
            self.skiplist.deinit(allocator);

[3.1410]

[3.1490]

        pub fn deinit(self: @This()) void {
            self.skiplist.deinit();

Replacement in src/skipqueue.zig at line 48 [3.38]

B:BD[3.1501] → [4.438:595]

        pub fn add(self: *@This(), allocator: std.mem.Allocator, item: T) !void {
            _ = try self.skiplist.insert(allocator, item.key, item.value);

[3.1501]

[3.1617]

        pub fn add(self: *@This(), item: T) !void {
            _ = try self.skiplist.insert(item.key, item.value);

Replacement in src/skipqueue.zig at line 52 [3.38]

B:BD[3.1628] → [4.596:670]

        pub fn remove(self: *@This(), allocator: std.mem.Allocator) !?T {

[3.1628]

[3.1672]

        pub fn remove(self: *@This()) ?T {

Replacement in src/skipqueue.zig at line 54 [3.38]

B:BD[3.1704] → [3.1704:1747]

            var curr = self.skiplist.head;

[3.1704]

[3.1747]

            var curr = self.skiplist.getHead();

Replacement in src/skipqueue.zig at line 68 [3.38]

B:BD[3.2169] → [4.748:816]

                _ = try self.skiplist.remove(allocator, ret.?.key);

[3.2169]

[3.2226]

                _ = self.skiplist.remove(ret.?.key);

Deletion in src/main.zig at line 3 [5.33]
∅:D[3.2322] → [5.101:102]
B:BD[5.101] → [5.101:102]
B:BD[5.102] → [6.1106:1147]
```
pub const io_mode = std.io.Mode.evented;
```

Replacement in src/main.zig at line 11 [5.33]

B:BD[6.1396] → [4.1423:1444]

∅:D[4.1444] → [7.24:45]

B:BD[7.24] → [7.24:45]

B:BD[7.45] → [2.0:29]

    try benchPugh();
    try benchLazy();
    // try benchSkipQueue();

[6.1396]

[7.45]

    try benchSkipQueue();
    // try benchPugh();
    try benchLazyST();
    try benchLazyMT();

Deletion in src/main.zig at line 18 [5.33]

∅:D[7.71] → [6.1396:1541]

B:BD[6.1396] → [6.1396:1541]

    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    var arena = std.heap.ArenaAllocator.init(gpa.allocator());
    defer arena.deinit();

Replacement in src/main.zig at line 19 [5.33]

B:BD[6.1634] → [6.1634:1698]

        .init(arena.allocator(), BENCH_SKIP_SIZE, BENCH_ITEMS);

[6.1634]

[5.317]

        .init(std.heap.page_allocator, BENCH_SKIP_SIZE, BENCH_ITEMS);

Replacement in src/main.zig at line 29 [5.33]

B:BD[6.1923] → [8.99:212]

∅:D[8.212] → [6.2044:2076]

B:BD[6.2044] → [6.2044:2076]

        const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), std.math.maxInt(BENCH_KEY));
        try sl.insert(key, {});

[6.1923]

[6.2076]

        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);
            },
        }

Replacement in src/main.zig at line 48 [5.33]

B:BD[8.214] → [7.72:95]

fn benchLazy() !void {

[8.214]

[2.30]

fn benchLazyST() !void {
    const Stats = struct {
        hit: [3]usize = .{ 0, 0, 0 },
        total: [3]usize = .{ 0, 0, 0 },
    };

Insertion in src/main.zig at line 59 [5.33]
[7.454]
[8.619]
```
    var st = Stats{};
```

Replacement in src/main.zig at line 62 [5.33]

B:BD[8.620] → [4.1935:2012]

    // { // single thread
    //     var timer = try std.time.Timer.start();

[8.620]

[8.700]

    var timer = try std.time.Timer.start();
    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);
        const query_type = rnd.intRangeAtMostBiased(u8, 0, 99);
        switch (query_type) {
            0 => { // 1% remove
                st.total[0] = st.total[0] + 1;
                if (sl.remove(key)) st.hit[0] = st.hit[0] + 1;
            },
            1...9 => { // 9% insert
                st.total[1] = st.total[1] + 1;
                if (try sl.insert(key, {})) st.hit[1] = st.hit[1] + 1;
            },
            else => { // 90% search
                st.total[2] = st.total[2] + 1;
                if (sl.search(key) != null) st.hit[2] = st.hit[2] + 1;
            },
        }
    }

Replacement in src/main.zig at line 86 [5.33]

B:BD[8.701] → [4.2013:2283]

    //     var i: usize = 0;
    //     while (i < BENCH_ITEMS) : (i += 1) {
    //         const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), std.math.maxInt(BENCH_KEY));
    //         _ = try sl.insert(tsa.allocator(), key, {});
    //     }

[8.701]

[8.902]

    std.debug.print("Lazy 1 thread: {d} ms\n", .{timer.read() / std.time.ns_per_ms});
    std.debug.print("Total items: {d}, remove {d}/{d}, insert {d}/{d}, search {d}/{d}\n", .{
        BENCH_ITEMS,
        st.hit[0],
        st.total[0],
        st.hit[1],
        st.total[1],
        st.hit[2],
        st.total[2],
    });
}
fn benchLazyMT() !void {
    const Functions = struct {
        fn insert(skiplist: SL, key: BENCH_KEY, val: BENCH_VALUE) void {
            _ = @call(std.builtin.CallModifier.auto, SL.insert, .{ skiplist, key, val }) catch unreachable;
        }
        fn remove(skiplist: SL, key: BENCH_KEY) void {
            _ = @call(std.builtin.CallModifier.auto, SL.remove, .{ skiplist, key });
        }
        fn search(skiplist: SL, key: BENCH_KEY) void {
            _ = @call(std.builtin.CallModifier.auto, SL.search, .{ skiplist, key });
        }
    };

Replacement in src/main.zig at line 111 [5.33]

B:BD[8.903] → [4.2284:2386]

    //     std.debug.print("Lazy 1 thread: {d} ms\n", .{timer.read() / std.time.ns_per_ms});
    // }

[8.903]

[4.2386]

    var sl = try SL.init(std.heap.page_allocator);
    defer sl.deinit();

Replacement in src/main.zig at line 114 [5.33]

B:BD[4.2387] → [4.2387:2435]

    { // multithread
        const THREADS = 4;

[4.2387]

[4.2435]

    var rand = std.rand.DefaultPrng.init(@intCast(std.time.milliTimestamp()));
    const rnd = rand.random();

Replacement in src/main.zig at line 117 [5.33]

B:BD[4.2436] → [4.2436:2530]

B:BD[4.2530] → [2.105:155]

∅:D[2.155] → [4.2574:2687]

B:BD[4.2574] → [4.2574:2687]

        var pool: std.Thread.Pool = undefined;
        try pool.init(std.Thread.Pool.Options{
            .allocator = std.heap.page_allocator,
            .n_jobs = THREADS,
        });
        defer pool.deinit();
        var wg = std.Thread.WaitGroup{};

[4.2436]

[4.2687]

    var pool: std.Thread.Pool = undefined;
    try pool.init(std.Thread.Pool.Options{
        .allocator = std.heap.page_allocator,
    });
    defer pool.deinit();
    var wg = std.Thread.WaitGroup{};

Replacement in src/main.zig at line 124 [5.33]

B:BD[4.2688] → [4.2688:2736]

        var timer = try std.time.Timer.start();

[4.2688]

[8.950]

    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 127 [5.33]

B:BD[8.951] → [4.2737:2952]

B:BD[4.2952] → [2.156:215]

        for (0..BENCH_ITEMS) |_| {
            const key = rnd.intRangeAtMostBiased(
                BENCH_KEY,
                std.math.minInt(BENCH_KEY),
                std.math.maxInt(BENCH_KEY),
            );
            pool.spawnWg(&wg, testIns, .{ &sl, key, {} });

[8.951]

[4.3036]

        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
                pool.spawnWg(&wg, Functions.search, .{ sl, key });
            },

Insertion in src/main.zig at line 139 [5.33]
[4.3046]
[8.1396]
```
    }
```
Replacement in src/main.zig at line 141 [5.33]
B:BD[8.1397] → [4.3047:3078]
```
        pool.waitAndWork(&wg);
```
[8.1397]
[8.1422]
```
    var timer = try std.time.Timer.start();
```
Replacement in src/main.zig at line 143 [5.33]
B:BD[8.1423] → [4.3079:3189]
∅:D[4.3189] → [7.1343:1345]
B:BD[7.1343] → [7.1343:1345]
```
        std.debug.print("Lazy {d} threads: {d} ms\n", .{ THREADS, timer.read() / std.time.ns_per_ms });
    }
}
```
[8.1423]
[8.1514]
```
    pool.waitAndWork(&wg);
```

Replacement in src/main.zig at line 145 [5.33]

B:BD[8.1515] → [2.216:383]

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

[8.1515]

[3.2350]

    std.debug.print("Lazy {d} threads: {d} ms\n", .{
        try std.Thread.getCpuCount(),
        timer.read() / std.time.ns_per_ms,
    });

Replacement in src/main.zig at line 158 [5.33]
B:BD[3.2540] → [4.3399:3445]
```
    defer sq.deinit(std.heap.page_allocator);
```
[3.2540]
[3.2563]
```
    defer sq.deinit();
```

Replacement in src/main.zig at line 160 [5.33]

B:BD[3.2564] → [4.3446:3718]

    try sq.add(std.heap.page_allocator, .{ .key = 1, .value = 1 });
    try sq.add(std.heap.page_allocator, .{ .key = 2, .value = 2 });
    try sq.add(std.heap.page_allocator, .{ .key = 3, .value = 3 });
    try sq.add(std.heap.page_allocator, .{ .key = 0, .value = 4 });

[3.2564]

[3.2736]

    try sq.add(.{ .key = 1, .value = 1 });
    try sq.add(.{ .key = 2, .value = 2 });
    try sq.add(.{ .key = 3, .value = 3 });
    try sq.add(.{ .key = 0, .value = 4 });

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

B:BD[3.2737] → [4.3719:4099]

    std.debug.assert((try sq.remove(std.heap.page_allocator)).?.value == 4);
    std.debug.assert((try sq.remove(std.heap.page_allocator)).?.value == 1);
    std.debug.assert((try sq.remove(std.heap.page_allocator)).?.value == 2);
    std.debug.assert((try sq.remove(std.heap.page_allocator)).?.value == 3);
    std.debug.assert((try sq.remove(std.heap.page_allocator)) == null);

[3.2737]

[8.1751]

    std.debug.assert((sq.remove()).?.value == 4);
    std.debug.assert((sq.remove()).?.value == 1);
    std.debug.assert((sq.remove()).?.value == 2);
    std.debug.assert((sq.remove()).?.value == 3);
    std.debug.assert((sq.remove()) == null);

Insertion in src/lazy.zig at line 60 [9.108]

[9.1660]


        /// getHead returns the head element.
        pub fn getHead(self: @This()) *Node {
            _ = self;
            return head;
        }

Replacement in src/lazy.zig at line 157 [9.108]

B:BD[9.5810] → [2.1582:1660]

        pub fn insert(self: *@This(), insert_key: K, insert_value: V) !bool {

[9.5810]

[2.1660]

        pub fn insert(self: @This(), insert_key: K, insert_value: V) !bool {

Deletion in src/lazy.zig at line 187 [9.108]
B:BD[9.7468] → [4.7622:7712]
∅:D[4.7712] → [9.7508:7509]
B:BD[9.7508] → [9.7508:7509]
```
                    // std.debug.print("\n{any} locks:\n", .{std.Thread.getCurrentId()});
```

Deletion in src/lazy.zig at line 192 [9.108]

B:BD[4.7939] → [4.7939:8028]

                            // std.debug.print("\t{d} {any}\n", .{ level, pred.?.key });