1// zig run -O ReleaseFast --zig-lib-dir ../.. benchmark.zig
2const builtin = @import("builtin");
3
4const std = @import("std");
5const Io = std.Io;
6const time = std.time;
7const hash = std.hash;
8
9const KiB = 1024;
10const MiB = 1024 * KiB;
11const GiB = 1024 * MiB;
12
13var prng = std.Random.DefaultPrng.init(0);
14const random = prng.random();
15
16const Hash = struct {
17 ty: type,
18 name: []const u8,
19 has_iterative_api: bool = true,
20 has_crypto_api: bool = false,
21 has_anytype_api: ?[]const comptime_int = null,
22 /// `final` value should be read from this field.
23 has_struct_api: ?[]const u8 = null,
24 init_u8s: ?[]const u8 = null,
25 init_u64: ?u64 = null,
26 init_default: bool = false,
27};
28
29const hashes = [_]Hash{
30 Hash{
31 .ty = hash.XxHash3,
32 .name = "xxh3",
33 .init_u64 = 0,
34 .has_anytype_api = @as([]const comptime_int, &[_]comptime_int{ 8, 16, 32, 48, 64, 80, 96, 112, 128 }),
35 },
36 Hash{
37 .ty = hash.XxHash64,
38 .name = "xxhash64",
39 .init_u64 = 0,
40 .has_anytype_api = @as([]const comptime_int, &[_]comptime_int{ 8, 16, 32, 48, 64, 80, 96, 112, 128 }),
41 },
42 Hash{
43 .ty = hash.XxHash32,
44 .name = "xxhash32",
45 .init_u64 = 0,
46 .has_anytype_api = @as([]const comptime_int, &[_]comptime_int{ 8, 16, 32, 48, 64, 80, 96, 112, 128 }),
47 },
48 Hash{
49 .ty = hash.Wyhash,
50 .name = "wyhash",
51 .init_u64 = 0,
52 },
53 Hash{
54 .ty = hash.Fnv1a_64,
55 .name = "fnv1a",
56 },
57 Hash{
58 .ty = hash.Adler32,
59 .name = "adler32",
60 .has_struct_api = "adler",
61 .init_default = true,
62 },
63 Hash{
64 .ty = hash.Crc32,
65 .name = "crc32",
66 },
67 Hash{
68 .ty = hash.CityHash32,
69 .name = "cityhash-32",
70 .has_iterative_api = false,
71 },
72 Hash{
73 .ty = hash.CityHash64,
74 .name = "cityhash-64",
75 .has_iterative_api = false,
76 },
77 Hash{
78 .ty = hash.Murmur2_32,
79 .name = "murmur2-32",
80 .has_iterative_api = false,
81 },
82 Hash{
83 .ty = hash.Murmur2_64,
84 .name = "murmur2-64",
85 .has_iterative_api = false,
86 },
87 Hash{
88 .ty = hash.Murmur3_32,
89 .name = "murmur3-32",
90 .has_iterative_api = false,
91 },
92 Hash{
93 .ty = hash.SipHash64(1, 3),
94 .name = "siphash64",
95 .has_crypto_api = true,
96 .init_u8s = &@as([16]u8, @splat(0)),
97 },
98 Hash{
99 .ty = hash.SipHash128(1, 3),
100 .name = "siphash128",
101 .has_crypto_api = true,
102 .init_u8s = &@as([16]u8, @splat(0)),
103 },
104};
105
106const Result = struct {
107 hash: u64,
108 throughput: u64,
109};
110
111const block_size: usize = 8 * 8192;
112
113pub fn benchTime(io: Io) i96 {
114 return Io.Clock.awake.now(io).nanoseconds;
115}
116
117pub fn benchmarkHash(comptime H: anytype, bytes: usize, allocator: std.mem.Allocator, io: Io) !Result {
118 var blocks = try allocator.alloc(u8, bytes);
119 defer allocator.free(blocks);
120 random.bytes(blocks);
121
122 const block_count = bytes / block_size;
123
124 var h: H.ty = blk: {
125 if (H.init_u8s) |init| {
126 break :blk .init(init[0..H.ty.key_length]);
127 }
128 if (H.init_u64) |init| {
129 break :blk .init(init);
130 }
131 if (H.init_default) {
132 break :blk .{};
133 }
134 break :blk .init();
135 };
136
137 const start = benchTime(io);
138 for (0..block_count) |i| {
139 h.update(blocks[i * block_size ..][0..block_size]);
140 }
141 const final = if (H.has_struct_api) |field_name|
142 @field(h, field_name)
143 else if (H.has_crypto_api)
144 @as(u64, @truncate(h.finalInt()))
145 else
146 h.final();
147 std.mem.doNotOptimizeAway(final);
148
149 const elapsed_ns = benchTime(io) - start;
150
151 const elapsed_s = @as(f64, @floatFromInt(elapsed_ns)) / time.ns_per_s;
152 const size_float: f64 = @floatFromInt(block_size * block_count);
153 const throughput: u64 = @intFromFloat(size_float / elapsed_s);
154
155 return Result{
156 .hash = final,
157 .throughput = throughput,
158 };
159}
160
161pub fn benchmarkHashSmallKeys(comptime H: anytype, key_size: usize, bytes: usize, allocator: std.mem.Allocator, io: Io) !Result {
162 var blocks = try allocator.alloc(u8, bytes);
163 defer allocator.free(blocks);
164 random.bytes(blocks);
165
166 const key_count = bytes / key_size;
167
168 const start = benchTime(io);
169
170 var sum: u64 = 0;
171 for (0..key_count) |i| {
172 const small_key = blocks[i * key_size ..][0..key_size];
173 const final = blk: {
174 if (H.init_u8s) |init| {
175 if (H.has_crypto_api) {
176 break :blk @as(u64, @truncate(H.ty.toInt(small_key, init[0..H.ty.key_length])));
177 } else {
178 break :blk H.ty.hash(init, small_key);
179 }
180 }
181 if (H.init_u64) |init| {
182 break :blk H.ty.hash(init, small_key);
183 }
184 break :blk H.ty.hash(small_key);
185 };
186 sum +%= final;
187 }
188 const elapsed_ns = benchTime(io) - start;
189
190 const elapsed_s = @as(f64, @floatFromInt(elapsed_ns)) / time.ns_per_s;
191 const size_float: f64 = @floatFromInt(key_count * key_size);
192 const throughput: u64 = @intFromFloat(size_float / elapsed_s);
193
194 std.mem.doNotOptimizeAway(sum);
195
196 return Result{
197 .hash = sum,
198 .throughput = throughput,
199 };
200}
201
202// the array and array pointer benchmarks for xxhash are very sensitive to in-lining,
203// if you see strange performance changes consider using `.never_inline` or `.always_inline`
204// to ensure the changes are not only due to the optimiser inlining the benchmark differently
205pub fn benchmarkHashSmallKeysArrayPtr(
206 comptime H: anytype,
207 comptime key_size: usize,
208 bytes: usize,
209 allocator: std.mem.Allocator,
210 io: Io,
211) !Result {
212 var blocks = try allocator.alloc(u8, bytes);
213 defer allocator.free(blocks);
214 random.bytes(blocks);
215
216 const key_count = bytes / key_size;
217
218 const start = benchTime(io);
219
220 var sum: u64 = 0;
221 for (0..key_count) |i| {
222 const small_key = blocks[i * key_size ..][0..key_size];
223 const final: u64 = blk: {
224 if (H.init_u8s) |init| {
225 if (H.has_crypto_api) {
226 break :blk @truncate(H.ty.toInt(small_key, init[0..H.ty.key_length]));
227 } else {
228 break :blk H.ty.hash(init, small_key);
229 }
230 }
231 if (H.init_u64) |init| {
232 break :blk H.ty.hash(init, small_key);
233 }
234 break :blk H.ty.hash(small_key);
235 };
236 sum +%= final;
237 }
238 const elapsed_ns = benchTime(io) - start;
239
240 const elapsed_s = @as(f64, @floatFromInt(elapsed_ns)) / time.ns_per_s;
241 const throughput: u64 = @intFromFloat(@as(f64, @floatFromInt(bytes)) / elapsed_s);
242
243 std.mem.doNotOptimizeAway(sum);
244
245 return Result{
246 .hash = sum,
247 .throughput = throughput,
248 };
249}
250
251// the array and array pointer benchmarks for xxhash are very sensitive to in-lining,
252// if you see strange performance changes consider using `.never_inline` or `.always_inline`
253// to ensure the changes are not only due to the optimiser inlining the benchmark differently
254pub fn benchmarkHashSmallKeysArray(
255 comptime H: anytype,
256 comptime key_size: usize,
257 bytes: usize,
258 allocator: std.mem.Allocator,
259 io: Io,
260) !Result {
261 var blocks = try allocator.alloc(u8, bytes);
262 defer allocator.free(blocks);
263 random.bytes(blocks);
264
265 const key_count = bytes / key_size;
266
267 var i: usize = 0;
268 const start = benchTime(io);
269
270 var sum: u64 = 0;
271 while (i < key_count) : (i += 1) {
272 const small_key = blocks[i * key_size ..][0..key_size];
273 const final: u64 = blk: {
274 if (H.init_u8s) |init| {
275 if (H.has_crypto_api) {
276 break :blk @truncate(H.ty.toInt(small_key, init[0..H.ty.key_length]));
277 } else {
278 break :blk H.ty.hash(init, small_key.*);
279 }
280 }
281 if (H.init_u64) |init| {
282 break :blk H.ty.hash(init, small_key.*);
283 }
284 break :blk H.ty.hash(small_key.*);
285 };
286 sum +%= final;
287 }
288 const elapsed_ns = benchTime(io) - start;
289
290 const elapsed_s = @as(f64, @floatFromInt(elapsed_ns)) / time.ns_per_s;
291 const throughput: u64 = @intFromFloat(@as(f64, @floatFromInt(bytes)) / elapsed_s);
292
293 std.mem.doNotOptimizeAway(sum);
294
295 return Result{
296 .hash = sum,
297 .throughput = throughput,
298 };
299}
300
301pub fn benchmarkHashSmallApi(comptime H: anytype, key_size: usize, bytes: usize, allocator: std.mem.Allocator, io: Io) !Result {
302 var blocks = try allocator.alloc(u8, bytes);
303 defer allocator.free(blocks);
304 random.bytes(blocks);
305
306 const key_count = bytes / key_size;
307
308 const start = benchTime(io);
309
310 var sum: u64 = 0;
311 for (0..key_count) |i| {
312 const small_key = blocks[i * key_size ..][0..key_size];
313 const final: u64 = blk: {
314 if (H.init_u8s) |init| {
315 if (H.has_crypto_api) {
316 break :blk @truncate(H.ty.toInt(small_key, init[0..H.ty.key_length]));
317 } else {
318 break :blk H.ty.hashSmall(init, small_key);
319 }
320 }
321 if (H.init_u64) |init| {
322 break :blk H.ty.hashSmall(init, small_key);
323 }
324 break :blk H.ty.hashSmall(small_key);
325 };
326 sum +%= final;
327 }
328 const elapsed_ns = benchTime(io) - start;
329
330 const elapsed_s = @as(f64, @floatFromInt(elapsed_ns)) / time.ns_per_s;
331 const throughput: u64 = @intFromFloat(@as(f64, @floatFromInt(bytes)) / elapsed_s);
332
333 std.mem.doNotOptimizeAway(sum);
334
335 return Result{
336 .throughput = throughput,
337 .hash = sum,
338 };
339}
340
341fn usage() void {
342 std.debug.print(
343 \\throughput_test [options]
344 \\
345 \\Options:
346 \\ --filter [test-name]
347 \\ --seed [int]
348 \\ --count [int]
349 \\ --key-size [int]
350 \\ --iterative-only
351 \\ --small-key-only
352 \\ --help
353 \\
354 , .{});
355}
356
357fn mode(comptime x: comptime_int) comptime_int {
358 return if (builtin.mode == .debug) x / 64 else x;
359}
360
361pub fn main(init: std.process.Init) !void {
362 const io = init.io;
363 const arena = init.arena.allocator();
364
365 var stdout_buffer: [0x100]u8 = undefined;
366 var stdout_writer = Io.File.stdout().writer(io, &stdout_buffer);
367 const stdout = &stdout_writer.interface;
368
369 const args = try init.minimal.args.toSlice(arena);
370
371 var filter: ?[]const u8 = null;
372 var count: usize = mode(128 * MiB);
373 var key_size: ?usize = null;
374 var seed: u32 = 0;
375 var test_small_key_only = false;
376 var test_iterative_only = false;
377 var test_arrays = false;
378
379 const default_small_key_size = 32;
380
381 var i: usize = 1;
382 while (i < args.len) : (i += 1) {
383 if (std.mem.eql(u8, args[i], "--mode")) {
384 try stdout.print("{}\n", .{builtin.mode});
385 try stdout.flush();
386 return;
387 } else if (std.mem.eql(u8, args[i], "--seed")) {
388 i += 1;
389 if (i == args.len) {
390 usage();
391 std.process.exit(1);
392 }
393
394 seed = try std.fmt.parseUnsigned(u32, args[i], 10);
395 // we seed later
396 } else if (std.mem.eql(u8, args[i], "--filter")) {
397 i += 1;
398 if (i == args.len) {
399 usage();
400 std.process.exit(1);
401 }
402
403 filter = args[i];
404 } else if (std.mem.eql(u8, args[i], "--count")) {
405 i += 1;
406 if (i == args.len) {
407 usage();
408 std.process.exit(1);
409 }
410
411 const c = try std.fmt.parseUnsigned(usize, args[i], 10);
412 count = c * MiB;
413 } else if (std.mem.eql(u8, args[i], "--key-size")) {
414 i += 1;
415 if (i == args.len) {
416 usage();
417 std.process.exit(1);
418 }
419
420 key_size = try std.fmt.parseUnsigned(usize, args[i], 10);
421 if (key_size.? > block_size) {
422 try stdout.print("key_size cannot exceed block size of {}\n", .{block_size});
423 try stdout.flush();
424 std.process.exit(1);
425 }
426 } else if (std.mem.eql(u8, args[i], "--iterative-only")) {
427 test_iterative_only = true;
428 } else if (std.mem.eql(u8, args[i], "--small-key-only")) {
429 test_small_key_only = true;
430 } else if (std.mem.eql(u8, args[i], "--include-array")) {
431 test_arrays = true;
432 } else if (std.mem.eql(u8, args[i], "--help")) {
433 usage();
434 return;
435 } else {
436 usage();
437 std.process.exit(1);
438 }
439 }
440
441 if (test_iterative_only and test_small_key_only) {
442 try stdout.print("Cannot use iterative-only and small-key-only together!\n", .{});
443 try stdout.flush();
444 usage();
445 std.process.exit(1);
446 }
447
448 var gpa: std.heap.DebugAllocator(.{}) = .init;
449 defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
450 const allocator = gpa.allocator();
451
452 inline for (hashes) |H| {
453 if (filter == null or std.mem.find(u8, H.name, filter.?) != null) hash: {
454 if (!test_iterative_only or H.has_iterative_api) {
455 try stdout.print("{s}\n", .{H.name});
456 try stdout.flush();
457
458 // Always reseed prior to every call so we are hashing the same buffer contents.
459 // This allows easier comparison between different implementations.
460 if (H.has_iterative_api and !test_small_key_only) {
461 prng.seed(seed);
462 const result = try benchmarkHash(H, count, allocator, io);
463 try stdout.print(" iterative: {:5} MiB/s [{x:0<16}]\n", .{ result.throughput / (1 * MiB), result.hash });
464 try stdout.flush();
465 }
466
467 if (!test_iterative_only) {
468 if (key_size) |size| {
469 prng.seed(seed);
470 const result_small = try benchmarkHashSmallKeys(H, size, count, allocator, io);
471 try stdout.print(" small keys: {:3}B {:5} MiB/s {} Hashes/s [{x:0<16}]\n", .{
472 size,
473 result_small.throughput / (1 * MiB),
474 result_small.throughput / size,
475 result_small.hash,
476 });
477 try stdout.flush();
478
479 if (!test_arrays) break :hash;
480 if (H.has_anytype_api) |sizes| {
481 inline for (sizes) |exact_size| {
482 if (size == exact_size) {
483 prng.seed(seed);
484 const result_array = try benchmarkHashSmallKeysArray(H, exact_size, count, allocator, io);
485 prng.seed(seed);
486 const result_ptr = try benchmarkHashSmallKeysArrayPtr(H, exact_size, count, allocator, io);
487 try stdout.print(" array: {:5} MiB/s [{x:0<16}]\n", .{
488 result_array.throughput / (1 * MiB),
489 result_array.hash,
490 });
491 try stdout.print(" array ptr: {:5} MiB/s [{x:0<16}]\n", .{
492 result_ptr.throughput / (1 * MiB),
493 result_ptr.hash,
494 });
495 try stdout.flush();
496 }
497 }
498 }
499 } else {
500 prng.seed(seed);
501 const result_small = try benchmarkHashSmallKeys(H, default_small_key_size, count, allocator, io);
502 try stdout.print(" small keys: {:3}B {:5} MiB/s {} Hashes/s [{x:0<16}]\n", .{
503 default_small_key_size,
504 result_small.throughput / (1 * MiB),
505 result_small.throughput / default_small_key_size,
506 result_small.hash,
507 });
508 try stdout.flush();
509
510 if (!test_arrays) break :hash;
511 if (H.has_anytype_api) |sizes| {
512 try stdout.print(" array:\n", .{});
513 inline for (sizes) |exact_size| {
514 prng.seed(seed);
515 const result = try benchmarkHashSmallKeysArray(H, exact_size, count, allocator, io);
516 try stdout.print(" {d: >3}B {:5} MiB/s [{x:0<16}]\n", .{
517 exact_size,
518 result.throughput / (1 * MiB),
519 result.hash,
520 });
521 try stdout.flush();
522 }
523 try stdout.print(" array ptr: \n", .{});
524 inline for (sizes) |exact_size| {
525 prng.seed(seed);
526 const result = try benchmarkHashSmallKeysArrayPtr(H, exact_size, count, allocator, io);
527 try stdout.print(" {d: >3}B {:5} MiB/s [{x:0<16}]\n", .{
528 exact_size,
529 result.throughput / (1 * MiB),
530 result.hash,
531 });
532 try stdout.flush();
533 }
534 }
535 }
536 }
537 }
538 }
539 }
540}