Your code is fast – if you're lucky
A seemingly minor change in C code syntax (from two statements to a compact *ptr++ = val; form) surprisingly unlocked a 6x performance boost for a highly optimized Quicksort. This unexpected outcome highlights the profound impact compiler internals and specific code patterns can have on generating efficient, branchless machine code. It sparked a lively Hacker News discussion on compiler intelligence, low-level optimization strategies, and the delicate balance between high-level code clarity and underlying hardware performance.
The Lowdown
The author demonstrates a custom Quicksort implementation, already incorporating advanced techniques like sorting networks and loop unrolling, initially performing slower than std::sort. A 'cosmetic' rewrite of pointer assignments within a loop—from explicit *ptr = val; ptr++; to the more concise *ptr++ = val;—unexpectedly propelled the custom sort to be nearly twice as fast as std::sort, achieving a 6x speedup over its original version.
- The original Quicksort code, despite meticulous micro-optimizations, performed poorly (4.39s for 50 million doubles on M1 Clang) compared to C++'s
std::sort(1.33s). - The critical change involved simplifying
if (condition) { *lwr = x; lwr++; } else { *sw = x; sw++; }toif (condition) *lwr++ = x; else *sw++ = x;. - This seemingly minor syntactic adjustment caused Clang to generate fundamentally different machine code: the slower version used conditional branches, while the faster version employed branchless
csel(conditional select) instructions on ARM orcmov(conditional move) on x86. - The article illustrates the generated assembly, showing how
cselavoids branch prediction penalties, explaining the drastic performance improvement. - Notably, GCC did not exhibit this 'quirk,' consistently generating the slower branch-based code regardless of the syntax style.
This case study serves as a potent reminder that compiler-specific behaviors and the minutiae of code expression can profoundly influence performance, often in ways that defy intuitive expectations for semantic equivalence.
The Gossip
Compiler's Cryptic Capabilities
Commenters were deeply puzzled by why two semantically equivalent C code snippets result in such vastly different compiler outputs. The discussion delved into compiler internals, suggesting that the difference might stem from how the compiler's Abstract Syntax Tree (AST) represents the two forms, leading to different pattern recognition by optimization passes. Some speculated it's a 'compiler bug' or an overly conservative optimization strategy, while others pointed out that certain optimization passes might be designed to recognize specific, compact patterns more readily for correctness or performance reasons, especially regarding memory ordering in multi-threaded contexts.
Mastering Machine Mechanics
Many programmers expressed a desire to understand these low-level optimization techniques. The consensus was that true mastery comes from understanding computer architecture and hardware directly, not just compiler magic. Recommendations included reading books like 'Computer Organization and Design,' exploring resources like Godbolt to see generated assembly, and even practical experience debugging kernel core dumps. The key insight is that compilers optimize for specific patterns, and understanding these patterns (and the underlying hardware) is crucial for writing truly high-performance code.
Quicksort's Quirks & Benchmarking Blunders
A significant thread debated the appropriateness of Quicksort for this benchmark, given its variable O(N log N) average performance and potential O(N^2) worst-case. Critics argued that the results might be influenced by the random input data distribution, suggesting the code is 'fast if you picked a fast case for it.' The author clarified that the test's intent was to measure machine code generation for a hot loop with consistent data, not Quicksort's algorithmic complexity across varied inputs, and that the chosen pivot strategy provides near O(N log N) performance in practice.
Compiler Conservatism & Developer Control
The conversation extended to whether compilers should be 'smarter' or if developers need more explicit control over optimizations. Some argued that such subtle dependencies on syntax make optimizations fragile and can lead to 'unpredictable performance outcomes.' There was a call for better mechanisms to express optimization expectations (e.g., 'this loop is expected to be vectorized') so that compilers could issue errors if expectations aren't met, contrasting with past failed attempts like `register` and `inline` keywords. The trade-off between portable high-level code and target-specific performance was a central point.