# radix-sort

Published articles for radix-sort.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## CAFS: A Cache-Aware Frequency Sort for Low-Cardinality Integer Data on x86-64

DevFeed: [CAFS: A Cache-Aware Frequency Sort for Low-Cardinality Integer Data on x86-64](<https://devfeed.tech/articles/cafs-a-cache-aware-frequency-sort-for-low-cardinality-integer-data-on-x86-64-93870.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2605.25040>)

Author: Vasiliy S. Shlyk

Published: 2026-10-21T04:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [vectorization techniques](<https://devfeed.tech/topics/vectorization-techniques.md>), [Cache](<https://devfeed.tech/topics/cache.md>), [CPU Cache](<https://devfeed.tech/topics/cpu-cache.md>), [x86](<https://devfeed.tech/topics/x86.md>), [olap](<https://devfeed.tech/topics/olap.md>)

Tags: [adaptive](<https://devfeed.tech/tags/adaptive.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [array](<https://devfeed.tech/tags/array.md>), [avx2](<https://devfeed.tech/tags/avx2.md>), [cache](<https://devfeed.tech/tags/cache.md>), [cardinality](<https://devfeed.tech/tags/cardinality.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [olap](<https://devfeed.tech/tags/olap.md>), [open-addressing](<https://devfeed.tech/tags/open-addressing.md>), [operational](<https://devfeed.tech/tags/operational.md>), [pdqsort](<https://devfeed.tech/tags/pdqsort.md>), [radix-sort](<https://devfeed.tech/tags/radix-sort.md>), [simd](<https://devfeed.tech/tags/simd.md>), [ska-sort](<https://devfeed.tech/tags/ska-sort.md>), [sort](<https://devfeed.tech/tags/sort.md>), [throughput](<https://devfeed.tech/tags/throughput.md>), [x86-64](<https://devfeed.tech/tags/x86-64.md>)

### AI overview

CAFS targets integer arrays with many values but low cardinality, common in OLAP workloads. On x86-64 with AVX2, it combines a cache-line-sized SIMD bucket, a Chao1 estimator using 1,024 strided samples, and an adaptive dispatcher with a spill safety guard; its branchless hot loop uses cmpeq, movemask, and tzcnt. Across 592,770 benchmark runs, CAFS reached 1.7-3.1x pdqsort, 1.7-3.5x IPS4o, and 1.2-2.3x vqsort throughput when K was much smaller than N. The reported crossover is about K=130,000 for pdqsort and 670,000 for vqsort; only vqsort overtook CAFS beyond its crossover, making that threshold the stated limit of CAFS's operational range. The evidence is an abstract-level summary of benchmarks, not full paper coverage.

### Source excerpt

arXiv:2605.25040v2 Announce Type: replace-cross 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 $\Theta(N \log N)$ comparisons, and a radix sort still pays $\Theta(N \cdot 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 $10^3$ to $3 \cdot 10^7$ with dense $K$ schedules per $N$, producing 592770 timed runs against pdqsort, IPS4o, vqsort, ska_sort, and std::sort. In the $K \ll N$ band the throughput is 1.7 to 3.1x that of pdqsort, 1.7 to 3.5x IPS4o, and 1.2 to 2.3x vqsort. The operational crossover against pdqsort is at $K \approx 1.3 \cdot 10^5$; against ska_sort, $K \approx 8.14 \cdot 10^5$; against vqsort, $K \approx 6.7 \cdot 10^5$; 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 \approx 6.7 \cdot 10^5$ the binding constraint on the operational range of CAFS.