Say hello to x86_64 assembly, part 4

Sometimes the compiler does something really stupid and inefficient, but other times it does something really clever that I (who never wrote any serious assembly by hand) would never think of.

Yup. I've seen 40x speedup over C/C++ code just by using SIMD (SSE/AVX) and eliminating the branches other than loop condition. It was possible to process up to 16 results in parallel (using just one CPU core), with about same number of cycles as the C version took to process one, while getting rid of the penalties from mispredicted branches. Data dependent branches are very expensive. They often have nearly 50% branch mispredict rate. If the branch is data dependent and thus unpredictable, it's usually much faster to compute it every time regardless and simply mask to ignore unwanted results than to eliminate computation by branching over it. Depending on the CPU model, with SIMD you can compute roughly up to 100-400 floating point ops (in SIMD vectors) and 200-800 integer ops in same time as one mispredicted branch takes. In those 14-20 clock cycles! Haswell executes up to 16 floating point ops per core in one clock cycle using SIMD. This is, assuming you don't get data starved, of course. Or have pipeline stalls due to unbreakable too long dependency chains, etc.

One thing compilers just can't get right is when there's a large switch-statement in performance critical code. Compilers can't seem to be able to make intelligent decisions about register allocation in that case, and behave as if you had true function pointers (=disable optimizations). In that particular situation you can gain 2-3x performance over a compiler just by dropping to assembler.

Compilers are pretty good in most cases, though. I wish they were smarter at eliminating branches.

Any optimizing compiler should generate a single 32-bit MUL for uint64_t z = (uint64_t) x * (uint64_t) y. It's easy for instruction selection to match against such patterns.

A better example would be generating a single instruction for the 128-bit product of 64-bit integers on a 64-bit processor. There are no standard types for 128-bit integers, but you can still avoid assembly code by using compiler-specific types or intrinsics. With GCC, Clang and ICC, you can write unsigned __int128 z = (unsigned __int128) x * (unsigned __int128) y. The odd one out is MSVC, where you have to use the _umul128 intrisic.

Mostly you just have to do what is outlined in the next few paragraphs. Optimization is actually pretty simple - don't work against the hardware, work with it. Measure.

Memory is slow. Just changing how things are ordered in the memory can do sometimes 2x speed. So try to keep your data sequential in memory. Avoid locks if you can - it's shared memory between cores which requires a lot of slow communication between cores. Avoid atomic operations if you can - also memory shared between cores. Avoid sharing any mutable data with other cores, if you can. If NUMA (multiple physical CPU sockets, each with it's own physically connected memory), use local CPU memory, otherwise you'll very quickly saturate CPU socket interconnects! Avoid function pointers, especially to short functions; they cause compilers to drop optimizations and cause often CPU branch mispredicts. Avoid pointer chasing, but if you do, measure if it makes sense to early prefetch next entry/entries. Don't waste cache lines! You have less than 512 or 1024 of those very valuable L1 cache lines, they're easy to exhaust. Don't write unnecessarily to cache lines shared by other cores, this makes a lot of very slow things happen behind the scenes. Try to align structs to next larger power of two size, but do remember often just having more data in cache is better, so measure. Or align structs to cache line boundary (usually 32, 64 or 128 bytes), so that CPU doesn't need to fetch two cache lines. Otherwise align to data type size, but measure too. Try to keep your stack aligned.

Don't register spill, be frugal with how many registers you need in inner loops (especially on 32-bit x86!). Don't do long dependency chains in computations, if you can avoid it.

Minimize the number of branches, even nearly 100% predictable ones - they still take up valuable CPU branch resources.

If you have a lot of memory random access, arrange your data in a way that maximizes locality of reference. Use large pages to avoid TLB misses (and worse, page faults).

Noticed a pattern? Computation is fast, memory is very slow. Sequential streaming from memory is faster by an order of magnitude compared to random access. You might be able to do thousands of floating point operations during a single cache miss! Communicating with other cores is slower. A lot of effective optimization comes down to managing cache better.

Always assume what you know is outdated and even when it isn't, that you're simply wrong! Read CPU model specific documentation, but don't trust it blindly. Assume nothing, measure. Small changes in code can affect performance in seemingly unaffected locations. Don't do silly things: it doesn't matter if your loop counters count up or down. "register" keyword does nothing and even if it did, you'd probably make your code slower.

Be sure to measure on multiple CPU architectures (for X86: a few AMD generations, Intel Sandy Bridge, Atom, etc. All of those behave differently, often very differently! Take advantage of the CPU performance counters, they're really useful seeing what happens inside the chip.

Don't optimize until you're really sure you need to, and that you've done all you can in choosing the best algorithm. Is everything really necessary code to execute? Anything you could precompute? Do remember that you can do a huge amount of computation during a memory access! Don't naively assume you should always choose the algorithm with the best big O. Your constants are often large and data is usually small!

> ARM isn't really simpler than x86. ARMv7 has about as many instructions as x86, and probably has more if you differentiate between thumb and arm (which you should if you are micro-optimizing). It also features some constructs like general conditional execution that are notoriously difficult for compilers to use effectively. The 64-bit ARM ISA is every bit as complex as modern x86_64 (though more orthogonal, which makes it lovely to program for).

True. ARMv7 conditional execution (predicates) is also reading from flags register. On a simple pipelined ARM implementation that equals a stall, if flags were touched by the few previous instructions, until last flag touching instruction is retired. And on more complicated designs that implement out-of-order execution it can still often mean a stall because of long dependency chains.

On ARMv7 practically all instructions can have dependency on flags register!

You do avoid branch mispredicts, but at what cost? Having so many read/write ports in the flags register consumes silicon and power too. The cost increases the deeper the pipeline. To get higher clock frequencies, the CPU pipeline needs to become longer.

ARMv8 (64-bit) did the only sensible thing and removed predicate insanity.