<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Ha - never mind, I was wrong. My calculation of cost for getting to default is wrong. Please ignore.<div class=""><br class=""></div><div class="">-Filip<br class=""><div class=""><br class=""><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jan 31, 2015, at 12:40 PM, Filip Pizlo <<a href="mailto:fpizlo@apple.com" class="">fpizlo@apple.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">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.</div><div class=""><br class=""></div><div class="">Here’s the basic switch JIT algorithm:</div><div class=""><br class=""></div><div class="">jitSwitchRecurse(cases) {</div><div class=""> if (cases.size < N) {</div><div class=""> for (C in cases) {</div><div class=""> emit code that checks, and executes, C</div><div class=""> }</div><div class=""> fall through to default</div><div class=""> } else {</div><div class=""> // 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: <a href="https://bugs.webkit.org/show_bug.cgi?id=141046" class="">https://bugs.webkit.org/show_bug.cgi?id=141046</a></div><div class=""> 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</div><div class=""> lessThanJump = emit lessThan comparison against M</div><div class=""> jitSwitchRecurse(those cases that are >= M)</div><div class=""> lessThanJump.link()</div><div class=""> jitSwitchRecurse(those cases that are < M)</div><div class=""> }</div><div class=""><br class=""></div><div class="">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 <i class="">significantly</i> more optimal for default: it usually results in two fewer comparisons before getting to default. N = 3 is <i class="">slightly</i> 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.</div><div class=""><br class=""></div><div class="">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?</div><div class=""><br class=""></div><div class="">-Filip</div><div class=""><br class=""></div></div></div></blockquote></div><br class=""></div></div></div></body></html>