sketch_hll_vs_materialized_set_bench.nx
buildroot/runtime/sketch_hll_vs_materialized_set_bench.nx
about
sketch_hll_vs_materialized_set_bench.nx -- STRUCTURAL class comparison.
HONEST SCOPE (do not overclaim):
This bench proves HLL's memory is N-INDEPENDENT vs a naive O(N)
i64 array, which is the algorithmic-class baseline that any
"store every input then dedupe" approach must pay. Do NOT read
this as "beats Mathematica 100x" -- we never actually run
Mathematica here. For real head-to-head numbers see
bench_python_vs_substrate_cardinality.sh which actually invokes
Python's set() and measures sys.getsizeof.
This bench remains useful as a STRUCTURAL gate: HLL's allocation
does NOT grow with N, which is the bits-up property that lets the
substrate run unboundedly on RAM-constrained devices.
SUBSTRATE: HLL lg_k=12 uses 4128 bytes regardless of N.
HARD-WIN GATE:
At N=100k:
HLL memory <= 5 KB
Materialized memory >= 500 KB (>=100x larger)
HLL cardinality estimate within 5% of truth=100000
Memory ratio >= 100x → structural EXCEED vs the standard
incumbent approach.
Note: the bench DOES materialize 100k keys in a deduped array to
emulate the incumbent storage cost. That's not 'cheating' -- it's
the EXACT cost any non-streaming tool must pay.
dependencies 4 imports · 0 importers
imports: syscalls.nxsketch_hll.nxsketch_comparator.nxsketch_types.nx
imported by: nobody (leaf or entry point)
call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown
structs
| none |
consts
| none |
functions
| 35 | func iabs_m(x: i64) -> i64 called by 1: main |
| 40 | func write_bm(buf: *u8, value: i64) -> i64 called by 1: main |
| 51 | func main() -> i64 |