When Compiler Optimizations Hurt Performance

ARM64 has many registers but I believe the lack of suitably large immediate values and, apparently, compilers that are willing to use them all across functions, puts it at a disadvantage here. Assuming we want the return value in eax and the leading count comes in cl, this can be done branchlessly and data-lessly on x86 as follows:

    mov eax, 0x00043201
    test cl, 8
    setz al
    shl cl, 2
    shr eax, cl
    and eax, 15

Something similar may be possible on ARM64, but I suspect it will definitely be more than 19 bytes ;-)

  utf8_sequence_length_lookup:
    shl edi, 24
    mov ecx, 274945
    not edi
    lzcnt eax, edi
    shl al, 2
    shrx rax, rcx, rax
    and al, 7
    ret

    t = 0x2020c6 >> x
    return (t << (t & 31)) >> 27

    mov eax, 0x2020c6
    shr eax, cl
    mov cl, al
    shl eax, cl
    shr eax, 27

    mov ax, 0x4681
    lea ecx, [ecx+ecx*2]
    shr eax, cl
    and eax, 7

  return (0x43201 >> x*4) & 7

I’ve seen many examples of a similar phenomenon. Modern compilers are impressively good at generating bit-twiddling micro-optimizations from idiomatic code. They are also good at larger scale structural macro-optimization. However, there is a No Man’s Land for compiler optimization between micro-optimization and macro-optimization where the effectiveness of compiler optimizations are much less reliable.

Intuitively I understand why it is a hard problem. Micro-optimizations have deterministic properties that are simple enough that optimality is all but certain. Macro-optimization heuristics create incidental minor pessimization effects that are buried below the noise floor by major optimization effects on average.

In the middle are optimizations that are too complex to guarantee effective optimization but too small in effect to offset any incidental pessimization. It is easy to inadvertently make things worse in these cases. Most cases of surprising performance variances I see fall into this gap.

It is also where the codegen from different compilers seems to disagree the most, which lends evidence to the idea that the “correct” codegen is far from obvious to a compiler.

I think some people misunderstand how compiler optimizations work. it's not magic, which makes each piece of code faster, it's just a bunch of deterministic code transformation rules, which usually make code faster (considering large set of use-cases), but it's not proven that they always do so. So, by writing performant code one should always keep this in mind.

It's a simple rule of thumb to avoid branching in performance-critical code. Branchless code is pretty predictable, but if branching takes place, one can no longer reason so easy about code performance, since compiler optimizations and CPU branch prediction may be involved.

If you wanna really see this at work on a whole other extreme, try compiling code for an N64 game. It's no surprise that optimizations for modern-day x86_64 and Arm64 processors with a lot of cache would not generalize well to a MIPS CPU with a cache that must be manipulated at the software layer and abysmal RDRAM latency, but the exact mechanics of it are interesting.

KazeEmmanuar did a great job analyzing exactly this so we don't have to!

https://www.youtube.com/watch?v=Ca1hHC2EctY

This is a good reminder that optimization without measurement is stupidity.

It’s also a reminder that compilers aren’t magic and optimizers aren’t all-knowing.

People have a tendency to ascribe magical properties to anything they don’t understand. Compilers and optimizers more so.

Measure before and after any optimization. You’d be surprised at what does and doesn’t improve efficiency.

Today’s CPUs are more complex than a human can understand.

Measure twice, cut once.

Since the biggest one is only 11110 (5 bits), can't you use a lookup table of 32 characters by masking the last 3 bits?

I suspect over time as memory latency, bandwidth and branch prediction have become increasingly the hot aspect of CPUs that optimisations put into compilers before now often end up improving for the wrong thing. Maintaining sequential reads of memory and ahead of the calculation is now critical for peak performance as is the branch being correctly predicted. Saving calculation time on the ports of the CPU however much less impactful as we mostly struggle to shuttle the work into them to achieve peak performance.

Branch predictors are a lot bigger and more capable now than they were and there is every chance when the optimisation for jump tables was tested against the equivalent branch code it outperformed it, but on more recent CPUs the situation reverses.

Notably this is on an arm processor (aarch64) and they don't say specifically which one. I've seen extreme differences in jump table performance between x86/amd64 cpus. Specifically I remember seeing a big speedup on similar code with either Haswell or Skylake that I pinned down to a jump table suddenly performing blazing fast compared to the previous architecture. Which actually led me to implement the same thing here (avoid generating the jump table) so it would perform better on the earlier processors. This was code that was, basically, stream parsing varint values so the code pattern immediately triggered that core memory!

When I used to code in C++, I went down a long rabbit hole of compiler optimizations. It's way more complicated than we give developers credit for. Coming from C++ to Rust, I was happy to see that `--release` optimizes (almost) everything for you.