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

101–110 of 155 posts

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

#101

Post by mvuksano »

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/) and halide (https://halide-lang.org/). Both can be used to speed up certain workloads significantly.

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

#102

Post by sampo »

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.

> 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 + C;
        Y[2] =   4*A + 2*B + C;
        Y[3] =   9*A + 3*B + C;
        Y[4] =  16*A + 4*B + C;
        Y[5] =  25*A + 5*B + C;
        Y[6] =  36*A + 6*B + C;
        Y[7] =  49*A + 7*B + C;
        Z[0] =  64*A + 8*B;
        Z[1] =  80*A + 8*B;
        Z[2] =  96*A + 8*B;
        Z[3] = 112*A + 8*B;
        Z[4] = 128*A + 8*B;
        Z[5] = 144*A + 8*B;
        Z[6] = 160*A + 8*B;
        Z[7] = 176*A + 8*B;
    
        int i;
        for(i=0; i

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

#103

Post by Izkata »

anticensor wrote: post #47
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.

There is a compiler switch for that too: -fassociative-math -funsafe-math-optimizations

I like how the flag combines in that second one to create "fun safe", pretty much flipping its meaning.

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

#104

Post by eklitzke »

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.

To be precise, they're both "vectorized" in the sense that both versions are using SSE vector instructions (and in fact, Clang will even generate AVX instructions for the first version if you use -mavx2). The difference is really the data dependency which has a massive effect on the ability of the CPU to pipeline the operation.

For the first version w/ AVX I get:

$ perf stat ./a.out [-] Took: 225634 ns.

Performance counter stats for './a.out':

            247.34 msec task-clock:u              #    0.998 CPUs utilized          
                 0      context-switches:u        #    0.000 /sec                   
                 0      cpu-migrations:u          #    0.000 /sec                   
             2,009      page-faults:u             #    8.122 K/sec                  
       960,495,151      cycles:u                  #    3.883 GHz                    
     2,125,347,630      instructions:u            #    2.21  insn per cycle         
        62,572,806      branches:u                #  252.982 M/sec                  
             3,072      branch-misses:u           #    0.00% of all branches        
     4,764,794,900      slots:u                   #   19.264 G/sec                  
     2,298,312,834      topdown-retiring:u        #     48.2% retiring              
        37,370,940      topdown-bad-spec:u        #      0.8% bad speculation       
       186,854,701      topdown-fe-bound:u        #      3.9% frontend bound        
     2,242,256,423      topdown-be-bound:u        #     47.1% backend bound         

       0.247734256 seconds time elapsed

       0.241338000 seconds user
       0.004943000 seconds sys
For the second version with SSE and the data dependency I get:

$ perf stat ./a.out [-] Took: 955104 ns.

Performance counter stats for './a.out':

            975.30 msec task-clock:u              #    1.000 CPUs utilized          
                 0      context-switches:u        #    0.000 /sec                   
                 0      cpu-migrations:u          #    0.000 /sec                   
             2,010      page-faults:u             #    2.061 K/sec                  
     4,031,519,362      cycles:u                  #    4.134 GHz                    
     3,400,341,362      instructions:u            #    0.84  insn per cycle         
       200,073,542      branches:u                #  205.140 M/sec                  
             3,192      branch-misses:u           #    0.00% of all branches        
    20,091,613,665      slots:u                   #   20.600 G/sec                  
     3,110,995,283      topdown-retiring:u        #     15.5% retiring              
       236,371,925      topdown-bad-spec:u        #      1.2% bad speculation       
       236,371,925      topdown-fe-bound:u        #      1.2% frontend bound        
    16,546,034,782      topdown-be-bound:u        #     82.2% backend bound         

       0.975762759 seconds time elapsed

       0.967603000 seconds user
       0.004937000 seconds sys
As you can see the first version gets nearly 3x better IPC (2.21 vs 0.84) and spends half as much time being backend bound.

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

#105

Post by titzer »

astrange wrote: post #59
magicalhippo wrote: post #50

Earlier quoted context omitted.

Not really, the compiler did the round-trip into the local variable (memory), I did it via register. I asked around at the time and someone mentioned that I might have overtaxed certain execution ports or something like that, but yeah that just cemented my belief that x86 optimization is not my cup of tea anymore. Better to spend time learning how to write code the compiler can optimize well.

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

It's not so secret, TBH. Usually the intel microarchitecture manuals are detailed enough to describe how many and what type of execution ports there are, how many stages in the pipeline, the size of the reorder buffer, latency of most u-ops, and any frontend hazards. The super secret stuff are things like the design of the branch predictors, memory disambiguation, etc, as well as the low-level tricks to optimize each of these down to the fewest gate delays (for high clockspeeds, etc), as well as where and how they figure out placement, etc.

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

#106

Post by titzer »

magicalhippo wrote: post #50
userbinator wrote: post #49

Earlier quoted context omitted.

You probably added an extra instruction or two to put the value in a register? The CPU can already split memory accesses into uops and cached accesses are fast, so there's no point in doing that because it'll just waste an additional register (vs. using one of the many the renamer generates) and add instructions to decode. x86 is fundamentally a CISC; if you treat it like a RISC, it will definitely disappoint.

Not really, the compiler did the round-trip into the local variable (memory), I did it via register. I asked around at the time and someone mentioned that I might have overtaxed certain execution ports or something like that, but yeah that just cemented my belief that x86 optimization is not my cup of tea anymore. Better to spend time learning how to write code the compiler can optimize well.

It's hard to know exactly without staring at the code and knowing the exact CPU, because nothing stands out as a red flag. If you used an extra register, maybe you caused a spill (pushed something else out of registers into memory). Maybe you made the loop code bigger and it no longer fit in the loop stream buffer (if that model had one). Maybe you hit a weird frontend decode issue and it could only decode N-1 instructions per clock in that line instead of N, and that was critical to the loop's performance. Maybe your code layout changed for another reason, or the memory layout, and you got some bad cache aliasing.

These things are knowable if you have enough curiosity and maybe masochism :)

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

#107

Post by rasz »

gpderetta wrote: post #86
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.

>The slower algo will use more instructions

The whole point of this thread is realization of opposite. Slower algo executes only 2 instructions in a loop, but second one directly depends on the result of the first (induces pipeline stall) while the fast version brute forces a ton of instructions at full CPU IPC.

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

#108

Post by shp0ngle »

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

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

#109

Post by astrange »

bee_rider wrote: post #100
userbinator wrote: post #88

Earlier quoted context omitted.

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

Intel has released at least some of their software suite for free (as in beer, not as in speech). https://www.intel.com/content/www/us/en/developer/articles/n... I think software is not a huge profit center for them. The original comment presents: > The actual details there are [1] too secret for Intel to want to accurately describe them in gcc, [2] they’re different across different CPUs, [3] and compilers just aren…

You can just look at gcc and llvm source. GCC’s x86 backend is maintained by an Intel employee and it doesn’t have especially detailed descriptions of any cpu in -mtune.

Actually, compiler optimizations like scheduling tend to be neutral to negative on x86 because they increase register pressure. You’d probably want to do “anti-scheduling” and hope the CPU decoder takes care of it if anything.

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

#110

Post by djmips »

kortex wrote: post #73
djmips wrote: post #42

Earlier quoted context omitted.

You can't ignore the details if you want the fastest performance. Unfortunately sometimes the solution that's the fastest is also more complex. Simplicity tends to win and also is less likely to be buggy, easier to maintain etc but sometimes the fastest code deliberately introduces coupling, hardware specific cache shenanigans or unreadable hand written asm and/or inlined SIMD. This is often counter to your hypothesi…

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