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 <fpi...@apple.com> 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 webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev