News for hackers. Stuff that matters.
Re:Lomuto's Comeback by ncmncm on Sunday May 17, 2020 @05:15PM (#23215552)
Indeed, 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.
Re:Lomuto's Comeback by sesuximo on Sunday May 17, 2020 @10:31PM (#23217621)
You mean sorting within a vector register? Can you provide a link or something? I can't find info on this
Re:Lomuto's Comeback by ncmncm on Monday May 18, 2020 @08:21PM (#23229947)
The keyword to look for is "sorting network". See, for example, 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.

Re:Lomuto's Comeback by zbjornson on Monday May 18, 2020 @01:44AM (#23218786)
Re:Lomuto's Comeback by sesuximo on Monday May 18, 2020 @03:15PM (#23227110)
Thanks. 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