lib/simd/src/cuckoo/builder.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const simd = @import("../root.zig");
3
4 const random = simd.random;
5
6 pub const CuckooBuildError = error{
7 BuildFailed,
8 CapacityExceeded,
9 DuplicateKey,
10 EmptyKey,
11 InputOutputOverlap,
12 InvalidEpsilon,
13 PlanMismatch,
14 ScratchTooSmall,
15 SlotsTooSmall,
16 UnsupportedEpsilon,
17 };
18
19 pub const CuckooBuildStats = struct {
20 success: bool = false,
21 num_primary: u32 = 0,
22 global_seed: u32 = 0,
23 attempts: u32 = 0,
24 num_unmatched_after_greedy: u32 = 0,
25 collect_path_cost_stats: bool = false,
26 paths_per_path_cost: []const u32 = &.{},
27 };
28
29 pub fn Plan(comptime Family: type) type {
30 return struct {
31 config: Family.Config,
32 scratch_len: usize,
33 slots_len: usize,
34
35 const Self = @This();
36
37 pub fn inspect(num_keys: usize, epsilon: f64) CuckooBuildError!Self {
38 const config = Family.Config.init(num_keys, epsilon) catch |err| return err;
39 _ = try dfsStepLimit(Family, config);
40 return .{
41 .config = config,
42 .scratch_len = try scratchLength(Family, config),
43 .slots_len = config.num_slots,
44 };
45 }
46
47 pub fn build(
48 self: Self,
49 scratch: []u32,
50 slots: []Family.Key,
51 keys: []const Family.Key,
52 max_attempts: u32,
53 stats: ?*CuckooBuildStats,
54 ) CuckooBuildError!Family.Table {
55 resetStats(stats);
56 if (!supportedEpsilon(self.config.epsilon)) return error.UnsupportedEpsilon;
57 try self.validateBuffers(scratch, slots, keys);
58 try validateKeys(Family, slots, keys);
59 var cuckoo_builder = try Builder(Family).init(self.config, scratch);
60 const engine = random.AesCtrEngine.initDeterministic();
61 for (0..@as(usize, max_attempts)) |attempt_index| {
62 const attempt: u32 = @intCast(attempt_index);
63 const primary = Family.Hash.initSeed(&engine, @as(u64, attempt) * 2);
64 const secondary = Family.Hash.initSeed(&engine, @as(u64, attempt) * 2 + 1);
65 if (!try cuckoo_builder.build(keys, primary, secondary, stats)) continue;
66 const table = try cuckoo_builder.take(keys, slots);
67 if (stats) |build_stats| {
68 build_stats.success = true;
69 build_stats.num_primary = table.num_primary;
70 build_stats.global_seed = attempt;
71 build_stats.attempts = attempt + 1;
72 }
73 return table;
74 }
75 if (stats) |build_stats| build_stats.attempts = max_attempts;
76 return error.BuildFailed;
77 }
78
79 pub fn buildWithHashes(
80 self: Self,
81 scratch: []u32,
82 slots: []Family.Key,
83 keys: []const Family.Key,
84 hash_primary: Family.Hash,
85 hash_secondary: Family.Hash,
86 stats: ?*CuckooBuildStats,
87 ) CuckooBuildError!Family.Table {
88 resetStats(stats);
89 try self.validateBuffers(scratch, slots, keys);
90 try validateKeys(Family, slots, keys);
91 var cuckoo_builder = try Builder(Family).init(self.config, scratch);
92 if (!try cuckoo_builder.build(keys, hash_primary, hash_secondary, stats)) {
93 if (stats) |build_stats| build_stats.attempts = 1;
94 return error.BuildFailed;
95 }
96 const table = try cuckoo_builder.take(keys, slots);
97 if (stats) |build_stats| {
98 build_stats.success = true;
99 build_stats.num_primary = table.num_primary;
100 build_stats.attempts = 1;
101 }
102 return table;
103 }
104
105 fn validateBuffers(
106 self: Self,
107 scratch: []u32,
108 slots: []Family.Key,
109 keys: []const Family.Key,
110 ) CuckooBuildError!void {
111 if (keys.len != self.config.num_keys) return error.PlanMismatch;
112 if (scratch.len < self.scratch_len) return error.ScratchTooSmall;
113 if (slots.len < self.slots_len) return error.SlotsTooSmall;
114 if (storageOverlaps(u32, scratch, Family.Key, slots) or
115 storageOverlaps(u32, scratch, Family.Key, keys))
116 {
117 return error.InputOutputOverlap;
118 }
119 }
120 };
121 }
122
123 pub fn Placement(comptime Family: type) type {
124 return struct {
125 config: Family.Config,
126 hash_primary: Family.Hash = undefined,
127 hash_secondary: Family.Hash = undefined,
128 primary_bucket: []u32,
129 secondary_bucket: []u32,
130 match_key_to_slot: []u32,
131 match_slot_to_key: []u32,
132 bucket_fill: []u32,
133 matched: bool = false,
134
135 const Self = @This();
136
137 pub fn init(config: Family.Config, scratch: []u32) CuckooBuildError!Self {
138 const required = try placementScratchLength(config);
139 if (scratch.len < required) return error.ScratchTooSmall;
140 var offset: usize = 0;
141 const primary_bucket = takeWords(scratch, &offset, config.num_keys);
142 const secondary_bucket = takeWords(scratch, &offset, config.num_keys);
143 const match_key_to_slot = takeWords(scratch, &offset, config.num_keys);
144 const match_slot_to_key = takeWords(scratch, &offset, config.num_slots);
145 const bucket_fill = takeWords(scratch, &offset, config.num_buckets);
146 std.debug.assert(offset == required);
147 return .{
148 .config = config,
149 .primary_bucket = primary_bucket,
150 .secondary_bucket = secondary_bucket,
151 .match_key_to_slot = match_key_to_slot,
152 .match_slot_to_key = match_slot_to_key,
153 .bucket_fill = bucket_fill,
154 };
155 }
156
157 pub fn prepare(
158 self: *Self,
159 keys: []const Family.Key,
160 hash_primary: Family.Hash,
161 hash_secondary: Family.Hash,
162 stats: ?*CuckooBuildStats,
163 ) CuckooBuildError!usize {
164 return preparePlacement(
165 Family,
166 self,
167 keys,
168 hash_primary,
169 hash_secondary,
170 stats,
171 );
172 }
173
174 pub fn take(
175 self: Self,
176 keys: []const Family.Key,
177 slots: []Family.Key,
178 ) CuckooBuildError!Family.Table {
179 return takePlacement(Family, self, keys, slots);
180 }
181 };
182 }
183
184 pub fn Builder(comptime Family: type) type {
185 return struct {
186 config: Family.Config,
187 hash_primary: Family.Hash = undefined,
188 hash_secondary: Family.Hash = undefined,
189 primary_bucket: []u32,
190 secondary_bucket: []u32,
191 match_key_to_slot: []u32,
192 match_slot_to_key: []u32,
193 dist: []u32,
194 bucket_fill: []u32,
195 queue: []u32,
196 cursor: []u32,
197 dfs_step_limit: usize,
198 matched: bool = false,
199
200 const Self = @This();
201 const unmatched = std.math.maxInt(u32);
202 const edge_count = Family.bucket_size * 2;
203
204 pub fn init(config: Family.Config, scratch: []u32) CuckooBuildError!Self {
205 const required = try scratchLength(Family, config);
206 if (scratch.len < required) return error.ScratchTooSmall;
207 const key_count = config.num_keys;
208 var offset: usize = 0;
209 const primary_bucket = takeWords(scratch, &offset, key_count);
210 const secondary_bucket = takeWords(scratch, &offset, key_count);
211 const match_key_to_slot = takeWords(scratch, &offset, key_count);
212 const match_slot_to_key = takeWords(scratch, &offset, config.num_slots);
213 const dist = takeWords(scratch, &offset, key_count);
214 const bucket_fill = takeWords(scratch, &offset, config.num_buckets);
215 const queue = takeWords(scratch, &offset, key_count);
216 const cursor = takeWords(scratch, &offset, key_count);
217 std.debug.assert(offset == required);
218 return .{
219 .config = config,
220 .primary_bucket = primary_bucket,
221 .secondary_bucket = secondary_bucket,
222 .match_key_to_slot = match_key_to_slot,
223 .match_slot_to_key = match_slot_to_key,
224 .dist = dist,
225 .bucket_fill = bucket_fill,
226 .queue = queue,
227 .cursor = cursor,
228 .dfs_step_limit = try dfsStepLimit(Family, config),
229 };
230 }
231
232 pub fn build(
233 self: *Self,
234 keys: []const Family.Key,
235 hash_primary: Family.Hash,
236 hash_secondary: Family.Hash,
237 stats: ?*CuckooBuildStats,
238 ) CuckooBuildError!bool {
239 const initial_matching_size = try self.prepare(
240 keys,
241 hash_primary,
242 hash_secondary,
243 stats,
244 );
245 return self.completeMaximumMatching(initial_matching_size);
246 }
247
248 pub fn prepare(
249 self: *Self,
250 keys: []const Family.Key,
251 hash_primary: Family.Hash,
252 hash_secondary: Family.Hash,
253 stats: ?*CuckooBuildStats,
254 ) CuckooBuildError!usize {
255 return preparePlacement(
256 Family,
257 self,
258 keys,
259 hash_primary,
260 hash_secondary,
261 stats,
262 );
263 }
264
265 pub fn completeMaximumMatching(
266 self: *Self,
267 initial_matching_size: usize,
268 ) bool {
269 var matching_size = initial_matching_size;
270 if (matching_size == self.config.num_keys) {
271 self.matched = true;
272 return true;
273 }
274 for (0..self.config.num_keys) |_| {
275 if (!self.breadthFirst()) break;
276 const before = matching_size;
277 for (0..self.config.num_keys) |key_index| {
278 if (self.match_key_to_slot[key_index] != unmatched) continue;
279 matching_size += @intFromBool(self.depthFirst(@intCast(key_index)));
280 }
281 std.debug.assert(matching_size > before);
282 if (matching_size == self.config.num_keys) break;
283 }
284 self.matched = matching_size == self.config.num_keys;
285 return self.matched;
286 }
287
288 pub fn take(
289 self: Self,
290 keys: []const Family.Key,
291 slots: []Family.Key,
292 ) CuckooBuildError!Family.Table {
293 return takePlacement(Family, self, keys, slots);
294 }
295
296 fn breadthFirst(self: *Self) bool {
297 @memset(self.dist, unmatched);
298 var tail: usize = 0;
299 for (self.match_key_to_slot, 0..) |slot, key_index| {
300 if (slot != unmatched) continue;
301 self.dist[key_index] = 0;
302 self.queue[tail] = @intCast(key_index);
303 tail += 1;
304 }
305 var head: usize = 0;
306 var found = false;
307 for (0..self.config.num_keys) |_| {
308 if (head == tail) break;
309 const key_index = self.queue[head];
310 head += 1;
311 for (0..edge_count) |edge_index| {
312 const slot = self.candidateSlot(key_index, edge_index);
313 const other_key = self.match_slot_to_key[slot];
314 if (other_key == unmatched) {
315 found = true;
316 } else if (self.dist[other_key] == unmatched and !found) {
317 self.dist[other_key] = self.dist[key_index] + 1;
318 std.debug.assert(tail < self.queue.len);
319 self.queue[tail] = other_key;
320 tail += 1;
321 }
322 }
323 }
324 std.debug.assert(head == tail);
325 return found;
326 }
327
328 fn depthFirst(self: *Self, root: u32) bool {
329 var depth: usize = 1;
330 self.queue[0] = root;
331 self.cursor[0] = 0;
332 for (0..self.dfs_step_limit) |_| {
333 if (depth == 0) return false;
334 const frame = depth - 1;
335 const key_index = self.queue[frame];
336 const edge_index = self.cursor[frame];
337 if (edge_index == edge_count) {
338 self.dist[key_index] = unmatched;
339 depth -= 1;
340 continue;
341 }
342 self.cursor[frame] += 1;
343 const slot = self.candidateSlot(key_index, edge_index);
344 const other_key = self.match_slot_to_key[slot];
345 if (other_key == unmatched) {
346 self.augment(depth, slot);
347 return true;
348 }
349 if (self.dist[other_key] != self.dist[key_index] +% 1) {
350 continue;
351 }
352 std.debug.assert(depth < self.queue.len);
353 self.queue[depth] = other_key;
354 self.cursor[depth] = 0;
355 depth += 1;
356 }
357 std.debug.assert(false);
358 return false;
359 }
360
361 fn augment(self: *Self, depth: usize, free_slot: u32) void {
362 var assigned_slot = free_slot;
363 for (0..depth) |reverse_index| {
364 const frame = depth - reverse_index - 1;
365 const key_index = self.queue[frame];
366 const old_slot = self.match_key_to_slot[key_index];
367 self.match_key_to_slot[key_index] = assigned_slot;
368 self.match_slot_to_key[assigned_slot] = key_index;
369 assigned_slot = old_slot;
370 }
371 std.debug.assert(assigned_slot == unmatched);
372 }
373
374 fn candidateSlot(self: Self, key_index: u32, edge_index: usize) u32 {
375 const secondary = edge_index >= Family.bucket_size;
376 const bucket = if (secondary)
377 self.secondary_bucket[key_index]
378 else
379 self.primary_bucket[key_index];
380 const within_bucket = edge_index & (Family.bucket_size - 1);
381 return @intCast(@as(usize, bucket) * Family.bucket_size + within_bucket);
382 }
383 };
384 }
385
386 fn preparePlacement(
387 comptime Family: type,
388 placement: anytype,
389 keys: []const Family.Key,
390 hash_primary: Family.Hash,
391 hash_secondary: Family.Hash,
392 stats: ?*CuckooBuildStats,
393 ) CuckooBuildError!usize {
394 if (keys.len != placement.config.num_keys) return error.PlanMismatch;
395 placement.hash_primary = hash_primary;
396 placement.hash_secondary = hash_secondary;
397 placement.matched = false;
398 for (keys, 0..) |key, key_index| {
399 if (key == Family.empty_key) return error.EmptyKey;
400 placement.primary_bucket[key_index] = @intCast(
401 placement.hash_primary.hash(key) & placement.config.bucket_mask,
402 );
403 placement.secondary_bucket[key_index] = @intCast(
404 placement.hash_secondary.hash(key) & placement.config.bucket_mask,
405 );
406 }
407 const matching_size = greedyPlacement(Family, placement);
408 if (stats) |build_stats| {
409 build_stats.num_unmatched_after_greedy = @intCast(keys.len - matching_size);
410 }
411 return matching_size;
412 }
413
414 fn greedyPlacement(comptime Family: type, placement: anytype) usize {
415 const unmatched = std.math.maxInt(u32);
416 @memset(placement.match_key_to_slot, unmatched);
417 @memset(placement.match_slot_to_key, unmatched);
418 @memset(placement.bucket_fill, 0);
419 var matching_size: usize = 0;
420 for (placement.primary_bucket, 0..) |bucket, key_index| {
421 matching_size += @intFromBool(greedyPlace(Family, placement, key_index, bucket));
422 }
423 for (placement.secondary_bucket, 0..) |bucket, key_index| {
424 if (placement.match_key_to_slot[key_index] != unmatched) continue;
425 matching_size += @intFromBool(greedyPlace(Family, placement, key_index, bucket));
426 }
427 return matching_size;
428 }
429
430 fn greedyPlace(
431 comptime Family: type,
432 placement: anytype,
433 key_index: usize,
434 bucket: u32,
435 ) bool {
436 const bucket_index: usize = bucket;
437 if (placement.bucket_fill[bucket_index] >= Family.bucket_size) return false;
438 const slot = bucket_index * Family.bucket_size + placement.bucket_fill[bucket_index];
439 placement.match_key_to_slot[key_index] = @intCast(slot);
440 placement.match_slot_to_key[slot] = @intCast(key_index);
441 placement.bucket_fill[bucket_index] += 1;
442 return true;
443 }
444
445 fn takePlacement(
446 comptime Family: type,
447 placement: anytype,
448 keys: []const Family.Key,
449 slots: []Family.Key,
450 ) CuckooBuildError!Family.Table {
451 const unmatched = std.math.maxInt(u32);
452 if (!placement.matched) return error.BuildFailed;
453 if (keys.len != placement.config.num_keys) return error.PlanMismatch;
454 if (slots.len < placement.config.num_slots) return error.SlotsTooSmall;
455 const output = slots[0..placement.config.num_slots];
456 if (slicesOverlap(Family.Key, output, keys)) return error.InputOutputOverlap;
457 @memset(output, Family.empty_key);
458 var num_primary: u32 = 0;
459 for (keys, placement.match_key_to_slot, 0..) |key, slot_index, key_index| {
460 std.debug.assert(slot_index != unmatched);
461 std.debug.assert(output[slot_index] == Family.empty_key);
462 output[slot_index] = key;
463 const bucket: u32 = @intCast(slot_index / Family.bucket_size);
464 num_primary += @intFromBool(bucket == placement.primary_bucket[key_index]);
465 }
466 return Family.Table.init(
467 placement.config,
468 placement.hash_primary,
469 placement.hash_secondary,
470 output,
471 num_primary,
472 ) catch unreachable;
473 }
474
475 pub fn placementScratchLength(config: anytype) CuckooBuildError!usize {
476 const key_words = std.math.mul(usize, config.num_keys, 3) catch
477 return error.CapacityExceeded;
478 const keys_and_slots = std.math.add(usize, key_words, config.num_slots) catch
479 return error.CapacityExceeded;
480 return std.math.add(usize, keys_and_slots, config.num_buckets) catch
481 return error.CapacityExceeded;
482 }
483
484 pub fn scratchLength(comptime Family: type, config: Family.Config) CuckooBuildError!usize {
485 const key_words = std.math.mul(usize, config.num_keys, 6) catch
486 return error.CapacityExceeded;
487 const keys_and_slots = std.math.add(usize, key_words, config.num_slots) catch
488 return error.CapacityExceeded;
489 return std.math.add(usize, keys_and_slots, config.num_buckets) catch
490 return error.CapacityExceeded;
491 }
492
493 pub fn dfsStepLimit(comptime Family: type, config: Family.Config) CuckooBuildError!usize {
494 const steps_per_key = std.math.add(usize, Family.bucket_size * 2, 1) catch
495 return error.CapacityExceeded;
496 const all_steps = std.math.mul(usize, config.num_keys, steps_per_key) catch
497 return error.CapacityExceeded;
498 return std.math.add(usize, all_steps, 1) catch return error.CapacityExceeded;
499 }
500
501 pub fn takeWords(storage: []u32, offset: *usize, len: usize) []u32 {
502 const begin = offset.*;
503 const end = begin + len;
504 offset.* = end;
505 return storage[begin..end];
506 }
507
508 pub fn resetStats(stats: ?*CuckooBuildStats) void {
509 if (stats) |build_stats| {
510 const collect_path_cost_stats = build_stats.collect_path_cost_stats;
511 build_stats.* = .{ .collect_path_cost_stats = collect_path_cost_stats };
512 }
513 }
514
515 pub fn supportedEpsilon(epsilon: f64) bool {
516 for ([_]f64{ 0.01, 0.05, 0.10, 0.25, 0.50, 0.75 }) |supported| {
517 if (epsilon == supported) return true;
518 }
519 return false;
520 }
521
522 pub fn validateKeys(
523 comptime Family: type,
524 slots: []Family.Key,
525 keys: []const Family.Key,
526 ) CuckooBuildError!void {
527 if (slicesOverlap(Family.Key, slots, keys)) return error.InputOutputOverlap;
528 const sorted = slots[0..keys.len];
529 for (keys, sorted) |key, *copy| {
530 if (key == Family.empty_key) return error.EmptyKey;
531 copy.* = key;
532 }
533 std.mem.sort(Family.Key, sorted, {}, std.sort.asc(Family.Key));
534 if (sorted.len < 2) return;
535 for (sorted[1..], sorted[0 .. sorted.len - 1]) |current, previous| {
536 if (current == previous) return error.DuplicateKey;
537 }
538 }
539
540 pub fn slicesOverlap(comptime T: type, mutable: []T, immutable: []const T) bool {
541 if (mutable.len == 0 or immutable.len == 0) return false;
542 const mutable_begin = @intFromPtr(mutable.ptr);
543 const immutable_begin = @intFromPtr(immutable.ptr);
544 const mutable_bytes = std.math.mul(usize, mutable.len, @sizeOf(T)) catch return true;
545 const immutable_bytes = std.math.mul(usize, immutable.len, @sizeOf(T)) catch return true;
546 const mutable_end = std.math.add(usize, mutable_begin, mutable_bytes) catch return true;
547 const immutable_end = std.math.add(usize, immutable_begin, immutable_bytes) catch return true;
548 return mutable_begin < immutable_end and immutable_begin < mutable_end;
549 }
550
551 pub fn storageOverlaps(
552 comptime Left: type,
553 left: []const Left,
554 comptime Right: type,
555 right: []const Right,
556 ) bool {
557 if (left.len == 0 or right.len == 0) return false;
558 const left_begin = @intFromPtr(left.ptr);
559 const right_begin = @intFromPtr(right.ptr);
560 const left_bytes = std.math.mul(usize, left.len, @sizeOf(Left)) catch return true;
561 const right_bytes = std.math.mul(usize, right.len, @sizeOf(Right)) catch return true;
562 const left_end = std.math.add(usize, left_begin, left_bytes) catch return true;
563 const right_end = std.math.add(usize, right_begin, right_bytes) catch return true;
564 return left_begin < right_end and right_begin < left_end;
565 }
566
567 test "Highway generic Cuckoo builder completes maximum matching" {
568 const Family = simd.cuckoo.DefaultCuckoo;
569 const key_count = 1000;
570 var keys: [key_count]u32 = undefined;
571 const engine = random.AesCtrEngine.initDeterministic();
572 const permutation = simd.hash.Triple32.initSeed(&engine, 0);
573 for (&keys, 0..) |*key, key_index| {
574 key.* = permutation.hash(@intCast(key_index));
575 if (key.* == Family.empty_key) key.* = 0;
576 }
577 const plan = try Family.BuildPlan.inspect(key_count, 0.01);
578 const allocator = std.testing.allocator;
579 const scratch = try allocator.alloc(u32, plan.scratch_len);
580 defer allocator.free(scratch);
581 const slots = try allocator.alloc(u32, plan.slots_len);
582 defer allocator.free(slots);
583 var stats: CuckooBuildStats = .{};
584 const table = try plan.build(scratch, slots, &keys, 200, &stats);
585 try std.testing.expect(stats.success);
586 try std.testing.expectEqual(@as(usize, 7088), plan.scratch_len);
587 try std.testing.expectEqual(@as(usize, 1024), plan.slots_len);
588 try std.testing.expectEqual(@as(u32, 916), stats.num_primary);
589 try std.testing.expectEqual(@as(u32, 0), stats.global_seed);
590 try std.testing.expectEqual(@as(u32, 1), stats.attempts);
591 try std.testing.expectEqual(@as(u32, 47), stats.num_unmatched_after_greedy);
592 try std.testing.expectEqual(key_count, table.config.num_keys);
593 try std.testing.expectEqualSlices(u32, &.{
594 0x1f66_f859, 0x0a9c_8235, 0x0814_b9d8, 0x13ae_2206,
595 0xf399_d47d, 0xc57b_e2db, 0xfbcd_0050, 0x34c2_2bf3,
596 0xefa8_2035, 0x2efc_254c, 0x8bb2_4319, 0xfe07_ee01,
597 0x7fb0_0d51, 0xe858_34af, 0x31f9_ecbf, 0x9376_9934,
598 }, table.slots()[0..16]);
599 var digest: u64 = 1_469_598_103_934_665_603;
600 for (table.slots()) |slot| digest = (digest ^ slot) *% 1_099_511_628_211;
601 try std.testing.expectEqual(@as(u64, 0x911d_fe6f_4dc9_fc9b), digest);
602 for (keys) |key| try std.testing.expect(table.queryOne(key));
603 }
604
605 test "Highway generic Cuckoo build plan enforces caller storage and key contracts" {
606 const Family = simd.cuckoo.DefaultCuckoo;
607 const keys = [_]u32{ 1, 2, 3, 4, 5, 6, 7, 8 };
608 const plan = try Family.BuildPlan.inspect(keys.len, 0.25);
609 const allocator = std.testing.allocator;
610 const scratch = try allocator.alloc(u32, plan.scratch_len);
611 defer allocator.free(scratch);
612 const slots = try allocator.alloc(u32, plan.slots_len);
613 defer allocator.free(slots);
614 try std.testing.expectError(
615 error.ScratchTooSmall,
616 plan.build(scratch[0 .. scratch.len - 1], slots, &keys, 1, null),
617 );
618 try std.testing.expectError(
619 error.SlotsTooSmall,
620 plan.build(scratch, slots[0 .. slots.len - 1], &keys, 1, null),
621 );
622 try std.testing.expectError(
623 error.PlanMismatch,
624 plan.build(scratch, slots, keys[0..7], 1, null),
625 );
626 const duplicate = [_]u32{ 1, 2, 3, 3, 5, 6, 7, 8 };
627 try std.testing.expectError(error.DuplicateKey, plan.build(
628 scratch,
629 slots,
630 &duplicate,
631 1,
632 null,
633 ));
634 const with_empty = [_]u32{ 1, 2, 3, 4, 5, 6, 7, Family.empty_key };
635 try std.testing.expectError(error.EmptyKey, plan.build(
636 scratch,
637 slots,
638 &with_empty,
639 1,
640 null,
641 ));
642 }
643
644 test "Highway generic Cuckoo build plan rejects overlap unsupported epsilon and no attempts" {
645 const Family = simd.cuckoo.DefaultCuckoo;
646 const keys = [_]u32{ 1, 2, 3, 4, 5, 6, 7, 8 };
647 const plan = try Family.BuildPlan.inspect(keys.len, 0.25);
648 var scratch: [65]u32 = undefined;
649 var aliased: [16]u32 = undefined;
650 @memcpy(aliased[0..keys.len], &keys);
651 try std.testing.expectError(error.InputOutputOverlap, plan.build(
652 &scratch,
653 &aliased,
654 aliased[0..keys.len],
655 1,
656 null,
657 ));
658 try std.testing.expectError(error.InputOutputOverlap, plan.build(
659 &scratch,
660 scratch[0..plan.slots_len],
661 &keys,
662 1,
663 null,
664 ));
665 const unsupported = try Family.BuildPlan.inspect(keys.len, 0.20);
666 try std.testing.expectError(
667 error.UnsupportedEpsilon,
668 unsupported.build(&.{}, &.{}, &keys, 1, null),
669 );
670 var slots: [16]u32 = undefined;
671 var stats: CuckooBuildStats = .{};
672 try std.testing.expectError(
673 error.BuildFailed,
674 plan.build(&scratch, &slots, &keys, 0, &stats),
675 );
676 try std.testing.expect(!stats.success);
677 try std.testing.expectEqual(@as(u32, 0), stats.attempts);
678 }
679
680 test "Highway generic Cuckoo builder represents the empty set" {
681 const Family = simd.cuckoo.DefaultCuckoo;
682 const plan = try Family.BuildPlan.inspect(0, 0.25);
683 var scratch: [17]u32 = undefined;
684 var slots: [16]u32 = undefined;
685 var stats: CuckooBuildStats = .{};
686 const table = try plan.build(&scratch, &slots, &.{}, 1, &stats);
687 try std.testing.expect(table.isEmpty());
688 try std.testing.expect(stats.success);
689 try std.testing.expectEqual(@as(u32, 1), stats.attempts);
690 try std.testing.expectEqual(@as(u32, 0), stats.num_primary);
691 for (table.slots()) |slot| try std.testing.expectEqual(Family.empty_key, slot);
692 }
693
694 const family_test_key_count: usize = 1000;
695 const family_test_scratch_count: usize = 10_096;
696 const family_test_slot_count: usize = 2048;
697
698 var family_test_keys32: [family_test_key_count]u32 = undefined;
699 var family_test_keys64: [family_test_key_count]u64 = undefined;
700 var family_test_scratch: [family_test_scratch_count]u32 = undefined;
701 var family_test_slots32: [family_test_slot_count]u32 = undefined;
702 var family_test_slots64: [family_test_slot_count]u64 = undefined;
703
704 fn expectFamilyBuild(
705 comptime Family: type,
706 keys: []Family.Key,
707 scratch: []u32,
708 slots: []Family.Key,
709 epsilon: f64,
710 ) !void {
711 for (keys, 0..) |*key, key_index| {
712 key.* = @as(Family.Key, @intCast(key_index)) *% 37 +% 1;
713 }
714 const plan = try Family.BuildPlan.inspect(keys.len, epsilon);
715 try std.testing.expect(plan.scratch_len <= scratch.len);
716 try std.testing.expect(plan.slots_len <= slots.len);
717 var stats: CuckooBuildStats = .{};
718 const table = try plan.build(scratch, slots, keys, 200, &stats);
719 try std.testing.expect(stats.success);
720 try std.testing.expectEqual(keys.len, table.config.num_keys);
721 for (keys) |key| try std.testing.expect(table.queryOne(key));
722 }
723
724 test "Highway generic Cuckoo builder supports upstream bucket sizes and u64 keys" {
725 inline for ([_]usize{ 1, 2, 4, 8, 16, 32 }) |bucket_size| {
726 const Family = simd.cuckoo.CuckooFamily(simd.hash.WeakTwoMul, bucket_size, 1);
727 try expectFamilyBuild(
728 Family,
729 &family_test_keys32,
730 &family_test_scratch,
731 &family_test_slots32,
732 0.75,
733 );
734 }
735 const Wide = simd.cuckoo.CuckooFamily(simd.hash.Moremur, 16, 1);
736 try expectFamilyBuild(
737 Wide,
738 &family_test_keys64,
739 &family_test_scratch,
740 &family_test_slots64,
741 0.05,
742 );
743 }
744
745 const default_test_max_keys: usize = 10_000;
746 const default_test_scratch_count: usize = 77_408;
747 const default_test_slot_count: usize = 16_384;
748
749 var default_test_keys: [default_test_max_keys]u32 = undefined;
750 var default_test_scratch: [default_test_scratch_count]u32 = undefined;
751 var default_test_slots: [default_test_slot_count]u32 = undefined;
752
753 fn expectDefaultBuild(key_count: usize, epsilon: f64) !void {
754 const keys = default_test_keys[0..key_count];
755 const engine = random.AesCtrEngine.initDeterministic();
756 const permutation = simd.hash.Triple32.initSeed(&engine, 0);
757 for (keys, 0..) |*key, key_index| {
758 key.* = permutation.hash(@intCast(key_index));
759 if (key.* == simd.DefaultCuckoo.empty_key) key.* = 0;
760 }
761 const scratch_len = try simd.cuckooScratchLen(key_count, epsilon, .hopcroft_karp);
762 const slots_len = try simd.cuckooSlotsLen(key_count, epsilon);
763 try std.testing.expect(scratch_len <= default_test_scratch.len);
764 try std.testing.expect(slots_len <= default_test_slots.len);
765 var stats: CuckooBuildStats = .{};
766 const table = try simd.buildCuckoo(
767 default_test_scratch[0..scratch_len],
768 default_test_slots[0..slots_len],
769 keys,
770 epsilon,
771 200,
772 .hopcroft_karp,
773 &stats,
774 );
775 try std.testing.expect(stats.success);
776 try std.testing.expect(stats.attempts >= 1);
777 try std.testing.expect(stats.attempts <= 200);
778 try std.testing.expectEqual(scratch_len, table.config.num_keys * 6 +
779 table.config.num_slots + table.config.num_buckets);
780 for (keys) |key| try std.testing.expect(table.queryOne(key));
781 }
782
783 test "Highway generic Cuckoo top-level builder covers upstream sizes and epsilons" {
784 try expectDefaultBuild(100, 0.25);
785 try expectDefaultBuild(10_000, 0.25);
786 for ([_]f64{ 0.01, 0.05, 0.10, 0.25, 0.50, 0.75 }) |epsilon| {
787 try expectDefaultBuild(1000, epsilon);
788 }
789 }