forked from hexops/fastfilter
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbenchmark.zig
179 lines (162 loc) · 8.1 KB
/
benchmark.zig
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
// zig run -O ReleaseFast src/benchmark.zig
const std = @import("std");
const time = std.time;
const Timer = time.Timer;
const xorfilter = @import("main.zig");
const MeasuredAllocator = @import("MeasuredAllocator.zig");
fn formatTime(writer: anytype, comptime spec: []const u8, start: u64, end: u64, division: usize) !void {
const ns = @as(f64, @floatFromInt((end - start) / division));
if (ns <= time.ns_per_ms) {
try std.fmt.format(writer, spec, .{ ns, "ns " });
return;
}
if (ns <= time.ns_per_s) {
try std.fmt.format(writer, spec, .{ ns / @as(f64, @floatFromInt(time.ns_per_ms)), "ms " });
return;
}
if (ns <= time.ns_per_min) {
try std.fmt.format(writer, spec, .{ ns / @as(f64, @floatFromInt(time.ns_per_s)), "s " });
return;
}
try std.fmt.format(writer, spec, .{ ns / @as(f64, @floatFromInt(time.ns_per_min)), "min" });
return;
}
fn formatBytes(writer: anytype, comptime spec: []const u8, bytes: u64) !void {
const kib = 1024;
const mib = 1024 * kib;
const gib = 1024 * mib;
if (bytes < kib) {
try std.fmt.format(writer, spec, .{ bytes, "B " });
}
if (bytes < mib) {
try std.fmt.format(writer, spec, .{ bytes / kib, "KiB" });
return;
}
if (bytes < gib) {
try std.fmt.format(writer, spec, .{ bytes / mib, "MiB" });
return;
}
try std.fmt.format(writer, spec, .{ bytes / gib, "GiB" });
return;
}
fn bench(algorithm: []const u8, Filter: anytype, size: usize, trials: usize) !void {
const allocator = std.heap.page_allocator;
var filterMA = MeasuredAllocator.init(allocator);
const filterAllocator = filterMA.allocator();
var buildMA = MeasuredAllocator.init(allocator);
const buildAllocator = buildMA.allocator();
const stdout = std.io.getStdOut().writer();
var timer = try Timer.start();
// Initialize filter.
var filter = try Filter.init(filterAllocator, size);
defer filter.deinit(allocator);
// Generate keys.
var keys = try allocator.alloc(u64, size);
defer allocator.free(keys);
for (keys, 0..) |_, i| {
keys[i] = i;
}
// Populate filter.
timer.reset();
const populateTimeStart = timer.lap();
try filter.populate(buildAllocator, keys[0..]);
const populateTimeEnd = timer.read();
// Perform random matches.
var random_matches: u64 = 0;
var i: u64 = 0;
var rng = std.rand.DefaultPrng.init(0);
const random = rng.random();
timer.reset();
const randomMatchesTimeStart = timer.lap();
while (i < trials) : (i += 1) {
const random_key: u64 = random.uintAtMost(u64, std.math.maxInt(u64));
if (filter.contain(random_key)) {
if (random_key >= keys.len) {
random_matches += 1;
}
}
}
const randomMatchesTimeEnd = timer.read();
const fpp = @as(f64, @floatFromInt(random_matches)) * 1.0 / @as(f64, @floatFromInt(trials));
const bitsPerEntry = @as(f64, @floatFromInt(filter.sizeInBytes())) * 8.0 / @as(f64, @floatFromInt(size));
const filterBitsPerEntry = @as(f64, @floatFromInt(filterMA.state.peak_memory_usage_bytes)) * 8.0 / @as(f64, @floatFromInt(size));
if (!std.math.approxEqAbs(f64, filterBitsPerEntry, bitsPerEntry, 0.001)) {
@panic("sizeInBytes reporting wrong numbers?");
}
try stdout.print("| {s: <12} ", .{algorithm});
try stdout.print("| {: <10} ", .{keys.len});
try stdout.print("| ", .{});
try formatTime(stdout, "{d: >7.1}{s}", populateTimeStart, populateTimeEnd, 1);
try stdout.print(" | ", .{});
try formatTime(stdout, "{d: >8.1}{s}", randomMatchesTimeStart, randomMatchesTimeEnd, trials);
try stdout.print(" | {d: >12} ", .{fpp});
try stdout.print("| {d: >14.2} ", .{bitsPerEntry});
try stdout.print("| ", .{});
try formatBytes(stdout, "{: >9} {s}", buildMA.state.peak_memory_usage_bytes);
try formatBytes(stdout, " | {: >8} {s}", filterMA.state.peak_memory_usage_bytes);
try stdout.print(" |\n", .{});
}
fn usage() void {
std.log.warn(
\\benchmark [options]
\\
\\Options:
\\ --num-trials [int=10000000] number of trials / containment checks to perform
\\ --help
\\
, .{});
}
pub fn main() !void {
var buffer: [1024]u8 = undefined;
var fixed = std.heap.FixedBufferAllocator.init(buffer[0..]);
const args = try std.process.argsAlloc(fixed.allocator());
var num_trials: usize = 100_000_000;
var i: usize = 1;
while (i < args.len) : (i += 1) {
if (std.mem.eql(u8, args[i], "--num-trials")) {
i += 1;
if (i == args.len) {
usage();
std.process.exit(1);
}
num_trials = try std.fmt.parseUnsigned(usize, args[i], 10);
}
}
const stdout = std.io.getStdOut().writer();
try stdout.print("| Algorithm | # of keys | populate | contains(k) | false+ prob. | bits per entry | peak populate | filter total |\n", .{});
try stdout.print("|--------------|------------|------------|-------------|--------------|----------------|---------------|--------------|\n", .{});
try bench("binaryfuse8", xorfilter.BinaryFuse(u8), 1_000_000, num_trials);
try bench("binaryfuse16", xorfilter.BinaryFuse(u16), 1_000_000, num_trials);
try bench("binaryfuse32", xorfilter.BinaryFuse(u32), 1_000_000, num_trials);
try bench("xor2", xorfilter.Xor(u2), 1_000_000, num_trials);
try bench("xor4", xorfilter.Xor(u4), 1_000_000, num_trials);
try bench("xor8", xorfilter.Xor(u8), 1_000_000, num_trials);
try bench("xor16", xorfilter.Xor(u16), 1_000_000, num_trials);
try bench("xor32", xorfilter.Xor(u32), 1_000_000, num_trials);
try stdout.print("| | | | | | | | |\n", .{});
try bench("binaryfuse8", xorfilter.BinaryFuse(u8), 10_000_000, num_trials / 10);
try bench("binaryfuse16", xorfilter.BinaryFuse(u16), 10_000_000, num_trials / 10);
try bench("binaryfuse32", xorfilter.BinaryFuse(u32), 10_000_000, num_trials / 10);
try bench("xor2", xorfilter.Xor(u2), 10_000_000, num_trials / 10);
try bench("xor4", xorfilter.Xor(u4), 10_000_000, num_trials / 10);
try bench("xor8", xorfilter.Xor(u8), 10_000_000, num_trials / 10);
try bench("xor16", xorfilter.Xor(u16), 10_000_000, num_trials / 10);
try bench("xor32", xorfilter.Xor(u32), 10_000_000, num_trials / 10);
try stdout.print("| | | | | | | | |\n", .{});
try bench("binaryfuse8", xorfilter.BinaryFuse(u8), 100_000_000, num_trials / 100);
try bench("binaryfuse16", xorfilter.BinaryFuse(u16), 100_000_000, num_trials / 100);
try bench("binaryfuse32", xorfilter.BinaryFuse(u32), 100_000_000, num_trials / 100);
try bench("xor2", xorfilter.Xor(u2), 100_000_000, num_trials / 100);
try bench("xor4", xorfilter.Xor(u4), 100_000_000, num_trials / 100);
try bench("xor8", xorfilter.Xor(u8), 100_000_000, num_trials / 100);
try bench("xor16", xorfilter.Xor(u16), 100_000_000, num_trials / 100);
try bench("xor32", xorfilter.Xor(u32), 100_000_000, num_trials / 100);
try stdout.print("| | | | | | | | |\n", .{});
try stdout.print("\n", .{});
try stdout.print("Legend:\n\n", .{});
try stdout.print("* **contains(k)**: The time taken to check if a key is in the filter\n", .{});
try stdout.print("* **false+ prob.**: False positive probability, the probability that a containment check will erroneously return true for a key that has not actually been added to the filter.\n", .{});
try stdout.print("* **bits per entry**: The amount of memory in bits the filter uses to store a single entry.\n", .{});
try stdout.print("* **peak populate**: Amount of memory consumed during filter population, excluding keys themselves (8 bytes * num_keys.)\n", .{});
try stdout.print("* **filter total**: Amount of memory consumed for filter itself in total (bits per entry * entries.)\n", .{});
}