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

Reply via email to