Show HN: Avoiding "if" makes Quicksort faster(easylang.online)

3 pointsby chrkahá 2 meses4 comments

easylang.online

Show HN: Avoiding "if" makes Quicksort faster

https://easylang.online/blog/qsort

4 comments

jjgreenhá 2 meses

In line 423 or the optimised code there's a typo: "sort2(e,i)" should be "sort2(i,e)"

chkashá 2 meses

That should give the same result.

anticleiadeshá 2 meses

branch-less programming is a fascinating area. you have used -O3. Possibly, the compiler is also vectorizing some parts of the code. I am curious to know the contribution of AVX/SIMD to the speed-up (i.e, how much speed-up avoiding branches "alone" yields)

chkashá 2 meses

You can take a look at this - it's fast even without vector operations, as long as you avoid the branches that are often predicted incorrectly.

https://easylang.online/blog/branchless