The part about data dependencies across loop iterations is fascinating to me, becuase it's mostly invisible even when you look at the generated assembly. There's a related optimization that comes up in implementations of ChaCha/BLAKE, where we permute columns around in a kind of weird order, because it breaks a data dependency for an operation that's about to happen: https://github.com/sneves/blake2-avx2/pull/4#issuecomment-50...
Why does this code execute more slowly after strength-reducing multiplications?
31–40 of 155 posts
Re: Why does this code execute more slowly after strength-reducing multiplications?
#32Tldr: autovectorizer transforms the first code into SIMD instructions, but the second into 64 bit instructions. SIMD is very powerful, and modern compilers can sometimes simd-ify your code automatically. ------- The second code can probably become SIMD as well, but it's beyond GCC's ability to autovectorizer it in that form. I kinda want to give it a go myself but don't have time today... Autovectorizers are mysterio…
both versions use SSE and are pipelined, the problem with the second one is data dependency, only two adds but the second one directly depends on the first ones result = stall
SSE includes "scalar" adds (addsd), which are a 1x floating point instruction. These are "non-SIMD" instructions, serving as a replacement for the legacy x87 instructions.
There is also "parallel" adds (addpd).
Carefully look at the assembly language, the 1st version uses parallel adds (addpd) and parallel multiplies. The 2nd version uses scalar adds (addsd)
The other major point is that the 2nd version uses a singular move qword (64-bit) per loop iteration, while the 1st version is using the full 128-bit move per loop iteration.
---------
SSE is used for scalar double-precision these days, because scalar-SSE is faster than x87 instructions... and better matches the standards (x87 had "higher precision" than the IEEE specs, so it has different results compared to other computers. SSE is closer to the specs)
Re: Why does this code execute more slowly after strength-reducing multiplications?
#33In the post, multiplications and 2 additions are not faster than 2 additions. The post compares (1) loop code that can be vectorized, as loop rounds are independent and do not depend on the result from the previous round, and (2) an "optimization" that makes calculations shorter, but also makes each loop round depend on the result of the previous round, so this cannot be vectorized.
The other issue is instruction-level parallelism, as another poster in TFA pointed out. Even within a single loop iteration the "unoptimized" code is more likely to exploit multiple ALUs if they exist, regardless of vectorization instructions.
Re: Why does this code execute more slowly after strength-reducing multiplications?
#34In the post, multiplications and 2 additions are not faster than 2 additions. The post compares (1) loop code that can be vectorized, as loop rounds are independent and do not depend on the result from the previous round, and (2) an "optimization" that makes calculations shorter, but also makes each loop round depend on the result of the previous round, so this cannot be vectorized.
Ok, we've reverted the title to what the article says.
(Submitted title was "Multiplications and 2 additions are faster than 2 additions")
Re: Why does this code execute more slowly after strength-reducing multiplications?
#35Tldr: autovectorizer transforms the first code into SIMD instructions, but the second into 64 bit instructions. SIMD is very powerful, and modern compilers can sometimes simd-ify your code automatically. ------- The second code can probably become SIMD as well, but it's beyond GCC's ability to autovectorizer it in that form. I kinda want to give it a go myself but don't have time today... Autovectorizers are mysterio…
> The second code can probably become SIMD as well, but it's beyond GCC's ability to autovectorizer it in that form. Usually, for floating point operations the compiler simply has no chance to do anything clever. NaNs, infinities and signed zero mean that even the most "obvious" identities don't actually hold. For example, x + 0 == x (where the == is bitwise) does not hold for x = -0.
so x+0 is 0?
Re: Why does this code execute more slowly after strength-reducing multiplications?
#36Is the implication here that tail call optimizations don't work anymore? They might seem to do the proper thing on the language level but the CPU just can't think that way.
Tail calls will work the same as loop. So if you have data dependencies between loop iterations or between tail-call-eliminated stack frames, then it will be slower than if you do not have those dependencies.
At least in some languages like Elixir and probably most FP languages, tail calls are practically only used when said dependencies exist, so their usage can perhaps be a marker for when some optimizations are not possible.
Re: Why does this code execute more slowly after strength-reducing multiplications?
#37Earlier quoted context omitted.
The other essential insight is that the second version has data dependencies between loop iterations. Without that, the tldr is incomplete.
That is the 'why' autovectorization fails. But it seems solvable in this case pretty easily actually. EDIT: Solvable by a human. I dunno much about compilers though, so I dunno if there's some kind of language issue that would prevent the unrolling of this dependency.
It's a different issue altogether. Even in vectorized code artificial data dependencies are an issue. E.g., for fast dot products (not actually usually applicable on most input sizes because of memory bandwidth, but related problems can be CPU bound) you'll roughly double your execution speed by alternating between two running totals and merging those at the end, and that gain is mostly orthogonal to the question of whether those running totals are vectorized.
Edit: And many modern compilers have been doing that particular optimization for a few years anyway, but it's still an important idea to keep in mind for any non-trivial graph of operations.
Re: Why does this code execute more slowly after strength-reducing multiplications?
#38Earlier quoted context omitted.
both versions use SSE and are pipelined, the problem with the second one is data dependency, only two adds but the second one directly depends on the first ones result = stall
SSE includes "scalar" adds (addsd), which are a 1x floating point instruction. These are "non-SIMD" instructions, serving as a replacement for the legacy x87 instructions. There is also "parallel" adds (addpd). Carefully look at the assembly language, the 1st version uses parallel adds (addpd) and parallel multiplies. The 2nd version uses scalar adds (addsd) The other major point is that the 2nd version uses a singul…
[deleted]
Re: Why does this code execute more slowly after strength-reducing multiplications?
#39If we ignore the details, then this is a perfect example of how simpler code should be preferred _by default_ over complex code. Both for performance and reasoning. In this case and often elsewhere, these are related things.
I'm taking the definition of simple and complex (or complected) from this talk[0]. In short: Simple means individual pieces are standing on their own, not necessarily easy or minimal. Complex means individual pieces are braided together into a whole.
The first code is simpler than the second. Just have a look at the two solutions and you see what I mean: The individual instructions in the first stand on their own and clearly declare what they mean as well. The second example is more complex, because each line/subexpression cannot be understood in isolation, there is an implicit coupling that requires the programmer _and_ the machine code interpreter to understand the whole thing for it to make sense. The CPU apparently fails at that and cannot optimize the machine instructions into more efficient microcode.
The example illustrates performance benefits of simpler code, but there are others too:
For example a type checker might be able to infer things from simpler code, but not from complex code. Again, complexity is about coupling, which can for example arise from making assumptions about things that are out of bounds or logic that happens in some other part of your program, which _this_ part relies on.
Things like these can either be outright rejected by a type checker or simply ignored and sometimes we can provide additional ceremony to make it happy. But there is always an underlying question when these issues arise: Can I express this in a simpler way? It's sometimes possible to describe rich semantics with simpler, more primitive types and explicit coordination.
Another thing that comes to mind are rich ORMs. They can be very convenient for common cases. But they have footguns for the general case, because they _complect_ so many things, such as validation, storage, domain rules, caching etc. And they are leaky abstractions because we have to do certain things in certain ways to avoid bloated SQL, N+1 etc.
They are not simple (and certainly not declarative) so we program against a black box. There are simpler "ORMs" that I very much like, but they typically only provide a minimal set of orthogonal features, such as query builders, and mapping results into plain data structures. It is simpler to use these kind of orthogonal tools.
Last but not least: Simple code can be pulled apart and changed more easily without having to worry about introducing problems. The substitution rule or referential transparency enables this by guaranteeing that each expression can be replaced by the value it will evaluate to. This also implies that other expressions that evaluate to the same value can be substituted freely.
[0] Simple Made Easy - Rich Hickey at Strangeloop 2011 https://www.youtube.com/watch?v=LKtk3HCgTa8
Re: Why does this code execute more slowly after strength-reducing multiplications?
#40Earlier quoted context omitted.
How can one go about making one's code apt for a compiler to be able to do these kinds of things?
A good way is to have your data arranged in structs of arrays rather than in arrays of structs. This allows the compiler to generate code which just loads in linear sections of memory to SIMD registers. It’s also just more cache efficient in general. Check out data oriented design if you aren’t already familiar.
Note that sometimes it's sufficient to have arrays of structs of arrays. That is you don't need to necessarily go whole hog.