<< Back to previous view

[CLJS-713] optimized case Created: 04/Dec/13  Updated: 23/Jun/14

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

Type: Enhancement Priority: Major
Reporter: David Nolen Assignee: David Nolen
Resolution: Unresolved Votes: 0
Labels: None

Attachments: Text File 0001-CLJS-713-Allow-test-expressions-for-case-to-be-chars.patch     Text File 0001-CLJS-713-first-cut-at-compiling-case-to-switch.patch    


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.

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

First cut impl also available here:


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);
      case 2:
      case 3:
        caseval__6470 = new cljs.core.Keyword(null, "bar", "bar", 1014001541);
        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).

Comment by David Nolen [ 10/May/14 3:59 PM ]

I've merged the case* analyzer and emitter bits by hand into master.

Comment by David Nolen [ 10/May/14 4:42 PM ]

I'v merged the rest of the patch into master. If any further optimizations are done it will be around dispatching on hash code a la Clojure.

Comment by Francis Avila [ 11/May/14 12:53 AM ]

Your keyword-test optimization has a bug: https://github.com/clojure/clojurescript/commit/9872788b3caa86f639633ff14dc0db49f16d3e2a

Test case:

(let [x "a"] (case x :a 1 "a"))
;=> 1
;;; Should be "a"

Github comment suggests two possible fixes.

Comment by David Nolen [ 11/May/14 10:50 AM ]

Thanks fix in master.

Comment by Christoffer Sawicki [ 23/Jun/14 3:41 PM ]

case over "chars" is currently not being optimized to switch (in other words: (case c (\a) :a :other) uses if instead of switch).

Given that ClojureScript chars are just strings of length 1, could this perhaps simply be fixed by tweaking https://github.com/clojure/clojurescript/blob/master/src/clj/cljs/core.clj#L1187 ?

Comment by Christoffer Sawicki [ 23/Jun/14 4:11 PM ]

OK, I couldn't resist trying and it seems to be that easy. Would be great if somebody more knowledgeable could look at it and say if it has any side-effects. (See patch with name 0001-CLJS-713-Allow-test-expressions-for-case-to-be-chars.patch.)

Comment by David Nolen [ 23/Jun/14 4:15 PM ]

The patch looks good I would have applied it if I hadn't already gone and done it master myself just now

Comment by Christoffer Sawicki [ 23/Jun/14 4:22 PM ]

Hehe. Thanks! Don't forget to update the "case* tests must be numbers or strings" message on line 496 too.

Comment by David Nolen [ 23/Jun/14 4:48 PM ]

The existing docstring is inaccurate - case supports all compile time literals.

Generated at Thu Jul 24 18:13:03 CDT 2014 using JIRA 4.4#649-r158309.