Timeline for Generic QuickSort with Performance Optimised Swap for small types
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 30, 2020 at 0:46 | comment | added | Oliver Schönrock | Perhaps there is some compiler optimisation magic/inlining which is possible when the type is known in the local source file, but not possible when linking against a shared object file (memcpy) from libc? | |
| Dec 29, 2020 at 23:37 | comment | added | Oliver Schönrock |
That could well be, yes. Either way, I am super surprised that this "hack" (which is what it feels like) gets me 1.75 -> 2.2x performance improvements for small primitive types..switch or if/else, because the type will be same for entire sort, so the branch predictor is doing good work.
|
|
| Dec 29, 2020 at 23:34 | comment | added | Loki Astari |
marginally faster => branch prediction. The trouble is for times when the predication fails. switch will be faster in most situations.
|
|
| Dec 29, 2020 at 23:33 | comment | added | Oliver Schönrock |
Yeah, not so on my machine with above compilers. if/else is marginally faster than switch, don't ask me why.
|
|
| Dec 29, 2020 at 23:32 | comment | added | Oliver Schönrock |
Both gcc-9.3 and clang-10 exhibit the significant perf improvement from the size switch/if. gcc is faster overall, but has a > 2x difference. clang is slightly slower but has a ~ 1.75x difference.
|
|
| Dec 29, 2020 at 23:32 | comment | added | Loki Astari |
If you use if/else if/else you will loose performance. You could add #if sizeof(long) != sizeof(int)
|
|
| Dec 29, 2020 at 23:26 | comment | added | Oliver Schönrock |
I timed it with if / else if / else and it's marginally faster than with switch, so that's definitely the way to go.
|
|
| Dec 29, 2020 at 23:17 | comment | added | Oliver Schönrock |
Interesting point on the duplicate sizes. You're right. If I add a case for double (which is same size as long on my machine) then it fails to compile. Might be safer as an if / else if / else?
|
|
| Dec 29, 2020 at 23:12 | comment | added | Oliver Schönrock |
I am compiling with clang-10 on ubuntu 20.04 btw. clang -O3 -Wall -Wextra -Werror
|
|
| Dec 29, 2020 at 23:11 | comment | added | Oliver Schönrock |
I like the idea of time(NULL) as a fallback. I guess if I really cared enough about quality randomness, I probably shouldn't be using rand() anyway?
|
|
| Dec 29, 2020 at 23:08 | comment | added | Oliver Schönrock |
Yes I did time it. Without the sizeof() switch just using memcpy for small types it is twice as slow. As soon as I made swap() type aware the performance improved by 2x.
|
|
| Dec 29, 2020 at 23:06 | history | edited | Loki Astari | CC BY-SA 4.0 |
added 819 characters in body
|
| Dec 29, 2020 at 22:58 | comment | added | Oliver Schönrock | Sure thanks. Aware of that technique and use it often. | |
| Dec 29, 2020 at 22:57 | history | answered | Loki Astari | CC BY-SA 4.0 |