ceylon / ceylon-js

DEPRECATED
Apache License 2.0
54 stars 9 forks source link

cartesian product slow enough to be mistaken for a hang #623

Open jvasileff opened 9 years ago

jvasileff commented 9 years ago

This program seemingly takes forever to finish on js:

shared void run() {
    {[Integer]*} x({[Integer]*} previous={[0]})
        =>  if (previous.empty)
            then {}
            else previous.chain(x(previous
                .filter((row) => row[0] < 101)
                .map((row) => [row[0] + 1])));

    print([for (x1 in x()) for (x2 in x()) 1].size);
}

The x function is an obtuse way to generate a sequence of wrapped integers in the range 0..101.

Adjusting 101 to a lower value, such as 40, does produce results prior to an overwhelming urge to press ctrl-c.

The similar program below runs quickly:

shared void run() {
    {[Integer]*} x() => (0..101).map((i) => [i]);
    print([for (x1 in x()) for (x2 in x()) 1].size);
}
chochos commented 9 years ago

not sure if I'd call this a bug. But some optimization is needed for sure.

chochos commented 9 years ago

It seems a lot of the time is spent in calling the lambdas for map and filter, due to the fact that they're wrapped in special functions that check for spread arguments and tuples and such when invoked.

chochos commented 9 years ago

I already removed redundant initialization but that didn't seem to make much of a difference.

chochos commented 9 years ago

Huh, on a totally unrelated note, if I change {[0]} to Singleton([0]) the time to generate 15 (instead of 101) goes from 1 second to 80ms. So perhaps the optimization should be in the way we render sequenced arguments.

chochos commented 9 years ago

Actually [[0]] is just a fraction faster than {[0]}. So sequenced arguments and tuples are slow.

chochos commented 9 years ago

testing this with 40 takes 6 seconds now on my machine. Up to 101 still takes more than a minute (77 seconds). But please try this again @jvasileff and let me know what you think.

jvasileff commented 9 years ago

Whoa, huge improvement!

ftr, here are some (rough) measurements:

Backend Seconds
JS-20150909 110.063
JS-Current 38.551
Dart 2.201
JVM (no warmup) 0.088
FroMage commented 9 years ago

Dart as in your Ceylon->Dart compiler?

@chochos I don't quite understand why we have 38s for this. Surely there must be a way to get rid of the cruft?

jvasileff commented 9 years ago

Dart as in your Ceylon->Dart compiler?

yes

chochos commented 9 years ago

What I did last was optimize the native tuple implementation; instantiation was taking too long. I already checked the iterable I use for sequenced arguments and there's no obvious bottleneck there (that's how I got to the tuple, in fact). The callables need to be wrapped in case of a spread args call (as in JVM).

Yes the performance sucks but I haven't found a way to make all that stuff about spreading args/flattening/unflattening work fast.

jvasileff commented 9 years ago

Ok, this is a bit insane (and slightly off topic, sorry). I compiled the Dart output to JS using dart2js, fixed up the source since dart:io is not available in js, and ran the benchmark, with a result of 4 seconds.

Note: the timing isn't really fair since the Dart backend doesn't have reified generics.

The proof:

Dart file (modules/simple/1.0.0/simple-1.0.0.dart) compiled to JavaScript: out.js
jvasileff@orion:simple$ 
jvasileff@orion:simple$ vi out.js

[1]+  Stopped                 vi out.js
jvasileff@orion:simple$ node out.js

Warmup round 1/2
10404
Test #1  4259

Warmup round 2/2
10404
Test #1  4171

Benchmarking round 1/2
10404
Test #1  4088*
Test #1  4088/4088/4088/?% (100%)

Benchmarking round 2/2
10404
Test #1  4136
Test #1  4088/4136/4112/0% (100%)

Summary min/max/avg/rstddev/pct
Test #1  4088/4136/4112/0% (100%)
jvasileff@orion:simple$ 
FroMage commented 9 years ago

yes

Kewl :)

FroMage commented 9 years ago

So can we compare the produced code between Dart-js and our js? Is the cost paid for reified generics?

FroMage commented 9 years ago

I don't see anything obvious that would call flatten/unflatten in the original code. I don't think it calls it on the JVM.

FroMage commented 9 years ago

In other words: why would map and filter do anything special wrt spread/tuple arguments?

jvasileff commented 9 years ago

If @chochos is interested I can make it available. It's 3.4MB and includes a significant portion of the language module.

chochos commented 9 years ago

it's not that map and filter do anything special about that. It's that any function reference can be called with spread or tuple args. That's easier to check on the JVM than on JS

chochos commented 9 years ago

@jvasileff mine's only 3K (without language module of course), plus 1K for the model.

FroMage commented 9 years ago

On the JVM functions can only be called one way. You only pay for spreading when you spread. Can't you do the same?

jvasileff commented 9 years ago

Haha, yeah. For the language module in particular, each object satisfies Iterable<T> { } is pretty big in Dart (and Java) with all of the bridge methods. And no telling what dart2js does.

To be fair, the simple.dart module is 21K including my benchmark utility.

jvasileff commented 9 years ago

So one of these tests will always fail in js:

shared void run() {
    value echoFirst = (Object+ xs) => xs.first;
    assert (echoFirst([[""]]) == [[""]]);
    assert (echoFirst(*[[""]]) == [""]);
}
chochos commented 9 years ago

hmmm that sounds like a separate bug. Something to do with that damn wrapper for spreading.

chochos commented 9 years ago

OK so that latest example works now @jvasileff but I'm still searching for ways to optimize function ref calls.

FroMage commented 9 years ago

Unless you can pull a magic trick and make it FTL, shall we move this to 1.3?

chochos commented 9 years ago

definitely not FTL but I'm (was?) working on something that reduces the time by half. But I'm afraid it requires moving around a lot of stuff related to callable references and wrapping callables etc, and we need to maintain backwards compat, so yeah moving this to 1.3 seems the most prudent thing to do at this point.

FroMage commented 9 years ago

Cool.