lib/simd/src/cuckoo/optimizer.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const matching = @import("builder.zig");
3 const simd = @import("../root.zig");
4
5 const random = simd.random;
6
7 pub fn Plan(comptime Family: type) type {
8 return struct {
9 config: Family.Config,
10 scratch_len: usize,
11 slots_len: usize,
12
13 const Self = @This();
14
15 pub fn inspect(num_keys: usize, epsilon: f64) matching.CuckooBuildError!Self {
16 const config = Family.Config.init(num_keys, epsilon) catch |err| return err;
17 if (config.num_keys >= std.math.maxInt(i32)) return error.CapacityExceeded;
18 _ = try breadthFirstStepLimit(config);
19 _ = try depthFirstStepLimit(Family, config);
20 return .{
21 .config = config,
22 .scratch_len = try scratchLength(Family, config),
23 .slots_len = config.num_slots,
24 };
25 }
26
27 pub fn build(
28 self: Self,
29 scratch: []u32,
30 slots: []Family.Key,
31 keys: []const Family.Key,
32 max_attempts: u32,
33 stats: ?*matching.CuckooBuildStats,
34 ) matching.CuckooBuildError!Family.Table {
35 matching.resetStats(stats);
36 if (!matching.supportedEpsilon(self.config.epsilon)) {
37 return error.UnsupportedEpsilon;
38 }
39 try self.validateBuffers(scratch, slots, keys);
40 try matching.validateKeys(Family, slots, keys);
41 var optimizer = try Optimizer(Family).init(self.config, scratch);
42 const engine = random.AesCtrEngine.initDeterministic();
43 for (0..@as(usize, max_attempts)) |attempt_index| {
44 const attempt: u32 = @intCast(attempt_index);
45 const primary = Family.Hash.initSeed(&engine, @as(u64, attempt) * 2);
46 const secondary = Family.Hash.initSeed(&engine, @as(u64, attempt) * 2 + 1);
47 if (!try optimizer.build(keys, primary, secondary, stats)) continue;
48 const table = try optimizer.take(keys, slots);
49 if (stats) |build_stats| {
50 build_stats.success = true;
51 build_stats.num_primary = table.num_primary;
52 build_stats.global_seed = attempt;
53 build_stats.attempts = attempt + 1;
54 }
55 return table;
56 }
57 if (stats) |build_stats| build_stats.attempts = max_attempts;
58 return error.BuildFailed;
59 }
60
61 pub fn buildWithHashes(
62 self: Self,
63 scratch: []u32,
64 slots: []Family.Key,
65 keys: []const Family.Key,
66 hash_primary: Family.Hash,
67 hash_secondary: Family.Hash,
68 stats: ?*matching.CuckooBuildStats,
69 ) matching.CuckooBuildError!Family.Table {
70 matching.resetStats(stats);
71 try self.validateBuffers(scratch, slots, keys);
72 try matching.validateKeys(Family, slots, keys);
73 var optimizer = try Optimizer(Family).init(self.config, scratch);
74 if (!try optimizer.build(keys, hash_primary, hash_secondary, stats)) {
75 if (stats) |build_stats| build_stats.attempts = 1;
76 return error.BuildFailed;
77 }
78 const table = try optimizer.take(keys, slots);
79 if (stats) |build_stats| {
80 build_stats.success = true;
81 build_stats.num_primary = table.num_primary;
82 build_stats.attempts = 1;
83 }
84 return table;
85 }
86
87 fn validateBuffers(
88 self: Self,
89 scratch: []u32,
90 slots: []Family.Key,
91 keys: []const Family.Key,
92 ) matching.CuckooBuildError!void {
93 if (keys.len != self.config.num_keys) return error.PlanMismatch;
94 if (scratch.len < self.scratch_len) return error.ScratchTooSmall;
95 if (slots.len < self.slots_len) return error.SlotsTooSmall;
96 if (matching.storageOverlaps(u32, scratch, Family.Key, slots) or
97 matching.storageOverlaps(u32, scratch, Family.Key, keys))
98 {
99 return error.InputOutputOverlap;
100 }
101 }
102 };
103 }
104
105 pub fn Optimizer(comptime Family: type) type {
106 return struct {
107 base: matching.Builder(Family),
108 cost_l: []u32,
109 layer_r: []u32,
110 cost_r: []u32,
111 visited_r: []u8,
112 prim_offset: []u32,
113 sec_offset: []u32,
114 frontier_l: []u32,
115 frontier_r: []u32,
116 targets_r: []u32,
117 path_counts: []u32,
118 breadth_first_step_limit: usize,
119 depth_first_step_limit: usize,
120 path_counts_len: usize = 0,
121
122 const Self = @This();
123 const unmatched: u32 = std.math.maxInt(u32);
124 const pending = @as(u32, 1) << 31;
125 const cost_mask = pending - 1;
126 const inf_cost: u32 = 1_000_000;
127
128 pub fn init(
129 config: Family.Config,
130 scratch: []u32,
131 ) matching.CuckooBuildError!Self {
132 if (config.num_keys >= std.math.maxInt(i32)) return error.CapacityExceeded;
133 const required = try scratchLength(Family, config);
134 if (scratch.len < required) return error.ScratchTooSmall;
135 const base_len = try matching.scratchLength(Family, config);
136 var offset = base_len;
137 const cost_l = matching.takeWords(scratch, &offset, config.num_keys);
138 const layer_r = matching.takeWords(scratch, &offset, config.num_slots);
139 const cost_r = matching.takeWords(scratch, &offset, config.num_slots);
140 const visited_words = matching.takeWords(
141 scratch,
142 &offset,
143 visitedWordLength(config.num_slots),
144 );
145 const visited_r = std.mem.sliceAsBytes(visited_words)[0..config.num_slots];
146 const prim_offset = matching.takeWords(
147 scratch,
148 &offset,
149 config.num_buckets + 1,
150 );
151 const sec_offset = matching.takeWords(
152 scratch,
153 &offset,
154 config.num_buckets + 1,
155 );
156 const frontier_l = matching.takeWords(scratch, &offset, config.num_keys);
157 const frontier_r = matching.takeWords(scratch, &offset, config.num_slots);
158 const targets_r = matching.takeWords(scratch, &offset, config.num_slots);
159 const path_counts = matching.takeWords(scratch, &offset, config.num_keys + 1);
160 std.debug.assert(offset == required);
161 std.debug.assert(config.num_slots > config.num_keys);
162 return .{
163 .base = try matching.Builder(Family).init(config, scratch[0..base_len]),
164 .cost_l = cost_l,
165 .layer_r = layer_r,
166 .cost_r = cost_r,
167 .visited_r = visited_r,
168 .prim_offset = prim_offset,
169 .sec_offset = sec_offset,
170 .frontier_l = frontier_l,
171 .frontier_r = frontier_r,
172 .targets_r = targets_r,
173 .path_counts = path_counts,
174 .breadth_first_step_limit = try breadthFirstStepLimit(config),
175 .depth_first_step_limit = try depthFirstStepLimit(Family, config),
176 };
177 }
178
179 pub fn build(
180 self: *Self,
181 keys: []const Family.Key,
182 hash_primary: Family.Hash,
183 hash_secondary: Family.Hash,
184 stats: ?*matching.CuckooBuildStats,
185 ) matching.CuckooBuildError!bool {
186 @memset(self.path_counts, 0);
187 self.path_counts_len = 0;
188 if (stats) |build_stats| build_stats.paths_per_path_cost = &.{};
189 var matching_size = try self.base.prepare(
190 keys,
191 hash_primary,
192 hash_secondary,
193 stats,
194 );
195 if (matching_size == self.base.config.num_keys) {
196 self.base.matched = true;
197 return true;
198 }
199 self.buildGraph();
200 for (0..self.base.config.num_keys) |cost_index| {
201 const path_cost: u32 = @intCast(cost_index + 1);
202 var found_for_cost = true;
203 for (0..self.base.config.num_keys + 1) |_| {
204 if (!found_for_cost or matching_size == self.base.config.num_keys) break;
205 const target_count = self.breadthFirst(path_cost);
206 if (target_count == 0) break;
207 @memset(self.visited_r, 0);
208 var paths_found: u32 = 0;
209 for (self.targets_r[0..target_count]) |target| {
210 if (self.visited_r[target] != 0) continue;
211 if (!self.depthFirst(target)) continue;
212 matching_size += 1;
213 paths_found += 1;
214 }
215 found_for_cost = paths_found != 0;
216 self.recordPathCost(path_cost, paths_found, stats);
217 }
218 if (matching_size == self.base.config.num_keys) break;
219 }
220 self.base.matched = matching_size == self.base.config.num_keys;
221 self.publishPathCosts(stats);
222 return self.base.matched;
223 }
224
225 pub fn take(
226 self: Self,
227 keys: []const Family.Key,
228 slots: []Family.Key,
229 ) matching.CuckooBuildError!Family.Table {
230 return self.base.take(keys, slots);
231 }
232
233 fn buildGraph(self: *Self) void {
234 @memset(self.prim_offset, 0);
235 @memset(self.sec_offset, 0);
236 for (self.base.primary_bucket, self.base.secondary_bucket) |primary, secondary| {
237 self.prim_offset[@as(usize, primary) + 1] += 1;
238 if (primary != secondary) {
239 self.sec_offset[@as(usize, secondary) + 1] += 1;
240 }
241 }
242 for (0..self.base.config.num_buckets) |bucket| {
243 self.prim_offset[bucket + 1] += self.prim_offset[bucket];
244 self.sec_offset[bucket + 1] += self.sec_offset[bucket];
245 }
246 @memset(self.base.bucket_fill, 0);
247 for (self.base.primary_bucket, 0..) |bucket, key_index| {
248 const bucket_index: usize = bucket;
249 const target = self.prim_offset[bucket_index] +
250 self.base.bucket_fill[bucket_index];
251 self.base.queue[target] = @intCast(key_index);
252 self.base.bucket_fill[bucket_index] += 1;
253 }
254 @memset(self.base.bucket_fill, 0);
255 for (
256 self.base.primary_bucket,
257 self.base.secondary_bucket,
258 0..,
259 ) |primary, secondary, key_index| {
260 if (primary == secondary) continue;
261 const bucket_index: usize = secondary;
262 const target = self.sec_offset[bucket_index] +
263 self.base.bucket_fill[bucket_index];
264 self.base.cursor[target] = @intCast(key_index);
265 self.base.bucket_fill[bucket_index] += 1;
266 }
267 }
268
269 fn breadthFirst(self: *Self, path_cost: u32) usize {
270 @memset(self.base.dist, unmatched);
271 @memset(self.layer_r, unmatched);
272 @memset(self.cost_l, inf_cost);
273 @memset(self.cost_r, inf_cost);
274 @memset(self.visited_r, 0);
275 var left_count: usize = 0;
276 for (self.base.match_key_to_slot, 0..) |slot, key_index| {
277 if (slot != unmatched) continue;
278 self.base.dist[key_index] = 0;
279 self.cost_l[key_index] = pending;
280 self.frontier_l[left_count] = @intCast(key_index);
281 left_count += 1;
282 }
283 var right_count: usize = 0;
284 var target_count: usize = 0;
285 var target_layer = unmatched;
286 for (0..self.breadth_first_step_limit) |_| {
287 if (left_count == 0) {
288 std.debug.assert(right_count == 0);
289 return target_count;
290 }
291 const current_left_count = left_count;
292 left_count = 0;
293 for (self.frontier_l[0..current_left_count]) |key_index| {
294 self.cost_l[key_index] &= cost_mask;
295 const current_layer = self.base.dist[key_index];
296 const current_cost = self.cost_l[key_index];
297 if (target_layer != unmatched and current_layer >= target_layer) continue;
298 std.debug.assert(current_layer < unmatched);
299 std.debug.assert(current_cost < cost_mask);
300 const new_layer = current_layer + 1;
301 const primary = self.base.primary_bucket[key_index];
302 self.relaxBucket(
303 key_index,
304 primary,
305 new_layer,
306 current_cost,
307 path_cost,
308 &right_count,
309 &target_count,
310 &target_layer,
311 );
312 const secondary = self.base.secondary_bucket[key_index];
313 if (primary == secondary) continue;
314 self.relaxBucket(
315 key_index,
316 secondary,
317 new_layer,
318 current_cost + 1,
319 path_cost,
320 &right_count,
321 &target_count,
322 &target_layer,
323 );
324 }
325 if (right_count == 0) return target_count;
326 const current_right_count = right_count;
327 right_count = 0;
328 for (self.frontier_r[0..current_right_count]) |slot_index| {
329 self.cost_r[slot_index] &= cost_mask;
330 const current_layer = self.layer_r[slot_index];
331 const current_cost = self.cost_r[slot_index];
332 if (target_layer != unmatched and current_layer >= target_layer) continue;
333 const matched_left = self.base.match_slot_to_key[slot_index];
334 if (matched_left == unmatched) continue;
335 const bucket: u32 = @intCast(slot_index / Family.bucket_size);
336 const secondary_edge = bucket == self.base.secondary_bucket[matched_left] and
337 self.base.primary_bucket[matched_left] !=
338 self.base.secondary_bucket[matched_left];
339 if (secondary_edge and current_cost == 0) continue;
340 const new_cost = current_cost - @intFromBool(secondary_edge);
341 const old_cost = self.cost_l[matched_left] & cost_mask;
342 if (self.base.dist[matched_left] != unmatched and new_cost >= old_cost) {
343 continue;
344 }
345 std.debug.assert(current_layer < unmatched);
346 self.base.dist[matched_left] = current_layer + 1;
347 const already_pending = self.cost_l[matched_left] & pending != 0;
348 self.cost_l[matched_left] = new_cost | pending;
349 if (already_pending) continue;
350 std.debug.assert(left_count < self.frontier_l.len);
351 self.frontier_l[left_count] = matched_left;
352 left_count += 1;
353 }
354 }
355 std.debug.assert(false);
356 return target_count;
357 }
358
359 fn relaxBucket(
360 self: *Self,
361 key_index: u32,
362 bucket: u32,
363 new_layer: u32,
364 new_cost: u32,
365 path_cost: u32,
366 right_count: *usize,
367 target_count: *usize,
368 target_layer: *u32,
369 ) void {
370 const base_slot = @as(usize, bucket) * Family.bucket_size;
371 for (base_slot..base_slot + Family.bucket_size) |slot| {
372 if (self.base.match_key_to_slot[key_index] == slot) continue;
373 const old_cost = self.cost_r[slot] & cost_mask;
374 if (self.layer_r[slot] != unmatched and new_cost >= old_cost) continue;
375 self.layer_r[slot] = new_layer;
376 if (self.base.match_slot_to_key[slot] == unmatched) {
377 self.cost_r[slot] = new_cost;
378 if (new_cost != path_cost) continue;
379 if (target_layer.* == unmatched) target_layer.* = new_layer;
380 if (new_layer != target_layer.* or self.visited_r[slot] != 0) continue;
381 std.debug.assert(target_count.* < self.targets_r.len);
382 self.visited_r[slot] = 1;
383 self.targets_r[target_count.*] = @intCast(slot);
384 target_count.* += 1;
385 continue;
386 }
387 const already_pending = self.cost_r[slot] & pending != 0;
388 self.cost_r[slot] = new_cost | pending;
389 if (already_pending) continue;
390 std.debug.assert(right_count.* < self.frontier_r.len);
391 self.frontier_r[right_count.*] = @intCast(slot);
392 right_count.* += 1;
393 }
394 }
395
396 fn depthFirst(self: *Self, root: u32) bool {
397 std.debug.assert(self.base.match_slot_to_key[root] == unmatched);
398 self.visited_r[root] = 1;
399 var depth: usize = 1;
400 self.frontier_r[0] = root;
401 self.frontier_l[0] = 0;
402 for (0..self.depth_first_step_limit) |_| {
403 const frame = depth - 1;
404 const slot = self.frontier_r[frame];
405 const bucket = @as(usize, slot) / Family.bucket_size;
406 const primary_count = self.prim_offset[bucket + 1] -
407 self.prim_offset[bucket];
408 const secondary_count = self.sec_offset[bucket + 1] -
409 self.sec_offset[bucket];
410 const edge_index = self.frontier_l[frame];
411 if (edge_index == primary_count + secondary_count) {
412 if (depth == 1) return false;
413 const failed_slot = slot;
414 depth -= 1;
415 const parent_slot = self.frontier_r[depth - 1];
416 const moved_key = self.base.match_slot_to_key[parent_slot];
417 std.debug.assert(moved_key != unmatched);
418 std.debug.assert(self.base.match_key_to_slot[moved_key] == parent_slot);
419 std.debug.assert(self.base.match_slot_to_key[failed_slot] == unmatched);
420 self.base.match_key_to_slot[moved_key] = failed_slot;
421 self.base.match_slot_to_key[failed_slot] = moved_key;
422 self.base.match_slot_to_key[parent_slot] = unmatched;
423 continue;
424 }
425 self.frontier_l[frame] += 1;
426 const primary_edge = edge_index < primary_count;
427 const key_index = if (primary_edge)
428 self.base.queue[self.prim_offset[bucket] + edge_index]
429 else
430 self.base.cursor[
431 self.sec_offset[bucket] + edge_index - primary_count
432 ];
433 const right_layer = self.layer_r[slot];
434 if (right_layer == 0 or self.base.dist[key_index] != right_layer - 1) {
435 continue;
436 }
437 if (depth > 1) {
438 const parent_slot = self.frontier_r[frame - 1];
439 if (self.base.match_slot_to_key[parent_slot] == key_index) continue;
440 } else if (self.base.match_key_to_slot[key_index] == slot) {
441 continue;
442 }
443 const edge_cost: u32 = @intFromBool(!primary_edge);
444 if ((self.cost_l[key_index] & cost_mask) + edge_cost !=
445 (self.cost_r[slot] & cost_mask))
446 {
447 continue;
448 }
449 const old_slot = self.base.match_key_to_slot[key_index];
450 if (old_slot == unmatched) {
451 self.base.match_key_to_slot[key_index] = slot;
452 self.base.match_slot_to_key[slot] = key_index;
453 return true;
454 }
455 if (self.visited_r[old_slot] != 0 or self.layer_r[old_slot] == unmatched) {
456 continue;
457 }
458 std.debug.assert(self.base.match_slot_to_key[slot] == unmatched);
459 self.base.match_key_to_slot[key_index] = slot;
460 self.base.match_slot_to_key[slot] = key_index;
461 self.base.match_slot_to_key[old_slot] = unmatched;
462 self.visited_r[old_slot] = 1;
463 std.debug.assert(depth < self.frontier_l.len);
464 std.debug.assert(depth < self.frontier_r.len);
465 self.frontier_r[depth] = old_slot;
466 self.frontier_l[depth] = 0;
467 depth += 1;
468 }
469 std.debug.assert(false);
470 return false;
471 }
472
473 fn recordPathCost(
474 self: *Self,
475 path_cost: u32,
476 paths_found: u32,
477 stats: ?*matching.CuckooBuildStats,
478 ) void {
479 if (paths_found == 0) return;
480 const build_stats = stats orelse return;
481 if (!build_stats.collect_path_cost_stats) return;
482 self.path_counts[path_cost] += paths_found;
483 self.path_counts_len = @max(self.path_counts_len, @as(usize, path_cost) + 1);
484 build_stats.paths_per_path_cost = self.path_counts[0..self.path_counts_len];
485 }
486
487 fn publishPathCosts(self: Self, stats: ?*matching.CuckooBuildStats) void {
488 const build_stats = stats orelse return;
489 if (!build_stats.collect_path_cost_stats) return;
490 build_stats.paths_per_path_cost = self.path_counts[0..self.path_counts_len];
491 }
492 };
493 }
494
495 pub fn scratchLength(
496 comptime Family: type,
497 config: Family.Config,
498 ) matching.CuckooBuildError!usize {
499 var words = try matching.scratchLength(Family, config);
500 try addWords(&words, config.num_keys);
501 try addWords(&words, config.num_slots);
502 try addWords(&words, config.num_slots);
503 try addWords(&words, visitedWordLength(config.num_slots));
504 const offsets = std.math.add(usize, config.num_buckets, 1) catch
505 return error.CapacityExceeded;
506 try addWords(&words, offsets);
507 try addWords(&words, offsets);
508 try addWords(&words, config.num_keys);
509 try addWords(&words, config.num_slots);
510 try addWords(&words, config.num_slots);
511 const path_counts = std.math.add(usize, config.num_keys, 1) catch
512 return error.CapacityExceeded;
513 try addWords(&words, path_counts);
514 return words;
515 }
516
517 fn addWords(words: *usize, additional: usize) matching.CuckooBuildError!void {
518 words.* = std.math.add(usize, words.*, additional) catch
519 return error.CapacityExceeded;
520 }
521
522 fn visitedWordLength(num_slots: usize) usize {
523 return std.math.divCeil(usize, num_slots, @sizeOf(u32)) catch unreachable;
524 }
525
526 fn breadthFirstStepLimit(
527 config: anytype,
528 ) matching.CuckooBuildError!usize {
529 const nodes = std.math.add(usize, config.num_keys, config.num_slots) catch
530 return error.CapacityExceeded;
531 const cost_states = std.math.add(usize, config.num_keys, 2) catch
532 return error.CapacityExceeded;
533 const relaxations = std.math.mul(usize, nodes, cost_states) catch
534 return error.CapacityExceeded;
535 return std.math.add(usize, relaxations, 1) catch return error.CapacityExceeded;
536 }
537
538 fn depthFirstStepLimit(
539 comptime Family: type,
540 config: Family.Config,
541 ) matching.CuckooBuildError!usize {
542 const key_edges = std.math.mul(usize, config.num_keys, Family.bucket_size * 2) catch
543 return error.CapacityExceeded;
544 const with_pops = std.math.add(usize, key_edges, config.num_slots) catch
545 return error.CapacityExceeded;
546 return std.math.add(usize, with_pops, 1) catch return error.CapacityExceeded;
547 }
548
549 test "Highway optimized Cuckoo builder completes minimum-cost matching" {
550 const Family = simd.cuckoo.DefaultCuckoo;
551 const key_count = 1000;
552 var keys: [key_count]u32 = undefined;
553 const engine = random.AesCtrEngine.initDeterministic();
554 const permutation = simd.hash.Triple32.initSeed(&engine, 0);
555 for (&keys, 0..) |*key, key_index| {
556 key.* = permutation.hash(@intCast(key_index));
557 if (key.* == Family.empty_key) key.* = 0;
558 }
559 const plan = try Family.OptimizedBuildPlan.inspect(key_count, 0.01);
560 const allocator = std.testing.allocator;
561 const scratch = try allocator.alloc(u32, plan.scratch_len);
562 defer allocator.free(scratch);
563 const slots = try allocator.alloc(u32, plan.slots_len);
564 defer allocator.free(slots);
565 var stats: matching.CuckooBuildStats = .{ .collect_path_cost_stats = true };
566 const table = try simd.buildCuckoo(
567 scratch,
568 slots,
569 &keys,
570 0.01,
571 200,
572 .min_cost,
573 &stats,
574 );
575 try std.testing.expect(stats.success);
576 try std.testing.expectEqual(@as(usize, 14_571), plan.scratch_len);
577 try std.testing.expectEqual(@as(u32, 47), stats.num_unmatched_after_greedy);
578 try std.testing.expectEqual(@as(u32, 919), stats.num_primary);
579 try std.testing.expectEqualSlices(u32, &.{ 0, 47 }, stats.paths_per_path_cost);
580 var path_count: u32 = 0;
581 for (stats.paths_per_path_cost) |count| path_count += count;
582 try std.testing.expectEqual(stats.num_unmatched_after_greedy, path_count);
583 var digest: u64 = 1_469_598_103_934_665_603;
584 for (table.slots()) |slot| digest = (digest ^ slot) *% 1_099_511_628_211;
585 try std.testing.expectEqual(@as(u64, 0x5a3d_3a92_beff_3b1d), digest);
586 for (keys) |key| try std.testing.expect(table.queryOne(key));
587 }
588
589 test "Highway optimized Cuckoo builder preserves deeper path costs" {
590 const Family = simd.cuckoo.DefaultCuckoo;
591 const key_count = 1900;
592 var keys: [key_count]u32 = undefined;
593 const engine = random.AesCtrEngine.initDeterministic();
594 const permutation = simd.hash.Triple32.initSeed(&engine, 15);
595 for (&keys, 0..) |*key, key_index| {
596 key.* = permutation.hash(@intCast(key_index));
597 if (key.* == Family.empty_key) key.* = 0;
598 }
599 const plan = try Family.OptimizedBuildPlan.inspect(key_count, 0.01);
600 const allocator = std.testing.allocator;
601 const scratch = try allocator.alloc(u32, plan.scratch_len);
602 defer allocator.free(scratch);
603 const slots = try allocator.alloc(u32, plan.slots_len);
604 defer allocator.free(slots);
605 var stats: matching.CuckooBuildStats = .{ .collect_path_cost_stats = true };
606 const table = try plan.build(scratch, slots, &keys, 200, &stats);
607 try std.testing.expectEqual(@as(usize, 28_239), plan.scratch_len);
608 try std.testing.expectEqual(@as(u32, 1717), stats.num_primary);
609 try std.testing.expectEqual(@as(u32, 80), stats.num_unmatched_after_greedy);
610 try std.testing.expectEqualSlices(u32, &.{ 0, 78, 2 }, stats.paths_per_path_cost);
611 try std.testing.expectEqualSlices(u32, &.{
612 0xf158_aace, 0xbc75_05e6, 0xcb1e_1ca7, 0x5cda_bb9b,
613 0x9608_81c9, 0xcf5b_c588, 0x65ac_9cb1, 0xd5aa_8b48,
614 0x4793_b06c, 0x762e_7313, 0xe6b8_8454, 0x2198_49ca,
615 0x1961_3f4e, 0x4360_cd6d, 0x9c72_2ed3, 0xffff_ffff,
616 }, table.slots()[0..16]);
617 var digest: u64 = 1_469_598_103_934_665_603;
618 for (table.slots()) |slot| digest = (digest ^ slot) *% 1_099_511_628_211;
619 try std.testing.expectEqual(@as(u64, 0x518e_3842_c1a7_94b8), digest);
620 }
621
622 fn expectOptimizedFamily(comptime Family: type) !void {
623 const key_count = 64;
624 var keys: [key_count]Family.Key = undefined;
625 for (&keys, 0..) |*key, key_index| {
626 key.* = @as(Family.Key, @intCast(key_index)) *% 37 +% 1;
627 }
628 const plan = try Family.OptimizedBuildPlan.inspect(key_count, 0.01);
629 const allocator = std.testing.allocator;
630 const scratch = try allocator.alloc(u32, plan.scratch_len);
631 defer allocator.free(scratch);
632 const slots = try allocator.alloc(Family.Key, plan.slots_len);
633 defer allocator.free(slots);
634 var stats: matching.CuckooBuildStats = .{ .collect_path_cost_stats = true };
635 const table = try plan.build(scratch, slots, &keys, 200, &stats);
636 try std.testing.expect(stats.success);
637 try std.testing.expectEqual(key_count, table.config.num_keys);
638 for (keys) |key| try std.testing.expect(table.queryOne(key));
639 }
640
641 test "Highway optimized Cuckoo builder supports all bucket sizes and u64 keys" {
642 inline for ([_]usize{ 1, 2, 4, 8, 16, 32 }) |bucket_size| {
643 const Family = simd.cuckoo.CuckooFamily(simd.hash.WeakTwoMul, bucket_size, 1);
644 try expectOptimizedFamily(Family);
645 }
646 const Wide = simd.cuckoo.CuckooFamily(simd.hash.Moremur, 16, 1);
647 try expectOptimizedFamily(Wide);
648 }
649
650 test "Highway optimized Cuckoo plan enforces caller storage contracts" {
651 const Family = simd.cuckoo.DefaultCuckoo;
652 const keys = [_]u32{ 1, 2, 3, 4, 5, 6, 7, 8 };
653 const plan = try Family.OptimizedBuildPlan.inspect(keys.len, 0.25);
654 const allocator = std.testing.allocator;
655 const scratch = try allocator.alloc(u32, plan.scratch_len);
656 defer allocator.free(scratch);
657 const slots = try allocator.alloc(u32, plan.slots_len);
658 defer allocator.free(slots);
659 try std.testing.expectError(
660 error.ScratchTooSmall,
661 plan.build(scratch[0 .. scratch.len - 1], slots, &keys, 1, null),
662 );
663 try std.testing.expectError(
664 error.SlotsTooSmall,
665 plan.build(scratch, slots[0 .. slots.len - 1], &keys, 1, null),
666 );
667 try std.testing.expectError(
668 error.InputOutputOverlap,
669 plan.build(scratch, scratch[0..plan.slots_len], &keys, 1, null),
670 );
671 var stats: matching.CuckooBuildStats = .{ .collect_path_cost_stats = true };
672 try std.testing.expectError(error.BuildFailed, plan.build(
673 scratch,
674 slots,
675 &keys,
676 0,
677 &stats,
678 ));
679 try std.testing.expect(stats.collect_path_cost_stats);
680 try std.testing.expectEqual(@as(usize, 0), stats.paths_per_path_cost.len);
681 const unsupported = try Family.OptimizedBuildPlan.inspect(keys.len, 0.20);
682 try std.testing.expectError(
683 error.UnsupportedEpsilon,
684 unsupported.build(scratch, slots, &keys, 1, null),
685 );
686 }
687
688 test "Highway optimized Cuckoo builder handles an empty table" {
689 const Family = simd.cuckoo.DefaultCuckoo;
690 const plan = try Family.OptimizedBuildPlan.inspect(0, 0.25);
691 const allocator = std.testing.allocator;
692 const scratch = try allocator.alloc(u32, plan.scratch_len);
693 defer allocator.free(scratch);
694 const slots = try allocator.alloc(u32, plan.slots_len);
695 defer allocator.free(slots);
696 var stats: matching.CuckooBuildStats = .{};
697 const table = try plan.build(scratch, slots, &.{}, 1, &stats);
698 try std.testing.expect(table.isEmpty());
699 try std.testing.expect(stats.success);
700 try std.testing.expectEqual(@as(u32, 1), stats.attempts);
701 try std.testing.expectEqual(@as(usize, 0), stats.paths_per_path_cost.len);
702 }
703
704 test "Highway optimized Cuckoo builder rejects the pending-cost boundary" {
705 const Family = simd.cuckoo.CuckooFamily(simd.hash.WeakTwoMul, 1, 1);
706 const config = try Family.Config.init(std.math.maxInt(i32), 0);
707 try std.testing.expectError(error.CapacityExceeded, Family.Optimizer.init(config, &.{}));
708 }