VDX2MMS55XMEHH2TEMOOW225K6NGKB4QXPQFQ2WJLVXJK25BSXMQC FFUOEUJREZ6KR4BZFLM7ORBKTNLJC5WVTACO26NTKNQ37MDTKN5AC 7G5Y53RBBKF4QDPTVC2MFG45XHDOLEFPHA4XQIPJNW4RXCULMRQQC XJHUBLK673LN2VVQ5FIOENXMS5OFSFWXM5GSP2X7XEVOL74WV6OAC CNCKEJFP74UCJQ4YJPP6QEHWH2DNWRWDZB2XNXRPTDZBPCXMJDXAC P7OMU7PBSC76C6FLDU3TT6ZRSKMNRTYAA4IM65ICVIHSMNUQWRBAC GJA75BA6ZNFQL6DG7YSRQKJWGX52YJKL3DZO3OWO6D4HVH6JS7NQC UAUV6SYV72FWMQVALN5YFTANLHIG6B5JHTZLJJUN5SN7SALYAC3AC 2HKNCI4IG65FEWNSRBJ5SESMN4STJ6WSCNODP3UK6LBQMDHYPNTAC LD2TP6CDUHET2ISQB3P4JOTQTIDDPRLSZJTIYWAO7JTHKUWOF7MQC // var frames: [BENCH_ITEMS]@Frame(testInsert) = undefined;var frames = try std.ArrayList(@Frame(testInsert)).initCapacity(arena.allocator(), BENCH_ITEMS);defer frames.deinit();
// 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, {});// }
var timer = try std.time.Timer.start();
// std.debug.print("Lazy 1 thread: {d} ms\n", .{timer.read() / std.time.ns_per_ms});// }{ // multithreadconst THREADS = 4;var pool: std.Thread.Pool = undefined;try pool.init(std.Thread.Pool.Options{.allocator = arena.allocator(),.n_jobs = THREADS,});defer pool.deinit();var wg = std.Thread.WaitGroup{};var timer = try std.time.Timer.start();
var job: usize = 0;while (job < BENCH_ITEMS) : (job += 1) {const key = rnd.intRangeAtMostBiased(BENCH_KEY,std.math.minInt(BENCH_KEY),std.math.maxInt(BENCH_KEY),);// frames[job] = async testInsert(&sl, key, {});// batch.add(&frames[job]);const frame = async testInsert(&sl, key, {});frames.appendAssumeCapacity(frame);batch.add(&frames.items[job]);}
for (0..BENCH_ITEMS) |_| {const key = rnd.intRangeAtMostBiased(BENCH_KEY,std.math.minInt(BENCH_KEY),std.math.maxInt(BENCH_KEY),);pool.spawnWg(&wg, testIns, .{ std.heap.page_allocator, &sl, key, {} });}
fn testInsert(skiplist: *SL, key: BENCH_KEY, val: BENCH_VALUE) anyerror!void {if (@call(.{}, skiplist.insert, .{ key, val })) {// std.debug.print("Adding {d} done.\n", .{key});return;} else |err| return err;
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;
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 });
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 });
std.debug.assert((try sq.remove()).?.value == 4);std.debug.assert((try sq.remove()).?.value == 1);std.debug.assert((try sq.remove()).?.value == 2);std.debug.assert((try sq.remove()).?.value == 3);std.debug.assert((try sq.remove()) == null);
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);
pub const Options = struct {/// Maximum number of items to be stored in the SkipList./// This is not a hard limit, but SkipList performance will degrade when badly choosen.items: usize,/// Number of items to skip with each level. This is a probabilistic value.skip_size: f32 = 4,/// Maximum number of levels in the SkipList.max_level: ?usize = null,};
std.debug.print("SkipList structure - P:{d}, max_level: {d}\n", .{ 1 / self.skip_size, self.max_level });var level: usize = self.max_level + 1;
std.debug.print("SkipList(Lazy) structure - P:{d}, max_level: {d}\n", .{ 1 / opts.skip_size, max_level });var level: usize = max_level + 1;
// XXX: compiler bug!if (found_level == null) {if (curr != null) {if (key == curr.?.key) {found_level = level - 1;}}
if (found_level == null and curr != null and key == curr.?.key) {found_level = level - 1;// NOTE: We could return at this point, but see Section 3.4// for optimizations based on this lazy method.
const found_level = self.findNode(insert_key, preds, succs);// We have found the key we are trying to insert...if (found_level != null) {const node = succs[found_level.?].?;
if (self.findNode(insert_key, &preds, &succs)) |fl| {// We have found the key we are trying to insert...const node = succs[fl].?;
// Lock handling partvar helds = try std.ArrayList(std.event.Lock.Held).initCapacity(self.allocator, rlevel + 1);defer {for (helds.items) |held| {held.release();}helds.deinit();}
// 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();
if (pred != prev_pred) {helds.appendAssumeCapacity(pred.?.lock.acquire());// highest_locked = level;prev_pred = pred;
if (pred != prev_pred) { // only count multilayer items once// std.debug.print("\t{d} {any}\n", .{ level, pred.?.key });pred.?.lock.lock();locks.set(level);prev_pred = pred;}std.debug.assert(pred != null);// Validation checks that for each layer:// 1) level ≤ rlevel// 2) preds[level] and succs[level] are still adjacent at `level`, and// 3) neither is marked.// If validation fails, the thread encountered a conflicting operation, so it releases// the locks it acquired and restarts place finding.valid = !pred.?.marked and (succ == null or !succ.?.marked) andpred.?.nexts[level] == succ;// If !valid cleanup and go to PLACEif (!valid) {// cleanup the locksvar lit = locks.iterator(.{});while (lit.next()) |lvl| {preds[lvl].?.lock.unlock();}break :PLACE;}
std.debug.assert(pred != null);// Validation checks that for each layer:// 1) level ≤ rlevel// 2) preds[level] and succs[level] are still adjacent at `level`, and// 3) neither is marked.// If validation fails, the thread encountered a conflicting operation, so it releases// the locks it acquired (defer) and retries.valid = !pred.?.marked and (succ == null or !succ.?.marked) andpred.?.nexts[level] == succ;}if (!valid) continue;
// At this point everything is set for adding the new Node.
var node = try Node.init(self.allocator, insert_key, rlevel);node.value = insert_value;
for (0..rlevel + 1) |level| {node.nexts[level] = succs[level]; // unlocked, but safe, as not linked yetpreds[level].?.nexts[level] = node;}node.fully_linked = true;
level = 0;while (level <= rlevel) : (level += 1) {node.nexts[level] = succs[level]; // unlocked, but safe, as not linked yetpreds[level].?.nexts[level] = node;}node.fully_linked = true;
// cleanup the locksvar lit = locks.iterator(.{});while (lit.next()) |lvl| {// std.debug.print("\tfinal unlocks {d} {any}\n", .{ lvl, preds[lvl].?.key });preds[lvl].?.lock.unlock();}
var preds = try self.allocator.alloc(?*Node, self.max_level + 1);std.mem.set(?*Node, preds, null);defer self.allocator.free(preds);
var preds = try allocator.alloc(?*Node, max_level + 1);@memset(preds, null);defer allocator.free(preds);
var succs = try self.allocator.alloc(?*Node, self.max_level + 1);std.mem.set(?*Node, succs, null);defer self.allocator.free(succs);
const succs = try allocator.alloc(?*Node, max_level + 1);@memset(succs, null);defer allocator.free(succs);
const SL = Lazy(KeyType, void, {}, comptime std.sort.asc(KeyType));var sl = try SL.init(std.testing.allocator, 4, 16);defer sl.deinit();
const SL = Lazy(Options{ .items = 16, .skip_size = 4 }, KeyType, void, {}, comptime std.sort.asc(KeyType));var sl = try SL.init(std.testing.allocator);defer sl.deinit(std.testing.allocator);errdefer sl.deinit(std.testing.allocator);
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(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(8, {})) == 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);
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);
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);
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);
pub fn build(b: *std.build.Builder) void {// Standard target options allows the person running `zig build` to choose// what target to build for. Here we do not override the defaults, which// means any target is allowed, and the default is native. Other options// for restricting supported target set are available.
pub fn build(b: *std.Build) void {
// Standard release options allow the person running `zig build` to select// between Debug, ReleaseSafe, ReleaseFast, and ReleaseSmall.const mode = b.standardReleaseOptions();
const exe = b.addExecutable(.{.name = "skiplist.zig",.root_source_file = b.path("src/main.zig"),.target = target,.optimize = optimize,});
const exe = b.addExecutable("skiplist.zig", "src/main.zig");exe.setTarget(target);exe.setBuildMode(mode);exe.use_stage1 = true;exe.install();
// This declares intent for the executable to be installed into the// standard location when the user invokes the "install" step (the default// step when running `zig build`).b.installArtifact(exe);
const run_cmd = exe.run();
// This *creates* a Run step in the build graph, to be executed when another// step is evaluated that depends on it. The next line below will establish// such a dependency.const run_cmd = b.addRunArtifact(exe);// By making the run step depend on the install step, it will be run from the// installation directory rather than directly from within the cache directory.// This is not necessary, however, if the application depends on other installed// files, this ensures they will be present and in the expected location.
const exe_tests = b.addTest("src/main.zig");exe_tests.setTarget(target);exe_tests.setBuildMode(mode);exe_tests.use_stage1 = true;exe_tests.test_evented_io = true;
// Creates a step for unit testing. This only builds the test executable// but does not run it.const exe_unit_tests = b.addTest(.{.root_source_file = b.path("src/lib.zig"),.target = target,.optimize = optimize,});const run_exe_unit_tests = b.addRunArtifact(exe_unit_tests);