<< Back to previous view

[CLJS-713] optimized case Created: 04/Dec/13  Updated: 22/Feb/14

Status: Open
Project: ClojureScript
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: David Nolen Assignee: Michał Marczyk
Resolution: Unresolved Votes: 0
Labels: None

Attachments: Text File 0001-CLJS-713-first-cut-at-compiling-case-to-switch.patch    

 Description   

With the advent of asm.js many engines will like compile switch statements over integers into jump tables. We should provide a real `case*` ast node that compiles to JS `switch` when possible - i.e. numbers, strings, keywords etc.



 Comments   
Comment by Michał Marczyk [ 18/Feb/14 5:56 PM ]

First cut impl also available here:

https://github.com/michalmarczyk/clojurescript/tree/713-compile-case-to-switch

With this patch applied, case expressions are compiled to switch + some extra bits when all tests are numbers or strings, otherwise old logic is used.

For example, {{(fn [] (let [x 1] (case x 1 :foo (2 3) :bar :quux)))}} gets compiled to

function () {
    var x = 1;
    var G__6469 = x;
    var caseval__6470;
    switch (G__6469) {
      case 1:
        caseval__6470 = new cljs.core.Keyword(null, "foo", "foo", 1014005816);
        break;
      case 2:
      case 3:
        caseval__6470 = new cljs.core.Keyword(null, "bar", "bar", 1014001541);
        break;
      default:
        caseval__6470 = new cljs.core.Keyword(null, "quux", "quux", 1017386809);
    }
    return caseval__6470;
}

The existing test suite passes, but I suppose it wouldn't hurt to add some tests with case in all possible contexts.

Comment by Michał Marczyk [ 18/Feb/14 6:05 PM ]

As a next step, I was planning to arrange things so that numbers/strings are fished out from among the tests and compiled to switch always, with any leftover tests put in an old-style nested-ifs-based case under default:. Does this sound good?

It seems to me that to deal with symbols and keywords in a similar manner we'd have to do one of two things:

1. check symbol? and keyword? at the top, then compile separate switches (the one for keywords would extract the name from the given keyword and use strings in the switch);

2. use hashes for dispatch.

Which one sounds better? Or is there a third way?

Comment by Michał Marczyk [ 18/Feb/14 6:11 PM ]

Of course we'd need to compute hashes statically to go with 2. I'd kind of like it if it were impossible (randomized seed / universal hashing), but currently it isn't.

Comment by Francis Avila [ 19/Feb/14 12:22 AM ]

At least on v8, there are surprisingly few cases where a switch statement will be optimized to a jump table. Basically the type of the switched-over value must always (across calls) match the type of every case, and there must be fewer than 128 cases, and integer cases must be 31-bit ints (v8's smi type). So mixing string and number cases in the same switch guarantees the statement will never be compiled. In many cases an equivalent if-else will end up being significantly faster on v8 just because the optimizing jit recognizes them better. There's an oldish bug filed against v8 switch performance. Looking at the many jsperfs of switch statements, it doesn't seem that v8 has improved. Relevant jsperf

Firefox is much better at optimizing switch statements (maybe because of their asm.js/emscripten work) but I don't know what conditions trigger (de)optimization.

I suspect the best approach is probably going to be your option one: if-else dispatch on type if any case is not a number, and then a switch statement covering the values for each of the keyword/string/symbol types present (no nested switch statements, and outlining the nested switches might be necessary). Even with a good hash, to guarantee v8 optimizing-compilation you would need to truncate the hashes into an smi (signed-left-shift once?) inside the case*.

Comment by David Nolen [ 19/Feb/14 12:50 AM ]

There's no need for invention here. We should follow the strategy that Clojure adopts - compile time hash calculation.

Comment by Francis Avila [ 19/Feb/14 3:09 PM ]

The problem, as Michal alluded to, is that the hash functions in cljs's runtime environment are not available at compile-time (unlike in Clojure). This might be a good opportunity to clean up that situation or even use identical hash values across Clojure and Clojurescript (i.e. CLJS-754), but that's a much bigger project. Especially considering it will probably not bring much of a speedup over an if-else-if implementation except in very narrow circumstances.

Comment by David Nolen [ 19/Feb/14 4:38 PM ]

Francis Avila I would make no such assumptions about performance without benchmarks. One of the critical uses for case is over keywords. Keyword hashes are computed at compile time, so that's one function call and a jump on some JavaScript engines. This is particularly useful for the performance of records where you want to lookup a field via keyword before checking the extension map.

This ticket should probably wait for CLJS-754 before proceeding.

Comment by Francis Avila [ 22/Feb/14 4:44 AM ]

Record field lookup is a good narrow use case to test. I put together a jsperf to compare if-else (current) vs switch with string cases vs switch with int cases (i.e., hash-compares, assuming perfect hashing).

Generated at Wed Apr 23 15:31:45 CDT 2014 using JIRA 4.4#649-r158309.