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

[Maciej Stachowiak]

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

___
webkit-dev mailing list
webkit-dev@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-dev

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

[Filip Pizlo]

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

[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

___
webkit-dev mailing list
webkit-dev@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-dev