Your code is fast – if you're lucky
7 hours ago
- #quicksort algorithm
- #branchless programming
- #compiler optimization
- Modern compilers, particularly Clang, optimize loops using branch-free instructions when using certain programming styles.
- A Quicksort implementation with sorting networks and loop unrolling was initially slower than C++ std::sort.
- Rewriting a beginner-friendly if-statement into a compact C idiom (using post-increment operators) significantly improved performance.
- The 'cosmetic' change triggered Clang to replace branches with csel (conditional select) instructions, making the code branchless.
- On x86, Clang similarly generates branchless code using cmov, while GCC consistently produces slower branch-based versions.
- The optimized Quicksort became over 6 times faster than the original and nearly twice as fast as std::sort.