code wiki / (root) / sketch_hll_vs_materialized_set_bench.nx

sketch_hll_vs_materialized_set_bench.nx

buildroot/runtime/sketch_hll_vs_materialized_set_bench.nx

3993 B117 linesdepth 6pulls 12 transitivereach 0 importersview sourcekind benchtopic sketch
docsdependenciesstructsconstsfunctions

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

syscalls.nx sketch_hll.nx sketch_comparator.nx sketch_types.nx sketch_hll_vs_materialized_set

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

main nx_hll_alloc write_bm nx_hll_add murmur3_32 mm_load_u32_le mm_rotl32 nx_clz32 nx_bits_clz32 nx_hll_estimate nx_hll_pow2_neg_q32 nx_hll_alpha_m_sq_q64 nx_hll_bias_table_n nx_hll_bias_table_get nx_hll_bias_lgk4 nx_hll_bias_lgk5 nx_hll_bias_lgk6 nx_hll_bias_lgk7 nx_hll_bias_lgk8 nx_hll_bias_lgk9 nx_hll_bias_lgk10 nx_hll_log2_ppm nx_hll_bias_correct nx_hll_bias_table_n ↻ nx_hll_bias_table_get ↻ nx_mulshl_div_i64 nx_i128_alloc nx_i128_mul_i64 nx_i128_mul_u64 nx_i128_neg nx_i128_shl nx_i128_div_i64 nx_i128_is_neg nx_i128_neg ↻ nx_i128_udiv_u64 iabs_m nx_cmp_memory

structs

none

consts

none

functions

35func iabs_m(x: i64) -> i64
called by 1: main
40func write_bm(buf: *u8, value: i64) -> i64
called by 1: main
51func main() -> i64