F5: A Robust SIMD-Accelerated MSD Radix Sort

Sorting is a building block of many data-intensive applications, databases, MapReduce pipelines, and large-scale distributed systems. In this paper, we focus on MSD (mostsignificant digit first) radix sort, in which we identify three main bottlenecks - slow small-bucket sorts at the end of recursion, partitioning algorithms susceptible to read-after-write stalls, and unnecessarily deep recursion chains on non-uniform distributions. We overcome these issues in a framework we call F5, which consists of a) vectorized small sorts that perform well on a wide range of input sizes; b) a partitioning engine that delivers bursts of keys into buckets at significantly increased speed; c) a prefix extractor and sortedness checker that allow jumping over common bits and terminating recursion early; and d) an adaptive radix selector that optimally decides the number of bits for each level of partitioning. Results show that F5 often doubles the speed of prior methods, including recent AVX-512 endeavors from Google [13] and Intel [19], on both uniform/skewed distributions, while also remaining in-place.