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

141–150 of 155 posts

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

#141

Post by ascar »

gpderetta wrote: post #125
rasz wrote: post #107

Earlier quoted context omitted.

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

If you look carefully at the generated assembly shown in the article, the vectorized loop actually executes less instructions in total as while an iteration is longer it more than make it up by iterating less times. Edit: btw, while the fast version has bo loop carried dependencies and it uses 4x SIMD, it us only twice as fast I wonder if a manually unrolled (with 4 accumulators) and vectorized version of the strengt…

If you look carefully you will find that the slower algorithm uses less instructions and the faster algorithm uses 2xSIMD and more than twice as many instructions.

And yes unrolling the loop carried dependency on the strength reduced version will certainly make it faster as it's the only reason it's slower to begin with.

I encourage you to read my other comment here https://news.ycombinator.com/item?id=31551375

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

#142

Post by gpderetta »

ascar wrote: post #141
gpderetta wrote: post #125

Earlier quoted context omitted.

If you look carefully at the generated assembly shown in the article, the vectorized loop actually executes less instructions in total as while an iteration is longer it more than make it up by iterating less times. Edit: btw, while the fast version has bo loop carried dependencies and it uses 4x SIMD, it us only twice as fast I wonder if a manually unrolled (with 4 accumulators) and vectorized version of the strengt…

If you look carefully you will find that the slower algorithm uses less instructions and the faster algorithm uses 2xSIMD and more than twice as many instructions. And yes unrolling the loop carried dependency on the strength reduced version will certainly make it faster as it's the only reason it's slower to begin with. I encourage you to read my other comment here https://news.ycombinator.com/item?id=31551375

I might be somehow miscounting, but it seems to me that for the slow implementation a loop iteration issues 6 instructions, for the fast one it issues 21, but it is unrolled 4 times (compare the loop counter increment), so it iterates one fourth of the times and for the whole loop it ends up actually issuing slightly less instructions.

edit: to be clear, I'm only arguing about two things that the original parent quitestioned: whether vectorization is not free (it is because wider ALUs require less instructions) and whether the second loop used more instructions (it does not as it is unrolled by 4).

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

#143

Post by joaonmatos »

zeusk wrote: post #81
sillysaurusx wrote: post #46

Earlier quoted context omitted.

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.

LLVM is geared towards providing a single toolchain for frontends to target, but is essentially made to target von Neumann/serial-ish/homogenous machines. You can get an overview of its philosophy in Lattner’s original 2004 paper [1]. MLIR (Lattner 2021 [2]) aims to generalize the compiler toolchain to support different compute paradigms and heterogeneous targets (polyhedral compilation/parallel kernels/afine loops) and so on, by defining a declarative framework of IR _dialects_ and transforms between them. I’m writing my MSc thesis on using C/C++ as the IR, assuming it has enough compiler support for different targets to provide a suitable platform for optimisation transforms using a source-to-source compiler, but MLIR seems like a better first-principles approach, maybe suffering from the impracticality of using it _right now_.

[1] "LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation", Lattner and Adve. https://llvm.org/pubs/2004-01-30-CGO-LLVM.pdf

[2] “MLIR: Scaling Compiler Infrastructure for Domain Specific Computation”, Lattner et al. https://ieeexplore.ieee.org/document/9370308

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

#144

Post by tomxor »

gpderetta wrote: post #142
ascar wrote: post #141

Earlier quoted context omitted.

If you look carefully you will find that the slower algorithm uses less instructions and the faster algorithm uses 2xSIMD and more than twice as many instructions. And yes unrolling the loop carried dependency on the strength reduced version will certainly make it faster as it's the only reason it's slower to begin with. I encourage you to read my other comment here https://news.ycombinator.com/item?id=31551375

I might be somehow miscounting, but it seems to me that for the slow implementation a loop iteration issues 6 instructions, for the fast one it issues 21, but it is unrolled 4 times (compare the loop counter increment), so it iterates one fourth of the times and for the whole loop it ends up actually issuing slightly less instructions. edit: to be clear, I'm only arguing about two things that the original parent quit…

I think the confusion might be coming from mixing "instructions" with "operations", which are not equivalent especially since we are discussing SIMD which packs in multiple operations (single instruction operating on multiple data). If you re-read this thread and replace instructions with operations it makes more sense.

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

#145

Post by dragontamer »

btdmaster wrote: post #131
sampo wrote: post #102

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

On my machine, your code is faster for smaller LEN values. I'm not sure why this is though.

8x 64-bit is 512-bit, which is designed for AVX512. You'll probably need AVX512 to fully benefit from unrolling x8.

4x 64-bit is 256-bit, which requires special compiler flags for 256-bit AVX2, but most x86 CPUs should support them these days.

2x64-bit is 128-bit, which fits in default SSE 128-bit SIMD with default GCC / Visual Studio compiler flags.

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

#146

Post by tomxor »

janwas wrote: post #118
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 probab…

> The surprising fact is that the energy cost of executing an instruction (scheduling etc.) is much higher than the actual operation.

Good point, decoding and scheduling are expensive and SIMD certainly eliminates a lot of that. However the alternative algorithm has even less decoding and scheduling to do, since it completely eliminates the multiplication operations without increasing the number of additions. But even then I wouldn't be surprised that it makes no difference to energy on any x86, as I said it was more of a fundamental observation - for a different application this is useful when selecting the actual hardware if you are not already constrained to a particular chip.

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

#147

Post by aidenn0 »

dreamcompiler wrote: post #78
sillysaurusx wrote: post #46

Earlier quoted context omitted.

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…

> stop storing state, unless it makes the program less complicated I had hoped that functional programming languages would lead us to automatic high-level parallelization. That hasn't happened much in the real world. But what we got is "write code like a functional programmer would even in a low-level language and the compiler and the ISA will parallelize it for you." That surprises me, but I'll take it.

I think it's that it's easier to detect a lack of data dependencies in C than it is to write an efficient Haskell compiler. Well, that and the fact that there is at least an order of magnitude more people working on the former than the latter

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

#148

Post by ascar »

gpderetta wrote: post #142
ascar wrote: post #141

Earlier quoted context omitted.

If you look carefully you will find that the slower algorithm uses less instructions and the faster algorithm uses 2xSIMD and more than twice as many instructions. And yes unrolling the loop carried dependency on the strength reduced version will certainly make it faster as it's the only reason it's slower to begin with. I encourage you to read my other comment here https://news.ycombinator.com/item?id=31551375

I might be somehow miscounting, but it seems to me that for the slow implementation a loop iteration issues 6 instructions, for the fast one it issues 21, but it is unrolled 4 times (compare the loop counter increment), so it iterates one fourth of the times and for the whole loop it ends up actually issuing slightly less instructions. edit: to be clear, I'm only arguing about two things that the original parent quit…

oh you're right, my bad. Sloppy on my part!

I somehow got tripped up by the 4xSIMD. I was assuming you meant it's using 4x 64bit SIMD there which it doesn't. mulpd and addpd are 2x 64bit, also visible by the xmm instead of ymm registers.

I got sloppy on the difference between all instructions including the loop logic vs just the instructions necessary to do the main computation. Obviously the first is the correct measure and I was sloppy.

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

#149

Post by tomxor »

ascar wrote: post #77
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…

Do you have a reference for that? I googled and I couldn't find anything good. While it might sound intuitive that SIMD instructions consume more power, I don't think that's necessarily true to a relevant degree in practice. My understanding is CPU power consumption is mostly tied to inefficiences that cause energy loss via heat, while the actual computation doesn't consume any energy per se. So electrons traveling a…

I think in summary what you are alluding to is instruction decoding and scheduling as the sibling comment points out, which is indeed a large cost in both speed and power.

> SIMD vs no SIMD has a neglectable overhead compared to entering a lower power state sooner.

Yes on the same CPU as I suggested, real world difference may be unmeasurable. However note that this particular case is interesting because it's not comparing fewer serial multiplies to more SIMD multiplies, it's comparing SIMD multiplies to no multiplies but with a serial constraint due to variable dependence... i.e it's SIMD vs no multiply without any other difference in number or type of ALU ops... which again could make no difference on a big x86 in practice, but it would be interesting to know.

All of this changes if you are coding for a lower power device and have choice of hardware.

Post reply on HN