8 ms·

Why does this code execute more slowly after strength-reducing multiplications?

434 points by ttsiodras 4y ago

deleted 4y ago
[deleted]
ummonk 4y ago
The addition based version should be hand vectorizable if you do the math to figure out the increment based on vector sizes.
btdmaster 4y ago
I'm running into an interesting result -- on my machine, the fast version runs at the same speed at LEN=1000000 (the default in the sample), but starts running 1.5 times faster at LEN=500000 and ends up twice as fast at LEN=100000 and lower. This is with gcc -O3. Why could this be?
- rasz 4y ago
  cache size pushing you out to high latency memory
AtNightWeCode 4y ago
On older arcs there is also a cost for casting int to float. Not like float to int but anyway. The general advice when I worked with CG was to use deltas in iterations.
dragontamer 4y ago
Tldr: 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 mysterious, often harder to see and use than explicitly SIMD code (like OpenCL or CUDA).
- parenthesis 4y ago
  How can one go about making one's code apt for a compiler to be able to do these kinds of things?
  - DangitBobby 4y ago
    I also wonder if there's any compiler that allows you to hint that you expect certain optinizations to occur (like vectorization), and if they do not, fails to compile at all.
  - dragontamer 4y ago
    You study autovectorizers, then you enable autovectorization warning flags, and carefully read your compilers output. If the compiler says autovectorization failed, you rewrite the code until the autovectorizer works. https://docs.microsoft.com/en-us/cpp/build/reference/qvec-report-auto-vectorizer-reporting-level?view=msvc-170 https://docs.microsoft.com/en-us/cpp/build/reference/qvec-re...
    - janwas 4y ago
      hm, I have had limited success with such nudging - it's certainly not a programming model with a predictable outcome. And as soon as the compiler or its flags are updated, maybe the situation changes.
  - skavi 4y ago
    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.
    - ummonk 4y ago
      That very much depends on access patterns. If you’re performing an operation I’ve ever object with a certain field, struct of array makes sense. If you’re doing an operation which uses many fields on some arbitrary dynamic randomly ordered subset of objects, then array of structs will yield better because at least you recover some memory locality.
savant_penguin 4y ago
What would be the difference in power consumption from each method? (Would it be always better to multiply? If so why not multiply by one?)
- varajelle 4y ago
  The problem here is that the additions depends on values computed in the previous iteration of the loop. The version with multiplication is faster because there is no dependencies with the previous iteration so the CPU has more freedom scheduling the operations. The power consumption is a good question.
  - MikeHolman 4y ago
    Scheduling plays a part, but it is definitely more about vectorization.
    - kllrnohj 4y ago
      It's almost certainly more about scheduling than vectorization. The data dependencies is going to constantly stall the CPU pipeline, so it's just not able to retire instructions very quickly. The SIMD part is almost certainly a red herring. It's helping, but it's far from why it's so much faster. Tiger Lake can retire 4 plain ol' ADD operations per clock[1] - you don't need SIMD / vectorization to get instruction level parallelism. But you do need to ensure there's no data dependencies. The data dependency here is the 90% cost. The SIMD is just the cherry on top. 1: https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf
- dento 4y ago
  Usually faster version always consumes less power, as this allows the core more time in sleep. This is known as the race-to-sleep or race-to-idle paradox.
- chaboud 4y ago
  The general rule to follow in power consumption on CPUs is to do your work quickly and then get to sleep. Propagating clock is going to eat the bulk of your power. The mild difference between multiply and add in actual usage is inside the noise (orders of magnitude smaller). The bigger penalty in this case is the inter-iteration dependency, which, vectorized or not, runs the risk of holding up the whole show due to pipelining. As a performance rule on modern processors: avoid using the result of a calculation as long as you reasonably can (in tight loops... You don't want to be out of cache.). Have fun threading the needle!
ww520 4y ago
Besides the autovectorization, the second version also has two additional assignments. Depending on how the storage is used for these, whether it’s to registers, L1/L2, or stack, there might be performance hit.
- ummonk 4y ago
  Why would it be in anything but registers?
deleted 4y ago
[deleted]
Beltiras 4y ago
Is 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.
- Retr0id 4y ago
  How does this relate to tail calls?
  - Beltiras 4y ago
    Tail calls have a collector that accumulates the result, very similar pattern as in the example. It's an optimization in LISP and similar languages.
- readams 4y ago
  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.
  - lvass 4y ago
    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.
sampo 4y ago
In 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.
- dreamcompiler 4y ago
  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.
- dang 4y ago
  Ok, we've reverted the title to what the article says. (Submitted title was "Multiplications and 2 additions are faster than 2 additions")
- sillysaurusx 4y ago
  More generally, “stop storing state, unless it makes the program less complicated.” The first version is simple. The second version is more complicated. The simplicity is because the first version can be represented as a formula; imagine trying to write out the second version as a formula, and the complexity becomes obvious. (The addition loop would have to be written as a recurrence relation, which of course means every step depends on the previous step.) Complexity isn’t always obvious. It’s sometimes common in C programs to write a loop like dst[index++] = src[i], particularly in deeply nested for-loops. In my experience it’s almost always worth rewriting it so that the indices are computable entirely from the loop iteration variables, with no state. It helps you build a mental map of the operations, because you can think of it in terms of geometry (memcpy = copying rectangles onto other larger rectangles) whereas when the index is stateful it becomes quite a lot harder to visualize in higher dimensions. At least for me. We’ve been building a compiler at Groq for our custom ML hardware. (Roughly, “turn pytorch into our ISA with no extra programmer effort.”) I used to think of posts like this as “Well, modern compilers are so fast, who really cares about autovectorization?” — it turns out you care when you need to write your own compiler. :) MLIR is pretty cool. It makes a lot of transformations like this pretty easy. The MLIR “krnl” dialect can also automatically transform nested loops into tiled iteration. Graphics devs will know what I mean — no need to loop over 8x8 blocks of pixels manually, just write “for x in range(width): for y in range(height): …” and set the block size to 8.
layer8 4y ago
TLDR: Due to loop-carried dependencies preventing parallelized execution: https://en.wikipedia.org/wiki/Loop_dependence_analysis#Loop-carried_dependence_vs._loop_independent_dependence https://en.wikipedia.org/wiki/Loop_dependence_analysis#Loop-... In the 2 additions version, computation of the next iteration depends on the results of the preceding iteration. In the multiplication version, the computations are independent for each iteration, enabling parallel execution (by SIMD and/or pipelined/superscalar execution).
mlatu 4y ago
you could try to prefill first cell with -(A+B), then each cell gets a+b+c and in a loop for (j=0; j<i; j++): (A+A) but im to lazy to test that
someweirdperson 4y ago
I doubt repeatedly adding floating point numbers is a good idea. With every addition the sum increases further away from the addend, and with their growing relative difference problems grow as well. Just because the algebra works it doesn't guarantee that the code does, too.
- sray 4y ago
  The author of the post is aware of this. They explicitly say that is not the point of the question.
- ascar 4y ago
  Your points are factually correct, but in practice not a big concern, if your floating point value is much more precise than necessary for the numbers used. E.g. if you use doubles for the range of 32bit integers even adding 1.0 2 billion times to 2 billion still ends up at 4 billion. Even adding 1.0 20 billion times to 20 billion ends up at 40 billion. Now adding 0.1 20 billion times to 2 billion ends up 1908 short on my CPU, i.e. about 19080 absorptions/rounding errors occured. You need some serious differences and amount of operations to actually trigger errors.
  - kzrdude 4y ago
    You're talking about the best case, but we need to take the reasonable worst cases into account, where x + y nearly cancel etc.
- LAC-Tech 4y ago
  The algebra works for reals, binary floating point is a different beast!
oconnor663 4y ago
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-502507027 https://github.com/sneves/blake2-avx2/pull/4#issuecomment-50...
- ummonk 4y ago
  The pipelining issue is interesting because my reaction becomes “shouldn’t the CPU just come with a larger vector size and then operate on chunks within the vector to optimize pipelining?” but then I realize I’m just describing a GPU.
dgb23 4y ago
If 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 https://www.youtube.com/watch?v=LKtk3HCgTa8
manholio 4y ago
Seems like you can have the cake and eat it too, by manually parallelizing the code to something like this: double A4 = A+A+A+A; double Z = 3A+B; double Y1 = C; double Y2 = A+B+C; int i; // ... setup unroll when LEN is odd... for(i=0; i<LEN; i++) { data[i] = Y1; data[++i] = Y2; Y1 += Z; Y2 += Z; Z += A4; } Probably not entirely functional as written, but you get the idea: unroll the loop so that the data dependent paths can each be done in parallel. For the machine being considered, a 4 step unroll should achieve maximum performance, but of course, you get all the fun things that come with hard-coding the architecture in your software.
- sounds 4y ago
  Looks like someone wrote pretty good parallelizable code on the original question, here: https://stackoverflow.com/a/72333152 https://stackoverflow.com/a/72333152
  - im3w1l 4y ago
    That code isn't faster for me while Manholios's is. And his gets even faster with 4x parallelization.
- im3w1l 4y ago
  The idea is right, but some details are wrong. You need a separate Z for each Y. But even if that's done, it is indeed faster.
  - manholio 4y ago
    I'm shocked and aghast to hear you found a bug in my code - I assure you it compiled and ran flawlessly in my brain.
mgaunard 4y ago
It's fairly obvious: the rewrite prevents parallelization because floating-point isn't associative. You'd need to parallelize it explicitly (which can be done by just unrolling the loop).
oezi 4y ago
Funny that this question gained 180 upvotes in 10 days when it also could have received the reverse for being quite lacking in things the author has tried to figure the (rather obvious) data dependency out on his own.
- LAC-Tech 4y ago
  I'll put my hand up and say none of the post or answers were obvious to me. I found it all very interesting.
benreesman 4y ago
Oh man I have been smoked by data-dependency like this so many times. I've gotten a lot better over the years at "seeing" data dependencies in godbolt or whatever, but it still slips through by my code and that of my colleagues way more often than I'd like. Is anyone aware of good tooling for automatically catching this sort of thing even some of the time?
- slaymaker1907 4y ago
  I'm not sure if there are existing rules for it, but you could write a CodeQL query looking for data dependencies in loops. Obviously dependencies are sometimes required, but it at least could tell your they were there.
- ummonk 4y ago
  Don’t use state in a loop unless you have to? Avoiding such use of state also makes code a lot easier to read and debug - the performance benefits are really just a bonus.
diarrhea 4y ago
Is this relevant to interpreted languages as well? I’m thinking perhaps Pythons bytecode could have similar optimisations.
tomxor 4y ago
Vectorisation is not free, There is one other dimension to optimise for: power. The suggested "slower" optimisation does fundamentally use less instructions. Chucking more hardware at parallelisable problems makes it run faster but does not necessarily reduce the power requirements much because there are fundamentally the same number of instructions, it's just gobbling up the same power over a shorter period of time - The "slower" serial algorithm uses less instructions and in theory less power in total. Disclaimer: I mean power vs speed fundamentally in theory, in practice there may be no measurable difference depending on the particular CPU and code.
- ascar 4y ago
  Do you have a reference for that? I googled and I couldn't find anything good. While it might sound intuitive that SIMD instructions consume more power, I don't think that's necessarily true to a relevant degree in practice. My understanding is CPU power consumption is mostly tied to inefficiences that cause energy loss via heat, while the actual computation doesn't consume any energy per se. So electrons traveling a more complex path probably cause somehwat more energy loss as there is more wire/transistors to pass. But most of the total loss doesn't actually occure in the ALU. Empirically from what you can see operating systems do, the most effective way of consuming less power is actually running on a slower clock cycle and the most effective way to achieve that is getting work done faster and that's not tied to the number of instructions. The Stackoverflow question here [1] seems to suggest that SIMD vs no SIMD has a neglectable overhead compared to entering a lower power state sooner. [1] https://stackoverflow.com/questions/19722950/do-sse-instructions-consume-more-power-energy https://stackoverflow.com/questions/19722950/do-sse-instruct...
  - tomxor 4y ago
    I think in summary what you are alluding to is instruction decoding and scheduling as the sibling comment points out, which is indeed a large cost in both speed and power. > SIMD vs no SIMD has a neglectable overhead compared to entering a lower power state sooner. Yes on the same CPU as I suggested, real world difference may be unmeasurable. However note that this particular case is interesting because it's not comparing fewer serial multiplies to more SIMD multiplies, it's comparing SIMD multiplies to no multiplies but with a serial constraint due to variable dependence... i.e it's SIMD vs no multiply without any other difference in number or type of ALU ops... which again could make no difference on a big x86 in practice, but it would be interesting to know. All of this changes if you are coding for a lower power device and have choice of hardware.
foxes 4y ago
It’s almost like managing the state yourself on a modern cpu is a complicated task. Automatic vectorisation, reordering, etc can all be more easily done to a pure declarative program. Imperatively managing the state and the control flow with an ancient language like C etc really does no longer reflect the underlying hardware which is significantly more advanced.
mvuksano 4y ago
I think it's worth pointing out that the reason why these two examples execute at different speed is due to how compiler translated code AND because CPU was able to parallelize work. Compilers take knowledge about target platform (e.g. instruction set) and code and translate it into executable code. Compiler CAN (but doesn't have to) rewrite code only if it ALWAYS produces the same result as input code. I feel like last 110-15 years (majority of) people have stopped thinking about specific CPU and only think about ISA. That works for a lot of workloads but in recent years I have observed that there is more and more interest in how specific CPU can execute code as efficiently as possible. If you're interested in the kind of optimizations performed in the example you should check out polyhedral compilation (https://polyhedral.info/ https://polyhedral.info/) and halide (https://halide-lang.org/ https://halide-lang.org/). Both can be used to speed up certain workloads significantly.
shp0ngle 4y ago
For fun, I tried this in go on M1 Mac (basically because benchmarking in go is so easy) And... the two codes runs with exactly the same speed, on M1 Mac, with go. edit: of course, with go, you can manually parallelize the faster option with goroutines... but that does something else, doesn't it. (and it's 500x faster.)
- hayley-patton 4y ago
  Does the Go compiler auto-vectorise? Vectorisation appears to have been the cause of the weird performance.
  - shp0ngle 4y ago
    No, I don't think so.
lawrenceyan 4y ago
Given that in terms of “absolute work” done, the optimization does hold true, is there any situation where it would be beneficial to implement this? (Super low energy processors, battery powered, etc?
- pjscott 4y ago
  Certainly! It makes sense in processors that don't do SIMD or speculative execution. There are a lot of those, but mostly for embedded stuff.
  - formerly_proven 4y ago
    Those are also CPUs were multiplication is most likely to be significantly more expensive, or not implemented in hardware at all (though almost everything has a multiplier these days).
  - kllrnohj 4y ago
    > or speculative execution This isn't actually taking advantage of speculative execution that much. The only speculation here would be in the predicting the loop repeats, which loop unrolling would mostly negate for CPUs that don't do speculative execution. The data dependency issue, however, would still be a punishing factor. You'd need a CPU that isn't superscalar, which does exist but is increasingly less common (even 2014's Cortex-M7 was superscalar, although it kinda sounds like ARM backed off on that for later Cortex M's?) Also many low-end / embedded CPUs that are in-order will still do branch prediction.
arunprakash01 4y ago
paradite 4y ago
Is this kind of parallelization possible on only compiled language? Or is it also possible for interpreted language like JavaScript?
- garethrowlands 4y ago
  The same considerations apply, though not always. JavaScript can be JIT compiled, though the JIT might not make the same optimisations as a C compiler. It's running on the same CPU though.
ribit 4y ago
First: we need to finally stop the harmful myth that floating point multiplication is slower than addition. This has not been true for a long while. Second: why are so many people insisting that the loop is auto-vectorised? Is there any evidence to that? Data dependencies alone explain the observed performance delta. Auto-vectorization would have resulted in a higher speedup.
andyjohnson0 4y ago
I curious about how an optimiser determines that a block of code can be vectorised. It's trivial to see this in the initial version of compute() but I'm not sure how an optimiser does this. Is it as simple as checking that A, B, and C are cost? And how far would an optimiser typically take its analysis? For example, if B was defined inside the loop as (non -const) A * 2 ? Or as A * f() , where f() always returns 2, maybe using a constant or maybe a calculation etc. Seems like a very hard problem,
desperate 4y ago
How would the energy cost of the two methods compare?

434 points by ttsiodras 4y ago

deleted 4y ago

[deleted]

The addition based version should be hand vectorizable if you do the math to figure out the increment based on vector sizes.

btdmaster 4y ago

I'm running into an interesting result -- on my machine, the fast version runs at the same speed at LEN=1000000 (the default in the sample), but starts running 1.5 times faster at LEN=500000 and ends up twice as fast at LEN=100000 and lower. This is with gcc -O3. Why could this be?

rasz 4y ago
cache size pushing you out to high latency memory

AtNightWeCode 4y ago

On older arcs there is also a cost for casting int to float. Not like float to int but anyway. The general advice when I worked with CG was to use deltas in iterations.

dragontamer 4y ago

Tldr: 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 mysterious, often harder to see and use than explicitly SIMD code (like OpenCL or CUDA).

parenthesis 4y ago
How can one go about making one's code apt for a compiler to be able to do these kinds of things?
- DangitBobby 4y ago
  I also wonder if there's any compiler that allows you to hint that you expect certain optinizations to occur (like vectorization), and if they do not, fails to compile at all.
- dragontamer 4y ago
  You study autovectorizers, then you enable autovectorization warning flags, and carefully read your compilers output. If the compiler says autovectorization failed, you rewrite the code until the autovectorizer works. https://docs.microsoft.com/en-us/cpp/build/reference/qvec-report-auto-vectorizer-reporting-level?view=msvc-170 https://docs.microsoft.com/en-us/cpp/build/reference/qvec-re...
  - janwas 4y ago
    hm, I have had limited success with such nudging - it's certainly not a programming model with a predictable outcome. And as soon as the compiler or its flags are updated, maybe the situation changes.
- skavi 4y ago
  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.
  - ummonk 4y ago
    That very much depends on access patterns. If you’re performing an operation I’ve ever object with a certain field, struct of array makes sense. If you’re doing an operation which uses many fields on some arbitrary dynamic randomly ordered subset of objects, then array of structs will yield better because at least you recover some memory locality.

savant_penguin 4y ago

What would be the difference in power consumption from each method? (Would it be always better to multiply? If so why not multiply by one?)

varajelle 4y ago
The problem here is that the additions depends on values computed in the previous iteration of the loop. The version with multiplication is faster because there is no dependencies with the previous iteration so the CPU has more freedom scheduling the operations. The power consumption is a good question.
- MikeHolman 4y ago
  Scheduling plays a part, but it is definitely more about vectorization.
  - kllrnohj 4y ago
    It's almost certainly more about scheduling than vectorization. The data dependencies is going to constantly stall the CPU pipeline, so it's just not able to retire instructions very quickly. The SIMD part is almost certainly a red herring. It's helping, but it's far from why it's so much faster. Tiger Lake can retire 4 plain ol' ADD operations per clock[1] - you don't need SIMD / vectorization to get instruction level parallelism. But you do need to ensure there's no data dependencies. The data dependency here is the 90% cost. The SIMD is just the cherry on top. 1: https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf
dento 4y ago
Usually faster version always consumes less power, as this allows the core more time in sleep. This is known as the race-to-sleep or race-to-idle paradox.
chaboud 4y ago
The general rule to follow in power consumption on CPUs is to do your work quickly and then get to sleep. Propagating clock is going to eat the bulk of your power. The mild difference between multiply and add in actual usage is inside the noise (orders of magnitude smaller). The bigger penalty in this case is the inter-iteration dependency, which, vectorized or not, runs the risk of holding up the whole show due to pipelining. As a performance rule on modern processors: avoid using the result of a calculation as long as you reasonably can (in tight loops... You don't want to be out of cache.). Have fun threading the needle!

ww520 4y ago

Besides the autovectorization, the second version also has two additional assignments. Depending on how the storage is used for these, whether it’s to registers, L1/L2, or stack, there might be performance hit.

ummonk 4y ago
Why would it be in anything but registers?

deleted 4y ago

[deleted]

Beltiras 4y ago

Is 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.

Retr0id 4y ago
How does this relate to tail calls?
- Beltiras 4y ago
  Tail calls have a collector that accumulates the result, very similar pattern as in the example. It's an optimization in LISP and similar languages.
readams 4y ago
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.
- lvass 4y ago
  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.

sampo 4y ago

In 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.

dreamcompiler 4y ago
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.
dang 4y ago
Ok, we've reverted the title to what the article says. (Submitted title was "Multiplications and 2 additions are faster than 2 additions")
sillysaurusx 4y ago
More generally, “stop storing state, unless it makes the program less complicated.” The first version is simple. The second version is more complicated. The simplicity is because the first version can be represented as a formula; imagine trying to write out the second version as a formula, and the complexity becomes obvious. (The addition loop would have to be written as a recurrence relation, which of course means every step depends on the previous step.) Complexity isn’t always obvious. It’s sometimes common in C programs to write a loop like dst[index++] = src[i], particularly in deeply nested for-loops. In my experience it’s almost always worth rewriting it so that the indices are computable entirely from the loop iteration variables, with no state. It helps you build a mental map of the operations, because you can think of it in terms of geometry (memcpy = copying rectangles onto other larger rectangles) whereas when the index is stateful it becomes quite a lot harder to visualize in higher dimensions. At least for me. We’ve been building a compiler at Groq for our custom ML hardware. (Roughly, “turn pytorch into our ISA with no extra programmer effort.”) I used to think of posts like this as “Well, modern compilers are so fast, who really cares about autovectorization?” — it turns out you care when you need to write your own compiler. :) MLIR is pretty cool. It makes a lot of transformations like this pretty easy. The MLIR “krnl” dialect can also automatically transform nested loops into tiled iteration. Graphics devs will know what I mean — no need to loop over 8x8 blocks of pixels manually, just write “for x in range(width): for y in range(height): …” and set the block size to 8.

layer8 4y ago

TLDR: Due to loop-carried dependencies preventing parallelized execution: https://en.wikipedia.org/wiki/Loop_dependence_analysis#Loop-carried_dependence_vs._loop_independent_dependence https://en.wikipedia.org/wiki/Loop_dependence_analysis#Loop-... In the 2 additions version, computation of the next iteration depends on the results of the preceding iteration. In the multiplication version, the computations are independent for each iteration, enabling parallel execution (by SIMD and/or pipelined/superscalar execution).

mlatu 4y ago

you could try to prefill first cell with -(A+B), then each cell gets a+b+c and in a loop for (j=0; j<i; j++): (A+A) but im to lazy to test that

someweirdperson 4y ago

I doubt repeatedly adding floating point numbers is a good idea. With every addition the sum increases further away from the addend, and with their growing relative difference problems grow as well. Just because the algebra works it doesn't guarantee that the code does, too.

sray 4y ago
The author of the post is aware of this. They explicitly say that is not the point of the question.
ascar 4y ago
Your points are factually correct, but in practice not a big concern, if your floating point value is much more precise than necessary for the numbers used. E.g. if you use doubles for the range of 32bit integers even adding 1.0 2 billion times to 2 billion still ends up at 4 billion. Even adding 1.0 20 billion times to 20 billion ends up at 40 billion. Now adding 0.1 20 billion times to 2 billion ends up 1908 short on my CPU, i.e. about 19080 absorptions/rounding errors occured. You need some serious differences and amount of operations to actually trigger errors.
- kzrdude 4y ago
  You're talking about the best case, but we need to take the reasonable worst cases into account, where x + y nearly cancel etc.
LAC-Tech 4y ago
The algebra works for reals, binary floating point is a different beast!

oconnor663 4y ago

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-502507027 https://github.com/sneves/blake2-avx2/pull/4#issuecomment-50...

ummonk 4y ago
The pipelining issue is interesting because my reaction becomes “shouldn’t the CPU just come with a larger vector size and then operate on chunks within the vector to optimize pipelining?” but then I realize I’m just describing a GPU.

dgb23 4y ago

If 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 https://www.youtube.com/watch?v=LKtk3HCgTa8

manholio 4y ago

Seems like you can have the cake and eat it too, by manually parallelizing the code to something like this: double A4 = A+A+A+A; double Z = 3A+B; double Y1 = C; double Y2 = A+B+C; int i; // ... setup unroll when LEN is odd... for(i=0; i<LEN; i++) { data[i] = Y1; data[++i] = Y2; Y1 += Z; Y2 += Z; Z += A4; } Probably not entirely functional as written, but you get the idea: unroll the loop so that the data dependent paths can each be done in parallel. For the machine being considered, a 4 step unroll should achieve maximum performance, but of course, you get all the fun things that come with hard-coding the architecture in your software.

sounds 4y ago
Looks like someone wrote pretty good parallelizable code on the original question, here: https://stackoverflow.com/a/72333152 https://stackoverflow.com/a/72333152
- im3w1l 4y ago
  That code isn't faster for me while Manholios's is. And his gets even faster with 4x parallelization.
im3w1l 4y ago
The idea is right, but some details are wrong. You need a separate Z for each Y. But even if that's done, it is indeed faster.
- manholio 4y ago
  I'm shocked and aghast to hear you found a bug in my code - I assure you it compiled and ran flawlessly in my brain.

mgaunard 4y ago

It's fairly obvious: the rewrite prevents parallelization because floating-point isn't associative. You'd need to parallelize it explicitly (which can be done by just unrolling the loop).

oezi 4y ago

Funny that this question gained 180 upvotes in 10 days when it also could have received the reverse for being quite lacking in things the author has tried to figure the (rather obvious) data dependency out on his own.

LAC-Tech 4y ago
I'll put my hand up and say none of the post or answers were obvious to me. I found it all very interesting.

benreesman 4y ago

Oh man I have been smoked by data-dependency like this so many times. I've gotten a lot better over the years at "seeing" data dependencies in godbolt or whatever, but it still slips through by my code and that of my colleagues way more often than I'd like. Is anyone aware of good tooling for automatically catching this sort of thing even some of the time?

slaymaker1907 4y ago
I'm not sure if there are existing rules for it, but you could write a CodeQL query looking for data dependencies in loops. Obviously dependencies are sometimes required, but it at least could tell your they were there.
ummonk 4y ago
Don’t use state in a loop unless you have to? Avoiding such use of state also makes code a lot easier to read and debug - the performance benefits are really just a bonus.

diarrhea 4y ago

Is this relevant to interpreted languages as well? I’m thinking perhaps Pythons bytecode could have similar optimisations.

tomxor 4y ago

Vectorisation is not free, There is one other dimension to optimise for: power. The suggested "slower" optimisation does fundamentally use less instructions. Chucking more hardware at parallelisable problems makes it run faster but does not necessarily reduce the power requirements much because there are fundamentally the same number of instructions, it's just gobbling up the same power over a shorter period of time - The "slower" serial algorithm uses less instructions and in theory less power in total. Disclaimer: I mean power vs speed fundamentally in theory, in practice there may be no measurable difference depending on the particular CPU and code.

ascar 4y ago
Do you have a reference for that? I googled and I couldn't find anything good. While it might sound intuitive that SIMD instructions consume more power, I don't think that's necessarily true to a relevant degree in practice. My understanding is CPU power consumption is mostly tied to inefficiences that cause energy loss via heat, while the actual computation doesn't consume any energy per se. So electrons traveling a more complex path probably cause somehwat more energy loss as there is more wire/transistors to pass. But most of the total loss doesn't actually occure in the ALU. Empirically from what you can see operating systems do, the most effective way of consuming less power is actually running on a slower clock cycle and the most effective way to achieve that is getting work done faster and that's not tied to the number of instructions. The Stackoverflow question here [1] seems to suggest that SIMD vs no SIMD has a neglectable overhead compared to entering a lower power state sooner. [1] https://stackoverflow.com/questions/19722950/do-sse-instructions-consume-more-power-energy https://stackoverflow.com/questions/19722950/do-sse-instruct...
- tomxor 4y ago
  I think in summary what you are alluding to is instruction decoding and scheduling as the sibling comment points out, which is indeed a large cost in both speed and power. > SIMD vs no SIMD has a neglectable overhead compared to entering a lower power state sooner. Yes on the same CPU as I suggested, real world difference may be unmeasurable. However note that this particular case is interesting because it's not comparing fewer serial multiplies to more SIMD multiplies, it's comparing SIMD multiplies to no multiplies but with a serial constraint due to variable dependence... i.e it's SIMD vs no multiply without any other difference in number or type of ALU ops... which again could make no difference on a big x86 in practice, but it would be interesting to know. All of this changes if you are coding for a lower power device and have choice of hardware.

foxes 4y ago

It’s almost like managing the state yourself on a modern cpu is a complicated task. Automatic vectorisation, reordering, etc can all be more easily done to a pure declarative program. Imperatively managing the state and the control flow with an ancient language like C etc really does no longer reflect the underlying hardware which is significantly more advanced.

mvuksano 4y ago

I think it's worth pointing out that the reason why these two examples execute at different speed is due to how compiler translated code AND because CPU was able to parallelize work. Compilers take knowledge about target platform (e.g. instruction set) and code and translate it into executable code. Compiler CAN (but doesn't have to) rewrite code only if it ALWAYS produces the same result as input code. I feel like last 110-15 years (majority of) people have stopped thinking about specific CPU and only think about ISA. That works for a lot of workloads but in recent years I have observed that there is more and more interest in how specific CPU can execute code as efficiently as possible. If you're interested in the kind of optimizations performed in the example you should check out polyhedral compilation (https://polyhedral.info/ https://polyhedral.info/) and halide (https://halide-lang.org/ https://halide-lang.org/). Both can be used to speed up certain workloads significantly.

shp0ngle 4y ago

For fun, I tried this in go on M1 Mac (basically because benchmarking in go is so easy) And... the two codes runs with exactly the same speed, on M1 Mac, with go. edit: of course, with go, you can manually parallelize the faster option with goroutines... but that does something else, doesn't it. (and it's 500x faster.)

hayley-patton 4y ago
Does the Go compiler auto-vectorise? Vectorisation appears to have been the cause of the weird performance.
- shp0ngle 4y ago
  No, I don't think so.

lawrenceyan 4y ago

Given that in terms of “absolute work” done, the optimization does hold true, is there any situation where it would be beneficial to implement this? (Super low energy processors, battery powered, etc?

pjscott 4y ago
Certainly! It makes sense in processors that don't do SIMD or speculative execution. There are a lot of those, but mostly for embedded stuff.
- formerly_proven 4y ago
  Those are also CPUs were multiplication is most likely to be significantly more expensive, or not implemented in hardware at all (though almost everything has a multiplier these days).
- kllrnohj 4y ago
  > or speculative execution This isn't actually taking advantage of speculative execution that much. The only speculation here would be in the predicting the loop repeats, which loop unrolling would mostly negate for CPUs that don't do speculative execution. The data dependency issue, however, would still be a punishing factor. You'd need a CPU that isn't superscalar, which does exist but is increasingly less common (even 2014's Cortex-M7 was superscalar, although it kinda sounds like ARM backed off on that for later Cortex M's?) Also many low-end / embedded CPUs that are in-order will still do branch prediction.

arunprakash01 4y ago

paradite 4y ago

Is this kind of parallelization possible on only compiled language? Or is it also possible for interpreted language like JavaScript?

garethrowlands 4y ago
The same considerations apply, though not always. JavaScript can be JIT compiled, though the JIT might not make the same optimisations as a C compiler. It's running on the same CPU though.

ribit 4y ago

First: we need to finally stop the harmful myth that floating point multiplication is slower than addition. This has not been true for a long while. Second: why are so many people insisting that the loop is auto-vectorised? Is there any evidence to that? Data dependencies alone explain the observed performance delta. Auto-vectorization would have resulted in a higher speedup.

andyjohnson0 4y ago

I curious about how an optimiser determines that a block of code can be vectorised. It's trivial to see this in the initial version of compute() but I'm not sure how an optimiser does this. Is it as simple as checking that A, B, and C are cost? And how far would an optimiser typically take its analysis? For example, if B was defined inside the loop as (non -const) A * 2 ? Or as A * f() , where f() always returns 2, maybe using a constant or maybe a calculation etc. Seems like a very hard problem,

desperate 4y ago

How would the energy cost of the two methods compare?