3 ms·

I like it as an exercise for understanding the CPU but is this stuff really useful in the real world - the example given is "optimised" away by GCC/clang withou

I like it as an exercise for understanding the CPU but is this stuff really useful in the real world - the example given is "optimised" away by GCC/clang without hacks. My guess is that if this is a good way to iterate over linked lists compilers would have optimised for this by now? Either through cleverness or hints added to your code.

dragontamer 5y ago
Compilers are 'just' graph transformations applied to code which probably leads to improved performance. A compiler can therefore optimize away unnecessary loads/stores, or recognize implicit parallelism and transform a loop into a SIMD loop. But a compiler will not change the logic of your code or add extra steps.
- matheusmoreira 5y ago
  > But a compiler will not change the logic of your code or add extra steps. Compilers can and do delete checks for null pointers, integer overflow... The stuff they do when they're faced with simple aliasing is honestly pretty crazy.
- andy_ppp 5y ago
  I mean this is quite easy to disprove - what do you think -funroll-loops is doing under the hood if not adding extra steps?
  - dragontamer 5y ago
    A "loop" is just a cycle in a graph. A -> B -> C -> A, hey look, its a cycle. Eventually A->D (where D exits the loop). So really node A has an edge going to B and D. Knowing that A has an edge to B and D, an equivalent transformation is A1->B1->C1->A2->B2->C2->A1, but also A1->D and A2->D. Both A1 and A2 have to still point at D. But A1 points to B1, and A2 points to B2. Etc. etc. That's all your compiler is doing, its reasoning about the graph and transforming it with actually... very simple rules. (Unfortunately, those rules are NP-complete so heuristics are used to make the compile times reasonable. NP-complete seems to keep coming about transformations associated with "simple" rules...) Then, we might see that some logic could make A2 not necessarily point to D (cutting out one possible jump statement). And that's where we get our optimization from: a simple reasoning about the graph which removes one instruction per 2-loops. Unroll to 8 and we get to 7-instructions (cmp/jump instructions) saved over every 8 loops. An "optimizing" compiler just reasons about this graph and all possible equivalent transformations (or at least, uses a heuristic to reason over a portion of equivalent transformations), and chooses such a graph transformation that minimizes various cost estimates. ------- That's the thing. Compilers can only transform the code-graph in ways that are "equivalent". Now yes, things get a bit weird with undefined behavior (and pointer-aliasing: assuming a lack of aliasing is needed for C/C++ compilers to make even the simplest of transformations. So that's a bit of a corner case). But that's the gist of what they're doing.
10000truths 5y ago
For a compiler to properly do the optimization detailed here would require it to have knowledge of runtime execution/memory access patterns. This might be done through profile-guided optimization, or by providing hints like __builtin_expect. That said, compilers are not magic boxes. Relying on your compiler for optimal codegen has diminishing returns as you approach the point where microarchitectural details start making a difference. Most people don't get to that point, so it's rarely an issue.
sly010 5y ago
This is not a 'static' optimization. It relies on knowledge that the compiler cannot decide by looking at the code (whether the linked list is _mostly_ laid out continuously). It might still be a very useful optimization in a JIT runtime. If your loop variable keeps increasing the same amount after every lookup, maybe rewrite the loop to add speculation...
groby_b 5y ago
The code relies on information not present in the program - "this linked list consist mostly of nodes sequentially arranged". If you could express that in your programming language, then yes, the compiler could optimize it. One could argue that the "weird" if statement is just that hint. And is it useful? It depends. There are plenty of situations where doubling your throughput is worth a lot of effort. There've been situations in my career where I've spent a month or two to shave a cycle or two. It's rare. But when you need it, you want the biggest bag of tricks you can bring, because it really matters :)

dragontamer 5y ago

Compilers are 'just' graph transformations applied to code which probably leads to improved performance. A compiler can therefore optimize away unnecessary loads/stores, or recognize implicit parallelism and transform a loop into a SIMD loop. But a compiler will not change the logic of your code or add extra steps.

matheusmoreira 5y ago
> But a compiler will not change the logic of your code or add extra steps. Compilers can and do delete checks for null pointers, integer overflow... The stuff they do when they're faced with simple aliasing is honestly pretty crazy.
andy_ppp 5y ago
I mean this is quite easy to disprove - what do you think -funroll-loops is doing under the hood if not adding extra steps?
- dragontamer 5y ago
  A "loop" is just a cycle in a graph. A -> B -> C -> A, hey look, its a cycle. Eventually A->D (where D exits the loop). So really node A has an edge going to B and D. Knowing that A has an edge to B and D, an equivalent transformation is A1->B1->C1->A2->B2->C2->A1, but also A1->D and A2->D. Both A1 and A2 have to still point at D. But A1 points to B1, and A2 points to B2. Etc. etc. That's all your compiler is doing, its reasoning about the graph and transforming it with actually... very simple rules. (Unfortunately, those rules are NP-complete so heuristics are used to make the compile times reasonable. NP-complete seems to keep coming about transformations associated with "simple" rules...) Then, we might see that some logic could make A2 not necessarily point to D (cutting out one possible jump statement). And that's where we get our optimization from: a simple reasoning about the graph which removes one instruction per 2-loops. Unroll to 8 and we get to 7-instructions (cmp/jump instructions) saved over every 8 loops. An "optimizing" compiler just reasons about this graph and all possible equivalent transformations (or at least, uses a heuristic to reason over a portion of equivalent transformations), and chooses such a graph transformation that minimizes various cost estimates. ------- That's the thing. Compilers can only transform the code-graph in ways that are "equivalent". Now yes, things get a bit weird with undefined behavior (and pointer-aliasing: assuming a lack of aliasing is needed for C/C++ compilers to make even the simplest of transformations. So that's a bit of a corner case). But that's the gist of what they're doing.

10000truths 5y ago

For a compiler to properly do the optimization detailed here would require it to have knowledge of runtime execution/memory access patterns. This might be done through profile-guided optimization, or by providing hints like __builtin_expect. That said, compilers are not magic boxes. Relying on your compiler for optimal codegen has diminishing returns as you approach the point where microarchitectural details start making a difference. Most people don't get to that point, so it's rarely an issue.

sly010 5y ago

This is not a 'static' optimization. It relies on knowledge that the compiler cannot decide by looking at the code (whether the linked list is _mostly_ laid out continuously). It might still be a very useful optimization in a JIT runtime. If your loop variable keeps increasing the same amount after every lookup, maybe rewrite the loop to add speculation...

groby_b 5y ago

The code relies on information not present in the program - "this linked list consist mostly of nodes sequentially arranged". If you could express that in your programming language, then yes, the compiler could optimize it. One could argue that the "weird" if statement is just that hint. And is it useful? It depends. There are plenty of situations where doubling your throughput is worth a lot of effort. There've been situations in my career where I've spent a month or two to shave a cycle or two. It's rare. But when you need it, you want the biggest bag of tricks you can bring, because it really matters :)