In case you still want an answer to the original question - I would expect good programming practice to be that you explicitly list all your relevant cases in a switch statement, so hitting default should never happen or should be a rare exception. But I don’t know if real programs are like that and I’m sure there’s at least some code where this is not true.
Regards, Maciej > On Jan 31, 2015, at 12:53 PM, Filip Pizlo <[email protected]> wrote: > > Ha - never mind, I was wrong. My calculation of cost for getting to default > is wrong. Please ignore. > > -Filip > > >> On Jan 31, 2015, at 12:40 PM, Filip Pizlo <[email protected] >> <mailto:[email protected]>> wrote: >> >> I’m having fun calculating the average performance of different switch >> implementations, to be used in the DFG JIT and in our inline caching logic. >> I’ve got two possible implementations that appear to be very nearly optimal >> assuming the capabilities of the hardware we care about and other >> constraints of our JITs. Both implementations involve a tree of branches, >> and they both come into play in exactly those cases where a tree of branches >> is already known to be less expensive than a lookup table. >> >> Here’s the basic switch JIT algorithm: >> >> jitSwitchRecurse(cases) { >> if (cases.size < N) { >> for (C in cases) { >> emit code that checks, and executes, C >> } >> fall through to default >> } else { >> // Note that this only divides-and-conquers and does not explicitly >> check and execute the median case; I’ve calculated that this is the superior >> choice. You can follow along with this here: >> https://bugs.webkit.org/show_bug.cgi?id=141046 >> <https://bugs.webkit.org/show_bug.cgi?id=141046> >> let M = right-median case in cases // for even sizes of cases, pick >> the greater of the two medians; for odd cases, pick either the median or the >> value to the right of the median at random. the point is to split the list >> into two equal-sized lists >> lessThanJump = emit lessThan comparison against M >> jitSwitchRecurse(those cases that are >= M) >> lessThanJump.link() >> jitSwitchRecurse(those cases that are < M) >> } >> >> The two implementations of this algorithm that I’m picking between either >> have N = 2 or N = 3 - i.e. we either stop divide-and-conquering once we have >> two remaining cases, or when we have 3 remaining cases. Those two versions >> are the most optimal for a variety of reasons, but neither is obviously >> better than the other: N = 3 is more optimal for the case that the switch >> bottoms out in one of the cases. N = 2 is more optimal if the switch >> bottoms out in the default (“fall through”) case. N = 2 is significantly >> more optimal for default: it usually results in two fewer comparisons before >> getting to default. N = 3 is slightly more optimal for the non-default >> (i.e. hitting some explicit case) case: it usually results in one fewer >> comparisons before getting to some case. >> >> We could have a switch emitter that selects the strategy based on profiling >> (did we hit the default case, or not?), but that isn’t always available and >> it might be overkill. We could tune this for benchmarks, and I might do >> some of that. But I’m curious what other people’s intuitions and >> experiences are: do your switch statements usually hit some case, or take >> default? If you could control which one was faster, which one of those >> would you be most likely to make faster in the kind of code that you write? >> >> -Filip >> > > _______________________________________________ > webkit-dev mailing list > [email protected] > https://lists.webkit.org/mailman/listinfo/webkit-dev
_______________________________________________ webkit-dev mailing list [email protected] https://lists.webkit.org/mailman/listinfo/webkit-dev
