Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

stackoverflow.com

Post reply on HN
Print view View original

131–140 of 155 posts

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

#131

Post by btdmaster »

sampo wrote: post #102
dragontamer wrote: post #11

Earlier quoted context omitted.

Unroll the dependency until you are longer than the SIMD width. Ex: as long as i, i+1, i+2, i+3, ... i+7 are not dependent on each other, you can vectorize to SIMD-width 8. Or in other words: i+7 can depend on i-1 no problems.

> Unroll the dependency until you are longer than the SIMD width. > Ex: as long as i, i+1, i+2, i+3, ... i+7 are not dependent on each other, you can vectorize to SIMD-width 8. Do you mean like this? I get this to about as fast as the first "unoptimized" version in the SO post, but not faster. void compute() { const double A = 1.1, B = 2.2, C = 3.3; const double A128 = 128*A; double Y[8], Z[8]; Y[0] = C; Y[1] = A + B…

On my machine, your code is faster for smaller LEN values. I'm not sure why this is though.

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

#132

Post by tialaramex »

djmips wrote: post #110
kortex wrote: post #73

Earlier quoted context omitted.

> sometimes the fastest code deliberately introduces coupling, hardware specific cache shenanigans or unreadable hand written asm and/or inlined SIMD. >> this is a perfect example of how simpler code should be preferred _by default_ over complex code. Extra emphasis on *by default*. You are both on the same side of the coin. This is the essence of "premature optimization is the root of all evil". Simplicity should be…

Agreed. But can we stop using "premature optimization is the root of all evil". It has jumped the shark. I have more grief in my life because people adhere to this tenet. This is why we end up with the software equivalent of concrete airplanes. Ok it's your turn now. Make it fly!

Did you measure ? Because if you didn't measure you aren't optimising, you are just wanking.

And of course one reason we say premature is that most likely until the project is mostly finished you can't really measure because you don't have anything to measure.

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

#133

Post by andyjohnson0 »

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,

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

#134

Post by Cthulhu_ »

dreamcompiler wrote: post #78
sillysaurusx wrote: post #46

Earlier quoted context omitted.

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 e…

> stop storing state, unless it makes the program less complicated I had hoped that functional programming languages would lead us to automatic high-level parallelization. That hasn't happened much in the real world. But what we got is "write code like a functional programmer would even in a low-level language and the compiler and the ISA will parallelize it for you." That surprises me, but I'll take it.

Yeah I mean any functional operation on a list (I'm thinking of JS mainly) should be parallelizable, assuming the interpreter can determine that the order of execution does not matter.

I recall that Scala was the first language that introduced FP to me, and they made the developer explicitly tell that a functional operation could be done in parallel, after which the compiler and runtime would take care of the rest.

This was implemented in the extreme in a project that allowed you to write a functional style series of operations, which were translated to Hadoop map and reduce jobs, each of which could be executed in parallel at large scale. So very compact and succinct code, but very powerful.

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

#135

Post by projektfu »

magicalhippo wrote: post #48
sampo wrote: post #22

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.

> In the post, multiplications and 2 additions are not faster than 2 additions. Reminded me of when I tried to optimize some code using assembly on x86, maybe 8-10 years go. The compiler spit out a DIV [EDI] instruction which was inside a hot loop. I saw how I could easily rewrite it to use a register instead of the indirect memory access. So I did, and it was significantly slower, like 10-15%... I even took care to…

It would be interesting to test it on 486, Pentium, and Pentium Pro, as you get much different execution and caching behavior between those architectures.

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

#136

Post by projektfu »

userbinator wrote: post #88
athrun wrote: post #79

Earlier quoted context omitted.

Would it not be in Intel's best interest to have popular compilers be able to squeeze the most performance out of its own line of CPUs? I'm wondering how the incentives play out to keep this stuff private?

Intel sells a compiler. I've only used it briefly a long time ago, but its code generation was well ahead of MSVC at the time even for scalar (non-SIMD) stuff, and I remember GCC was far behind too (it would generate roughly the same performance in microbenchmarks, but far more bloated.)

https://en.wikipedia.org/wiki/Intel_C%2B%2B_Compiler

Interesting that it generates suboptimal code for non-Intel processors.

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

#137

Post by manholio »

im3w1l wrote: post #96
manholio wrote: post #43

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 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…

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.

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.

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

#138

Post by kllrnohj »

MikeHolman wrote: post #20
varajelle wrote: post #10

Earlier quoted context omitted.

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.

Scheduling plays a part, but it is definitely more about vectorization.

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

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

#139

Post by kllrnohj »

savant_penguin wrote: post #4

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?)

In this case since the slower one is spending most of its time stalled out, the faster one will probably be more power efficient. This isn't an AVX512 power-gobbling monstrosity issue.

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

#140

Post by kllrnohj »

pjscott wrote: post #115
lawrenceyan wrote: post #114

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?

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.

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

Post reply on HN