In switch statements with dense case values, the typical result is a jump
table, which is fast. If the values are sparse, a tree of compares is
generated instead.
What if nearly all cases are dense but there are a few outliers? An example
appears in the NFS protocol parser, where you get a switch statement with cases
for each of the opcode values. All but one are small integers assigned in
sequence, but one is 10044. So the "sparse" case kicks in and a compare tree
is generated for everything.
I can avoid this by putting in special case code for the 10044 case, then all
the rest ends up being a jump table. That brings up the question if GCC should
recognize such scenarios and break up the switch statement into "dense parts"
handled by a jump table, leaving the sorting between those as a compare tree.
paul