voroskoi/skiplist.zig - Change NKL44S6YUCLZDH5EDDUJB5BHX2QWDP7SI5RROBVAUXKAU4ADKPAQC

another messy update

Created by voroskoi on December 21, 2024

NKL44S6YUCLZDH5EDDUJB5BHX2QWDP7SI5RROBVAUXKAU4ADKPAQC

Dependencies

In channels

main

Change contents

Replacement in src/main.zig at line 15 [5.33]
B:BD[3.45] → [4.2323:2349]
```
    try benchSkipQueue();
```
[3.45]
[3.45]
```
    // try benchSkipQueue();
```

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

B:BD[3.95] → [2.1603:1674]

∅:D[2.1674] → [3.213:239]

B:BD[3.213] → [3.213:239]

B:BD[3.239] → [2.1675:1768]

∅:D[3.239] → [6.392:393]

∅:D[2.1768] → [6.392:393]

B:BD[6.392] → [6.392:393]

B:BD[6.393] → [2.1769:1854]

    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    // var tsa = std.heap.ThreadSafeAllocator{ .child_allocator = std.heap.page_allocator };
    var sl = try SL.init(arena.allocator());
    defer sl.deinit(arena.allocator());

[3.95]

[6.497]

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

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

B:BD[2.2530] → [2.2530:2574]

            .allocator = arena.allocator(),

[2.2530]

[2.2574]

            .allocator = std.heap.page_allocator,

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

B:BD[2.2952] → [2.2952:3036]

            pool.spawnWg(&wg, testIns, .{ std.heap.page_allocator, &sl, key, {} });

[2.2952]

[2.3036]

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

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

B:BD[6.1515] → [2.3190:3398]

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

[6.1515]

[4.2350]

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

Replacement in src/lazy.zig at line 24 [7.108]

B:BD[7.319] → [2.4609:4649]

∅:D[2.4649] → [7.319:354]

B:BD[7.319] → [7.319:354]

B:BD[7.591] → [7.591:663]

        // XXX: these should be hidden!
        rnd: std.rand.DefaultPrng,
        /// Starting Node pointer of the SkipList.
        head: *Node,

[7.319]

[7.663]

        /// Allocator to use when creating SkipList and its Node items.
        /// Make sure it is threadsafe if You want to use the SkipList from multiple threads!
        allocator: std.mem.Allocator,
        var rnd: std.rand.DefaultPrng = undefined;
        var head: *Node = undefined;

Insertion in src/lazy.zig at line 62 [7.108]
[7.1868]
[2.4934]
```
            _ = self;
```

Replacement in src/lazy.zig at line 66 [7.108]

B:BD[7.2084] → [7.2084:2147]

                var node: ?*Node = self.head.nexts[level - 1];

[7.2084]

[7.2147]

                var node: ?*Node = head.nexts[level - 1];

Replacement in src/lazy.zig at line 81 [7.108]

B:BD[7.3100] → [7.3100:3130]

B:BD[7.3130] → [2.5199:5286]

∅:D[2.5286] → [7.3302:3337]

B:BD[7.3302] → [7.3302:3337]

            var sl = @This(){
                .rnd = std.rand.DefaultPrng.init(@intCast(std.time.milliTimestamp())),
                .head = undefined,

[7.2921]

[7.3337]

            const sl = @This(){
                .allocator = allocator,

Replacement in src/lazy.zig at line 84 [7.108]

B:BD[7.3352] → [2.5287:5349]

∅:D[2.5349] → [7.3470:3502]

B:BD[7.3470] → [7.3470:3502]

            sl.head = try Node.init(allocator, 0, max_level);
            sl.head.key = null;

[7.3352]

[7.3502]

            rnd = std.rand.DefaultPrng.init(@intCast(std.time.milliTimestamp()));
            head = try Node.init(allocator, 0, max_level);
            head.key = null;

Replacement in src/lazy.zig at line 90 [7.108]

B:BD[7.3536] → [2.5350:5424]

∅:D[2.5424] → [7.3602:3646]

B:BD[7.3602] → [7.3602:3646]

        pub fn deinit(self: @This(), allocator: std.mem.Allocator) void {
            var current: *Node = self.head;

[7.3536]

[7.3646]

        pub fn deinit(self: @This()) void {
            var current: *Node = head;

Replacement in src/lazy.zig at line 93 [7.108]

B:BD[7.3692] → [2.5425:5516]

                allocator.free(current.nexts);
                allocator.destroy(current);

[7.3692]

[7.3793]

                self.allocator.free(current.nexts);
                self.allocator.destroy(current);

Replacement in src/lazy.zig at line 98 [7.108]

B:BD[7.3840] → [2.5517:5600]

            allocator.free(current.nexts);
            allocator.destroy(current);

[7.3840]

[7.3933]

            self.allocator.free(current.nexts);
            self.allocator.destroy(current);

Replacement in src/lazy.zig at line 104 [7.108]

∅:D[2.5736] → [7.3944:4030]

B:BD[7.3944] → [7.3944:4030]

        fn findNode(self: @This(), key: K, preds: []?*Node, succs: []?*Node) ?usize {

[2.5736]

[7.4030]

        fn findNode(key: K, preds: []?*Node, succs: []?*Node) ?usize {

Replacement in src/lazy.zig at line 107 [7.108]

B:BD[7.4075] → [7.4075:4116]

            var pred: *Node = self.head;

[7.4075]

[7.4116]

            var pred: *Node = head;

Insertion in src/lazy.zig at line 133 [7.108]
[7.4949]
[2.6172]
```
            _ = self;
```
Deletion in src/lazy.zig at line 135 [7.108]
B:BD[2.6230] → [2.6230:6265]
∅:D[2.6265] → [7.5119:5120]
B:BD[7.5119] → [7.5119:5120]
```
            @memset(&preds, null);
```
Deletion in src/lazy.zig at line 136 [7.108]
B:BD[2.6324] → [2.6324:6359]
```
            @memset(&succs, null);
```

Replacement in src/lazy.zig at line 137 [7.108]

B:BD[7.5291] → [2.6360:6454]

            const found_level = self.findNode(search_key, &preds, &succs) orelse return null;

[7.5291]

[7.5383]

            const found_level = findNode(search_key, &preds, &succs) orelse return null;

Replacement in src/lazy.zig at line 143 [7.108]

B:BD[7.5530] → [7.5530:5577]

        fn randomLevel(self: *@This()) usize {

[7.5530]

[7.5577]

        fn randomLevel() usize {

Replacement in src/lazy.zig at line 145 [7.108]

B:BD[7.5611] → [7.5611:5657]

            const random = self.rnd.random();

[7.5611]

[2.6455]

            const random = rnd.random();

Replacement in src/lazy.zig at line 151 [7.108]

B:BD[7.5810] → [2.6567:6675]

∅:D[2.6675] → [7.5888:5935]

B:BD[7.5888] → [7.5888:5935]

        pub fn insert(self: *@This(), allocator: std.mem.Allocator, insert_key: K, insert_value: V) !bool {
            const rlevel = self.randomLevel();

[7.5810]

[7.5935]

        pub fn insert(self: *@This(), insert_key: K, insert_value: V) !bool {
            const rlevel = randomLevel();

Deletion in src/lazy.zig at line 155 [7.108]
B:BD[2.6734] → [2.6734:6772]
∅:D[2.6772] → [7.6106:6107]
B:BD[7.6106] → [7.6106:6107]
```
            // @memset(&preds, null);
```
Deletion in src/lazy.zig at line 156 [7.108]
B:BD[2.6831] → [2.6831:6869]
```
            // @memset(&succs, null);
```

Replacement in src/lazy.zig at line 158 [7.108]

B:BD[7.6305] → [2.6870:6940]

                if (self.findNode(insert_key, &preds, &succs)) |fl| {

[7.6305]

[2.6940]

                if (findNode(insert_key, &preds, &succs)) |fl| {

Replacement in src/lazy.zig at line 171 [7.108]

B:BD[7.6939] → [2.7059:7342]

                // FIXME: hardcoded!
                const bits = comptime blk: {
                    break :blk @as(usize, @intFromFloat(std.math.log(f32, 4, @as(f32, @floatFromInt(100_000)))));
                };
                var locks = std.StaticBitSet(bits + 1).initEmpty();

[7.6939]

[7.7273]

                var locks = std.StaticBitSet(max_level + 1).initEmpty();

Replacement in src/lazy.zig at line 217 [7.108]

B:BD[7.8593] → [2.9344:9421]

                    var node = try Node.init(allocator, insert_key, rlevel);

[7.8593]

[2.9421]

                    var node = try Node.init(self.allocator, insert_key, rlevel);

Replacement in src/lazy.zig at line 238 [7.108]

B:BD[7.9142] → [2.10116:10206]

        pub fn remove(self: @This(), allocator: std.mem.Allocator, remove_key: K) !bool {

[7.9142]

[7.9198]

        pub fn remove(self: @This(), remove_key: K) !bool {

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

B:BD[7.9382] → [2.10256:10399]

            var preds = try allocator.alloc(?*Node, max_level + 1);
            @memset(preds, null);
            defer allocator.free(preds);

[7.9382]

[7.9552]

            var preds: [max_level + 1]?*Node = undefined;
            var succs: [max_level + 1]?*Node = undefined;

Deletion in src/lazy.zig at line 247 [7.108]

B:BD[7.9553] → [2.10400:10545]

∅:D[2.10545] → [7.9723:9724]

B:BD[7.9723] → [7.9723:9724]

            const succs = try allocator.alloc(?*Node, max_level + 1);
            @memset(succs, null);
            defer allocator.free(succs);

Replacement in src/lazy.zig at line 248 [7.108]

B:BD[7.9751] → [7.9751:9828]

                const level_found = self.findNode(remove_key, preds, succs);

[7.9751]

[7.9828]

                const level_found = findNode(remove_key, &preds, &succs);

Replacement in src/lazy.zig at line 266 [7.108]

B:BD[7.10528] → [2.10638:10750]

                    var helds = try std.ArrayList(std.Thread.Mutex).initCapacity(allocator, node_height.? + 1);

[7.10528]

[7.10648]

                    var helds = try std.ArrayList(std.Thread.Mutex).initCapacity(self.allocator, node_height.? + 1);

Replacement in src/lazy.zig at line 298 [7.108]

B:BD[2.11005] → [2.11005:11058]

                    node_delete.?.deinit(allocator);

[2.11005]

[7.11912]

                    node_delete.?.deinit(self.allocator);

Replacement in src/lazy.zig at line 316 [7.108]

B:BD[2.11220] → [2.11220:11311]

    defer sl.deinit(std.testing.allocator);
    errdefer sl.deinit(std.testing.allocator);

[2.11220]

[7.12486]

    defer sl.deinit();
    errdefer sl.deinit();

Replacement in src/lazy.zig at line 319 [7.108]

B:BD[7.12487] → [2.11312:12737]

    try std.testing.expect((try sl.insert(std.testing.allocator, 3, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 6, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 7, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 9, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 12, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 12, {})) == false);
    try std.testing.expect((try sl.insert(std.testing.allocator, 12, {})) == false);
    try std.testing.expect((try sl.insert(std.testing.allocator, 19, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 8, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 17, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 26, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 21, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 25, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 42, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 88, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 22, {})) == true);
    try std.testing.expect((try sl.insert(std.testing.allocator, 66, {})) == true);

[7.12487]

[7.13521]

    try std.testing.expect((try sl.insert(3, {})) == true);
    try std.testing.expect((try sl.insert(6, {})) == true);
    try std.testing.expect((try sl.insert(7, {})) == true);
    try std.testing.expect((try sl.insert(9, {})) == true);
    try std.testing.expect((try sl.insert(12, {})) == true);
    try std.testing.expect((try sl.insert(12, {})) == false);
    try std.testing.expect((try sl.insert(12, {})) == false);
    try std.testing.expect((try sl.insert(19, {})) == true);
    try std.testing.expect((try sl.insert(8, {})) == true);
    try std.testing.expect((try sl.insert(17, {})) == true);
    try std.testing.expect((try sl.insert(26, {})) == true);
    try std.testing.expect((try sl.insert(21, {})) == true);
    try std.testing.expect((try sl.insert(25, {})) == true);
    try std.testing.expect((try sl.insert(42, {})) == true);
    try std.testing.expect((try sl.insert(88, {})) == true);
    try std.testing.expect((try sl.insert(22, {})) == true);
    try std.testing.expect((try sl.insert(66, {})) == true);

Replacement in src/lazy.zig at line 337 [7.108]

B:BD[7.13522] → [2.12738:12844]

    try std.testing.expect((try sl.insert(std.testing.allocator, std.math.minInt(KeyType), {})) == true);

[7.13522]

[7.13605]

    try std.testing.expect((try sl.insert(std.math.minInt(KeyType), {})) == true);

Replacement in src/lazy.zig at line 345 [7.108]

B:BD[7.13809] → [2.12845:13189]

    try std.testing.expect((try sl.remove(std.testing.allocator, 13)) == false);
    try std.testing.expect((try sl.remove(std.testing.allocator, 12)) == true);
    try std.testing.expect((try sl.remove(std.testing.allocator, 12)) == false);
    try std.testing.expect((try sl.remove(std.testing.allocator, std.math.minInt(KeyType))) == true);

[7.13809]

[7.14061]

    try std.testing.expect((try sl.remove(13)) == false);
    try std.testing.expect((try sl.remove(12)) == true);
    try std.testing.expect((try sl.remove(12)) == false);
    try std.testing.expect((try sl.remove(std.math.minInt(KeyType))) == true);