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

111–120 of 155 posts

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

#111

Post by astrange »

titzer wrote: post #105
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.)

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…

The front end (the decoder stage and branch predictors) are what would theoretically be important for compilers as they’re the bottleneck. But Intel’s optimization advice doesn’t say much about branches anymore, they pretty much want you to rely on them to take care of it.

That’s only part secrecy and part to give them freedom to change it. It is of course somewhat described in their patents.

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

#112

Post by titzer »

astrange wrote: post #111
titzer wrote: post #105

Earlier quoted context omitted.

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…

The front end (the decoder stage and branch predictors) are what would theoretically be important for compilers as they’re the bottleneck. But Intel’s optimization advice doesn’t say much about branches anymore, they pretty much want you to rely on them to take care of it. That’s only part secrecy and part to give them freedom to change it. It is of course somewhat described in their patents.

There are sometimes vague hints about things to avoid, e.g. putting too many branches on the same cache line, and they usually publish the size of their tables, typically 4K, 8K entries these days? But the actual predictors are wicked devils; they clearly are doing some tournament predictors, using tiny ML modules (perceptrons), and god knows what else. I studied this carefully when trying to make good Spectre gadgets, but it is very very difficult to 100% trick (or utilize!) a branch predictor these days--they just learn in interesting ways...and entries alias :-)

I honestly don't know if it's worth it to try to optimize branch prediction in compilers these days, beyond the obvious step of putting the highest probability target next (for fallthrough prediction) and generally laying out hot parts of the code together. TurboFan and most other dynamically-optimizing compilers put rare code at the end of functions, and that's a huge boost.

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

#113

Post by dragontamer »

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…

> Do you mean like this? I get this to about as fast as the first "unoptimized" version in the SO post, but not faster.

Yeah, something like that. I haven't double-checked your math, but the idea is what I was going for.

I'm always "surprised" by the fact that CPUs care more about bandwidth rather than latency these days. A lot of CPUs (Intel, AMD, ARM, etc. etc.) support 1x or even 2x SIMD-multiplications per clock tick, even though they take 5 clock ticks to execute.

I guess the original "simple" code may have had a multiply in there, but that's not a big deal these days (throughput wise), even though its a big-deal latency wise.

So getting rid of those multiplies and cutting down the latency (ie: using only add statements) barely helps at all, maybe with no measurable difference.

One of these days, I'll actually remember that fact, lol.

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

#115

Post by pjscott »

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.

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

#116

Post by hayley-patton »

shp0ngle wrote: post #108

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

Does the Go compiler auto-vectorise? Vectorisation appears to have been the cause of the weird performance.

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

#117

Post by janwas »

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

Don’t bother. Autovectorization almost fundamentally doesn’t work. You can write code using explicit vectors and it’s not too bad, though less cross platform than you’d like. An actual answer involves things like restrict and alignment keywords.

Explicit vectors can be made portable (to SSE4/AVX2/AVX-512/NEON/SVE/SVE2/RISC-V V/WASM SIMD) using the Highway library which gives you wrapper functions over the platform's intrinsics, emulating missing functionality where required: github.com/google/highway. Disclosure: I am the main author.

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

#118

Post by janwas »

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…

We mean energy, right? The surprising fact is that the energy cost of executing an instruction (scheduling etc.) is much higher than the actual operation. Thus SIMD amortizes that per-instruction overhead over multiple elements, leading to 5-10x gains ( https://pdfs.semanticscholar.org/f464/74f6ae2dde68d6ccaf9f53...).

Even in this example, which apparently has 4x vector instructions vs 1x scalar, AVX-512 (and probably even AVX2) would reduce energy usage because they can do 8 (or 4 for AVX2) 64-bit elements per cycle.

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

#119

Post by shp0ngle »

hayley-patton wrote: post #116
shp0ngle wrote: post #108

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

Does the Go compiler auto-vectorise? Vectorisation appears to have been the cause of the weird performance.

No, I don't think so.

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

#120

Post by formerly_proven »

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.

Those are also CPUs were multiplication is most likely to be significantly more expensive, or not implemented in hardware at all (though almost everything has a multiplier these days).
Post reply on HN