3 ms·

Thank you for such detailed analysis! Just curious to know which version of x86-simd-sort did you benchmark: release v1.0 or the top of main current branch? (I'

• Voultapher 3y ago
  Hi, hope you found this analysis helpful. I vendored the code Feb 16 2023 from the main branch.
  • rdevulap 3y ago
    Of course! Appreciate all the time you put in. I added a few more optimizations to qsort after that (see https://github.com/intel/x86-simd-sort/pull/33 https://github.com/intel/x86-simd-sort/pull/33), just wanted to know if your analysis took that into account.
  • rdevulap 3y ago
    Still using the simple way of getting the pivot though.
    • Voultapher 3y ago
      No matter how sophisticated the pivot selection is, you can always risk having some degenerate worst case. I recommend having something like a heapsort fallback after a certain recursion limit is reached, as do pdqsort, ipnsort and vqsort(I'm a little fuzzy what their fallback is, but they have one).
      • janwas 3y ago
        Yes, vqsort does indeed resort to Heapsort after too many recursions. I'd be surprised if that happens on real data, though, because we apply a lot more effort to the pivot selection. Would be curious to see any input distribution that triggers a fallback.