5 ms·
Branches also can't be vectorized, so going branch free can lead to a substantial speedup if you can use vector instructions (you might be doing twice the work,
by cozzyd 6y ago
Branches also can't be vectorized, so going branch free can lead to a substantial speedup if you can use vector instructions (you might be doing twice the work, but your vector instruction may let you do it 4-16 times faster).
- ncmncm 6y agoIndeed, AVX512 instructions can sort 16 int32 or well-behaved float values optimally, with no branches. It is a good final pass to any other algorithm.
- sesuximo 6y agoYou mean sorting within a vector register? Can you provide a link or something? I can't find info on this
- zbjornson 6y agoFor one: https://arxiv.org/abs/1704.08579 https://arxiv.org/abs/1704.08579
- sesuximo 6y agoThanks. It's kind of sad that there's no single instruction for horizontally sorting in vectors of integers. Horizontal merge/reduce would also be cool
- ncmncm 6y agoThe keyword to look for is "sorting network". See, for example, http://cs.brandeis.edu/~hugues/sorting_networks.html http://cs.brandeis.edu/~hugues/sorting_networks.html. There is a 28-step 16-input network there. It admits a direct translation to AVX-512 instructions. What is usually considered minimal differs from what is best for AVX512. AVX512 is happy to do 16 comparisons at each stage; its efficiency is limited only by the number of stages. Thus, a network that did more comparisons in fewer stages would be faster.
- mehrdadn 6y agoTrue! Though I have yet to see vectorized sorting in production...