significant slowdown calculating complements

[jvasileff]

Narrowing operations involving several cases can be quite slow. Using the test program:

import ceylon.ast.core {
    Node
}

Anything slowness1(String|Node node)
    =>  if (is String node) then null else null;
    //{ if (is String node) { return null; } else { return node; }

Anything slowness2(String|Node node)
    =>  if (is String node) then null else null;
    //{ if (is String node) { return null; } else { return node; }

Anything slowness3(String|Node node)
    =>  if (is String node) then null else null; 
    //{ if (is String node) { return null; } else { return node; }

Anything slowness4(String|Node node)
    =>  if (is String node) then null else null;
    //{ if (is String node) { return null; } else { return node; }

void load(Node n) {}            

abstract class Foo() {}         

abstract class Enum() of        
A | B | C | D | E | F | G | H | I | J | 
K | L | M | N | O | P | Q | R | S | T {}

class A() extends Enum() {} class B() extends Enum() {}
class C() extends Enum() {} class D() extends Enum() {}
class E() extends Enum() {} class F() extends Enum() {}
class G() extends Enum() {} class H() extends Enum() {}
class I() extends Enum() {} class J() extends Enum() {}
class K() extends Enum() {} class L() extends Enum() {}
class M() extends Enum() {} class N() extends Enum() {}
class O() extends Enum() {} class P() extends Enum() {}
class Q() extends Enum() {} class R() extends Enum() {}
class S() extends Enum() {} class T() extends Enum() {}

I'm getting the following timings on my laptop:

slownessx(String|Node) (as shown above)

$ time ceylon compile-js --suppress-warning
Note: Created module simple/1.0.0

real    0m24.732s
user    0m32.355s
sys 0m0.610s

slownessx(String|Enum)

$ time ceylon compile-js --suppress-warning
Note: Created module simple/1.0.0

real    0m3.796s
user    0m9.294s
sys 0m0.295s

slownessx(String|Foo)

$ time ceylon compile-js --suppress-warning
Note: Created module simple/1.0.0

real    0m1.872s
user    0m4.039s
sys 0m0.232s

And with the slownessx functions commented out:

$ time ceylon compile-js --suppress-warning
Note: Created module simple/1.0.0

real    0m1.788s
user    0m3.924s
sys 0m0.226s

[FroMage]

I suppose it should be possible to optimise for the case of unions and enums and final classes. For example, I suppose String (being final) is necessarily disjoint for the Node union type if it's not already part of it exactly (using equals, not subtyping).

Similarly, adding A (an enumerated type) to B|C (list of cases of the same enumerated type) should not need subtyping to reduce the union type because they're necessarily all disjoint.

[gavinking]

@jvasileff are you saying that this was faster before, and has recently got slower?

[gavinking]

@jvasileff if this is a problem that only occurs in recent builds, would you please try changing the impl of Type.isExactlyNothing() to just return isNothing() and see if that affects anything.

[jvasileff]

@gavinking, no, sorry, I see how that was misleading. I suspect I've been impacted by this for a while, but haven't had such an extreme case.

In fact, I now see that it is gotten faster since May 15th (arbitrarily chosen date.)

I tried the Type.isExactlyNothing() change, and it cuts the time in half for String|Node, but given how slow it is I'm not sure that's meaningful. The Enum test also speeds up, but still a full second wall clock time slower than Foo.

May 15th Test

$ time ~/Dropbox/work-temp/ceylon-20150515/bin/ceylon compile-js
Note: Created module simple/1.0.0

real    0m45.959s
user    0m54.337s
sys 0m0.910s

Current

$ time ceylon compile-js --suppress-warning
Note: Created module simple/1.0.0

real    0m28.134s
user    0m37.628s
sys 0m0.556s

return isNothing() test

$ time ceylon compile-js --suppress-warning
Note: Created module simple/1.0.0

real    0m11.308s
user    0m18.783s
sys 0m0.428s

[jvasileff]

FWIW, testing for Node first is much faster (i.e. if (is Node node) then null else null;, avoiding a huge union result) with significantly less incremental cost for each slownessX.