Improve speed of javascript with Minimax Algorithm

RESOLVED WORKSFORME

Status

()

defect
RESOLVED WORKSFORME
8 years ago
6 years ago

People

(Reporter: ttsiodras, Assigned: bhackett)

Tracking

(Blocks 1 bug, {perf})

Trunk
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: js-triage-done)

Attachments

(3 attachments)

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...
Component: General → Nanojit
OS: Windows 7 → All
Product: Firefox → Core
QA Contact: general → nanojit
Hardware: x86_64 → All
Version: 5 Branch → Trunk
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?
Summary: Firefox 5 is the slowest one by far in this JavaScript game I made → Improve speed of javascript with Minimax Algorithm
Keywords: perf
Nightly ... 7.641sec
TI Nightly ... 2.467sec
Chrome 14 ... 2.043sec
Assignee: nobody → general
Component: Nanojit → JavaScript Engine
QA Contact: nanojit → general
Thanassis, would you mind attaching a self-contained version of the testcase to this bug so it doesn't disappear on us?
Status: UNCONFIRMED → NEW
Ever confirmed: true
I don't mind at all - attaching the self-sufficient .html now.
Posted file 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.
(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.
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.
No,no - the .html is standalone - disregard the included .js, they have no impact whatsoever (remove the references to see).
No impact whatsoever: I mean they have to do with rendering the page, and are not called during the move calculations.
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?
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.
Oh, I see. Thanks for clarifying.
Blocks: WebJSPerf
Whiteboard: js-triage-needed
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.
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.
Whiteboard: js-triage-needed → js-triage-done
I am glad this helped improve Firefox. Thank you, for all your work.
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.
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.
 */
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.
Attachment #549384 - Attachment mime type: text/plain → text/html
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
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).
Assignee: general → bhackett1024
Status: NEW → ASSIGNED
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!
> 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).
With Firefox 9, speed is now just as good as with Chrome. Kudos, Mozilla engineers!
Status: ASSIGNED → RESOLVED
Closed: 8 years ago
Resolution: --- → WORKSFORME
Flags: in-testsuite?
Thank you, I fixed that in Bug 685150. And also added quite a few regression tests.
Flags: in-testsuite? → in-testsuite+
(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.
Oh, I kind of skimmed that ...
Flags: in-testsuite+ → in-testsuite?
Flags: in-testsuite?
You need to log in before you can comment on or make changes to this bug.