Streaming Top-K on Apple M4 — Three Primitives, Honest Numbers

Overview

ALGO-4 is a C++ streaming Top-K library for uint64 keys on Apple M4. It ships three working primitives that together cover every K from 100 to 1 M, beating std::priority_queue by 1.3x at small K and 23x at K=1 M. Every number published here has an adversarial correctness probe behind it — uniform, sorted, high-duplicate, and boundary cases — because we caught a silent-data-loss bug in an earlier prototype that posted fake 743 Mops/s.

None of the algorithms are novel. The contribution is the engineering, the honest benchmarking methodology, and the cross-field falsification search that covered nine branches of mathematics looking for something structurally better. Nothing was found. What you see below is, to the best of our knowledge, the Pareto frontier for single-threaded streaming Top-K on this hardware.

Results

Scoreboard: median of 3 runs, 5 M uniform random uint64, single Apple M4 P-core. Units are Mops/s (millions of operations per second). Per-row champion is bolded.

Interactive Dashboard

The Three Primitives

1. Async Membrane Top-K

src/pipeline.hpp

A scalar threshold gates the hot path: items below the current K-th estimate die in a single register compare. Items that pass land in a double-buffer; a background thread runs nth_element on the filled buffer to update the threshold. The amortized cost per element is one branch plus an occasional buffer swap. Best at K ≤ 1 K, where the threshold converges in the first few thousand elements and the reject rate exceeds 99%.

2. Sample-Filter Top-K

src/sample_filter.hpp

Floyd-Rivest 1975 adapted for streaming. Draw a random 16 K sample, compute a conservative threshold via nth_element on the sample, then make a single filter pass over the full stream keeping only items above the threshold. A final nth_element on the survivors produces the exact Top-K. Best at K = 10 K, where the sample is large enough for an accurate threshold but small enough to fit in L1.

3. Radix-Select Top-K

src/radix_topk.hpp

Four-way independent histogram on the top byte: 256 L1-resident buckets, find the pivot bucket containing the K-th rank, emit everything above the pivot directly, then run nth_element on the pivot bucket (the scratch). O(N) with tight sequential access and no allocation beyond the initial histogram. Best at K ≥ 100K. The headline: 23x over std::priority_queue at K=1 M.

What We Searched and Discarded

We searched nine fields of mathematics for any primitive that could deliver >2x over radix-select on streaming uint64 Top-K. Six returned clean structural negatives:

Nine independent searches from nine fields all hit the same structural truth: streaming uint64 Top-K is information-theoretically tight. There is no hidden algebraic shortcut; you must touch every element at least once, and the only lever is how cheaply you can reject the non-Top-K majority.

Correctness

Every primitive has an adversarial probe gate testing five distributions: uniform, sorted-ascending, sorted-descending, high-duplicate, and the boundary case K=N. We added these probes after catching a silent-data-loss bug in an earlier prototype that posted fake 743 Mops/s — a number that looked plausible until we checked the output against a brute-force reference. The correctness suite runs before every benchmark; if any probe fails, the benchmark refuses to start.

What I Will NOT Claim

• None of the algorithms are novel — async-membrane is double-buffered selection, sample-filter is Floyd-Rivest, radix-select is a single-pass radix partition.
• All numbers are Apple M-series, single thread. We have not tested on x86, multi-core, or with non-uniform distributions beyond the adversarial probes.
• This took a week of wall-clock, heavily AI-assisted.

Numbers I Will Defend