[webkit-dev] Request for intuition: should switch statements be faster for the default case, or the explicit cases?

[Filip Pizlo]

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
        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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.webkit.org/pipermail/webkit-dev/attachments/20150131/fdabdc6b/attachment.html>