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

11–20 of 155 posts

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

#11

Post by dragontamer »

zeusk wrote: post #9
dragontamer wrote: post #2

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

How would the second approach be vectorized given each iteration's input has dependence on previous iteration's output??

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.

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

#12

Post by janwas »

dragontamer wrote: post #6
parenthesis wrote: post #3

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

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

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.

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

#13

Post by dragontamer »

loeg wrote: post #8
dragontamer wrote: post #2

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

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.

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

#14

Post by MauranKilom »

dragontamer wrote: post #2

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

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

#15

Post by dento »

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

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.

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

#19

Post by stormbrew »

dragontamer wrote: post #13
loeg wrote: post #8

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

I think the point GP is making is that even without vectorization, the data dependency causes stalls even in normal, single data instructions. That is, a data dependency between iterations of loops will hurt performance even for non-vectorizable calculations (or on CPUs with high ILP but no really good vector instructions, which granted is probably a small pool since both those things came about at about the same time).

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

#20

Post by MikeHolman »

varajelle wrote: post #10
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?)

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.
Post reply on HN