675167 - Improve speed of javascript with Minimax Algorithm

Status: RESOLVED WORKSFORME

(Core :: JavaScript Engine, defect)

Description

[Thanassis Tsiodras]

User Agent: Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/534.30 (KHTML, like Gecko) Chrome/12.0.742.122 Safari/534.30

Steps to reproduce:

I created a Javascript port of my Score4 game:

http://users.softlab.ntua.gr/~ttsiod/score4js.html


Actual results:

I then tried it under my Windows 7 64bit with all the 5 major browsers: IE9, Firefox5, Chrome12, Opera 11.5 and Safari 5.1. Results were...

Google Chrome 12.0.742.122 - 2.147 seconds
Internet Explorer 9.0.8112.16421 - 4.007 seconds
Safari 5.1 (7534.50) - 4.754 seconds
Opera 11.50 (build 1074) - 5.016 seconds
Firefox 5.0.1 - 7.328 seconds


Expected results:

Well, my favorite browser should not have been lagging 3.5 times behind Chrome!

Seriously, I know this is not actually a bug - but I don't know what forum to address this to, in order to indicate it to the JavaScript engine maintainers...

Comment 1

[Mardeg]

Work on this would need to happen on trunk, so I moved the version to that.
Can someone please test this with TI or perhaps on IonMonkey?

Comment 2

[Makoto Kato [:m_kato]]

Nightly ... 7.641sec
TI Nightly ... 2.467sec
Chrome 14 ... 2.043sec

Comment 3

[Boris Zbarsky [:bzbarsky]]

Thanassis, would you mind attaching a self-contained version of the testcase to this bug so it doesn't disappear on us?

Comment 4

[Thanassis Tsiodras]

I don't mind at all - attaching the self-sufficient .html now.

Comment 5

[Thanassis Tsiodras]

Attachment: Just open this .html and click on the middle column.

Comment 6

[Jan de Mooij [:jandem]]

Attachment: Shell testcase

JM tip:

js -m -n    : 2.2
d8          : 2.4
js -m       : 5.2
js -m -j -p : 7.3

Maybe my d8 is outdated, but it looks like TI helps us here. With the last JM nightly I get 3.1 seconds though, not sure why it's slower. Need to run, will investigate later.

Comment 7

[Jan de Mooij [:jandem]]

(In reply to comment #6)
> With the last
> JM nightly I get 3.1 seconds though, not sure why it's slower.

To be clear, 3.1 seconds in the browser, 2.2 in the shell.

Comment 8

[Jan de Mooij [:jandem]]

OK, I get 3 seconds with TI+JM in the browser, 2 seconds after removing the prototype.js include. I will bisect prototype.js to find out what causes this.

Comment 9

[Thanassis Tsiodras]

No,no - the .html is standalone - disregard the included .js, they have no impact whatsoever (remove the references to see).

Comment 10

[Thanassis Tsiodras]

No impact whatsoever: I mean they have to do with rendering the page, and are not called during the move calculations.

Comment 11

[Thanassis Tsiodras]

From the comments so far, I am getting the picture that speed has already improved a lot, just not in the "Stable" Firefox that people are using. Correct?

Comment 12

[Boris Zbarsky [:bzbarsky]]

Speed has improved a lot on the type inference branch.  It's a few months from being in a stable release, though.

And the point of comment 8 was that simply including prototype.js but doing nothing with it makes this script run 50% slower on the type inference branch.  That's what Jan was going to look into.

Comment 13

[Thanassis Tsiodras]

Oh, I see. Thanks for clarifying.

Comment 14

[Jan de Mooij [:jandem]]

Attachment: Hacked shell testcase

The problem is that prototype.js adds many properties to Array.prototype. This attachment demonstrates the problem.

I added this:
--
function foo() {
    return 0;
}
(function() {
    var N = 50;
    for (var i=0; i<N; i++) {
        Array.prototype["foo" + i] = foo;
    }
})();
--
N = 39 is fast (2.3 seconds), N >= 40 is slow (3.2 seconds). With N = 40, Array.prototype has 64 properties according to Object.getOwnPropertyNames(Array.prototype).

Brian, does TI have a property limit somewhere? I vaguely remember a 64-properties-limit somewhere else, but I don't see this problem with -m -j -p.

Comment 15

[Jan de Mooij [:jandem]]

Thanassis, thanks for reporting this btw! Brian Hackett's type inference branch fixes the problem for the most part but there's still the problem in comment 14. Since prototype.js is quite common, it's good to know about this.

With this fixed we should be about as fast as V8.

Comment 16

[Thanassis Tsiodras]

I am glad this helped improve Firefox. Thank you, for all your work.

Comment 17

[Jan de Mooij [:jandem]]

Simpler testcase:
--
function foo() {
    return 0;
}
(function() {
    var N = 30;
    for (var i=0; i<N; i++) {
        Array.prototype["foo" + i] = foo;
    }
})();

var a = [1, 2, 3, 4, 5];

function g() {
    var x = 0;
    for (var i=0; i<100; i++) {
        x = a[0];
    }
}
g();
--
With N >= 40 there's a type barrier for the GETELEM because the element type is unknown.

Comment 18

[Jan de Mooij [:jandem]]

Argh, the problem is not the *number* of properties we add to Array.prototype but whether we add these properties from JM or in the interpreter (after 40 iterations we compile the function, should have realized this earlier).

So this also slows us down:
--
(function() {
    for (var i=0; i<50; i++) {};
    var j = 0;
    Array.prototype["foo" + j] = foo;
})();
--
The reason properties are marked unknown is this:

/*
 * Mark as unknown any object which has had dynamic assignments to
 * non-integer properties at SETELEM opcodes. This avoids making large
 * numbers of type properties for hashmap-style objects. :FIXME: this
 * is too aggressive for things like prototype library initialization.
 */

Comment 19

[Brian Hackett [Laid off!]]

Mmm, JM and the interpreter should definitely do the same thing here.  Had been wondering how to fix this right for a while, and then the solution presented itself with the last TI refactoring.  We keep track of property types for singleton objects lazily now, so we can be precise for such objects without bloating the type object even for hashmap-style objects.  In this case Array.prototype has singleton type so we should be precise, something is just plain broken.

Comment 20

[Brian Hackett [Laid off!]]

We were testing for a lazy type on the affected JS object, not a singleton type.  This fixes things so that SETELEM of string properties on singletons does not mark their properties unknown, and also a followup issue where we would still mark the element type of the singleton with the SETELEM rhs (when the singleton is Array.prototype, this would also disable optimized paths on array accesses).  Performance should be the same with and without including prototype.js

http://hg.mozilla.org/projects/jaegermonkey/rev/674160662e80

Comment 21

[Jan de Mooij [:jandem]]

Yes, I get 2.142 ms with the latest 32-bit JM tinderbox build, Chrome 14 gets 2.407 ms.

I will add the version which adds some properties to Array.prototype to assorted so that we don't regress this (or something else in this script).

Comment 22

[Ahmad Saleem]

My result:
I used latest Mozilla Firefox Nightly (http://hg.mozilla.org/mozilla-central/rev/b422fd99fe0d) with fresh profile:
FF8 Nightly: 5.345 sec
Chrome 14.0.835.18: 1.585 sec

Hope this will be helpful!

Comment 23

[Boris Zbarsky [:bzbarsky]]

> Hope this will be helpful!

Adding more timing data to a bug with lots of existing timing data, plus information on how things can be made faster plus links to builds in which things are faster is generally not all that helpful, unless the timing data is for those builds (like comment 21, say).

Comment 24

[Thanassis Tsiodras]

With Firefox 9, speed is now just as good as with Chrome. Kudos, Mozilla engineers!

Comment 25

[Tom S [:evilpie]]

Thank you, I fixed that in Bug 685150. And also added quite a few regression tests.

Comment 26

[Brian Hackett [Laid off!]]

(In reply to Tom Schuster (evilpie) from comment #25)
> Thank you, I fixed that in Bug 685150. And also added quite a few regression
> tests.

I don't think this site is bound on Math.min or Math.max.

Comment 27

[Tom S [:evilpie]]

Oh, I kind of skimmed that ...