CAFS: A Cache-Aware Frequency Sort for Low-Cardinality Integer Data on x86-64
Vasiliy S. Shlyk · 2026
Read CAFS: A Cache-Aware Frequency Sort for Low-Cardinality Integer Data on x86-64 by Vasiliy S. Shlyk (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25040.txt.
Introduction
Vasiliy S. Shlyk presents CAFS, a sort that exploits low cardinality on x86-64 with AVX2. In OLAP engines, columns after a group-by often have far fewer distinct values than rows. CAFS combines a cache-line-sized SIMD bucket, a Chao1 estimator over 1024 strided samples, and a dispatcher with a spill safety guard. Against baselines, CAFS runs 1.7 to 3.1 times pdqsort in the low-cardinality band. It also beats IPS4o and vqsort there.
Catalog record
| CREATOR | Vasiliy S. Shlyk |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57160 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.25040
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
CAFS: A Cache-Aware Frequency Sort for Low-Cardinality Integer Data on x86-64 Vasiliy S. Shlyk Abstract Integer sorts in OLAP engines often run on columns whose cardinality K K is much smaller than the array length N N . After a group-by stage the intermediate key column has K K bounded by the number of distinct group keys, and even a column-store scan typically operates on dictionary-encoded categorical fields where K K never exceeds a few thousand. A comparison sort on such a column still pays Θ ( N log N ) \Theta(N\log N) comparisons, and a radix sort still pays Θ ( N ⋅ B / b ) \Theta(N\cdot B/b) byte passes, irrespective of K K . This paper describes CAFS, an integer sort that does exploit it on x86-64 with AVX2. The algorithm combines a SIMD bucket sized to one cache line, a Chao1 cardinality estimator over 1024 strided samples (kept in a heap-allocated 40 KB open-addressing table), and an adaptive dispatcher backed by a spill safety guard. The hot loop is branchless and uses AVX2 cmpeq together with movemask and tzcnt to locate the matching lane. We benchmarked CAFS on a full-factorial grid of 58 array sizes N N from 10 3 10^{3} to 3 ⋅ 10 7 3\cdot 10^{7} with dense K K schedules per N N , producing 592770 timed runs against pdqsort, IPS4o, vqsort, ska_sort, and std::sort. In the K ≪ N K\ll N band the throughput is 1.7 to 3.1 × \times that of pdqsort, 1.7 to 3.5 × \times IPS4o, and 1.2 to 2.3 × \times vqsort. The operational crossover against pdqsort is at K ≈ 1.3 ⋅ 10 5 K\approx 1.3\cdot 10^{5} ; against ska_sort, K ≈ 8.14 ⋅ 10 5 K\approx 8.14\cdot 10^{5} ; against vqsort, K ≈ 6.7 ⋅ 10 5 K\approx 6.7\cdot 10^{5} ; and against IPS4o the curves only converge near K = N K=N . Of the five baselines, only vqsort actually overtakes CAFS once the crossover is passed, which makes the vqsort threshold at K ≈ 6.7 ⋅ 10 5 K\approx 6.7\cdot 10^{5} the binding constraint on the operational range of CAFS. 1 Introduction Sorting integer arrays serves as a core primitive in database management systems, OLAP engines, ETL pipelines, and column stores. Many of these workloads sort integer keys whose distinct-value count is small relative to the array length; common examples include status flags, event types, foreign keys into small dimension tables, and dictionary-encoded categorical attributes [ 3 , 20 ] . After a group-by stage, the intermediate key column has K\ll N by construction, and a downstream sort runs on data with a heavy concentration of repeats. Similar patterns recur outside the database setting, for instance whenever a categorical column has been quantized down to a small alphabet. Generic sorts ignore the property entirely. Comparison-based methods have an \Omega(N\log N) lower bound on comparisons regardless of the input distribution [ 13 , 6 ] , and distribution sorts pay \lceil B/b\rceil passes over key bytes (where B is the key width and b the radix digit width), so on 64-bit keys ska_sort [ 19 ] performs eight byte passes whether K is 8 or 10^{6} . On a 10^{7} -element array with K=200 a comparison sort issues about 2.3\cdot 10^{8} comparisons, while the count-and-emit cost would be near N+K\log K\approx 10^{7} [ 13 ] , more than 20\times smaller. A single such sort completes in milliseconds, but at typical OLAP query rates of 10^{3} – 10^{4} queries per second per node, the cumulative time spent inside the sort primitive becomes a non-trivial fraction of total CPU consumption. Recent x86-64 cores make this gap exploitable in hardware. AVX2 gives 256-bit registers and instructions that compare four 64-bit keys in a single cycle, and BMI1 supplies tzcnt to extract the matching lane in two more cycles [ 12 ] . Writing the hot loop with broadcast, cmpeq, movemask, and tzcnt also removes the conditional branches that would otherwise stall the pipeline by more than a dozen cycles per misprediction [ 12 , 7 ] . The combined effect is a per-element cost of about one SIMD operation on a low-cardinality input, below the rate of any comparison or radix sort we are aware of. We present CAFS (Cache-Aware Frequency Sort). CAFS uses a SIMD bucket on one cache line, a Chao1 cardinality estimator [ 5 ] on a 1024-sample frequency set, and an adaptive dispatcher. The dispatcher routes to a tiny-count branchless path for \hat{K}\leq 8 , a hash-count main path for 8<\hat{K}<N/2 , and a pdqsort [ 17 ] fallback when \hat{K}\cdot 2>N . A spill safety guard bounds the worst-case slowdown (Section 4 ). We evaluate CAFS empirically on a full-factorial (N,K) grid against five baselines and report per-baseline crossover points K^{*} above which CAFS no longer dominates. Our contributions are: • A SIMD bucket layout fitting one cache line, with branchless update via AVX2 cmpeq, movemask, and tzcnt. • An adaptive dispatcher driven by a Chao1 cardinality estimator over 1024 strided samples, with a fixed-size FreqSet on the heap as the backing storage. • A three-branch hybrid (tiny-count for \hat{K}\leq 8 , main hash-count, pdqsort fallback for \hat{K}\cdot 2>N ) with a spill safety guard that caps the worst-case slowdown. • A header-only C++20 implementation for AVX2 on x86-64, with wrappers around pdqsort, IPS4o, vqsort, ska_sort, and std::sort under a unified benchmark driver. • A full-factorial empirical study on a grid of 58 array sizes from 10^{3} to 3\cdot 10^{7} with dense per- N K schedules, with explicit crossover points against each baseline. Section 2 surveys the comparison, distribution, and SIMD sorting families together with the relevant cardinality estimators, and Section 3 fixes the formal model. The algorithm itself appears in Section 4 , with pseudocode for the bucket update, the Chao1 estimator, the dispatcher, and the reconstruction step (the main hot loop is described in prose alongside its RLE behaviour). The implementation is described in Section 5 . Section 6 reports the per-baseline evaluation and the joint applicability map, Section 7 covers limitations and operating-point guidance, and Section 8 concludes. 2 Background and Related Work 2.1 Three families of integer sorts Integer sorts split naturally by their primitive decision step [ 13 , 6 ] . Comparison sorts build the order through x<y and trace paths in a decision tree, which forces \Omega(N\log N) comparisons in the worst and average cases for any input distribution. Distribution sorts read each key directly and place it in the output at an index computed from its value, at a typical cost of O(N\cdot B/b) , where B is the key bit width and b the radix digit width. Hash-count sorts reduce sorting to frequency counting followed by ordered emission of (key, count) pairs. Their total cost decomposes as T(N,K)=T_{\text{count}}(N)+T_{\text{sort}}(K)+T_{\text{emit}}(N) , which collapses to O(N) with a small constant whenever K\ll N [ 13 ] . Table 1 arranges the main competitors along three axes: asymptotic cost, dependence on K , and use of SIMD. Algorithms that ignore K pay their full asymptotic cost on every input. Algorithms that exploit K win at K\ll N , but the classical implementations do not