When Compiler Optimizations Hurt Performance

Recently I have been working on benchmarks comparing techniques for calculating UTF-8 sequence lengths.

The method I described in Decoding UTF-8. Part IV: Determining Sequence Length - Counting Leading Bits uses hardware-assisted counting of leading zero bits:

#include int utf8_sequence_length(unsigned char lead_byte) { switch (std::countl_one(lead_byte)) { case 0: return 1; case 2: return 2; case 3: return 3; case 4: return 4; default: return 0; // invalid lead } }

I was pretty disappointed with the performance of this function. It was processing between 438 MB/s and 462 MB/s of text data which was far less than the “naive” method described at Decoding UTF-8. Part II: Determining Sequence Length - a Straightforward Approach.

As we saw in the Part IV post, the compiler (clang++ 18.1.3, aarch64) emits a small lookup table to avoid branching:

adrp x9,.Lswitch.table.utf8_sequence_length(unsigned char) add x9, x9,:lo12:.Lswitch.table.utf8_sequence_length(unsigned char) ldr w0, [x9, w8, uxtw #2] ... .Lswitch.table.utf8_sequence_length(unsigned char): .word 1 .word 0 .word 2 .word 3 .word 4

The lookup table generated by the compiler is a degenerate case of a jump table, which is a common optimization for switch-case statements. The “naive” code from Part II uses branching instructions instead and processes over 2000 MB/s. Obviously, the branch predictor did its magic for the case of pure ASCII text, but the performance gap still surprised me 1.

Playing with the Linux perf tool on a WSL Linux installation turned to be a pretty frustrating experience. It did point me to a very high number of cycles stalled in the back-end which often indicates that CPU is waiting for memory, but I couldn’t get perf annotate to work.

In any case, what I had was enough to let me try disabling jump tables; with

clang++ -O2 -fno-jump-tables --std=c++20

the switch-case part of the function compiles to:

cmp w0, #2 b.gt.LBB0_4 cbz w0,.LBB0_6 cmp w0, #2 b.eq.LBB0_5 .LBB0_3: mov w0, wzr…