lib/simd/src/phast/builder.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const simd = @import("../root.zig");
3 const family = @import("family.zig");
4 const compact = simd.compact;
5 const construct = simd.construct;
6 const hash_mod = simd.hash;
7 const indexed = simd.indexed;
8 const random = simd.random;
9 const shift = simd.shift;
10 const tag = simd.tag;
11
12 pub const max_attempts: usize = 512;
13 pub const max_hashes_per_bucket: usize = 32;
14 pub const max_swaps: usize = 20;
15 pub const scan_window: usize = 50_000;
16 pub const seed_count: usize = 256;
17 pub const max_config_count: usize = 28;
18
19 const headroom_percents = [_]usize{ 1, 2, 3, 4, 10, 15, 20 };
20 const insertion_threshold: usize = 16;
21 const failed_seed: u32 = std.math.maxInt(u32);
22 const PositionTag = tag.FixedTag(u32, 8);
23 const SortFrame = struct {
24 first: usize,
25 last: usize,
26 depth: usize,
27 };
28
29 pub const Plan = struct {
30 num_keys: usize,
31 payload_bytes: usize,
32 configs: [max_config_count]family.Config,
33 config_count: usize,
34 max_num_slots: usize,
35 max_num_buckets: usize,
36 scratch_len: usize,
37 seeds_len: usize,
38
39 const Self = @This();
40
41 pub fn inspect(num_keys: usize, payload_bytes: usize) family.PhastError!Self {
42 if (num_keys == 0) {
43 return .{
44 .num_keys = 0,
45 .payload_bytes = payload_bytes,
46 .configs = @splat(.{}),
47 .config_count = 0,
48 .max_num_slots = 0,
49 .max_num_buckets = 0,
50 .scratch_len = 0,
51 .seeds_len = 0,
52 };
53 }
54 if (num_keys > std.math.maxInt(u32)) return error.CapacityExceeded;
55 var configs: [max_config_count]family.Config = @splat(.{});
56 const config_count = try enumerateConfigs(num_keys, configs[0..]);
57 var max_num_slots: usize = 0;
58 var max_num_buckets: usize = 0;
59 for (configs[0..config_count]) |config| {
60 _ = try config.allocatedBytes(payload_bytes);
61 max_num_slots = @max(max_num_slots, config.num_slots);
62 max_num_buckets = @max(max_num_buckets, config.numBuckets());
63 }
64 sortConfigs(configs[0..config_count], payload_bytes);
65 return .{
66 .num_keys = num_keys,
67 .payload_bytes = payload_bytes,
68 .configs = configs,
69 .config_count = config_count,
70 .max_num_slots = max_num_slots,
71 .max_num_buckets = max_num_buckets,
72 .scratch_len = try scratchLength(num_keys, max_num_slots, max_num_buckets),
73 .seeds_len = family.seedWordLength(max_num_buckets),
74 };
75 }
76
77 pub fn build(
78 self: Self,
79 scratch: []u32,
80 seed_words: []u32,
81 keys: []const u32,
82 ) family.PhastError!family.Data {
83 try self.validateBuffers(scratch, seed_words, keys);
84 if (self.num_keys == 0) return .{};
85 var builder = try Builder.init(self, scratch, seed_words);
86 try builder.validateDistinct(keys);
87 const engine = random.AesCtrEngine.initDeterministic();
88 for (self.configs[0..self.config_count], 0..) |config, config_index| {
89 for (0..max_attempts) |attempt_index| {
90 const stream = @as(u64, config.hash_key) + attempt_index;
91 const hash_key: u32 = @truncate(engine.generate(stream, 0));
92 if (!builder.maybeBuild(keys, config, hash_key)) continue;
93 return builder.take(config_index, attempt_index);
94 }
95 }
96 @memset(seed_words[0..self.seeds_len], 0);
97 return error.BuildFailed;
98 }
99
100 fn validateBuffers(
101 self: Self,
102 scratch: []u32,
103 seed_words: []u32,
104 keys: []const u32,
105 ) family.PhastError!void {
106 if (keys.len != self.num_keys) return error.PlanMismatch;
107 if (scratch.len < self.scratch_len) return error.ScratchTooSmall;
108 if (seed_words.len < self.seeds_len) return error.SeedsTooSmall;
109 if (storageOverlaps(u32, scratch, u32, seed_words) or
110 storageOverlaps(u32, scratch, u32, keys) or
111 storageOverlaps(u32, seed_words, u32, keys))
112 {
113 return error.InputOutputOverlap;
114 }
115 }
116 };
117
118 const Builder = struct {
119 plan: Plan,
120 hashes: []u32,
121 all_positions: []u32,
122 key_indices: []u32,
123 occupancy: []u32,
124 committed_seeds: []u8,
125 bucket_sizes: []u8,
126 bucket_offsets: []u32,
127 bucket_order: []u32,
128 write_positions: []u32,
129 seed_candidates: []u32,
130 seed_words: []u32,
131 config: family.Config = .{},
132 hash: hash_mod.Triple32 = .{},
133 bucket_size_histogram: [max_hashes_per_bucket + 1]u32 = @splat(0),
134 succeeded: bool = false,
135
136 const Self = @This();
137
138 fn init(plan: Plan, scratch: []u32, seed_words: []u32) family.PhastError!Self {
139 if (scratch.len < plan.scratch_len) return error.ScratchTooSmall;
140 if (seed_words.len < plan.seeds_len) return error.SeedsTooSmall;
141 var offset: usize = 0;
142 const hashes = takeWords(scratch, &offset, plan.num_keys);
143 const all_positions = takeWords(
144 scratch,
145 &offset,
146 max_hashes_per_bucket * seed_count,
147 );
148 const key_indices = takeWords(scratch, &offset, plan.num_keys);
149 const occupancy = takeWords(
150 scratch,
151 &offset,
152 occupancyWordLength(plan.max_num_slots),
153 );
154 const committed_words = takeWords(
155 scratch,
156 &offset,
157 byteWordLength(plan.max_num_buckets),
158 );
159 const bucket_size_words = takeWords(
160 scratch,
161 &offset,
162 byteWordLength(plan.max_num_buckets),
163 );
164 const bucket_offsets = takeWords(
165 scratch,
166 &offset,
167 plan.max_num_buckets + 1,
168 );
169 const bucket_order = takeWords(scratch, &offset, plan.max_num_buckets);
170 const write_positions = takeWords(scratch, &offset, plan.max_num_buckets);
171 const seed_candidates = takeWords(scratch, &offset, seed_count);
172 std.debug.assert(offset == plan.scratch_len);
173 return .{
174 .plan = plan,
175 .hashes = hashes,
176 .all_positions = all_positions,
177 .key_indices = key_indices,
178 .occupancy = occupancy,
179 .committed_seeds = std.mem.sliceAsBytes(committed_words)[0..plan.max_num_buckets],
180 .bucket_sizes = std.mem.sliceAsBytes(bucket_size_words)[0..plan.max_num_buckets],
181 .bucket_offsets = bucket_offsets,
182 .bucket_order = bucket_order,
183 .write_positions = write_positions,
184 .seed_candidates = seed_candidates,
185 .seed_words = seed_words[0..plan.seeds_len],
186 };
187 }
188
189 fn validateDistinct(self: *Self, keys: []const u32) family.PhastError!void {
190 const engine = random.AesCtrEngine.initDeterministic();
191 const permutation = hash_mod.Triple32.initSeed(&engine, 0);
192 for (keys, self.hashes) |key, *hash| hash.* = permutation.hash(key);
193 std.mem.sort(u32, self.hashes, {}, std.sort.asc(u32));
194 for (self.hashes[1..], self.hashes[0 .. self.hashes.len - 1]) |right, left| {
195 if (left == right) return error.DuplicateKey;
196 }
197 }
198
199 fn maybeBuild(
200 self: *Self,
201 keys: []const u32,
202 base_config: family.Config,
203 hash_key: u32,
204 ) bool {
205 std.debug.assert(keys.len == self.plan.num_keys);
206 self.config = base_config;
207 self.config.hash_key = hash_key;
208 self.hash = hash_mod.Triple32.initKey(hash_key);
209 self.succeeded = false;
210 const num_buckets = self.config.numBuckets();
211 const occupancy_words = occupancyWordLength(self.config.num_slots);
212 @memset(self.occupancy[0..occupancy_words], 0);
213 @memset(self.seed_words[0..self.config.seedWordsLen()], 0);
214 @memset(self.committed_seeds[0..num_buckets], 0);
215 @memset(self.bucket_sizes[0..num_buckets], 0);
216 for (keys, self.hashes) |key, *hash| hash.* = self.hash.hash(key);
217 if (!self.populateBuckets()) return false;
218 const nonempty_count = num_buckets - self.bucket_size_histogram[0];
219 for (0..nonempty_count) |rank| {
220 const seed = self.tryPlaceBucket(@intCast(rank), failed_seed);
221 if (seed != failed_seed) {
222 self.committed_seeds[rank] = @truncate(seed);
223 continue;
224 }
225 if (!self.tryCuckooSwap(@intCast(rank))) return false;
226 }
227 self.succeeded = true;
228 return true;
229 }
230
231 fn take(self: Self, config_index: usize, attempt_index: usize) family.Data {
232 std.debug.assert(self.succeeded);
233 std.debug.assert(self.config.hash_key == self.hash.key());
234 return .{
235 .config = self.config,
236 .seeds = .{ .words = self.seed_words[0..self.config.seedWordsLen()] },
237 .config_index = config_index,
238 .attempt_index = attempt_index,
239 };
240 }
241
242 fn populateBuckets(self: *Self) bool {
243 const num_buckets = self.config.numBuckets();
244 for (self.hashes) |hash| {
245 const bucket: usize = hash & self.config.bucket_mask;
246 if (self.bucket_sizes[bucket] + 1 >= max_hashes_per_bucket) return false;
247 self.bucket_sizes[bucket] += 1;
248 }
249 @memset(&self.bucket_size_histogram, 0);
250 var maximum_size: usize = 0;
251 for (self.bucket_sizes[0..num_buckets]) |size| {
252 maximum_size = @max(maximum_size, size);
253 self.bucket_size_histogram[size] += 1;
254 }
255 self.bucket_offsets[0] = 0;
256 for (self.bucket_sizes[0..num_buckets], 0..) |size, bucket| {
257 self.bucket_offsets[bucket + 1] = self.bucket_offsets[bucket] + size;
258 }
259 @memcpy(
260 self.write_positions[0..num_buckets],
261 self.bucket_offsets[0..num_buckets],
262 );
263 for (self.hashes, 0..) |hash, key_index| {
264 const bucket: usize = hash & self.config.bucket_mask;
265 self.key_indices[self.write_positions[bucket]] = @intCast(key_index);
266 self.write_positions[bucket] += 1;
267 }
268 var order_begin: [max_hashes_per_bucket + 1]u32 = @splat(0);
269 order_begin[maximum_size] = 0;
270 var size = maximum_size;
271 while (size > 0) {
272 order_begin[size - 1] = order_begin[size] + self.bucket_size_histogram[size];
273 size -= 1;
274 }
275 for (self.bucket_sizes[0..num_buckets], 0..) |bucket_size, bucket| {
276 const position = order_begin[bucket_size];
277 self.bucket_order[position] = @intCast(bucket);
278 order_begin[bucket_size] += 1;
279 }
280 return true;
281 }
282
283 fn tryCuckooSwap(self: *Self, rank: u32) bool {
284 const scan_start = if (rank > scan_window) rank - scan_window else 0;
285 const failed_bucket_size = self.computeBucketPositions(rank);
286 const positions_to_find = failed_bucket_size * seed_count;
287 var overlap_ranks: [max_swaps]u32 = undefined;
288 var original_seeds: [max_swaps]u8 = undefined;
289 var overlap_count: usize = 0;
290 var scan_position = rank;
291 while (scan_position > scan_start and overlap_count < max_swaps) {
292 const scan_rank = scan_position - 1;
293 const bucket = self.bucket_order[scan_rank];
294 const seed = self.committed_seeds[scan_rank];
295 const begin = self.bucket_offsets[bucket];
296 const size = self.bucket_sizes[bucket];
297 var matches = false;
298 for (begin..begin + size) |bucket_position| {
299 const position = self.computeOnePosition(bucket_position, seed);
300 if (contains(self.all_positions[0..positions_to_find], position)) {
301 matches = true;
302 break;
303 }
304 }
305 if (matches) {
306 overlap_ranks[overlap_count] = scan_rank;
307 original_seeds[overlap_count] = seed;
308 overlap_count += 1;
309 }
310 scan_position -= 1;
311 }
312 for (overlap_ranks[0..overlap_count], original_seeds[0..overlap_count]) |
313 blocker_rank,
314 blocker_seed,
315 | {
316 self.undoBucket(blocker_rank, blocker_seed);
317 const failed_bucket_seed = self.tryPlaceBucket(rank, failed_seed);
318 if (failed_bucket_seed != failed_seed) {
319 self.committed_seeds[rank] = @truncate(failed_bucket_seed);
320 const new_blocker_seed = self.tryPlaceBucket(blocker_rank, blocker_seed);
321 if (new_blocker_seed != failed_seed) {
322 self.committed_seeds[blocker_rank] = @truncate(new_blocker_seed);
323 return true;
324 }
325 self.undoBucket(rank, failed_bucket_seed);
326 }
327 self.forcePlaceBucket(blocker_rank, blocker_seed);
328 self.committed_seeds[blocker_rank] = blocker_seed;
329 }
330 return false;
331 }
332
333 fn computeOnePosition(self: Self, bucket_position: usize, seed: u32) u32 {
334 const key_index = self.key_indices[bucket_position];
335 return family.positionFromHashAndSeed(
336 self.config.placement,
337 self.hashes[key_index],
338 seed,
339 );
340 }
341
342 fn computeBucketPositions(self: *Self, rank: u32) usize {
343 const bucket = self.bucket_order[rank];
344 const begin = self.bucket_offsets[bucket];
345 const size = self.bucket_sizes[bucket];
346 for (0..size) |local_index| {
347 const key_index = self.key_indices[begin + local_index];
348 const hash = self.hashes[key_index];
349 const hashes: PositionTag.Vector = @splat(hash);
350 var seed: usize = 0;
351 while (seed < seed_count) : (seed += 2 * PositionTag.lane_count) {
352 const first_seeds = construct.iota(PositionTag, @intCast(seed));
353 const second_seeds = construct.iota(
354 PositionTag,
355 @intCast(seed + PositionTag.lane_count),
356 );
357 const positions = family.positionPairFromHashesAndSeeds(
358 self.config.placement,
359 PositionTag,
360 hashes,
361 hashes,
362 first_seeds,
363 second_seeds,
364 );
365 const first: [PositionTag.lane_count]u32 = positions.first;
366 const second: [PositionTag.lane_count]u32 = positions.second;
367 const output = self.all_positions[local_index * seed_count + seed ..];
368 @memcpy(output[0..PositionTag.lane_count], &first);
369 @memcpy(
370 output[PositionTag.lane_count .. 2 * PositionTag.lane_count],
371 &second,
372 );
373 }
374 }
375 return size;
376 }
377
378 fn tryPlaceBucket(self: *Self, rank: u32, excluded_seed: u32) u32 {
379 const bucket_size = self.computeBucketPositions(rank);
380 const candidate_count = self.writeSeedCandidates(bucket_size);
381 var best_seed: u32 = 0;
382 var best_cost: u32 = std.math.maxInt(u32);
383 for (self.seed_candidates[0..candidate_count]) |seed| {
384 if (seed == excluded_seed) continue;
385 if (bucket_size >= 2) {
386 if (self.hasPairCollision(bucket_size, seed)) continue;
387 var cost: u32 = 0;
388 for (0..bucket_size) |local_index| {
389 const position = self.all_positions[local_index * seed_count + seed];
390 cost += @popCount(self.occupancy[position >> 5]);
391 }
392 if (cost >= best_cost) continue;
393 best_cost = cost;
394 best_seed = seed;
395 if (bucket_size <= 2 and cost == 0) break;
396 } else {
397 best_cost = 0;
398 best_seed = seed;
399 break;
400 }
401 }
402 if (best_cost == std.math.maxInt(u32)) return failed_seed;
403 for (0..bucket_size) |local_index| {
404 self.setOccupied(self.all_positions[local_index * seed_count + best_seed]);
405 }
406 self.setSeed(self.bucket_order[rank], best_seed);
407 return best_seed;
408 }
409
410 fn writeSeedCandidates(self: *Self, bucket_size: usize) usize {
411 var candidate_count: usize = 0;
412 var seed: usize = 0;
413 while (seed < seed_count) : (seed += 2 * PositionTag.lane_count) {
414 const first_seeds = construct.iota(PositionTag, @intCast(seed));
415 const second_seeds = construct.iota(
416 PositionTag,
417 @intCast(seed + PositionTag.lane_count),
418 );
419 var first_available: PositionTag.Mask = @splat(true);
420 var second_available: PositionTag.Mask = @splat(true);
421 for (0..bucket_size) |local_index| {
422 const positions = self.all_positions[local_index * seed_count + seed ..];
423 const first_positions: PositionTag.Vector =
424 positions[0..PositionTag.lane_count].*;
425 const second_positions: PositionTag.Vector =
426 positions[PositionTag.lane_count .. 2 * PositionTag.lane_count].*;
427 first_available &= self.unoccupied(first_positions);
428 second_available &= self.unoccupied(second_positions);
429 }
430 candidate_count += compact.compressStore(
431 PositionTag,
432 first_seeds,
433 first_available,
434 self.seed_candidates[candidate_count..],
435 );
436 candidate_count += compact.compressStore(
437 PositionTag,
438 second_seeds,
439 second_available,
440 self.seed_candidates[candidate_count..],
441 );
442 }
443 return candidate_count;
444 }
445
446 fn unoccupied(self: Self, positions: PositionTag.Vector) PositionTag.Mask {
447 const word_indices = shift.shiftRight(PositionTag, 5, positions);
448 const words = indexed.gatherIndex(PositionTag, self.occupancy, word_indices);
449 const bit_indices = positions & @as(PositionTag.Vector, @splat(31));
450 const bit_masks = shift.shl(PositionTag, @splat(1), bit_indices);
451 return words & bit_masks == @as(PositionTag.Vector, @splat(0));
452 }
453
454 fn hasPairCollision(self: Self, bucket_size: usize, seed: u32) bool {
455 for (0..bucket_size) |left| {
456 const left_position = self.all_positions[left * seed_count + seed];
457 for (left + 1..bucket_size) |right| {
458 if (left_position == self.all_positions[right * seed_count + seed]) {
459 return true;
460 }
461 }
462 }
463 return false;
464 }
465
466 fn undoBucket(self: *Self, rank: u32, seed: u32) void {
467 const bucket = self.bucket_order[rank];
468 const begin = self.bucket_offsets[bucket];
469 const size = self.bucket_sizes[bucket];
470 std.debug.assert(size > 0);
471 std.debug.assert(seed < seed_count);
472 for (begin..begin + size) |position| {
473 self.clearOccupied(self.computeOnePosition(position, seed));
474 }
475 self.clearSeed(bucket);
476 }
477
478 fn forcePlaceBucket(self: *Self, rank: u32, seed: u32) void {
479 const bucket = self.bucket_order[rank];
480 const begin = self.bucket_offsets[bucket];
481 const size = self.bucket_sizes[bucket];
482 std.debug.assert(size > 0);
483 std.debug.assert(seed < seed_count);
484 for (begin..begin + size) |position| {
485 self.setOccupied(self.computeOnePosition(position, seed));
486 }
487 self.setSeed(bucket, seed);
488 }
489
490 fn isOccupied(self: Self, position: u32) bool {
491 return self.occupancy[position >> 5] & (@as(u32, 1) << @intCast(position & 31)) != 0;
492 }
493
494 fn setOccupied(self: *Self, position: u32) void {
495 std.debug.assert(!self.isOccupied(position));
496 self.occupancy[position >> 5] |= @as(u32, 1) << @intCast(position & 31);
497 }
498
499 fn clearOccupied(self: *Self, position: u32) void {
500 std.debug.assert(self.isOccupied(position));
501 self.occupancy[position >> 5] &= ~(@as(u32, 1) << @intCast(position & 31));
502 }
503
504 fn setSeed(self: *Self, bucket: u32, seed: u32) void {
505 const bit_index = (bucket & 3) * 8;
506 self.seed_words[bucket >> 2] |= seed << @intCast(bit_index);
507 }
508
509 fn clearSeed(self: *Self, bucket: u32) void {
510 const bit_index = (bucket & 3) * 8;
511 self.seed_words[bucket >> 2] &= ~(@as(u32, 0xff) << @intCast(bit_index));
512 }
513 };
514
515 pub fn scratchLength(
516 num_keys: usize,
517 max_num_slots: usize,
518 max_num_buckets: usize,
519 ) family.PhastError!usize {
520 var words: usize = 0;
521 try addWords(&words, num_keys);
522 try addWords(&words, max_hashes_per_bucket * seed_count);
523 try addWords(&words, num_keys);
524 try addWords(&words, occupancyWordLength(max_num_slots));
525 try addWords(&words, byteWordLength(max_num_buckets));
526 try addWords(&words, byteWordLength(max_num_buckets));
527 const offsets = std.math.add(usize, max_num_buckets, 1) catch
528 return error.CapacityExceeded;
529 try addWords(&words, offsets);
530 try addWords(&words, max_num_buckets);
531 try addWords(&words, max_num_buckets);
532 try addWords(&words, seed_count);
533 return words;
534 }
535
536 fn enumerateConfigs(
537 num_keys: usize,
538 output: []family.Config,
539 ) family.PhastError!usize {
540 const minimum_slice = minimumSliceLength(num_keys);
541 if (minimum_slice > num_keys) return error.CapacityExceeded;
542 const previous_power = roundDownPowerOfTwo(num_keys);
543 const ratio = @as(f64, @floatFromInt(num_keys)) /
544 @as(f64, @floatFromInt(previous_power));
545 const keys_per_bucket = if (ratio < 1.3)
546 [_]usize{ 3, 0 }
547 else if (ratio > 1.7)
548 [_]usize{ 2, 0 }
549 else
550 [_]usize{ 3, 2 };
551 var count: usize = 0;
552 var permutation_index: usize = 0;
553 for (keys_per_bucket) |bucket_divisor| {
554 if (bucket_divisor == 0) continue;
555 for (headroom_percents) |headroom| {
556 for (0..2) |slice_shift| {
557 if (count >= output.len) return error.CapacityExceeded;
558 const slice_length = minimum_slice << @intCast(slice_shift);
559 const seed_base = std.math.mul(usize, permutation_index, max_attempts) catch
560 return error.CapacityExceeded;
561 output[count] = try makeConfig(
562 num_keys,
563 headroom,
564 bucket_divisor,
565 slice_length,
566 @intCast(seed_base),
567 );
568 count += 1;
569 permutation_index += 1;
570 }
571 }
572 }
573 return count;
574 }
575
576 fn makeConfig(
577 num_keys: usize,
578 headroom_percent: usize,
579 keys_per_bucket: usize,
580 slice_length: usize,
581 seed: u32,
582 ) family.PhastError!family.Config {
583 const scaled = std.math.mul(usize, num_keys, 100 + headroom_percent) catch
584 return error.CapacityExceeded;
585 const rounded = std.math.add(usize, scaled / 100, 1) catch
586 return error.CapacityExceeded;
587 const num_slots = @max(rounded, slice_length);
588 if (num_slots > std.math.maxInt(u32)) return error.CapacityExceeded;
589 const raw_buckets = num_keys / keys_per_bucket;
590 const num_buckets = roundUpPowerOfTwo(raw_buckets) catch
591 return error.CapacityExceeded;
592 if (num_buckets == 0 or num_buckets - 1 > std.math.maxInt(u32)) {
593 return error.CapacityExceeded;
594 }
595 return .{
596 .num_slots = num_slots,
597 .hash_key = seed,
598 .bucket_mask = @intCast(num_buckets - 1),
599 .placement = try family.Placement.init(num_slots, slice_length),
600 };
601 }
602
603 fn minimumSliceLength(num_keys: usize) usize {
604 std.debug.assert(num_keys >= 1);
605 if (num_keys < 64) return roundDownPowerOfTwo(num_keys / 2);
606 if (num_keys < 1_300) return 64;
607 if (num_keys < 9_500) return 128;
608 if (num_keys < 12_000) return 256;
609 if (num_keys < 140_000) return 512;
610 return 2_048;
611 }
612
613 fn sortConfigs(configs: []family.Config, payload_bytes: usize) void {
614 if (configs.len == 0) return;
615 introsort(configs, 0, configs.len, 2 * std.math.log2_int(usize, configs.len), payload_bytes);
616 finalInsertionSort(configs, payload_bytes);
617 }
618
619 fn introsort(
620 configs: []family.Config,
621 initial_first: usize,
622 initial_last: usize,
623 initial_depth: usize,
624 payload_bytes: usize,
625 ) void {
626 var frames: [max_config_count]SortFrame = undefined;
627 var frame_count: usize = 1;
628 frames[0] = .{
629 .first = initial_first,
630 .last = initial_last,
631 .depth = initial_depth,
632 };
633 while (frame_count != 0) {
634 frame_count -= 1;
635 var first = frames[frame_count].first;
636 const last = frames[frame_count].last;
637 var depth = frames[frame_count].depth;
638 while (last - first > insertion_threshold) {
639 if (depth == 0) {
640 std.sort.heap(
641 family.Config,
642 configs[first..last],
643 payload_bytes,
644 lessConfig,
645 );
646 break;
647 }
648 depth -= 1;
649 const cut = partitionPivot(configs, first, last, payload_bytes);
650 std.debug.assert(frame_count < frames.len);
651 frames[frame_count] = .{ .first = first, .last = cut, .depth = depth };
652 frame_count += 1;
653 first = cut;
654 }
655 }
656 }
657
658 fn partitionPivot(
659 configs: []family.Config,
660 first: usize,
661 last: usize,
662 payload_bytes: usize,
663 ) usize {
664 const middle = first + (last - first) / 2;
665 moveMedianToFirst(configs, first, first + 1, middle, last - 1, payload_bytes);
666 var left = first + 1;
667 var right = last;
668 while (true) {
669 while (configLess(configs[left], configs[first], payload_bytes)) left += 1;
670 right -= 1;
671 while (configLess(configs[first], configs[right], payload_bytes)) right -= 1;
672 if (left >= right) return left;
673 std.mem.swap(family.Config, &configs[left], &configs[right]);
674 left += 1;
675 }
676 }
677
678 fn moveMedianToFirst(
679 configs: []family.Config,
680 result: usize,
681 left: usize,
682 middle: usize,
683 right: usize,
684 payload_bytes: usize,
685 ) void {
686 const swap_index = if (configLess(configs[left], configs[middle], payload_bytes))
687 if (configLess(configs[middle], configs[right], payload_bytes))
688 middle
689 else if (configLess(configs[left], configs[right], payload_bytes))
690 right
691 else
692 left
693 else if (configLess(configs[left], configs[right], payload_bytes))
694 left
695 else if (configLess(configs[middle], configs[right], payload_bytes))
696 right
697 else
698 middle;
699 std.mem.swap(family.Config, &configs[result], &configs[swap_index]);
700 }
701
702 fn finalInsertionSort(configs: []family.Config, payload_bytes: usize) void {
703 if (configs.len > insertion_threshold) {
704 insertionSort(configs[0..insertion_threshold], payload_bytes);
705 for (insertion_threshold..configs.len) |index| {
706 unguardedLinearInsert(configs, index, payload_bytes);
707 }
708 } else {
709 insertionSort(configs, payload_bytes);
710 }
711 }
712
713 fn insertionSort(configs: []family.Config, payload_bytes: usize) void {
714 if (configs.len == 0) return;
715 for (1..configs.len) |index| {
716 const value = configs[index];
717 if (configLess(value, configs[0], payload_bytes)) {
718 var move = index;
719 while (move > 0) : (move -= 1) configs[move] = configs[move - 1];
720 configs[0] = value;
721 } else {
722 unguardedLinearInsert(configs, index, payload_bytes);
723 }
724 }
725 }
726
727 fn unguardedLinearInsert(
728 configs: []family.Config,
729 initial_index: usize,
730 payload_bytes: usize,
731 ) void {
732 const value = configs[initial_index];
733 var index = initial_index;
734 var previous = index - 1;
735 while (configLess(value, configs[previous], payload_bytes)) {
736 configs[index] = configs[previous];
737 index = previous;
738 std.debug.assert(previous > 0);
739 previous -= 1;
740 }
741 configs[index] = value;
742 }
743
744 fn configLess(left: family.Config, right: family.Config, payload_bytes: usize) bool {
745 return (left.allocatedBytes(payload_bytes) catch unreachable) <
746 (right.allocatedBytes(payload_bytes) catch unreachable);
747 }
748
749 fn lessConfig(payload_bytes: usize, left: family.Config, right: family.Config) bool {
750 return configLess(left, right, payload_bytes);
751 }
752
753 fn roundDownPowerOfTwo(value: usize) usize {
754 if (value <= 1) return 1;
755 return @as(usize, 1) << std.math.log2_int(usize, value);
756 }
757
758 fn roundUpPowerOfTwo(value: usize) error{Overflow}!usize {
759 if (value <= 1) return 1;
760 return std.math.ceilPowerOfTwo(usize, value);
761 }
762
763 fn occupancyWordLength(num_slots: usize) usize {
764 return std.math.divCeil(usize, num_slots, @bitSizeOf(u32)) catch unreachable;
765 }
766
767 fn byteWordLength(byte_count: usize) usize {
768 return std.math.divCeil(usize, byte_count, @sizeOf(u32)) catch unreachable;
769 }
770
771 fn addWords(words: *usize, additional: usize) family.PhastError!void {
772 words.* = std.math.add(usize, words.*, additional) catch
773 return error.CapacityExceeded;
774 }
775
776 fn takeWords(storage: []u32, offset: *usize, length: usize) []u32 {
777 const begin = offset.*;
778 const end = begin + length;
779 offset.* = end;
780 return storage[begin..end];
781 }
782
783 fn contains(values: []const u32, target: u32) bool {
784 for (values) |value| if (value == target) return true;
785 return false;
786 }
787
788 fn storageOverlaps(
789 comptime Left: type,
790 left: []const Left,
791 comptime Right: type,
792 right: []const Right,
793 ) bool {
794 if (left.len == 0 or right.len == 0) return false;
795 const left_begin = @intFromPtr(left.ptr);
796 const right_begin = @intFromPtr(right.ptr);
797 const left_bytes = std.math.mul(usize, left.len, @sizeOf(Left)) catch return true;
798 const right_bytes = std.math.mul(usize, right.len, @sizeOf(Right)) catch return true;
799 const left_end = std.math.add(usize, left_begin, left_bytes) catch return true;
800 const right_end = std.math.add(usize, right_begin, right_bytes) catch return true;
801 return left_begin < right_end and right_begin < left_end;
802 }
803
804 pub fn phastScratchLen(num_keys: usize, payload_bytes: usize) family.PhastError!usize {
805 return (try Plan.inspect(num_keys, payload_bytes)).scratch_len;
806 }
807
808 pub fn phastSeedsLen(num_keys: usize, payload_bytes: usize) family.PhastError!usize {
809 return (try Plan.inspect(num_keys, payload_bytes)).seeds_len;
810 }
811
812 pub fn buildPhast(
813 scratch: []u32,
814 seed_words: []u32,
815 keys: []const u32,
816 payload_bytes: usize,
817 ) family.PhastError!family.Data {
818 const plan = try Plan.inspect(keys.len, payload_bytes);
819 return plan.build(scratch, seed_words, keys);
820 }
821
822 fn fixtureKeys(comptime count: usize, key: u32) [count]u32 {
823 const permutation = hash_mod.Triple32.initKey(key);
824 var keys: [count]u32 = undefined;
825 for (&keys, 0..) |*value, index| value.* = permutation.hash(@intCast(index));
826 return keys;
827 }
828
829 fn digest(comptime T: type, values: []const T) u64 {
830 var result: u64 = 1_469_598_103_934_665_603;
831 for (values) |value| result = (result ^ @as(u64, value)) *% 1_099_511_628_211;
832 return result;
833 }
834
835 fn expectSliceLengths(num_keys: usize, first: usize, second: usize) !void {
836 const plan = try Plan.inspect(num_keys, 0);
837 var found_first = false;
838 var found_second = false;
839 for (plan.configs[0..plan.config_count]) |config| {
840 const slice_length = config.placement.sliceLength();
841 try std.testing.expect(slice_length == first or slice_length == second);
842 found_first = found_first or slice_length == first;
843 found_second = found_second or slice_length == second;
844 }
845 try std.testing.expect(found_first);
846 try std.testing.expect(found_second);
847 }
848
849 test "Highway PHAST one-key table image matches the pinned builder" {
850 const keys = fixtureKeys(1, 0);
851 const plan = try Plan.inspect(keys.len, 0);
852 try std.testing.expectEqual(@as(usize, 8_457), plan.scratch_len);
853 try std.testing.expectEqual(@as(usize, 1), plan.seeds_len);
854 const allocator = std.testing.allocator;
855 const scratch = try allocator.alloc(u32, plan.scratch_len);
856 defer allocator.free(scratch);
857 const seed_words = try allocator.alloc(u32, plan.seeds_len);
858 defer allocator.free(seed_words);
859 const data = try plan.build(scratch, seed_words, &keys);
860 try std.testing.expectEqual(@as(usize, 2), data.config.num_slots);
861 try std.testing.expectEqual(@as(usize, 1), data.config.numBuckets());
862 try std.testing.expectEqual(@as(u32, 0x7aa5_332d), data.config.hash_key);
863 try std.testing.expectEqual(@as(u32, 2), data.config.placement.num_slice_offsets);
864 try std.testing.expectEqual(@as(u32, 0), data.config.placement.slice_mask);
865 try std.testing.expectEqual(@as(usize, 0), data.config_index);
866 try std.testing.expectEqual(@as(usize, 0), data.attempt_index);
867 try std.testing.expectEqualSlices(u32, &.{0}, data.seeds.words);
868 try std.testing.expectEqual(@as(u32, 0), (try family.Phast.init(data)).index(keys[0]));
869 }
870
871 test "Highway PHAST 64-key table image matches the pinned builder" {
872 const keys = fixtureKeys(64, 0);
873 const plan = try Plan.inspect(keys.len, 0);
874 try std.testing.expectEqual(@as(usize, 8_693), plan.scratch_len);
875 try std.testing.expectEqual(@as(usize, 8), plan.seeds_len);
876 const allocator = std.testing.allocator;
877 const scratch = try allocator.alloc(u32, plan.scratch_len);
878 defer allocator.free(scratch);
879 const seed_words = try allocator.alloc(u32, plan.seeds_len);
880 defer allocator.free(seed_words);
881 const data = try plan.build(scratch, seed_words, &keys);
882 try std.testing.expectEqual(@as(usize, 65), data.config.num_slots);
883 try std.testing.expectEqual(@as(usize, 32), data.config.numBuckets());
884 try std.testing.expectEqual(@as(u32, 0x7aa5_332d), data.config.hash_key);
885 try std.testing.expectEqual(@as(u32, 2), data.config.placement.num_slice_offsets);
886 try std.testing.expectEqual(@as(u32, 63), data.config.placement.slice_mask);
887 try std.testing.expectEqual(@as(usize, 0), data.config_index);
888 try std.testing.expectEqual(@as(usize, 0), data.attempt_index);
889 try std.testing.expectEqual(@as(usize, 32), try data.allocatedBytes(0));
890 try std.testing.expectEqualSlices(u32, &.{
891 0x0203_0000,
892 0x0514_0600,
893 0x032c_0e16,
894 0x0a02_0000,
895 0x0007_7c02,
896 0x0020_1308,
897 0x4960_6701,
898 0x4307_020e,
899 }, data.seeds.words);
900 try std.testing.expectEqual(@as(u64, 0x40f9_1e97_5657_1114), digest(u32, data.seeds.words));
901 const phast = try family.Phast.init(data);
902 var positions: [keys.len]u32 = undefined;
903 for (keys, &positions) |key, *position| position.* = phast.index(key);
904 try std.testing.expectEqualSlices(u32, &.{
905 13, 55, 33, 23, 45, 50, 27, 31,
906 3, 16, 18, 40, 25, 2, 44, 24,
907 }, positions[0..16]);
908 try std.testing.expectEqual(@as(u64, 0x0dba_d93f_4650_dd0a), digest(u32, &positions));
909 var occupied: [65]bool = @splat(false);
910 for (positions) |position| {
911 try std.testing.expect(position < occupied.len);
912 try std.testing.expect(!occupied[position]);
913 occupied[position] = true;
914 }
915 const D = tag.FixedTag(u32, 8);
916 const paired = phast.twoVec(D, keys[0..8].*, keys[8..16].*);
917 try std.testing.expect(@reduce(.And, paired.first == @as(D.Vector, positions[0..8].*)));
918 try std.testing.expect(@reduce(.And, paired.second == @as(D.Vector, positions[8..16].*)));
919 var batch: [33]u32 = undefined;
920 for (0..batch.len + 1) |length| {
921 try phast.indexBatch(D, keys[0..length], batch[0..length]);
922 for (batch[0..length], keys[0..length]) |actual, key| {
923 try std.testing.expectEqual(phast.index(key), actual);
924 }
925 }
926 try std.testing.expectError(error.PlanMismatch, phast.indexBatch(D, keys[0..2], batch[0..1]));
927 }
928
929 test "Highway PHAST configuration ordering matches the pinned builder" {
930 const keys = fixtureKeys(100, 0);
931 const plan = try Plan.inspect(keys.len, 0);
932 try std.testing.expectEqual(@as(usize, 8_877), plan.scratch_len);
933 try std.testing.expectEqual(@as(usize, 16), plan.seeds_len);
934 const allocator = std.testing.allocator;
935 const scratch = try allocator.alloc(u32, plan.scratch_len);
936 defer allocator.free(scratch);
937 const seed_words = try allocator.alloc(u32, plan.seeds_len);
938 defer allocator.free(seed_words);
939 const data = try plan.build(scratch, seed_words, &keys);
940 try std.testing.expectEqual(@as(usize, 102), data.config.num_slots);
941 try std.testing.expectEqual(@as(usize, 64), data.config.numBuckets());
942 try std.testing.expectEqual(@as(u32, 0x2db7_aa3d), data.config.hash_key);
943 try std.testing.expectEqual(@as(u32, 39), data.config.placement.num_slice_offsets);
944 try std.testing.expectEqual(@as(u32, 63), data.config.placement.slice_mask);
945 try std.testing.expectEqual(@as(usize, 0), data.config_index);
946 try std.testing.expectEqual(@as(usize, 0), data.attempt_index);
947 try std.testing.expectEqual(@as(u64, 0x5a53_81c8_0a88_ff4e), digest(u32, data.seeds.words));
948 const phast = try family.Phast.init(data);
949 var positions: [keys.len]u32 = undefined;
950 try phast.indexBatch(tag.FixedTag(u32, 8), &keys, &positions);
951 try std.testing.expectEqualSlices(u32, &.{
952 43, 93, 33, 65, 94, 36, 92, 27,
953 46, 90, 74, 12, 61, 97, 22, 4,
954 }, positions[0..16]);
955 try std.testing.expectEqual(@as(u64, 0xb571_753a_626d_5579), digest(u32, &positions));
956 }
957
958 test "Highway PHAST builder matches a retried pinned table image" {
959 const keys = fixtureKeys(50, 0x816);
960 const plan = try Plan.inspect(keys.len, 0);
961 try std.testing.expectEqual(@as(usize, 8_663), plan.scratch_len);
962 try std.testing.expectEqual(@as(usize, 8), plan.seeds_len);
963 const allocator = std.testing.allocator;
964 const scratch = try allocator.alloc(u32, plan.scratch_len);
965 defer allocator.free(scratch);
966 const seed_words = try allocator.alloc(u32, plan.seeds_len);
967 defer allocator.free(seed_words);
968 const data = try plan.build(scratch, seed_words, &keys);
969 try std.testing.expectEqual(@as(usize, 51), data.config.num_slots);
970 try std.testing.expectEqual(@as(usize, 16), data.config.numBuckets());
971 try std.testing.expectEqual(@as(u32, 0x7f8c_17b1), data.config.hash_key);
972 try std.testing.expectEqual(@as(u32, 36), data.config.placement.num_slice_offsets);
973 try std.testing.expectEqual(@as(u32, 15), data.config.placement.slice_mask);
974 try std.testing.expectEqual(@as(usize, 1), data.config_index);
975 try std.testing.expectEqual(@as(usize, 216), data.attempt_index);
976 try std.testing.expectEqualSlices(u32, &.{
977 0x3260_035a,
978 0x2f14_13c2,
979 0x003e_301c,
980 0x0e00_b807,
981 }, data.seeds.words);
982 try std.testing.expectEqual(@as(u64, 0xace0_16b3_9ce4_5386), digest(u32, data.seeds.words));
983 const phast = try family.Phast.init(data);
984 var positions: [keys.len]u32 = undefined;
985 try phast.indexBatch(tag.FixedTag(u32, 8), &keys, &positions);
986 try std.testing.expectEqualSlices(u32, &.{
987 24, 15, 31, 37, 18, 11, 26, 48,
988 23, 42, 7, 36, 50, 25, 43, 39,
989 }, positions[0..16]);
990 try std.testing.expectEqual(@as(u64, 0x45a2_adf5_7dc4_cd42), digest(u32, &positions));
991 }
992
993 test "Highway PHAST plan enforces storage keys and empty input contracts" {
994 const keys = fixtureKeys(8, 91);
995 const plan = try Plan.inspect(keys.len, 4);
996 const allocator = std.testing.allocator;
997 const scratch = try allocator.alloc(u32, plan.scratch_len);
998 defer allocator.free(scratch);
999 const seed_words = try allocator.alloc(u32, plan.seeds_len);
1000 defer allocator.free(seed_words);
1001 try std.testing.expectError(
1002 error.ScratchTooSmall,
1003 plan.build(scratch[0 .. scratch.len - 1], seed_words, &keys),
1004 );
1005 try std.testing.expectError(
1006 error.SeedsTooSmall,
1007 plan.build(scratch, seed_words[0 .. seed_words.len - 1], &keys),
1008 );
1009 try std.testing.expectError(
1010 error.InputOutputOverlap,
1011 plan.build(scratch, scratch[0..plan.seeds_len], &keys),
1012 );
1013 try std.testing.expectError(
1014 error.InputOutputOverlap,
1015 plan.build(scratch, seed_words, scratch[0..keys.len]),
1016 );
1017 var duplicates = keys;
1018 duplicates[7] = duplicates[0];
1019 try std.testing.expectError(
1020 error.DuplicateKey,
1021 plan.build(scratch, seed_words, &duplicates),
1022 );
1023 const empty_plan = try Plan.inspect(0, std.math.maxInt(usize));
1024 const empty = try empty_plan.build(&.{}, &.{}, &.{});
1025 try std.testing.expect(empty.isEmpty());
1026 try std.testing.expectEqual(@as(usize, 0), empty_plan.scratch_len);
1027 try std.testing.expectEqual(@as(usize, 0), empty_plan.seeds_len);
1028 }
1029
1030 test "Highway PHAST placement and data reject malformed layouts" {
1031 try std.testing.expectError(error.InvalidData, family.Placement.init(8, 3));
1032 try std.testing.expectError(error.CapacityExceeded, family.Placement.init(3, 4));
1033 const words = [_]u32{0};
1034 const config = family.Config{
1035 .num_slots = 8,
1036 .hash_key = 7,
1037 .bucket_mask = 3,
1038 .placement = try family.Placement.init(8, 4),
1039 };
1040 _ = try family.Phast.init(.{ .config = config, .seeds = .{ .words = &words } });
1041 try std.testing.expectError(
1042 error.InvalidData,
1043 family.Phast.init(.{ .config = config, .seeds = .{} }),
1044 );
1045 var malformed = config;
1046 malformed.bucket_mask = 2;
1047 try std.testing.expectError(
1048 error.InvalidData,
1049 family.Phast.init(.{ .config = malformed, .seeds = .{ .words = &words } }),
1050 );
1051 malformed = config;
1052 malformed.placement.slice_mask = 2;
1053 try std.testing.expectError(
1054 error.InvalidData,
1055 family.Phast.init(.{ .config = malformed, .seeds = .{ .words = &words } }),
1056 );
1057 malformed = config;
1058 malformed.placement.num_slice_offsets -= 1;
1059 try std.testing.expectError(
1060 error.InvalidData,
1061 family.Phast.init(.{ .config = malformed, .seeds = .{ .words = &words } }),
1062 );
1063 try std.testing.expectError(error.BuildFailed, family.Phast.init(.{}));
1064 }
1065
1066 test "Highway PHAST configuration slice thresholds match the pinned builder" {
1067 try expectSliceLengths(63, 16, 32);
1068 try expectSliceLengths(64, 64, 128);
1069 try expectSliceLengths(1_299, 64, 128);
1070 try expectSliceLengths(1_300, 128, 256);
1071 try expectSliceLengths(9_499, 128, 256);
1072 try expectSliceLengths(9_500, 256, 512);
1073 try expectSliceLengths(11_999, 256, 512);
1074 try expectSliceLengths(12_000, 512, 1_024);
1075 try expectSliceLengths(139_999, 512, 1_024);
1076 try expectSliceLengths(140_000, 2_048, 4_096);
1077 }
1078
1079 test "Highway PHAST planning rejects unrepresentable capacities" {
1080 try std.testing.expectError(
1081 error.CapacityExceeded,
1082 Plan.inspect(std.math.maxInt(u32), 0),
1083 );
1084 try std.testing.expectError(
1085 error.CapacityExceeded,
1086 Plan.inspect(1, std.math.maxInt(usize)),
1087 );
1088 try std.testing.expectError(
1089 error.CapacityExceeded,
1090 (family.Config{ .num_slots = std.math.maxInt(usize) }).allocatedBytes(2),
1091 );
1092 try std.testing.expectError(
1093 error.CapacityExceeded,
1094 scratchLength(std.math.maxInt(usize), 0, 0),
1095 );
1096 }