Loop Optimizations: taking matters into your hands (2021)

https://johnnysswlab.com/loop-optimizations-taking-matters-into-your-hands/

by mooreds • 4 years ago

20 6 4 years ago

brrrrrm• 4 years ago

In my opinion performance optimization should be taught from the ground up, rather than with lists of "performance rules." I found learning this stuff that a solid mental model of the compute resources available (registers, cache) and the paranoia of a compiler (correctness) often made it easier to write fast code. With a good mental model, rather than memorizing rules, one can just walk through the code and re-derive them from first principles.

I also find visualization to be extremely important in this domain: https://jott.live/html/mm_impl_anim

TheMode• 4 years ago

While these optimizations make sense, I cannot hide my disappointment as to how easy they are to break. C-like branches/loops are definitely not designed for modern CPUs (at least not in an efficient manner)

Do anyone perhaps know one/multiple languages that try to push the programmer into manually defining dependencies/micro-parallelism? Or at least make it harder to write inefficient code? If not, what would you suggest?

ridiculous_fish• 4 years ago

How about...Fortran!

In Fortran, you can only take the address of variables which have been annotated with TARGET. This means that "cannot alias" is the default and compilers exploit this.

GeompMankle• 4 years ago

Yeah, people complain about Fortran but writing array operations in Fortran 2003 is great for avoiding aliasing problems and tell the compiler what we need to have done rather than how we think it needs to do it.

guenthert• 4 years ago

However, this kind of “performance tuning” is not necessarily portable, not between different compilers, nor between different hardware architectures on the same compiler, nor between different versions of the same compiler.

I do recall a time when we unrolled loops to minimize the number of decrement+jump instructions. Then there was a time when we stopped doing such in order to minimize the code size and increase the likelihood of it fitting into the cache. Later on loop unrolling became a thing again in order not to upset the CPU's branch predictor ...

So yes, definitively depending on architecture and pointless w/o testing.

hansvm• 4 years ago

In case anyone doesn't feel like they intuitively understand loop pipelining, an example most programmers respond to well is that of a running total.

CPUs are capable nowadays of executing multiple instructions per clock cycle, BUT those instructions still take maybe several cycles to finish, so if instruction B depends on the result of instruction A then you have to wait awhile to execute B.

for (i in 0..n) { total += v[i]; }

Here, the `total` variable changes every loop iteration, so even if we can execute 4 additions per clock cycle, we'll instead expect to see just one every 1 or 2 cycles. A trivial change (not safe when your addition isn't commutative and you care about the difference -- e.g., floats without fast math enabled) is to maintain two independent counters.

for (i in 0..(n-1):+2) { t1 += v[i]; t2 += v[i+1]; }

total = t1 + t2 + (n&1) && v[n-1];

You need a bit of cleanup code at the end to merge the running totals and handle a straggling element you might've missed when looping in increments of two, but for most of the procedure you're flip-flopping between doing operations on t1 and t2, so since there isn't a direct data dependence the CPU is free to execute them simultaneously and halve your latency.

Loop pipelining usually doesn't actually introduce changes in behavior like that (though occasionally I've seen a compiler do that for me -- not quite sure what that optimization stage is called), but it instead relies on there already not being any data dependencies and expresses your ordinary loop as several iterations being appropriately interleaved. It's a similar idea though, and it can have a massive performance benefit.

Loop Optimizations: taking matters into your hands (2021)

Related Stories