File VectorQuickSort.h

↰ Parent directory (ADS/sort)

The quicksort in the lanes of the vector registers, beyond the book: vectorQuickSort() sorts integers and floating point numbers of 32 or 64 bits by their natural order, partitioning W of them per instruction, where W is the number of lanes of a register (16 or 8 on AVX-512, 8 or 4 on AVX2), and sorting the parts of at most 16 W items by a sorting network held in 16 registers.

Definition (ADS/sort/VectorQuickSort.h)

Detailed Description

  • The keys: an integer is its own key, compared signed or not on AVX-512 and made signed on AVX2 by flipping its sign bit. A floating point number is sorted as the signed integer b of its bits, with no conversion: b keeps the order of the numbers with the sign bit clear and reverses that of those with it set, which come all first, since for them :math:` b = -2^{w-1} + | x |_{bits} ` grows with the magnitude; once sorted, their block, found by a binary search, is reversed in place, a pass over the negative numbers alone instead of a conversion of all of them before and after the sort. The order is that of IEEE 754 extended to a total order, -0 before +0 and the NaN at the ends, so that a NaN breaks nothing.

  • Few keys in a small range: on AVX-512, from 4096 integers, if a sample of 64 spans fewer than :math:` A L / 4 ` values, for L the bits of a lane and :math:` A in { 1 , 2 , 4 } ` registers (32 values for either width), the keys are counted in one pass with no comparison: the key :math:` x = lo + d ` sets the bit :math:` 4 ( d - a L / 4 ) ` of its lane in the register a by a variable shift (none if out of reach), so that each lane counts L / 4 values in its nibbles; every 15 registers the nibbles are added into bytes, every 17 of those the bytes into the counts, and the largest offset is checked, a key out of the window giving up the counting for the quicksort. A second pass writes the keys, whole registers at a time: :math:` O( n ) ` against the :math:` O( n log k ) ` of the partitions by three ways.

  • The partition of a part a[ 0 .. n ) by a pivot p, as in the quicksort of Bramas: the first and the last U W keys (U = 8) are loaded aside, which leaves U W free places at each end, and then U blocks of W keys at a time are read from the end with fewer free places; each block is compared with p in one instruction into a mask m of W bits, and its :math:` ell = | m | ` keys below p are written at the left end and the :math:` W - ell ` others at the right one. Before a read the two ends have :math:` f_L + f_R = 2 U W ` free places, and the read is from the end with :math:` min( f_L , f_R ) leq U W , so that after it both have at least U W: no write overtakes a key not yet read, and the partition is in place with no branch on the keys (the choice of the end is one branch per U blocks). On AVX-512 the two pieces are compressed into the memory (vpcompress); on AVX2 a table of :math: 2^W ` permutations puts the lanes of m first and the others after them in one register, which is written whole at the left end and whole at the right one, as in the quicksort of Gueron and Krasnov; on AVX-512 the keys of 64 bits take the same way, with a table of 256 permutations of 8 lanes and one vpermq, cheaper than two compressions into the memory. Each read of U blocks prefetches into the first level the U blocks 8 U W keys further in the same direction, which nearly halves the time of a pass over a part larger than the cache of the second level, where the hardware prefetcher alone falls behind the two ends read in turn.

  • The pivot is the median of a sample of :math:` S = max( 8 , W ) ` keys, one from each of S equal stretches of the part at the same random offset, sorted by the network below. If the sample repeats the pivot, on AVX-512 the partition goes three ways in one pass: the keys equal to p are not written, and the gap they leave between the two sides is filled with p at the end, while the minimum and the maximum of each side are kept by masked instructions, so that a side of one key is done; elsewhere the partition keeps the minimum and the maximum of the part and a second pass puts the keys equal to p apart. A pivot that is the minimum of the part, so that no key is below it, also gets that second pass. Hence k distinct keys take :math:` O( n log k ) `.

  • The smaller side recurs and the larger one loops, with a stack of :math:` O( log n ) ; past :math: 2 lfloor log_2 n rfloor ` levels a part is sorted by heapsort, as in the introsort of Musser, so that the worst case is :math:` O( n log n ) `.

  • A part of at most 16 W keys is loaded into :math:` M = 2^{lceil log_2 lceil n / W rceil rceil} ` registers, the lanes past n filled with the largest key, and sorted by a network of compare-exchange steps, each a minimum and a maximum. With :math:` M geq W ` the keys are held by columns, the key of index :math:` g = i M + h ` in the lane i of the register h: the columns are sorted by the odd-even merge sort of Batcher, register against register (63 comparators for M = 16, each a minimum and a maximum of whole registers), then merged by the bitonic network in its variant whose comparators all go upwards, the index g compared first with :math:` g oplus ( K - 1 ) ` for blocks of K keys and then with :math:` g oplus J ` for :math:` J = K / 4 , dots , 1 , a step between registers for J < M and within them, by a shuffle of the lanes, otherwise, and at last each block of W registers is transposed by :math: log_2 W ` steps of exchanges of blocks of lanes. The steps within registers, the dearer ones (a shuffle besides the minimum and the maximum), are then :math:` frac{1}{2} log_2 W ( log_2 W - 1 ) ` in all, besides a reversal per merge (one permutation of the lanes on AVX-512) and the transposition, 14 for M = W = 16 against the 26 of the bitonic network on registers held by rows, which the smaller networks use, with constant masks of the lanes that keep the minimum. On AVX-512 the column network also serves :math:` W / 2 leq M < W : each block of M lanes is transposed by :math: log_2 M ` steps, after which the lanes :math:` [ c M , c M + M ) ` of the register h hold the M keys from :math:` ( c M + h ) M `, each block written by a masked store.

  • Two sorted runs are merged in the registers by mergeRuns(), as in the merge sort of Chhugani et al.: the register of the keys carried over is merged with the next register of the run whose next key is smaller (the second one reversed, a minimum and a maximum, then the steps of a bitonic merge within each register), the smaller W keys written and the larger carried; the writes never overtake the reads, so that one run may stay in place while the other is a copy aside, forward from the smallest keys or backward from the largest. sort() merges with it the runs of the integers of 32 bits [see File Sort.h].

The instructions are chosen when compiling: AVX-512 (F) if AVX512F is defined, AVX2 if AVX2 is, with GCC or Clang; otherwise, or with ADS_VECTOR_SORT=0, a register is an array of W = 32 / w lanes for keys of w bytes, the same algorithm in portable code, which the compiler vectorizes as it can. kVectorSort tells whether the registers are real.

vectorQuickSort() is not stable (equal integers cannot be told apart, but -0 and +0 can). The contracts [see File Contract.h]: the vector ends with the same items sorted, an audit. The functions are defined in VectorQuickSort.tpp.

  1. Bramas, A novel hybrid quicksort algorithm vectorized using AVX-512 on Intel Skylake, International Journal of Advanced Computer Science and Applications 8(10), article 44, 2017, doi:10.14569/IJACSA.2017.081044

  1. Gueron, V. Krasnov, Fast quicksort implementation using AVX instructions, The Computer Journal 59(1), 83-90, 2016, doi:10.1093/comjnl/bxv063

  1. Wassenberg, M. Blacher, J. Giesen, P. Sanders, Vectorized and performance-portable quicksort, Software: Practice and Experience 52(12), 2684-2699, 2022, doi:10.1002/spe.3142

  1. Chhugani, A. D. Nguyen, V. W. Lee, W. Macy, M. Hagog, Y.-K. Chen, A. Baransi, S. Kumar, P. Dubey, Efficient implementation of sorting on multi-core SIMD CPU architecture, Proceedings of the VLDB Endowment 1(2), 1313-1324, 2008, doi:10.14778/1454159.1454171

    1. Batcher, Sorting networks and their applications, Proceedings of the AFIPS Spring Joint Computer Conference 32, 307-314, 1968, doi:10.1145/1468075.1468121

    1. Musser, Introspective sorting and selection algorithms, Software: Practice and Experience 27(8), 983-993, 1997

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions

Defines

Variables