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

81–90 of 155 posts

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

#81

Post by zeusk »

sillysaurusx wrote: post #46
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.

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…

memcpy is more like copying a single line, to copy a rectangle you need to call it in a loop or use specialized blit hw/sw.

How is MLIR different from LLVM IR?

And tile/block processing is not that novel for generic compute, graphics use it for other reasons - mostly how the pixel data is in memory and how the pipeline scales with tile size.

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

#83

Post by [deleted] »

dragontamer wrote: post #11
zeusk wrote: post #9

Earlier quoted context omitted.

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.

[deleted]

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

#84

Post by andreareina »

sampo wrote: post #69
MauranKilom wrote: post #61

Earlier quoted context omitted.

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.

You mean nan right?

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

#85

Post by foxes »

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.

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

#86

Post by gpderetta »

tomxor wrote: post #76

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 algo will use more instructions as will have to run for more iterations. The faster algo will use wider ALUs that are more power hungry, so it appears a wash. But because less instructions are in flight, less power need to be spent to keep track of them or renaming registers, caches need to powered for a smaller amount of time and so on.

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

#87

Post by ummonk »

skavi wrote: post #7
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?

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.

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.

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

#88

Post by userbinator »

athrun wrote: post #79
astrange wrote: post #59

Earlier quoted context omitted.

The compiler doesn’t know anything about optimizing x86 code either. The actual details there are too secret for Intel to want to accurately describe them in gcc, they’re different across different CPUs, and compilers just aren’t as good as you think they are. (But CPUs are usually better than you think they are.)

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

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

#89

Post by zeusk »

dragontamer wrote: post #11
zeusk wrote: post #9

Earlier quoted context omitted.

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.

> as long as i, i+1, i+2, i+3, ... i+7 are not dependent on each other

I really don't see how that works in improving this.

You can only calculate i+8, for calculating i+9 you depend on 8. And you can't go in strides either since i+16 depends on i+15 which you've not calculated so far unless you want to intermix the stateful and non-stateful code. I'd rather not go there.

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

#90

Post by ummonk »

yongjik wrote: post #58
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.

If they were integer variables, I guess the compiler would have done that, but you can't really do that with floats because i+A+A is not necessarily i+2*A. (Of course, in this particular example, the difference doesn't matter for the programmer, but the compiler doesn't know that!) I think there's some gcc option that enables these "dangerous" optimizations. -ffast-math, or something like that?

No the computer would have been unlikely to be able to figure out the math to coalesce 8 recursive additions into one operation.
Post reply on HN