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

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 ret .LBB0_4: cmp w0, #3 ccmp w0, #4, #4, ne b.ne .LBB0_3 .LBB0_5: ret .LBB0_6: mov w0, #1 ret

Lo and behold, the performance became comparable to the “naive” function from Part II.

I repeated the experiment using GNU g++ for AArch64. In that case, -fno-jump-tables had no effect because g++ never emitted a lookup table.

Not surprisingly, it turned out I was not the first to come up with this observation. For instance, there is an excellent article by Julian Squires from 2017 on the same topic, but focusing on x86-x64 platform: Are Jump Tables Always Fastest?