667096 - SpiderMonkey is 4.5x slower than v8 on plb sudoku benchmark

Status: RESOLVED WORKSFORME

(Core :: JavaScript Engine, defect)

Description

[David Mandelin [:dmandelin]]

It's easiest to check out the suite from git:

  git clone https://github.com/attractivechaos/plb.git


$ time d8 sudoku_v2.js < sudoku.txt > /dev/null
gc scavenge 1886560 0.707637

real	0m0.311s
user	0m0.303s
sys	0m0.008s

$ time js -m -a sudoku_v2.js < sudoku.txt > /dev/null
real	0m3.603s
user	0m3.587s
sys	0m0.010s

$ time js -j sudoku_v2.js < sudoku.txt > /dev/null

real	0m3.597s
user	0m3.589s
sys	0m0.006s

host-5-88:sudoku dmandelin$ time js sudoku_v2.js < sudoku.txt > /dev/null
real	0m3.607s
user	0m3.595s
sys	0m0.006s

It's as if the code is not running in the jits.

Comment 1

[Jan de Mooij [:jandem]]

Cool website. For me the interpreter is much slower here, 5.2s vs. 0.6 with -m -a, 32-bit OS X TM shell.

Comment 2

[David Mandelin [:dmandelin]]

(In reply to comment #1)
> Cool website. For me the interpreter is much slower here, 5.2s vs. 0.6 with
> -m -a, 32-bit OS X TM shell.

I get similar results on my Windows machine. Something must be wrong with my build on Mac, or it's not running the right flags, or something.

Comment 3

[David Mandelin [:dmandelin]]

Bleh, I had the wrong incantation for a 32-bit Mac build. This is what I get now:

host-5-88:opt32 dmandelin$ time shell/js -m -a ~/sources/plb/sudoku/sudoku_v2.j
s < ~/sources/plb/sudoku/sudoku.txt > /dev/null

real    0m0.526s
user    0m0.518s
sys     0m0.006s
host-5-88:opt32 dmandelin$ time shell/js -j ~/sources/plb/sudoku/sudoku_v2.js <
 ~/sources/plb/sudoku/sudoku.txt > /dev/null

real    0m0.468s
user    0m0.459s
sys     0m0.007s

Not quite such a big deal now.

Comment 4

[Boris Zbarsky [:bzbarsky]]

OK, so on my machine I see these numbers on jaegermonkey: 

interp:      2.853u 0.011s 0:02.86 100.0%    0+0k 0+0io 0pf+0w
-j -m -p -a: 0.558u 0.007s 0:00.56 98.2%     0+0k 0+0io 0pf+0w
-m:          0.593u 0.006s 0:00.60 98.3%     0+0k 0+0io 0pf+0w
-m -n:       0.318u 0.008s 0:00.32 96.8%     0+0k 0+0io 0pf+0w
d8:          0.434u 0.004s 0:00.44 97.7%     0+0k 0+0io 0pf+0w

So bhackett wins again.  ;)

Comment 5

[Jan de Mooij [:jandem]]

The website shows SM to be 4.8x slower than V8 (18.1 vs 3.7). Anybody knows how he runs the tests?

Comment 6

[David Mandelin [:dmandelin]]

OK, I can more or less reproduce the 4.8x on the website. The author apparently cats together 50 copies of sudoku.txt as the input. Somehow the larger input gives a bigger advantage to V8. I would guess either amortization of compile time, or better GC behavior. It would be great to get a profiler run on this.

Comment 7

[Boris Zbarsky [:bzbarsky]]

Happy to do that, if you can point me to the right URL.

Comment 8

[David Mandelin [:dmandelin]]

(In reply to comment #7)
> Happy to do that, if you can point me to the right URL.

There's a browser version here: 

  http://attractivechaos.github.com/plb/kudoku.html

Btw, I meant sfink's JS profiler--Shark mostly just says "lots of time in jitcode". It does say 30% of time in array_(g|s)etProperty, which might mean some sparse arrays.

Comment 9

[Boris Zbarsky [:bzbarsky]]

Ah.  If you've run Shark already, not much I can help with here....

Pointer to sphink's thing?

Comment 10

[Steve Fink [:sfink] [:s:]]

It's bug 642054, with a simple visualization available at http://people.mozilla.org/~sfink/v8/ui.html

I intended to do this earlier, but I managed to break it while fixing it up for use with the browser instead of just the JS shell, and then I got distracted by something that I wanted to have done by next Tuesday that still isn't quite working. I suppose I should just back up my patch queue to the last working version.

I'll take a swing at it now.

Comment 11

[Steve Fink [:sfink] [:s:]]

For what it's worth: http://people.mozilla.org/~sfink/v8/ui.html#?test=sudoku

It shows 77% of the time in sd_solve and 21% in sd_update. It claims all time is spent in the first line of each script, which is definitely a bug (probably a dumb format change bug or something.) 19% of the sd_solve time is in stub calls; I can resolve those to actual routines with some hand-munging, but it's not going to tell you anything Shark wouldn't, and the kids are awake now so I'll have to do that later.

When I get it to give me proper per-line info again, it may be more revealing.

Comment 12

[Jan de Mooij [:jandem]]

What's confusing here is that there's a sudoku_v1.js and sudoku_v2.js in the GitHub repo. The browser version seems to use v1 and I can only reproduce the ~5 times slower with v1, using dmandelin's instructions in comment 6. This commit [1] indicates v1 was modified and the old v1 was renamed to v2, meaning v1 is the most recent version.

For v1, 50x20 sudoku's:

d8          : 4.1
js -m -j -p : 22.2
js -m -n    : 38.8

For v2:

d8          : 14.9
js -m -j -p : 32.9
js -m -n    : 18.3

v1 modified sd_update and added some ELEMINC, DECELEM etc ops to sd_update. What happens if we replace the ELEMINC and friends in sd_update with equivalent +=, -= ops? (I verified that these modifications don't break the algorithm by comparing the output)

d8          : 4.5
js -m -j -p : 9.5
js -m -n    : 4.3

Suddenly JM+TI is 9x faster, because JM currently always calls a stub for INCELEM etc. The only way to beat V8 here is by making INCELEM fast.

This is especially bad because it's reasonable to assume that "var y = --arr[x]" is at least as fast as "arr[x] -= 1; var y = arr[x]". This is true for V8 (the modified version is a bit slower) but not for SM/JM.

And in case anybody wonders why -m -n is slower than -m -j -p on the unmodified v1, the INCELEM stubs call array_setProperty which calls TypeObject::addPropertyType where we spent quite some time according to the profile, but inlining INCELEM in JM should get rid of that.

1. https://github.com/attractivechaos/plb/commit/fac81548e34cf6f45161be9639a74d56f80f86a0

Comment 13

[Jan de Mooij [:jandem]]

Attachment: Standalone sudoku_v1.js

Added sudoku.txt as an array and a for-loop to solve all sudoku's 50 times, so that you can just run the script like this: ./js sudoku_v1.js This version does *not* have my INCELEM modifications.

Comment 14

[Boris Zbarsky [:bzbarsky]]

Hmm.  The INCELEM/DECELEM thing sounds bad; those are commonly used on the web.

Does JM do stub calls for ELEMINC as well?  Or just INCELEM?

Comment 15

[Boris Zbarsky [:bzbarsky]]

Also, does bug 647624 fix this?  If so, could we land the patch there that got review 3 months ago?

Comment 16

[Jan de Mooij [:jandem]]

(In reply to comment #14)
> Does JM do stub calls for ELEMINC as well?  Or just INCELEM?

Stub calls for all four, ELEMINC, INCELEM, ELEMDEC, DECELEM...

Comment 17

[Boris Zbarsky [:bzbarsky]]

> Stub calls for all four, ELEMINC, INCELEM, ELEMDEC, DECELEM...

Huh.  It's weird that dvander says these are rare on the web; I've certainly seen them a whole bunch in web script....

Comment 18

[David Anderson [:dvander] - inactive, e-mail if emergency]

I probably meant "rare" compared to, say, ADD or LAMBDA, rather than not existing at all. I don't have time to buddy bug 647624 into the tree right now, but it will essentially be an IonMonkey blocker someday.

If anyone wants to take over that bug and get it in I'd be much appreciative!

Comment 19

[Jan de Mooij [:jandem]]

(In reply to comment #18)
> If anyone wants to take over that bug and get it in I'd be much appreciative!

I can probably have a look next week if I have the time. What's needed to finish the patch, except rebasing and (perf) testing?

Comment 20

[David Anderson [:dvander] - inactive, e-mail if emergency]

That's it, I think. It passed tests IIRC.

Comment 21

[Jan de Mooij [:jandem]]

(In reply to comment #12)
> For v1, 50x20 sudoku's:
> 
> d8          : 4.1
> js -m -j -p : 22.2
> js -m -n    : 38.8

Latest JM tip, which has the patch for bug 647624:

js -m -n    :  3.9
d8          :  4.0
js -m       :  8.7
js -m -j -p : 10.3

Nice work!

Comment 22

[Ryan VanderMeulen [:RyanVM]]

So does something need to be done on this bug still?

Comment 23

[Guilherme Lima]

On the "Hardest 20x50" at http://attractivechaos.github.io/plb/kudoku.html I get
3.276s on Nightly and 2.942s on Chrome 30

Comment 24

[Nicholas Nethercote [inactive]]

Close enough, I reckon.