quadsort
quadsort copied to clipboard
scandum
Usage of bit masks and some code improvements
I've been looking at your code and noticed some improvements that can be made: Replacing all divisions of factors of 2 by Shift Right operations. Replacing all modulus operators of factors of 2 by bitmasks. Remove the swap_two function, using it on the spot, as it only currently appears in a total of 4 instances throughout the code. Around line 300, if you use pts[0] instead pts[cnt++] and initialize cnt = 5 you save some operations, reducing the computational intensity. Usage of constants whenever possible is always preferable for speedup! I will fork and submit a version later.
Thanks for checking it out. :)
As for bit operations, I decided not to use them because the performance gain was minimal or nonexistent while readability suffered.
Good call about using constants in that section, I'll go ahead and change that upstream since there've been a bunch of other changes since my last commit. I'll push out some updates in a few.
If you want, I can help you with reviewing code and ideas for the project as well. I feel like there's still some room for improvement :)
There's probably not much meat left on the bone, but I'm open to suggestions. I'll try to run some benchmarks in the next few days to check if a similar use of constants in the quad_swap routine is worth it.
I have uploaded an updated version of the code with your latest changes.
At the quad_swap function, instructions like if (cmp(&pta[0], &pta[2]) <= 0) became if (pta[2] > pta[0]), effectively reducing the amount of comparisons the code has to make.
I've tried other changes too but since they happened on code that only happened once, they seemed kind of pointless to me.
The cmp() call is needed however for string comparison support and qsort() compatibility.
Quadsort changed quite a bit since this discussion. Anyone interested in micro optimizations might want to have a look at:
https://github.com/scandum/tinysort