Your code is fast – if you're lucky
2 days ago
- #quicksort algorithm
- #branchless programming
- #compiler optimization
- 现代编译器，特别是 Clang，在使用某些编程风格时，会通过无分支指令来优化循环。
- 一个采用了排序网络和循环展开的快速排序实现，最初比 C++ 标准库的 std::sort 慢。
- 将一段初学者友好的 if 语句改写为紧凑的 C 语言惯用法（使用后置递增运算符）显著提高了性能。
- 这个“外观上”的改动触发 Clang 将分支替换为 csel（条件选择）指令，使代码变为无分支结构。
- 在 x86 架构上，Clang 类似地使用 cmov 指令生成无分支代码，而 GCC 则始终生成较慢的基于分支的版本。
- 优化后的快速排序比原始版本快了超过 6 倍，而且比 std::sort 也快了近一倍。