pub const LINEAR: usize = 32;Expand description
The most clusters a leaf of the decision tree tests one at a time, which is also the count below
which nothing new is built at all. A switch of this many clusters or fewer stays the chain of
compares it has always been, in the block it has always been in.
Thirty two, and the number is measured rather than picked. What it trades is not a comparison
against a comparison, which is what it looks like on paper and is the reason a small number looks
right. A walk of n clusters is n compares and a search is about log2(n), so on paper the
search wins from about five cases upward and the threshold should be about five.
The machine does not agree, because the two kinds of comparison do not cost the same. Every
compare in a walk is a branch that is almost never taken, one case out of n, so the predictor
gets all of them right and the front end runs through them several per cycle. Every branch in a
search is a branch that goes each way about half the time, so the predictor gets a fair share of
them wrong and each of those costs the whole pipeline. Twenty compares nobody mispredicts are
cheaper than six branches that mispredict a third of the time, and that stays true further up
than it seems it should.
Measured on an interpreter loop dispatching on a sparse switch, four million iterations picking
a case at random, the walk is ahead up to about thirty two cases and the search is ahead above
about thirty six. At seventeen cases a search costs sixteen percent, at twenty four it costs
twenty two, at thirty six it saves nine, at fifty it saves twenty three and at a hundred it saves
half. Thirty two is where those two lines cross.
Two things would move it. The first is a jump table, which is what a dense switch this large
should become and which is waiting on Opcode::IndirectBr. Once dense cases stop reaching the
tree at all, what is left in it is sparser, and a sparser search may be worth starting sooner.
The second is knowing which case is hot, because a walk that tests the common case first is
cheaper than any search and the tree cannot use that ordering. That is document 11’s Frequency
and it is not carried here yet.
gcc has the same knob under the name case-values-threshold and a small number in it, which is
the right number for gcc because gcc reaches for a jump table first and the tree is what it falls
back to on cases a table cannot hold.