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

61–70 of 155 posts

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

#61

Post by MauranKilom »

sampo wrote: post #44
MauranKilom wrote: post #14

Earlier quoted context omitted.

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

> For example, x + 0 == x (where the == is bitwise) does not hold for x = -0. But when operating on floating point numbers, == is not bitwise, and -0 == +0.

If the user provides code where the result should be +0.0 and the compiler emits code that results in -0.0 (and the user has not explicitly enabled relaxed IEEE754 conformance), that's a bug in the compiler.

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

#63

Post by Sesse__ »

ncmncm wrote: post #54
andi999 wrote: post #35

Earlier quoted context omitted.

so x+0 is 0?

No. -0.0 + 0 is not necessarily bitwise-equal to 0.0. Though it arguably could be, depending on details.

-0.0 + x = x, even if x should be -0.0 or +0.0.

+0.0 + x, on the other hand, is not always equal to x.

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

#64

Post by titzer »

ncmncm wrote: post #54
andi999 wrote: post #35

Earlier quoted context omitted.

so x+0 is 0?

No. -0.0 + 0 is not necessarily bitwise-equal to 0.0. Though it arguably could be, depending on details.

Note that IEEE 754 defines exactly which zero you get in every combination of operands. -0 + 0 is actually 0.

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

#65

Post by benreesman »

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?

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

#66

Post by touisteur »

stormbrew wrote: post #19
dragontamer wrote: post #13

Earlier quoted context omitted.

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

I think that is the point Peter Cordes is trying to make (quite politely but firmly) over there on stackoverflow. It's not only about autovectorization. The main point there is the loop-carried dependency that prevents both the compiler (autovec) and the processor (ILP) to do their thing.

Loop-carried dependency is the big culprit here. I wish we had a culture of writing for loops with the index a constant inside the loop, as in the Ada for statement, and not the clever C while loops or for with two running variables... Simpler loop syntax makes so many static analyses 'easier' and kind of forces the brain to think in bounded independant steps, or to reach for higher level constructs (e.g. reduce).

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

#67

Post by slaymaker1907 »

benreesman wrote: post #65

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?

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.

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

#68

Post by mike_hock »

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.

The first comment on the code does say precisely this.

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

#69

Post by sampo »

MauranKilom wrote: post #61
sampo wrote: post #44

Earlier quoted context omitted.

> For example, x + 0 == x (where the == is bitwise) does not hold for x = -0. But when operating on floating point numbers, == is not bitwise, and -0 == +0.

If the user provides code where the result should be +0.0 and the compiler emits code that results in -0.0 (and the user has not explicitly enabled relaxed IEEE754 conformance), that's a bug in the compiler.

That is correct. But we were talking about how the == operator compares zeros. According to IEEE 754, -0 == +0 even though their bit patterns are not identical. And, by the way, inf != inf even if their bit patterns are identical.

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

#70

Post by LAC-Tech »

oezi wrote: post #62

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.

I'll put my hand up and say none of the post or answers were obvious to me. I found it all very interesting.
Post reply on HN