sketch_hll_vs_materialized_set_bench.nx source
↩ module page · 117 lines · 3993 B
1// sketch_hll_vs_materialized_set_bench.nx -- STRUCTURAL class comparison.
2//
3// HONEST SCOPE (do not overclaim):
4// This bench proves HLL's memory is N-INDEPENDENT vs a naive O(N)
5// i64 array, which is the algorithmic-class baseline that any
6// "store every input then dedupe" approach must pay. Do NOT read
7// this as "beats Mathematica 100x" -- we never actually run
8// Mathematica here. For real head-to-head numbers see
9// bench_python_vs_substrate_cardinality.sh which actually invokes
10// Python's set() and measures sys.getsizeof.
11//
12// This bench remains useful as a STRUCTURAL gate: HLL's allocation
13// does NOT grow with N, which is the bits-up property that lets the
14// substrate run unboundedly on RAM-constrained devices.
15//
16// SUBSTRATE: HLL lg_k=12 uses 4128 bytes regardless of N.
17//
18// HARD-WIN GATE:
19// At N=100k:
20// HLL memory <= 5 KB
21// Materialized memory >= 500 KB (>=100x larger)
22// HLL cardinality estimate within 5% of truth=100000
23// Memory ratio >= 100x → structural EXCEED vs the standard
24// incumbent approach.
25//
26// Note: the bench DOES materialize 100k keys in a deduped array to
27// emulate the incumbent storage cost. That's not 'cheating' -- it's
28// the EXACT cost any non-streaming tool must pay.
29
30import "syscalls.nx"
31import "sketch_hll.nx"
32import "sketch_comparator.nx"
33import "sketch_types.nx"
34
35func iabs_m(x: i64) -> i64 {
36 if x < 0 { return -x }
37 return x
38}
39
40func write_bm(buf: *u8, value: i64) -> i64 {
41 var i: i64 = 0
42 var v: i64 = value
43 while i < 8 {
44 buf[i] = (v & 0xFF) as u8
45 v = v >> 8
46 i = i + 1
47 }
48 return 0
49}
50
51func main() -> i64 {
52 let n: i64 = 100000
53
54 // ---- Substrate: streaming HLL lg_k=12 (4096 regs = 4128 B) ----
55 let hll: *Hll = nx_hll_alloc(12, 42)
56 if hll == (0 as *Hll) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
57
58 // ---- Incumbent baseline: materialize 100k 8-byte keys ----
59 // (Represents Pandas/NumPy/Mathematica/R/SQL standard approach.)
60 let mat_keys_raw: *u8 = sys_mmap(n * 8)
61 let mat_keys: *i64 = mat_keys_raw as *i64
62
63 let key_buf_raw: *u8 = sys_mmap(8)
64 let key_buf: *u8 = key_buf_raw
65
66 var i: i64 = 0
67 while i < n {
68 let id: i64 = i + 9000000
69 write_bm(key_buf, id)
70 nx_hll_add(hll, key_buf, 8)
71 mat_keys[i] = id
72 i = i + 1
73 }
74
75 let hll_est: i64 = nx_hll_estimate(hll)
76
77 // ---- HLL accuracy: within 5% of truth ----
78 if iabs_m(hll_est - n) > (n * 5) / 100 {
79 return __syscall(93, 10, 0, 0, 0, 0, 0)
80 }
81
82 // ---- MEMORY axis ----
83 let hll_bytes: i64 = hll.m + 32 // 4096 + 32 = 4128
84 // Materialized cost: raw key array. Typical incumbents add 2.5x
85 // hash-table overhead. Conservative model: just the key array.
86 let mat_bytes: i64 = n * 8 // 800,000
87
88 let mem: *ComparisonResult = nx_cmp_memory(hll_bytes, mat_bytes, 100000)
89
90 // ---- HARD-WIN GATE ----
91 if mem.verdict != NX_CMP_VERDICT_BEATS {
92 return __syscall(93, 20, 0, 0, 0, 0, 0)
93 }
94 // Require ratio >= 100x. delta_ppm = (mat - hll) * 1e6 / mat
95 // = (800000 - 4128) * 1e6 / 800000 = 994,840 ppm = 99.5%
96 if mem.delta_ppm < 990000 {
97 return __syscall(93, 21, 0, 0, 0, 0, 0)
98 }
99
100 // ---- Sanity: 100x ratio confirmed in absolute terms ----
101 if mat_bytes < hll_bytes * 100 {
102 return __syscall(93, 22, 0, 0, 0, 0, 0)
103 }
104
105 // ---- Structural property: HLL memory is N-INDEPENDENT ----
106 // Verify by allocating ANOTHER HLL at lg_k=12 and confirming the
107 // memory is identical regardless of how many inserts we'd do.
108 let hll2: *Hll = nx_hll_alloc(12, 999)
109 if hll2 == (0 as *Hll) { return __syscall(93, 30, 0, 0, 0, 0, 0) }
110 if hll2.m != hll.m {
111 return __syscall(93, 31, 0, 0, 0, 0, 0)
112 }
113 // hll has consumed 100k inserts; hll2 is empty; same memory.
114 // This proves: HLL memory is FIXED at alloc time, not N-dependent.
115
116 return 0
117}