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});
// }
{ // multithread
const 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 part
var 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) and
pred.?.nexts[level] == succ;
// If !valid cleanup and go to PLACE
if (!valid) {
// cleanup the locks
var 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) and
pred.?.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 yet
preds[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 yet
preds[level].?.nexts[level] = node;
}
node.fully_linked = true;
// cleanup the locks
var 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);