GCC picks a jump table over a comparison tree by counting comparisons, not labels
Cases 0, 7, 14, 21, 34 compile to a jump table. Cases 0, 8, 16, 24, 40 compile to comparisons. A switch of twenty labels over 0 to 87 also loses its table.
The post walks through GCC's lowering order: bit tests first, then jump tables, then a binary tree. The speed rule allows a table up to 8 times the number of comparisons it replaces.
A commenter who builds compilers says GCC and Clang still lack perfect hashing for large sparse switches, and one reader explains why the missed divide-by-eight is actually correct.
Three strategies, in a fixed order
The write-up shows GCC's pass_lower_switch trying bit tests, then jump tables, then a binary decision tree. A bit test needs a combined range under 64, at most three distinct targets, and a minimum label count, then checks membership with the x86 bt instruction. Cases '0' through 'E' become a single bt against a 2753205 constant. Jump tables need at least five labels by default and enough density.
The density rule explains the oddities. GCC allows a table up to 8 times the comparisons it would replace for speed (2 times under -Os). Twenty labels spanning 0 to 87 merge into 10 comparisons, and 10 x 8 = 80 is less than 88, so no table.
The "missed" optimization that isn't
The post notes GCC does not divide x by 8 before the jump on the 8-spaced case.
"It could not because that would ensure that 7 values for each case would be handled by function calls instead of the default case - 0/8 is 0, but 3/8 is also 0" — a commenter replying to that remark
What the compilers don't do
A compiler developer said Clang and GCC still don't implement perfect hashes for large sparse switch tables, though he added them to his own C compiler in a day, and that they would help Unicode work. The LLVM patch was rejected a decade ago. A Rust crate author reached the same conclusion: LLVM took around half an hour to compile a giant MAC-vendor switch with optimizations on, so he switched to perfect hashing.
Get breakdowns like this every day
The top Hacker News stories, unpacked — by email, Telegram, or RSS.
Colin Percival says a scholar's duty is to find the people who need the truth
In 2004 he found that Intel Hyper-Threading leaked an RSA key through the cache, spent six months notifying vendors, and published in May 2005 over Intel's objection.