sketch_hll_packed_vs_hll8_bench.nx source
↩ module page · 89 lines · 2493 B
1// sketch_hll_packed_vs_hll8_bench.nx -- 6-bit register memory bench.
2//
3// CLAIM TO VALIDATE:
4// HLL_packed uses 6-bit registers (rho values cap at 63, more than
5// enough for cardinalities up to 2^63). 6/8 = 25% memory reduction
6// vs HLL_8. No exception table needed -- 6 bits suffices unlike
7// HLL_4's 4 bits. Cleaner trade-off than HLL_4 (no exception path).
8//
9// WORKLOAD:
10// Stream 10000 distinct keys at lg_k=10 into both.
11//
12// MEMORY:
13// HLL_8 (lg_k=10): 1024 bytes regs + 32 header = 1056 B
14// HLL_packed (lg_k=10): ceil(1024 * 6 / 8) = 768 bytes regs + 40 header = 808 B
15// Reduction: ~23%.
16
17import "syscalls.nx"
18import "sketch_hll.nx"
19import "sketch_hll_packed.nx"
20import "sketch_comparator.nx"
21import "sketch_types.nx"
22
23func iabs_p(x: i64) -> i64 {
24 if x < 0 { return -x }
25 return x
26}
27
28func write_bp(buf: *u8, value: i64) -> i64 {
29 var i: i64 = 0
30 var v: i64 = value
31 while i < 8 {
32 buf[i] = (v & 0xFF) as u8
33 v = v >> 8
34 i = i + 1
35 }
36 return 0
37}
38
39func main() -> i64 {
40 let lg_k: i64 = 10
41 let n: i64 = 10000
42 let seed: i64 = 42
43
44 let h8: *Hll = nx_hll_alloc(lg_k, seed)
45 let h6: *Hll6 = nx_hll6_alloc(lg_k, seed)
46 if h8 == (0 as *Hll) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
47 if h6 == (0 as *Hll6) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
48
49 let key_raw: *u8 = sys_mmap(8)
50 let key: *u8 = key_raw
51
52 var i: i64 = 0
53 while i < n {
54 write_bp(key, i + 6000000)
55 nx_hll_add(h8, key, 8)
56 nx_hll6_add(h6, key, 8)
57 i = i + 1
58 }
59
60 let h8_est: i64 = nx_hll_estimate(h8)
61 let h6_est: i64 = nx_hll6_estimate(h6)
62
63 // ---- Both within HLL 3-sigma band ----
64 if iabs_p(h8_est - n) > (n * 15) / 100 {
65 return __syscall(93, 10, 0, 0, 0, 0, 0)
66 }
67 if iabs_p(h6_est - n) > (n * 15) / 100 {
68 return __syscall(93, 11, 0, 0, 0, 0, 0)
69 }
70
71 // ---- MEMORY axis: HLL_packed < HLL_8 ----
72 let h8_bytes: i64 = h8.m + 32
73 let h6_bytes: i64 = nx_hll6_memory_bytes(h6)
74 let mem: *ComparisonResult = nx_cmp_memory(h6_bytes, h8_bytes, 10000)
75
76 if mem.verdict != NX_CMP_VERDICT_BEATS {
77 return __syscall(93, 20, 0, 0, 0, 0, 0)
78 }
79 if mem.delta_ppm < 150000 { // >=15% memory reduction
80 return __syscall(93, 21, 0, 0, 0, 0, 0)
81 }
82
83 // ---- Estimates close to each other ----
84 if iabs_p(h8_est - h6_est) > (n * 8) / 100 {
85 return __syscall(93, 30, 0, 0, 0, 0, 0)
86 }
87
88 return 0
89}