CAFS: A Cache-Aware Frequency Sort for Low-Cardinality Integer Data on x86-64 Vasiliy S. Shlyk [email protected]
arXiv:2605.25040v1 [cs.DS] 24 May 2026
May 2026 Abstract Integer sorts in OLAP engines often run on columns whose cardinality K is much smaller than the array length N . After a group-by stage the intermediate key column has K bounded by the number of distinct group keys, and even a column-store scan typically operates on dictionary-encoded categorical fields where K never exceeds a few thousand. A comparison sort on such a column still pays Θ(N log N ) comparisons, and a radix sort still pays Θ(N · B/b) byte passes, irrespective of 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 from 103 to 3 · 107 with dense K schedules per N , producing 592770 timed runs against pdqsort, IPS4o, vqsort, ska_sort, and std::sort. In the K ≪ N band the throughput is 1.7 to 3.1× that of pdqsort, 1.7 to 3.5× IPS4o, and 1.2 to 2.3× vqsort. The operational crossover against pdqsort is at K ≈ 1.3 · 105 ; against ska_sort, K ≈ 8.14 · 105 ; against vqsort, K ≈ 6.7 · 105 ; and against IPS4o the curves only converge near 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 · 105 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 ≪ 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 Ω(N log N ) lower bound on comparisons regardless of the input distribution [6, 13], and distribution sorts pay ⌈B/b⌉ 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 106 . On a 107 -element array with K = 200 a comparison sort issues about 2.3 · 108 comparisons, while the count-and-emit 1
cost would be near N + K log K ≈ 107 [13], more than 20× smaller. A single such sort completes in milliseconds, but at typical OLAP query rates of 103 –104 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 [7, 12]. 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 K̂ ≤ 8, a hash-count main path for 8 < K̂ < N/2, and a pdqsort [17] fallback when K̂ · 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 K̂ ≤ 8, main hash-count, pdqsort fallback for K̂ · 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 103 to 3 · 107 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 [6, 13]. Comparison sorts build the order through x < y and trace paths in a decision tree, which forces Ω(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 · 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
2
cost decomposes as T (N, K) = Tcount (N ) + Tsort (K) + Temit (N ), which collapses to O(N ) with a small constant whenever K ≪ 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 ≪ N , but the classical implementations do not vectorize the hot loop and lose to comparison and radix sorts on K ≈ N because of the high constant in the count step. CAFS exploits K and also vectorizes the hot loop, with a deliberate fallback to a strong comparison sort on high-K inputs. Table 1: Integer sort families compared on three axes.
Algorithm
Cost
std::sort (introsort) [15] pdqsort [17] IPS4o (sequential) [2] ska_sort (LSD radix) [19] vqsort (Highway) [22] generic hash-count CAFS (this paper)
O(N log N ) O(N log N ) O(N log N ) O(N · B/b) O(N log N ) O(N + K log K) O(N + K log K)
Uses K?
SIMD
no no no no no yes yes
no partial no no AVX2/AVX-512 no AVX2
Extra memory O(log N ) O(log N ) O(log N ) (in-place) O(N + 2b ) O(log N ) O(K) O(K)
2.2 Comparison sorts The C++ standard library ships introsort [15] as std::sort, which combines quicksort with a heapsort safeguard at recursion depth 2 log2 N and an insertion-sort cutoff under 16 elements. Pattern-defeating quicksort (pdqsort) [17] replaces the classical Lomuto partition with a branchless Hoare-style partition that eliminates the conditional store; pdqsort additionally detects alreadysorted, reverse-sorted, and almost-sorted prefixes and falls back to a different algorithm on adversarial inputs. On random inputs the branchless partition removes the dominant cost (a mispredicted comparison stalls a modern x86 pipeline for more than a dozen cycles [7, 12]) and yields a 1.5 to 3 times speedup over introsort. IPS4o [2] replaces the binary partition with an in-place k-way super-scalar samplesort whose classifier is a balanced binary tree built from a sampled splitter set; the predictable memory access pattern lets it outrun pdqsort by 1.2 to 1.5 times on random 64-bit integers in single-threaded mode. The branchless partitions in both pdqsort and IPS4o derive from BlockQuicksort [8]. None of the three algorithms exploits low K.
2.3 Distribution sorts Counting sort needs O(N + R) memory and time, which is infeasible for R = 264 . Radix sorts decompose the key into b-bit digits and apply counting sort per digit [13]. The least-significantdigit (LSD) variant scans from low to high in ⌈B/b⌉ passes. The most-significant-digit (MSD) variant sorts the high digits first and recurses on the resulting buckets, which permits early exit on short buckets and admits an in-place implementation. The ska_sort implementation [19] uses an in-place American-flag MSD radix with type-specialized inner loops, signed-integer handling, and an insertion-sort cleanup on short buckets; on 64-bit keys this amounts to eight byte passes of bucket rearrangement that touch every element on each pass, with the per-pass move count of order N and the constant depending on the bucket distribution. Subsequent work in this family includes the AVX-friendly radix sorts of Satish et al. [18] for CPUs and GPUs with vectorized digit extraction, and the SIMD-plus-cache-friendly merge sort of Inoue and Taura [11] for column-store workloads. The cost of every algorithm in this family scales with the key width B and is independent of K. 3
2.4 SIMD sorts SIMD-aware sorts push the hot loop onto vector lanes without adapting to K. Among earlier proposals, Bramas [4] built a hybrid quicksort on AVX-512 with sorting networks at the leaves, and Lemire et al. [14] showed that SIMD compression and decompression beat scalar baselines by an order of magnitude on integer streams, which already shows that vector lanes do useful work in sort-related kernels. The current strongest entry is vqsort [22], which drives a recursive partition through AVX2 or AVX-512 sorting networks on YMM/ZMM registers and merges sorted halves with masked stores. Its hot loop runs near 0.5 to 1 cycle per element against 4 to 5 cycles for scalar pdqsort, and on 64-bit random inputs it outpaces prior comparison and radix sorts by roughly a factor of two.
2.5 Cardinality estimation The Chao1 estimator [5] infers the unseen part of a population from singletons and doubletons in a sample. The original form is K̂ = u + f12 /(2f2 ) and the standard bias-corrected variant is K̂ = u+f1 (f1 −1)/(2(f2 +1)). Both are undefined or unstable when f2 = 0, so the implementation in this paper uses the simpler smoothed variant K̂Chao1 = u +
f12 , 2 (f2 + 1)
where u is the count of distinct values seen in the sample, f1 is the count of values seen exactly once, and f2 is the count of values seen exactly twice. The f2 + 1 keeps the formula welldefined when f2 = 0, and we use f12 in the numerator rather than the canonical f1 (f1 − 1) for implementation simplicity. The two expressions differ by f1 /(2(f2 + 1)), which can reach the order of f1 /2 when f2 is small, but in that saturated regime the dispatcher already routes to the high-entropy fallback through the K̂ · 2 > N guard, so the choice does not affect dispatching √ behaviour. HyperLogLog [9] reaches relative standard error around 1.04/ m with m registers, which is asymptotically tight but expensive at the fixed memory footprint we target (under 4 KB for the estimator). CAFS uses Chao1 because the algorithm needs only an order-of-magnitude estimate of K within microseconds, which a 1024-sample Chao1 on a 4096-slot table delivers.
2.6 Cache and SIMD context Two earlier results inform the cache and SIMD analysis below. Frigo et al. [10] formalized cache-oblivious algorithms that match the optimal cache behaviour up to constants. Drepper [7] catalogued the relevant x86 memory-hierarchy effects, namely branch-misprediction cost and the L1, L2, L3, and DRAM access latencies that govern the constants in our hot-loop analysis. Cycle counts for individual AVX2 and BMI1 instructions used in the bucket update are taken from the Intel Optimization Reference Manual [12].
3 Problem Setting 3.1 Inputs and goal Given an array X = (x1 , . . . , xN ) of 64-bit unsigned integers from a value set V ⊆ Z≥0 , the task is to compute a permutation π with xπ(i) ≤ xπ(i+1) for 1 ≤ i < N . Stability is not required: equal integer keys are indistinguishable. We write K = |{xi : 1 ≤ i ≤ N }| for the cardinality, 2 ≤ K ≤ N , and restrict attention to the regime K ≪ N that is typical of analytical workloads [3, 20].
4
3.2 Information-theoretic gap The Shannon entropy per key under a uniform distribution over K values is H = log2 K bits, so a 64-bit integer array with K unique values uses only H of its 64 bits per element. The gap ∆ = 64 − H is information capacity unused by the data but still loaded into registers and cache on every access. Neither comparison nor distribution sorts can recover this gap. A comparison sort issues log2 N comparisons per element and a radix sort visits ⌈B/b⌉ digits per key whatever H may be. With a hash function of adequate spread and a table large enough to keep buckets sparse, a hash-count scheme drops the per-element cost to O(H) comparisons, scaling with the information content rather than with the key width or the array length.
3.3 Cost model A hash-count sort decomposes into three components: T (N, K) = Tcount (N ) + Tsort (K) + Temit (N ).
(1)
For K ≪ N the middle term Tsort (K) = O(K log K) is negligible, and under a good count primitive the total cost approaches T (N, K) ≈ 2N . For K ≈ N the middle term rises to O(N log N ), the count overhead remains, and the comparison family regains the asymptotic advantage. Equation (1) thus covers the dominance and fallback regimes of CAFS with a single expression.
3.4 Entropy bin We aggregate measurements by entropy bin Hbin = ⌊log2 K⌋.
(2)
Bin 1 covers K ∈ [2, 4), bin 2 covers [4, 8), up to bin 24 for [223 , 224 ). Bin index is the information density of the input in bits per key. Aggregation by Hbin turns the (N, K) scatter into a heatmap and absorbs the per-bin noise from the exact K value within the bin.
3.5 Speedup, win rate, and crossover For a baseline X at point (N, K), the speedup is speedupX (N, K) =
tX (N, K) . tCAFS (N, K)
(3)
A value above 1 means CAFS wins. Inside an entropy bin we report the arithmetic mean (avg), minimum (min), maximum (max), and the win rate, defined as the fraction of points in the bin with speedup > 1. The operational crossover against baseline X is the largest K (at N > 106 ) for which CAFS wins on at least 50% of grid points in the corresponding entropy bin. We use the win rate rather than the bin mean to avoid sensitivity to outliers with extreme speedup. The Pearson correlation between log N and speedup inside the dominance zone indicates whether the lead grows, shrinks, or stays flat with N .
3.6 Methodology The grid covers 58 values of N from 103 to 3 · 107 , stepped in four piecewise-linear bands: 1000 to 50000 (step 2000), 50000 to 1 million (step 50000), 1 million to 10 million (step 1 million), and 10 million to 30 million (step 5 million). For each N the cardinality K is enumerated from 2 to N along a piecewise-coarsening schedule: step 1 below K = 200, step 10 from 200 to 15000, step 500 from 15000 to 105 , and max(5000, K/10) above that, which gives a dense sweep at small 5
K and a roughly geometric sweep once K grows past the L1 working set. Every algorithm is run twice on a fresh copy of the input and we keep the minimum of the two runs to suppress scheduler noise. Correctness is checked against a reference array sorted by std::sort and any point with a mismatch is dropped from aggregation, although CAFS produced no such failure on the grid. Each (N, K) point is tested against five baselines plus CAFS, and together with the rerun rows for low-entropy bins and the per-bin book-keeping rows the resulting CSV holds 592770 measurement rows.
4 The CAFS Algorithm 4.1 Overview and pipeline The algorithmic skeleton is the count-emit pair: count the frequency of each unique value, then emit (key, count) pairs in increasing key order. The hot loop never compares two input values with <; the only equality check it performs is between an input value and a bucket slot. The count step always costs O(N ) at one SIMD operation per element, so when K ≪ N the whole algorithm runs near that rate, whereas at K ≈ N the trailing pair sort dominates and a dedicated comparison engine wins. The pipeline runs in seven stages, drawn in Figure 1. The monotonicity check returns early on already-sorted input through a fast scan that exits at the first inversion (on random input that happens at the second or third element). The sampler then reads 1024 strided samples and feeds a heap-allocated open-addressing frequency set FreqSet of 4096 slots (about 40 KB for 64-bit keys), from which the Chao1 estimator computes K̂, u, f1 , and f2 . On those values the dispatcher selects a branch (Algorithm 3), the selected branch iterates over the input and updates buckets through the SIMD primitive of Section 4.2, reconstruction folds the buckets and the spill into a dense pair array, and a final emit step expands those pairs into the output via std::fill_n. O(N ) trivial: return / std::reverse
O(N log N )
O(N )
fallback (pdqsort)
tiny-count branchless (≤ 8 keys)
O(N log N ) fallback (pdqsort)
±1
input vector<T> N
T*, N
N < 2048
2. Chao1 1. monotonicity check order ∈ {−1, 0, 1} sampler O(N )
O(s), s = 1024
Kest , u
Kest ≤ 8
3. dispatcher O(1)
2Kest > N
else
4. hot loop (RLE + SIMD) O(N )
hash table + spill
5. spill drain O(s log s)
sorted spill
sorted
6. reconstruction (key, count) output (in-place) (radix + fill) O(8K +N )
Figure 1: CAFS pipeline.
The monotonicity check pays O(N ) comparisons with early exit. Sampling and Chao1 add O(s) at s = 1024, under 100 microseconds on a modern x86 core, and the dispatcher itself is a single comparison. The tiny-count branch pays O(N ) with eight branchless adds per element, while the main hot loop pays roughly one SIMD operation per element. Spill drain costs O(|spill| log |spill|) when the spill is non-empty and nothing otherwise. The trailing pair sort runs std::sort if K ′ < 256 and an 8-pass LSD byte radix otherwise.
4.2 The SIMD bucket The bucket is a fixed-capacity record aligned to a 64-byte cache line. For uint64_t the bucket holds four 64-bit keys (32 B), four 32-bit counters (16 B), and 16 B of padding. For int32_t it holds eight keys and eight counters, exposing one AVX2 instruction across all eight lanes. Figure 2 shows the layout. The update(val, inc) operation takes a value and an increment count. On a hit it adds inc to the matching counter, on a miss it claims the first empty slot (the one whose counter 6
keys (4×8 B)
counts (4×4 B)
keys[0]
keys[1]
keys[2]
keys[3]
8B
8B
8B
8B
0
8
16
cnt[0]cnt[1]cnt[2]cnt[3] 4B
24
_pad (4×4 B)
32
4B
36
4B
40
4B
44
(unused = padding)
48
64
Figure 2: Layout of Bucket<uint64_t>: 64 bytes aligned to a cache line.
is zero), and on a fully occupied bucket it returns false so the value is sent to the spill. The 64-bit specialization compiles to five instructions: _mm256_load_si256 pulls four keys into a YMM register, _mm256_set1_epi64x broadcasts the query value across the four lanes, _mm256_cmpeq_epi64 compares them in parallel, _mm256_movemask_pd packs the result into a 4-bit mask, and std::countr_zero (BMI1 tzcnt) returns the index of the matched lane. The data flow is drawn in Figure 3 and the operation is stated in Algorithm 1. With per-instruction latencies on Alder Lake [12] of 1 cycle for vmovdqa from L1, 1 for vpbroadcastq, 1 for vpcmpeqq, 2 for vmovmskpd, 3 for tzcnt, and 1 for the counter add, the critical-path dependency on a hit (vpcmpeqq → vmovmskpd → tzcnt → counter add) sums to 7 cycles, which out-of-order overlap across successive iterations amortizes to roughly 4 to 5 cycles per element. lane 3 [255:192]
lane 2 [191:128]
lane 1 [127: 64]
lane 0 [ 63: 0]
v_keys:
99
7
25
10
← _mm256_load_si256(&keys[0])
v_val:
25
25
25
25
← _mm256_set1_epi64x(25)
cmp:
0...0
0...0
1...1
0...0
bit 3
bit 2
bit 1
bit 0
0
0
1
0
← _mm256_cmpeq_epi64(v_keys, v_val) each lane:
mask:
0x0...0 or 0xF...F
← _mm256_movemask_pd( cmp ) mask = 0b0010 = 2
idx = std::countr_zero(mask) Result :
idx = 1
counts[1] += inc_cnt; return true ([[likely]] branch).
Figure 3: Branchless bucket update through AVX2 instructions.
The bucket does not resolve in-bucket collisions. When a bucket fills, the next miss spills to a side buffer. A Poisson model with capacity 4 and mean fill 0.5 puts the probability of overflow at P (X ≥ 5) ≈ 1.7 · 10−4 , so spills stay rare across the input distributions in our grid (Section 6). The hash function is the multiplicative hash with the inverse golden ratio: (x · φ−1 ) mod 264 h(x) = , φ−1 = 0x9E3779B97F4A7C15, (4) 264−log2 M which compiles into one multiplication and one shift [13]. The choice of hash matters because lowcardinality columns in practice exhibit arithmetic structure (sequential foreign keys, codes from a contiguous range {0, . . . , K −1}, or fixed-step quantized features), and the naive h(x) = x mod M collides catastrophically on such inputs because a linear progression maps to every M -th bucket. Multiplicative hashing distributes a linear progression across the index space pseudo-uniformly and cuts the collision rate by about three orders of magnitude at the same M .
7
Algorithm 1 Branchless bucket update for uint64_t on AVX2. 1: function Update(bucket, val, inc)
keys ← _mm256_load_si256(bucket.keys) q ← _mm256_set1_epi64x(val) 4: eq ← _mm256_cmpeq_epi64(keys, q) 5: m ← _mm256_movemask_pd(cast(eq)) 6: if m ̸= 0 then 7: j ← tzcnt(m) 8: bucket.counts[j] += inc 9: return true 10: end if 11: for j = 0 to CAP − 1 do 12: if bucket.counts[j] = 0 then 13: bucket.keys[j] ← val 14: bucket.counts[j] ← inc 15: return true 16: end if 17: end for 18: return false 19: end function 2: 3:
▷ hit path: 4–5 cycles ▷ cold path: claim empty slot
▷ full bucket, value goes to spill
4.3 Cardinality estimation Before the main path runs, CAFS samples the input at stride max(1, ⌊N/s⌋) with s = 1024, then drops the samples into a heap-allocated open-addressing table FreqSet of 4096 slots (40 KB for 64-bit keys: a 32 KB key array plus an 8 KB counter array). Three statistics fall out: u is the count of occupied slots, f1 is the count of slots with frequency 1, and f2 is the count of slots with frequency 2. Algorithm 2 states the estimator. Algorithm 2 Chao1 cardinality estimator on a fixed-size FreqSet. 1: function Chao1(X, N , s = 1024)
allocate FreqSet on the heap (4096 slots, all empty) 3: stride ← max(1, ⌊N/s⌋) 4: for i = 0, stride, 2stride, . . . until min(N, s · stride) do 5: linear-probe insert X[i] into FreqSet, increment its counter 6: end for 7: u ← count of occupied slots 8: f1 ← count of slots with counter = 1 9: f2 ← count of slots with counter = 2 10: if u = s then 11: return (N, u, f1 , f2 ) ▷ saturated; high-entropy input 12: end if 13: return u + f12 /(2(f2 + 1)), u, f1 , f2 14: end function 2:
The Chao1 estimator [5] reads K̂Chao1 = u +
f12 . 2 (f2 + 1)
(5)
The correction term f12 /(2(f2 + 1)) infers the unseen part of the population from the spectrum of rare values in the sample. The Laplace smoothing f2 + 1 avoids division by zero when 8
no doubletons appear; the asymptotic effect is negligible at f2 in the tens or higher. When u = s the estimator saturates to N , which routes the dispatcher to the high-entropy path. The full estimation costs 1024 hash computes, 1024 probes, and 4096 counter reads, under 100 microseconds on a modern x86 core. Figure 4 shows the data flow. stride = ⌊N/1024⌋ = 9765
input vector<T>
N = 107 , true K = 200
stride sampling: 1024 indices
FreqSet: 4096 slots, open-addressing, uint16_t cnt[4096] linear probe, 40 kB on heap
uniq = 184
f1 = 40
f2 = 51
(distinct keys)
(slots with cnt=1)
(slots with cnt=2)
b Chao1 estimator: K
=
184 +
40 2 2 · 52
=
=
uniq +
184 + 15.38
f12 2 (f2 + 1) ≈
199
Figure 4: The Chao1 estimator: sample, FreqSet, frequency spectrum, K̂.
4.4 Adaptive dispatcher and hot loop The dispatcher reads K̂, u, and N and routes to one of three content branches plus a trivial bypass. Table 2 lists the conditions; Algorithm 3 encodes the same logic. Figure 5 draws the decision tree.
9
Table 2: Dispatcher decisions and the selected branch.
Condition
Branch
Rationale
N < 2048 K̂ ≤ 8 ∧ u ≤ 8 K̂ · 2 > N otherwise
fallback (pdqsort) tiny-count branchless fallback (pdqsort) main CAFS
sampling does not amortize 8 stack counters beat the SIMD bucket high entropy, hash scheme not viable 8 < K̂ < N/2
input vector<T>, params (N, T)
N < 2048 ?
fallback (pdqsort)
typical: N ≤ 2,000
yes
tiny-count branchless (≤ 8 unrolled lanes)
typical: K ≤ 8, N ≥ 104
yes
fallback (pdqsort)
typical: K ∼ N (random)
yes
no
Chao1 sampler → Kest , u = sample_unique, all_uniq
Kest ≤ 8 ∧ u ≤ 8 ?
no
all_uniq ∨ 2Kest > N ?
else
main CAFS (RLE + SIMD bucket loop)
sweet spot: 10 ≤ K ≤ N/4
Figure 5: Dispatcher decision tree.
10
Algorithm 3 Adaptive dispatcher. 1: function Dispatch(X, N )
if IsMonotone(X, N ) then return early on already-sorted input 4: end if 5: if N < 2048 then 6: return pdqsort(X, N ) 7: end if 8: (K̂, u, f1 , f2 ) ← Chao1(X, N ) 9: if K̂ ≤ 8 ∧ u ≤ 8 then 10: return TinyCount(X, N , sample keys) 11: end if 12: if K̂ · 2 > N then 13: return pdqsort(X, N ) 14: end if 15: return main hot loop (X, N , K̂) 16: end function 2: 3:
11
▷ trivial bypass ▷ pre-pass too expensive at small N
▷ high-entropy fallback ▷ described in prose below
The dispatcher itself is a single comparison after the sampler. The pre-pass pays at most 3 · 105 cycles in total. When the condition K̂ ≤ 8 ∧ u ≤ 8 fires, the algorithm extracts up to eight keys from the sample and runs eight independent counters with branchless updates. Each comparison (v == kj ) compiles into a cmp/setcc pair without a conditional jump. The eight add instructions are register-independent and execute concurrently on the out-of-order back end, which yields P about 1 to 2 cycles per element on random 64-bit input. After the pass, the branch checks cj = N . On success it emits the output via std::fill_n. On failure (Chao1 underestimated and the input has a value outside the eight sampled keys) control falls into the main path. The main path also runs a run-length-encoding (RLE) pass over consecutive equal elements: before each update call CAFS extends the run and replaces r separate calls with a single update(val, run_len). The benefit depends on input shape. On fully random input with K ≫ 1 runs degenerate to length 1 and RLE adds one comparison per element without reducing the update count, whereas on sorted-by-group inputs the average run is N/K and the call count collapses from N to K (with already-sorted input as the degenerate end of the same curve). Figure 6 shows the loop state. extend run: ptr[i+k]==val ≈ 4–5 cyc/elem
cmpeq→movemask→tzcnt→add
hot loop: once per run
start
READ_VAL
RLE_SCAN
HASH
BUCKET_UPDATE
overflow i<N
success [[likely]]
i<N?
ADVANCE
SPILL_PUSH p ≈ 1.7·10−4 (rare)
i≥N
DONE
Figure 6: Main hot loop state: pointer ptr, index i, run_len, active bucket.
4.5 Reconstruction and complexity The hash table size adapts to the estimate: M = bit_ceil(8 · K̂/cap),
(6)
where cap is 4 for 64-bit keys and 8 for 32-bit keys. The target slot load factor is 1/8, which gives an expected full-bucket rate near 0.1% under a Poisson allocation. The size is clamped between M ≥ 8 and M ≤ bit_ceil(N/cap). Figure 7 maps M to the cache hierarchy of the test platform. At K̂ = 200, M = 512 buckets give a 32 KB table that fits comfortably inside the 48 KB L1d of the test platform (Table 4). At K̂ = 4 · 103 , M = 8192 gives a 512 KB table that fits in the 1.25 MB L2. At K̂ = 104 , M = 32768 gives a 2 MB table, which exceeds the L2 and lives in L3. At K̂ = 106 , M = 221 is 128 MB and goes to DRAM, but at that scale the dispatcher condition K̂ · 2 > N usually fires and CAFS routes to the fallback before the hash table is even allocated. Reconstruction after the hot loop has three steps. (a) If |spill| > N/2 the result is dropped and CAFS restarts with the pdqsort fallback. This guard caps the worst case at roughly twice pdqsort time, and the absolute worst case observed in our grid was about 5 times. (b) Otherwise the spill is sorted with std::sort, equal neighbors are folded into (key, count) pairs, and the resulting pairs are appended to the dense bucket pairs. (c) The combined dense array of size 12
256 MB
64 MB
64 MB
DRAM >32 MB ∼200 cyc/access
memory footprint (log scale)
16 MB L3 ≤32 MB ∼40 cyc/access
4 MB
1 MB
1 MB
256 KB
L2 ≤1 MB ∼12 cyc/access
64 KB
16 KB
16 KB L1d ≤32 KB ∼4 cyc/access
4 KB
1 KB
K = 200
K = 104
K = 106
256 buckets
16384 buckets
220 buckets
pick_num_buckets: nb = bit_ceil ⌈8Kest /c⌉ , bytes = 64 nb (here c = CAPACITY = 8 for int32_t).
Figure 7: Hash table size as a function of K̂, illustrative. The horizontal markers are drawn at generic x86 L1d / L2 / L3 sizes; the test platform (Table 4) has a 48 KB L1d, which shifts the L1d marker relative to the figure. The exact bucket counts for our K̂ = 200, 4 · 103 , 104 , 106 examples are given in the text below; figure values are sketched at illustrative resolution and may differ by a power of two from the formula in the text.
K ′ ≤ K̂ + |spill folded| is then sorted by key. The procedure is stated in Algorithm 4 and the data path is drawn in Figure 8. Algorithm 4 Reconstruction with spill safety guard. 1: function Reconstruct(buckets, spill, N , out)
if |spill| > N/2 then return pdqsort(X, N ) ▷ safety guard fires 4: end if 5: sort spill with std::sort 6: fold equal neighbors of the spill into (key, count) pairs → spill_pairs 7: collect non-empty bucket slots into pairs → dense_pairs 8: dense_pairs ← dense_pairs ∪ spill_pairs 9: K ′ ← |dense_pairs| 10: if K ′ < 256 then 11: sort dense_pairs by key with std::sort 12: else 13: sort dense_pairs by key with 8-pass LSD byte radix 14: end if 15: p ← out 16: for each (k, c) in dense_pairs do 17: std::fill_n(p, c, k); p ← p + c 18: end for 19: end function 2: 3:
The pair sort runs std::sort with a key comparator when K ′ < 256 and an 8-pass LSD byte 13
Phase 2. 8-pass LSD byte radix
Phase 1. Collect
b0
LSB
k2 , c2
b2 b3
collect non-empty
b4 b5 b6
k3 , c3
K pairs
⟨k1 , 3⟩
MSB
byte
byte
byte
byte
byte
byte
byte
byte
0
1
2
3
4
5
6
7
.. . kK , cK per pass: |dense_res| = K
histogram[256]
ping-pong:
O(K) (scan all buckets)
buf A
⇄
prefix-sum
buf B
⟨k2 , 1⟩
⟨k3 , 2⟩
sorted by key
k1
pass order: LSB → MSB
b7
nb buckets, load ∼ 1/8
output data[]
⟨k1 , c1 ⟩ ⟨k2 , c2 ⟩ . . . ⟨kK , cK ⟩
k1 , c1
b1
Phase 3. Expand & writeback
unsorted by key
dense_res
hash table
k1
k1
c1 = 3 scatter
k2 c2 = 1
k3
k3
c3 = 2
for each ⟨k, c⟩: fill_n writes c copies of k
8 passes ⇒ result in A
O(8K) (only when K ≥ 256, else std::sort)
O(N ) (streaming write)
Figure 8: Reconstruction: buckets, spill, dense_res, radix tail.
radix when K ′ ≥ 256. The expansion uses std::fill_n(out, count, key) per pair, which compiles to rep stosq or a SIMD store burst with throughput close to L2/L3 bandwidth (30 to 50 GB/s). registers
AVX2 lanes v_keys, v_val, cmp
512 B ∼1 cyc
loaded from the active bucket each step
access latency (slower ↓)
L1d cache
active bucket (64 B line) + hot neighbors
32 KB ∼4 cyc
RLE keeps one bucket hot for the whole run
L2 cache
hash-table working set (K ∼ 104 , ∼1 MB)
256 KB–1 MB ∼12 cyc
small-to-mid K: most accesses hit here
L3 cache
full table (large K), dense_res, spill
8–32 MB ∼40 cyc
touched during the reconstruction phase
DRAM
input data[] streamed sequentially
24–64 GB ∼200 cyc
prefetch-friendly; not cached after the pass
Cycles are typical for desktop x86-64 (Intel Skylake / AMD Zen-class). Capacities vary by SKU; ranges shown.
Figure 9: CAFS working set across the x86-64 cache hierarchy.
The branch-wise time complexities are: Ttiny (N ) = O(N ), Tmain (N, K) = O(N ) + O(K log K), Tmain+radix (N, K) = O(N ) + O(8K), Tfallback (N ) = O(s) + O(N log N ).
(7) (8) (9) (10)
Total memory is dominated by the bucket table at 64M bytes (one 64-byte cache line per bucket). The expected spill size on the input distributions in our grid is O(N · 1.7 · 10−4 ), with a hard cap of N/2 enforced by the guard. The dense pair array dense_res holds at most K + |spill folded| entries, and the radix buffer consumes a further K ′ · sizeof(Pair) bytes.
5 Implementation CAFS ships as a header-only C++20 library. It pulls only <algorithm>, <bit>, <cstdint>, <cstring>, <vector>, <utility>, and <immintrin.h>. The C++20 surface used is std::bit_ceil, std::bit_width, and std::countr_zero. The target ISA is x86-64 with AVX2; SIMD specializations exist for int32_t, int64_t, and uint64_t. Other integral types fall back to a scalar four-key linear scan with no loss of correctness. Builds were verified on g++ 13.2 (MinGW-w64) on Windows 11 with -O3 -mavx2 -mbmi -std=c++20 -DNDEBUG. All baselines enter the benchmark through thin wrappers in competitors.hpp. std::sort is taken from libstdc++. Both pdqsort [16] and ska_sort [19] are single-header libraries and are 14
included directly. IPS4o [1] is also distributed header-only, but its internal scheduler instantiates TBB types even on the sequential entry point; the wrapper supplies a stub header with empty TBB-type declarations to satisfy the includes, after which only the sequential entry point is called. vqsort is part of Google Highway [21] and is built via add_subdirectory in CMake, linking statically against the hwy and hwy_contrib targets. The i5-12400F does not expose AVX-512, so the Highway runtime dispatch lands on the AVX2 implementation, which is the same ISA target as CAFS. Artifact availability. The implementation, the benchmark driver, the baseline wrappers, and the raw measurement CSVs are released under the MIT license at https://github.com/ kexibq-official/cafs-lib. The repository also contains build scripts for libhwy and the vqsort object files, together with the Python notebooks used to produce the figures and tables. The source layout is summarized in Table 3. Table 3: Source layout of the implementation.
File
Contents
cafs.hpp cafs2.hpp competitors.hpp datagen.hpp main_bigdata.cpp
primitives: Bucket<T> with SIMD specializations, fast_hash, prototype v1 adaptive dispatcher, FreqSet, Chao1 estimator, tiny-count, radix tail wrappers for pdqsort, ska_sort, IPS4o, vqsort low-entropy input generator with controlled K benchmark driver: (N, K) grid, correctness check, CSV export
6 Evaluation 6.1 Goals, hypotheses, methodology The evaluation answers three questions. First, what is the bin-mean speedup of CAFS against each baseline at K ≪ N , and is it large enough to be useful? Second, where, in terms of K, does each baseline overtake CAFS at N > 106 ? Third, is the lead at fixed K stable across N , or does it grow or shrink as the array gets bigger? For each point (N, K) a palette of K values is built as the arithmetic progression a + b · i for i = 0, . . . , K − 1, where a and an odd step b are derived from the seed 42 + N + K through a SplitMix-style mixer, and the array of length N is then filled by uniform sampling from this palette, with each algorithm receiving its own fresh copy. Runs are timed with std::chrono::high_resolution_clock (reported as floating-point milliseconds), each algorithm is executed twice on every point regardless of N , and the minimum of the two replicates enters the result table. Correctness is verified by sorting a separate copy with std::sort and comparing element-wise, and CAFS produced no failures across the grid. The order of algorithms within a point is fixed at (CAFS, std::sort, pdqsort, ska_sort, IPS4o, vqsort) and we did not randomize it; the methodological consequences are discussed in Section 6.2. We benchmark CAFS against five single-threaded baselines: pdqsort and IPS4o (comparison), vqsort (SIMD), ska_sort (radix), and std::sort (the C++ standard library default). Each (N, K) point produces one speedup value per baseline, and we aggregate by entropy bin Hbin = ⌊log2 K⌋.
6.2 Bench platform The bench is single-threaded, background processes were minimized between runs, and the P-state lock was not enforced, so thermal throttling adds about ±5% noise across long runs (Table 4). The fixed algorithm order within each (N, K) point (Section 6) introduces an additional 15
systematic bias whose sign is the opposite of what one might assume: CAFS runs first on a cold cache and the baselines that follow benefit from a working set that is already paged in. The effect is at most a few percent of run time on the largest inputs and below measurement noise once the working set exceeds L3. We do not claim this bias cancels in the speedup ratio; it is a methodological limitation of the present study. Table 4: Bench platform and toolchain.
Parameter
Value
CPU ISA extensions L1d cache L2 cache L3 cache RAM OS Compiler Build flags
Intel Core i5-12400F, 6 P-cores, base 2.5 GHz, boost 4.4 GHz x86-64, AVX2, BMI1, BMI2 48 KB per core, 12-way associative 1.25 MB per core, 10-way associative 18 MB shared, 12-way associative 32 GB DDR4-3200 Windows 11 g++ 13.2 (MinGW-w64) -O3 -mavx2 -mbmi -std=c++20 -DNDEBUG
6.3 CAFS vs. pdqsort Across bins 1 to 16 the bin-mean speedup is between 1.7 and 3.1, with the win rate between 67% and 96%. The win rate stays above 90% all the way through bin 11 (the safe zone) and only drops to 67% by bin 16, where the bin mean is still above 1.6. Bin 17 is the transition (mean 1.29, win rate 56%), and parity sets in from bin 18 onward. The minimum entries between 0.20 and 0.39 mark the points where the safety guard fired and CAFS finished at about half the speed of pdqsort because of the sampling overhead; no point exceeded a 5× slowdown. The last dominance point at N > 106 is at K ≈ 1.72 · 107 (H ≈ 24 bits), and the operational crossover (the largest K where the win rate still clears 50%) corresponds to H ≈ 17 bits (K ≈ 1.3 · 105 ). Inside the dominance zone the Pearson correlation between log N and speedup is r = 0.232, so the lead trends mildly upward with N .
16
Figure 10: Heatmap of CAFS speedup over pdqsort across the (N, K) grid.
Table 5: Speedup of CAFS over pdqsort, by entropy bin.
Hbin
K range
avg
min
max
win-rate
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ≥ 19
2 to 4 4 to 8 8 to 16 16 to 32 32 to 64 64 to 128 128 to 256 256 to 512 512 to 1024 1024 to 2048 2048 to 4096 4096 to 8192 8192 to 16384 16384 to 32768 32768 to 65536 65536 to 131072 131072 to 262144 262144 to 524288 ≥ 524288
2.50 3.10 1.72 1.86 2.30 2.63 2.86 3.00 3.07 3.01 2.78 2.35 2.12 1.92 1.87 1.66 1.29 1.01 ≤ 1.00
0.20 0.29 0.14 0.25 0.26 0.20 0.25 0.27 0.24 0.24 0.30 0.21 0.24 0.34 0.29 0.33 0.34 0.39 0.36
7.38 6.49 6.36 3.72 4.23 4.92 8.09 5.16 6.84 5.93 7.31 9.57 6.30 4.35 4.23 3.54 3.14 2.29 1.71
94.8% 94.8% 88.4% 92.9% 94.6% 93.6% 94.9% 94.3% 94.4% 95.6% 93.4% 87.2% 71.5% 67.1% 81.5% 77.4% 55.9% 41.7% ≤ 49.6%
17
6.4 CAFS vs. IPS4o The bin-mean speedup in bins 1 to 11 (K from 2 to 4096) is between 1.97 and 3.52 at win rates above 97%, with a maximum of 3.52 in bin 9 (K = 512 to 1024). At that K the hash table fits in L1d, RLE injection stays inactive on random input, and the sampling cost is small relative to the count step. Through bins 12 to 16 (up to K = 131072) the mean falls to between 1.7 and 2.5 with win rates between 79% and 96% as the table moves out of L1d through L2 and into L3 while IPS4o keeps its prefetch-friendly partition pattern. Bin 17 is the transition (mean 1.33, win rate 58%), and from bin 18 onward the bin means are near 1.00. Unlike the pdqsort and vqsort pairings, there is no sharp crossover against IPS4o; the lead decreases smoothly to parity, with the last dominance point at N > 106 corresponding to K ≈ 1.72 · 107 (H ≈ 24 bits), close to K = N . The Pearson correlation between log N and speedup inside the dominance zone is r = −0.189, a slight tilt downward as N grows. Hypothesis H2 thus holds against a strong comparison engine, not only against introsort. The 1.97 to 3.52 range across the safe band exceeds the 2× threshold of H1 in most of bins 1 to 11.
Figure 11: Heatmap of CAFS speedup over IPS4o across the (N, K) grid.
18
Table 6: Speedup of CAFS over IPS4o, by entropy bin.
Hbin
K range
avg
min
max
win-rate
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ≥ 18
2 to 4 4 to 8 8 to 16 16 to 32 32 to 64 64 to 128 128 to 256 256 to 512 512 to 1024 1024 to 2048 2048 to 4096 4096 to 8192 8192 to 16384 16384 to 32768 32768 to 65536 65536 to 131072 131072 to 262144 ≥ 262144
3.24 3.50 1.97 2.09 2.57 2.90 3.27 3.40 3.52 3.35 3.03 2.44 2.18 1.99 1.98 1.73 1.33 ≈ 1.00
0.65 0.70 0.24 0.22 0.19 0.16 0.21 0.22 0.28 0.26 0.24 0.10 0.10 0.32 0.23 0.30 0.51 0.28
11.64 17.50 15.85 13.36 10.95 17.43 17.85 19.74 19.12 24.81 29.66 16.89 15.15 5.70 9.51 4.59 3.31 2.39
99.1% 99.6% 97.0% 97.4% 98.2% 97.9% 98.4% 97.9% 98.6% 98.5% 97.7% 95.7% 85.5% 82.4% 87.0% 79.3% 58.0% 41 to 83%
6.5 CAFS vs. vqsort Bins 5 to 15 give a lead with bin means between 1.27 and 2.34 and win rates between 57% and 93%. The maximum, 2.34, is in bin 9 (K = 512 to 1024) — the same point as in the IPS4o pairing — covering K between 32 and roughly 65000 (5 to 16 bits of entropy). CAFS wins here because the hash scheme runs at about one SIMD operation per element, while vqsort traverses log2 N partition levels with a YMM sorting network at each level. Bins 1, 3, and 4 are an anomaly: the bin mean dips to between 0.84 and 0.99 and the win rate falls to 19% to 40%, even though we would expect a comfortable lead at small K. Our best explanation is grid composition: most points in these bins are at small N , where the 100-microsecond sampling pre-pass is a substantial fraction of total run time and vqsort wins because it has no pre-pass. Bin 2 (K = 4 to 8) does not dip in the same way, which is consistent with that reading, because most bin-2 points fall into the tiny-count branch and bypass the Chao1 estimator. The cause has not been pinned down in our measurements, and this remains the weakest part of our characterisation of CAFS against vqsort at very low K. From bin 16 the bin mean drops to 1.21, then to 1.01 at bin 17, and from bin 18 (K ≥ 262144) it goes below 1, eventually reaching 0.58 to 0.63 in bins 21 to 24 with a zero win rate. At K ≈ N vqsort beats CAFS by a factor of 1.6 to 1.7 because its hot loop runs at 0.5 to 1 cycle per element through a YMM sorting network independent of K [22], leaving CAFS with no remaining advantage. The last dominance point at N > 106 corresponds to K ≈ 6.7 · 105 (H ≈ 19.36 bits), past which the safety guard fires on a fraction of cases and keeps the lag near 1.5 to 2 times. Within the lead band the speedup is essentially flat in N (Pearson r = 0.072 for log N vs. speedup). vqsort is therefore the only one of the five baselines that strictly overtakes CAFS in the high-K regime: CAFS beats vqsort for K ≤ 6.7 · 105 , and above that point vqsort wins by a factor of 1.5 to 1.7.
19
Figure 12: Heatmap of CAFS speedup over vqsort: transition through parity at H ≈ 19.4 bits. Table 7: Speedup of CAFS over vqsort, by entropy bin.
Hbin
K range
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ≥ 20
2 to 4 4 to 8 8 to 16 16 to 32 32 to 64 64 to 128 128 to 256 256 to 512 512 to 1024 1024 to 2048 2048 to 4096 4096 to 8192 8192 to 16384 16384 to 32768 32768 to 65536 65536 to 131072 131072 to 262144 262144 to 524288 524288 to 1048576 ≥ 1048576
avg
min
max
win-rate
0.89 1.32 0.84 0.99 1.27 1.54 1.78 2.06 2.34 2.18 1.91 1.64 1.59 1.45 1.39 1.21 1.01 0.77 0.73 0.58 to 0.68
0.09 0.14 0.13 0.15 0.15 0.11 0.13 0.12 0.14 0.14 0.18 0.06 0.05 0.18 0.12 0.16 0.26 0.22 0.19 0.17
6.54 3.42 3.08 3.19 3.94 10.25 9.22 8.75 18.10 10.53 16.34 14.77 14.24 9.42 5.37 4.18 3.48 2.06 1.85 1.42
25.9% 79.7% 19.0% 40.2% 91.3% 91.3% 93.7% 93.4% 93.1% 91.1% 83.0% 59.9% 57.6% 60.6% 65.4% 49.9% 39.1% 28.9% 21.7% 0 to 7.7%
20
6.6 CAFS vs. ska_sort Against ska_sort the curve has a different shape. The speedup in bins 1 and 2 reaches 17 times at a 100% win rate, and in bins 3 to 11 the bin mean stays between 4.5 and 8 with win rates above 94%, because ska_sort runs eight byte passes over a 64-bit key whatever K may be, while CAFS at small K runs one SIMD compare per element. The runtime gap is the entropy gap of Section 3 written in microseconds. The lead then contracts as K grows: by bin 12 the bin mean is down to 3.2, by bin 16 to 1.7, and the last dominance point at N > 106 corresponds to K ≈ 8.14 · 105 (H ≈ 19.63 bits). Past that boundary ska_sort takes the lead, and in bins 22 to 24 (K ∈ [4 · 106 , 3 · 107 ]) the bin mean is between 0.66 and 0.72 at a 0% win rate. The root cause at high K is memory pressure rather than instruction count: the CAFS hash table grows to tens of megabytes and loses L3 residency, so the hot loop becomes memory-bound, while ska_sort works only on the input array and a small histogram, keeping its working set compact even when K ≈ N . Inside the dominance zone the lead is independent of N (r = 0.127 between log N and speedup, near zero). The descent of the bin mean against ska_sort is monotonic from bin 1 through bin 18, in contrast to the non-monotonic dip near small K that appears against vqsort. The crossover at K ≈ 8.14 · 105 comes later than the vqsort crossover at K ≈ 6.7 · 105 , so any deployment that may push K beyond 106 should fall back to vqsort, not ska_sort, at the boundary.
Figure 13: Heatmap of CAFS speedup over ska_sort across the (N, K) grid.
21
Table 8: Speedup of CAFS over ska_sort, by entropy bin.
Hbin
K range
avg
min
max
win-rate
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ≥ 19
2 to 4 4 to 8 8 to 16 16 to 32 32 to 64 64 to 128 128 to 256 256 to 512 512 to 1024 1024 to 2048 2048 to 4096 4096 to 8192 8192 to 16384 16384 to 32768 32768 to 65536 65536 to 131072 131072 to 262144 262144 to 524288 ≥ 524288
17.65 16.96 7.87 7.03 7.60 7.64 7.43 6.19 5.87 5.38 4.49 3.17 2.45 2.19 2.07 1.69 1.26 0.89 ≤ 0.87
3.07 2.38 0.93 0.39 0.21 0.10 0.23 0.24 0.17 0.20 0.27 0.13 0.18 0.20 0.21 0.21 0.27 0.29 0.23
26.26 29.33 26.27 12.26 13.13 19.64 27.86 15.15 14.41 18.39 13.67 12.79 9.21 7.33 7.61 6.87 5.34 2.22 2.09
100.0% 100.0% 99.8% 99.4% 97.8% 95.1% 95.6% 95.2% 95.2% 95.9% 94.0% 78.9% 74.6% 63.0% 56.1% 50.8% 41.2% 37.2% ≤ 35.7%
6.7 CAFS vs. std::sort CAFS beats std::sort in every entropy bin, including the K ≈ N regime. Across the band Hbin ∈ [1, 16] the bin-mean speedup is between 7 and 17 at win rates above 97%. Even in the high-entropy zone (bins 22 to 24) the win rate is 100% with a 3.5 times speedup, driven by the CAFS fallback to pdqsort, since std::sort (introsort) loses to pdqsort across the whole grid and CAFS routes to pdqsort in the high-K branch. The last dominance point at N > 106 corresponds to K ≈ 1.72 · 107 (H ≈ 24 bits), and the lead grows with N (r = 0.351 between log N and speedup in the dominance zone) because introsort runs data-dependent branches whose mispredictions accumulate with N while the CAFS hot loop has no comparable branch. There is no point on the grid at which CAFS loses to std::sort.
22
Figure 14: Heatmap of CAFS speedup over std::sort across the (N, K) grid.
Table 9: Speedup of CAFS over std::sort, by entropy bin.
Hbin
K range
avg
min
max
win-rate
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ≥ 20
2 to 4 4 to 8 8 to 16 16 to 32 32 to 64 64 to 128 128 to 256 256 to 512 512 to 1024 1024 to 2048 2048 to 4096 4096 to 8192 8192 to 16384 16384 to 32768 32768 to 65536 65536 to 131072 131072 to 262144 262144 to 524288 524288 to 1048576 ≥ 1048576
13.09 17.10 9.67 10.02 12.21 13.52 14.51 14.76 14.74 14.08 12.74 10.71 9.46 8.56 8.34 7.15 5.30 3.93 3.70 ≥ 3.20
0.48 0.58 0.91 0.87 0.98 0.65 0.56 0.41 0.50 0.61 0.76 0.24 0.22 0.74 0.54 0.85 1.18 1.12 0.95 0.92
23.00 58.96 60.62 47.67 36.30 67.39 90.38 44.22 60.89 66.57 60.93 57.79 44.23 32.32 23.88 21.36 20.20 11.29 9.14 6.69
97.4% 99.1% 99.8% 99.8% 99.9% 99.9% 99.9% 99.7% 99.7% 99.6% 99.9% 99.9% 99.9% 99.6% 100.0% 99.9% 100.0% 100.0% 99.2% ≥ 94.8%
23
6.8 Summary applicability map Aggregating across the five baselines yields the applicability map of CAFS in (N, K) coordinates. 108
K=N K = N/2 (cutoff)
107
o ke
pdqsort fallback
distinct keys K (log scale)
104
v
wi
ns
ta rt so
106
105
rt so vq
er
s
vq
/ ort
103
a_ sk
CAFS dominant
102
101
K=8
tiny-count branchless 100 103
104
105
106
107
108
input size N (log scale)
Figure 15: Applicability map of CAFS in (N, K) coordinates.
Table 10: Applicability zones of CAFS.
Zone
Parameters
CAFS behavior
tiny-count
K ≤ 8, N ≥ 2048
main CAFS
8 < K ≤ 105
transitional
105 < K ≤ N/2 K≈N
beats all five baselines: 13 to 21 times vs std::sort, 2.5 to 5 times vs pdqsort, 17 to 19 times vs ska_sort, 3 to 4 times vs IPS4o, 1 to 2 times vs vqsort beats all five baselines: 1.7 to 3 times vs pdqsort, 4 to 8 times vs ska_sort, 8 to 15 times vs std::sort, 1.7 to 3.5 times vs IPS4o, 1.2 to 2.3 times vs vqsort bin-mean speedup vs pdqsort, ska_sort, IPS4o, vqsort drops toward 1; vs std::sort stays above 3 loses to vqsort (0.58 to 0.63 times) and ska_sort (about 0.66 times); parity with IPS4o and pdqsort; lead over std::sort triggers fallback; total time equals pdqsort plus a 100microsecond sampling overhead
high-entropy
pathological
N < 2048
The boundaries are: K ≈ 1.3 · 105 (H ≈ 17 bits) against pdqsort and std::sort, K ≈ 8.14 · 105 (H ≈ 19.63 bits) against ska_sort, K ≈ 6.7 · 105 (H ≈ 19.36 bits) against vqsort, and only K ≈ 1.72 · 107 (parity at K = N ) against IPS4o. Of the five baselines, only vqsort strictly 24
overtakes CAFS once its crossover is passed: against pdqsort and std::sort the algorithm falls back to pdqsort and matches it, against ska_sort the lag is modest, and against IPS4o the curves only converge at K = N . The binding constraint on the operational range of CAFS is therefore the vqsort threshold at K ≈ 6.7 · 105 . Coming back to the three questions of Section 6.1. The bin-mean speedup at K ≤ 103 is comfortably above 2× against std::sort, pdqsort, ska_sort, and IPS4o, and between 1 and 2.3× against vqsort (with a few low-K bins below 1 that we do not fully explain; see Section 6.5). The per-baseline crossovers are the four numbers above. The lead at fixed K is roughly stable in N within the dominance zone: the Pearson correlations between log N and speedup are all small in magnitude (|r| < 0.4 at ≈ 24000 measurements per pair) and the signs are consistent with the relative cost models, but with |r| this small they do not by themselves rule out a stationary lead. The spill safety guard (Section 4) keeps the worst case observed in the grid under a 5× slowdown.
7 Discussion and Limitations 7.1 Operating-point guidance CAFS is designed for a specific input class and degrades to pdqsort outside it. For deployment in OLAP engines the relevant operating point is the post-group-by sort, where the cardinality of the key column is bounded by the number of distinct group keys. That number is typically below 105 , which falls inside the main CAFS zone for every baseline considered. Beyond OLAP, the main CAFS zone also covers categorical column sorting and foreign-key sorting against a small dimension table. We recommend CAFS whenever an upper bound on K is available and falls below 105 , vqsort whenever K may exceed 6.7 · 105 , and the per-baseline crossover for cases between the two thresholds. The CAFS dispatcher implements a runtime version of the same rule through the K̂ · 2 > N guard, although a deployment that knows the schema can short-circuit the pre-pass entirely.
7.2 Why CAFS wins on K ≪ N
Comparison and radix sorts pay a per-element cost independent of the input entropy (log2 N comparisons for the former, ⌈B/b⌉ digit visits for the latter), whereas a hash-count sort pays one hash and one bucket compare per element when the bucket is sized correctly. With the bucket on one cache line and the compare folded into a single SIMD instruction, this drops to about 4 to 5 cycles per element, and in the main zone CAFS runs at that rate. The other stages (sampling, dispatcher, reconstruction) cost O(s) or O(K) and become negligible at large N .
7.3 Why CAFS loses at K ≈ N At K ≈ N the algorithm has nothing left to exploit. The hash table grows linearly with K̂ and now occupies tens of megabytes, so it falls out of L3 into DRAM and the hot loop becomes memory-bound. The trailing pair sort, which is negligible at K ≪ N , now runs on K ≈ N items at a cost of O(N log N ), equal to a full comparison sort but with extra setup. The dispatcher condition K̂ · 2 > N catches most such cases at the pre-pass and reroutes them to pdqsort directly, and the safety guard catches the rest after the hot loop runs. The net cost is pdqsort time plus the 100 microseconds of sampling overhead that we never recover.
7.4 Limitations Several limitations apply to the current evaluation. All measurements come from one hardware platform, an Intel Core i5-12400F, so behaviour on parts with different cache geometry (Zen, 25
Skylake-X, server-class Xeon, mobile Alder Lake E-cores) remains untested. The L1d cache on our test platform is 48 KB, and on parts with a 32 KB L1d the threshold at which the table leaves L1d shifts down by 0.5 bits in H, which would compress the main CAFS zone slightly. The AVX-512 path of vqsort is not in our measurements, even though on supporting CPUs it is roughly 1.5 times faster than the AVX2 path and would push the vqsort crossover toward smaller K. The benchmark is also restricted to single-threaded runs, so we do not compare against the parallel modes of pdqsort or IPS4o, and a parallel CAFS with per-thread hash tables and a final merge is plausible but not built. The grid uses a single input distribution, a uniform random palette of 64-bit values, while real workloads often have sorted-by-group, runs, or almost-sorted profiles where RLE injection would push CAFS further ahead. Because the multiplicative hash is deterministic and public, an adversary can construct inputs that drive collisions; no such inputs appear in our grid. Finally, the reported correlations between log N and speedup all have |r| < 0.4 at sample sizes near 24000 per pairing, so N is not the dominant factor inside the dominance zone.
7.5 Future directions The two short-term next steps are an AVX-512 bucket with eight 64-bit lanes (which should push the hot-loop throughput higher and move the vqsort crossover out) and a randomized hash seed (which closes the deterministic-collision attack noted above). The harder open items are a parallel CAFS with per-thread hash tables and a final merge, a floating-point variant via bit-cast, and a learned cardinality estimator that could replace Chao1 on workloads where the singletons-doubletons signal is weak. Two further items are integrating CAFS into a real query engine (DuckDB, ClickHouse, or MonetDB as the post-group-by sort) and extending the input grid past the uniform random palette to sorted-by-group, runs, and almost-sorted profiles. The grid extension is the most directly testable because RLE injection inside CAFS targets exactly those input shapes. A v2 of this paper is planned for autumn 2026. The platform moves to an AMD Ryzen 5 9600X with 32 GB DDR5-6000 on a bare Linux setup, wall-clock timing through std::chrono is replaced by perf stat, and the AVX2 hot loop is rewritten in AVX-512. IPS4o is dropped from the baseline set in v2 to keep every competitor single-header, and a plain hash-count sort over std::unordered_map is added. Informal runs already show CAFS beats it by orders of magnitude at every K we tried; v2 will report the full grid against it in Evaluation. Suggestions for additional baselines to include in v2, or proposals for collaborative research, are welcome at [email protected].
8 Conclusion CAFS targets a specific corner of integer sorting: inputs where K is much smaller than N . The algorithm pays a 100-microsecond Chao1 pre-pass to detect that regime, dispatches accordingly, and when it lands inside the regime runs the count-emit loop at about one SIMD operation per element. Two costs follow from the K-dependent working set. A spill safety guard catches inputs where the dispatcher misestimated K. And on inputs with K close to N the hash table eventually exceeds L3 cache, which is what gives vqsort the crossover at K ≈ 6.7 · 105 on our platform. On the 58-by-dense-K grid and inside the K ≪ N band, CAFS runs 1.7 to 3.1× faster than pdqsort, 1.7 to 3.5× faster than IPS4o, 4 to 17× faster than ska_sort, 8 to 17× faster than std::sort, and 1.2 to 2.3× faster than vqsort, with the operational range upper-bounded by the vqsort crossover at K ≈ 6.7 · 105 . Two questions remain open: whether an AVX-512 bucket and 26
a randomized hash seed can move that crossover above K = 107 , and how the picture changes on skewed inputs and on sorted-by-group profiles. The implementation and the raw measurements are available at https://github.com/kexibq-official/cafs-lib.
References [1] Michael Axtmann, Sascha Witt, Daniel Ferizovic, and Peter Sanders. IPS4 o: In-place parallel super scalar samplesort, C++ implementation. GitHub repository. URL https: //github.com/ips4o/ips4o. [2] Michael Axtmann, Sascha Witt, Daniel Ferizovic, and Peter Sanders. In-place parallel super scalar samplesort (ips4 o). ACM Transactions on Parallel Computing, 4(4):1–44, 2017. [3] Peter Boncz, Marcin Zukowski, and Niels Nes. MonetDB/X100: Hyper-pipelining query execution. In Proceedings of the Conference on Innovative Data Systems Research (CIDR), pages 225–237, 2005. [4] Bérenger Bramas. A novel hybrid quicksort algorithm vectorized using AVX-512 on Intel Skylake. arXiv:1704.08579 [cs.DS], 2017. URL https://arxiv.org/abs/1704.08579. arXiv:1704.08579 [cs.DS]. [5] Anne Chao. Nonparametric estimation of the number of classes in a population. Scandinavian Journal of Statistics, 11(4):265–270, 1984. [6] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, Cambridge, MA, 3 edition, 2009. [7] Ulrich Drepper. What every programmer should know about memory. Red Hat, Inc., 2007. URL https://akkadia.org/drepper/cpumemory.pdf. [8] Stefan Edelkamp and Armin Weiß. BlockQuicksort: Avoiding branch mispredictions in quicksort. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA), pages 38:1–38:16, 2016. [9] Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm. In Proceedings of the Conference on Analysis of Algorithms (AofA), pages 127–146, 2007. [10] Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. Cacheoblivious algorithms. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pages 285–297, 1999. [11] Hiroshi Inoue and Kenjiro Taura. SIMD- and cache-friendly algorithm for sorting an array of structures. Proceedings of the VLDB Endowment, 8(11):1274–1285, 2015. [12] Intel Corporation. Intel 64 and ia-32 architectures optimization reference manual. Order Number 248966-046, 2024. URL https://www.intel.com/content/www/us/en/developer/ articles/technical/intel-sdm.html. [13] Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, Reading, MA, 2 edition, 1998. [14] Daniel Lemire, Leonid Boytsov, and Nathan Kurz. SIMD compression and the intersection of sorted integers. arXiv:1401.6399 [cs.IR], 2014. URL https://arxiv.org/abs/1401.6399. arXiv:1401.6399 [cs.IR]. 27
[15] David R. Musser. Introspective sorting and selection algorithms. Software: Practice and Experience, 27(8):983–993, 1997. [16] Orson Peters. pdqsort: Pattern-defeating quicksort, C++ implementation. GitHub repository. URL https://github.com/orlp/pdqsort. [17] Orson Peters. Pattern-defeating quicksort. arXiv:2106.05123 [cs.DS], 2021. URL https: //arxiv.org/abs/2106.05123. arXiv:2106.05123 [cs.DS]. [18] Nadathur Satish, Changkyu Kim, Jatin Chhugani, Anthony D. Nguyen, Victor W. Lee, Daehyun Kim, and Pradeep Dubey. Fast sort on CPUs and GPUs: A case for bandwidth oblivious SIMD sort. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pages 351–362, 2010. [19] Malte Skarupke. ska_sort: A fast in-place radix sort. GitHub repository, 2017. URL https://github.com/skarupke/ska_sort. [20] Michael Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Sam Madden, Elizabeth O’Neil, Pat O’Neil, Alex Rasin, Nga Tran, and Stan Zdonik. C-Store: A column-oriented DBMS. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB), pages 553–564, 2005. [21] Jan Wassenberg, Jan Goebel, et al. Highway: A C++ library for SIMD/Vector intrinsics. Google Inc., GitHub repository. URL https://github.com/google/highway. [22] Jan Wassenberg, Mark Blacher, Joachim Giesen, and Peter Sanders. Vectorized and performance-portable quicksort. arXiv:2205.05982 [cs.DS], 2022. URL https://arxiv.org/ abs/2205.05982. arXiv:2205.05982 [cs.DS].
28