benchmark dashboard · Apple M4

Top-K Extreme — Streaming Selection

Three C++ primitives — async-membrane, sample-filter, radix-select — covering K from 100 to 1M. 23x over std::priority_queue at K=1M. Single-threaded, adversarially verified.

→ GitHub Repo README Article
Best small-K
2,084 Mops/s
Best large-K
945 Mops/s
Headline
23x vs stdlib
Correctness
100% probes
§1 Overall Profile

Performance Radar — three primitives vs stdlib baselines

Five normalized axes covering the dimensions that distinguish streaming selection primitives. Each approach has a different sweet spot; there is no single winner across all K regimes.

§2 Throughput by K

Throughput across K — 5M uniform random uint64

Grouped bar chart showing measured throughput (Mops/s) for each primitive at five K values from 100 to 1M. Higher is better. All runs on Apple M4, single-threaded, uniform random input.

ApproachK=100K=1KK=10KK=100KK=1M
std::priority_queue1,6351,54563214517
std::nth_element231222280266264
async-membrane ★2,0842,0831,02526915
sample-filter ★1,5101,1191,211613225
radix-select ★1,0109091,125945397
§3 Scaling Curve

Scaling curve — how each primitive degrades with K

Log-log line chart showing throughput decay as K increases. Flat curves indicate good scaling; steep drop-offs reveal regime boundaries. std::nth_element is flat but slow; async-membrane dominates small K but collapses at large K.

§4 Speedup vs stdlib

Speedup over std::priority_queue — per-row champion

For each K, we take the best of our three primitives and divide by std::priority_queue. The speedup grows dramatically at large K where the heap degrades.

§5 Regime Map

Four primitives, three regimes

Each primitive owns a K regime. The fourth card documents the nine cross-field approaches that were searched and discarded during adversarial verification.

🔥

async-membrane

Threshold + double-buffer — extreme value rejection
  • Hot path: 1 threshold compare, reject >99.9% of events.
  • Reject rate: near-perfect at small K; amortized flush via nth_element.
  • Best regime: K ≤ 1K — 2,084 Mops/s at K=100.
  • Weakness: collapses when K approaches N (threshold loses selectivity).
📊

sample-filter

Floyd-Rivest 1975 — sample-then-filter
  • Approach: draw 16K sample, find approximate pivot, single-pass filter.
  • Single pass: touches each element once after sampling.
  • Best regime: K = 10K — 1,211 Mops/s, balanced speed/accuracy.
  • Weakness: sample quality degrades at extreme K/N ratios.
🎯

radix-select

Radix partition — 256 L1-resident buckets
  • Approach: 4-way histogram over 8-bit digits, top-down narrowing.
  • Complexity: O(N) with small constant; cache-friendly bucket fits in L1.
  • Best regime: K ≥ 100K — 945 Mops/s at K=100K, 397 at K=1M.
  • Headline: 23x over std::priority_queue at K=1M.
🔍

Searched & discarded

Nine fields, zero wins — cross-field falsification
  • Tropical algebra: no selection primitive found.
  • Random matrix theory: eigenvalue methods too expensive.
  • Coding theory: no practical decoding advantage.
  • HDC / topology / AIT: theoretical interest, zero throughput wins.
§6 Live Data

Paste your bench output

Run ./build/bench --mode sweep --n 5000000 and paste the output below. The dashboard re-renders with your measured numbers overlaid against the baseline. Everything runs client-side.

Recognised lines: our-async-membrane ... X Mops/s, our-sample-filter ... X Mops/s, our-radix-select ... X Mops/s.