611423 - Getting integer-named properties from non-Array objects is slower than Chrome

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[David Humphrey (:humph)]

Probably known, and in other bugs, but in case not, this surprised me...

I did a small test to look at performance of for..in vs. for loops, and a side-effect of this test is that I noticed that Chrome is a lot faster than us iterating across an regular array.  Looking at

http://audioscene.org/scene-files/humph/perf/loop-perf.html

Chrome: 1173ms/90ms
Chromium: 1165ms/56ms

FF 3.6: 3457ms/421ms
Minefield: 1996ms/270ms

Safari: 1391ms/870ms
WebKit: 986ms/855ms

It's mainly the 56ms vs. 270ms that caught my eye.

Comment 1

[Boris Zbarsky [:bzbarsky]]

David, what numbers do you get if you turn off methodjit?  What if you turn off tracejit?  Pending billm's most recent changes to profiling stuff, that loop is getting run in JM, not TM... With his changes, I don't know, but it would be good to at least have an idea of what the numbers look like for JM vs TM.

Over here it looks like tracejit is at least 30% faster than methodjit on the for loop, and over 2x slower on the for/in loop (why?).

Comment 2

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

I just tried this on a 32-bit build in the shell and the tracejit and methodjit seem to be about the same in both tests. Chrome is several times faster on the for loop and around 60% faster on the for..in loop.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Ah, I was using a 64-bit build (and browser, but that should matter less)...  I wonder why I was seeing the for..in difference with TM being slower, though.

Comment 4

[Boris Zbarsky [:bzbarsky]]

And now I can't reproduce that effect (in shell)....

In any case, profiling the for loop, I see the following:

TM:
 25% trace-generated code
 22% self time in js::GetPropertyByIndex
 30% self time in js_GetProperty (called from js::GetPropertyByIndex)
 22% self time in js::PropertyTable:search (called from GetProperty)

JM:
 33% mjit-generated code
 22% self time in stubs::GetElem
 24% self time in js_GetProperty
 17% self time in js::PropertyTable::search

The search self times might get better as a result of fixing bug 610370 (because we'll replace a linear walk with a hashtable lookup).  But the rest of it will still be there.

So basically, most of the time is spent getting the property off |items|, not doing anything with the array.  This is because the property names for |items| are integers, and there are lots and lots of them...

This is fast in V8 because V8 has no difference between arrays and other objects; all objects support fast array-like access.  See also bug 586842.

Comment 5

[Boris Zbarsky [:bzbarsky]]

Though note that if I modify the testcase to use |i+"x"| as the property name in |items| and the value in |keys|, like so:

for (var i=0; i<1000; i++) {
  items[i+"x"] = i;
  keys.push(i+"x");
}

then:

1)  The time it takes us to do the |for ... in| thing goes down by a factor
    of 2 (I think we're doing a bunch of int-to-string conversions here when
    the property names are ints or something)
2)  The time it takes us to do the for loop goes up by a factor of 4.  It is
    now about equal to the |for ... in| time.
3)  The time it takes for V8 to do the |for ... in| loop gies up by 50% (ends
    up 2x slower than us).
4)  The time it takes for V8 to do the for loop goes up by a factor of 7 (but
    is still about 3x faster than us).

Comment 6

[Boris Zbarsky [:bzbarsky]]

Our time at that point is spent in the following places:

  42% under js_AtomizeString (called from js::GetPropertyByName).  Lots of fun
      CAS and locking and stuff here.
  39% js::GetPropertyByName self time
   9% js::PropertyTable::search (see bug 610370)
  12% self time in js_GetPropertyHelperWithShape.

So totally different bottlenecks from the integer situation.

Comment 7

[Brendan Eich [:brendan]]

Andreas, we never made a fast iterator for dense arrays, did we?

/be

Comment 8

[Nicholas Nethercote [inactive]]

Bug 827490 just landed.  Does it help?

Comment 9

[David Humphrey (:humph)]

Attachment: Test case

The original test case seems to be down, but this is what I was using when I filed.

Comment 10

[David Humphrey (:humph)]

On my Mac:

FF Stable:

For...In took 889 ms for 5000 test runs.
For...Loop with keys array took 199 ms for 5000 test runs.

FF Nightly:

For...In took 1427 ms for 5000 test runs.
For...Loop with keys array took 507 ms for 5000 test runs.

So not better, no.

Comment 11

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

I don't think bug 827490 will hit nightly until tomorrow.

Comment 12

[Zibi Braniecki [:zbraniecki][:gandalf]]

David:

I don't see the regression that you noticed on macos. What OS? Is it Firebug maybe?

Fx Nightly:

For...In took 1255 ms for 5000 test runs.
For...Loop with keys array took 442 ms for 5000 test runs.

Fx Stable:

For...In took 1145 ms for 5000 test runs.
For...Loop with keys array took 426 ms for 5000 test runs.

Comment 13

[David Humphrey (:humph)]

I'm running 10.6.8, and no, not using Firebug.

FF Stable: (Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:17.0) Gecko/20100101 Firefox/17.0)

For...In took 862 ms for 5000 test runs.
For...Loop with keys array took 183 ms for 5000 test runs.

FF Nightly (Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:21.0) Gecko/20130112 Firefox/21.0)

For...In took 1872 ms for 5000 test runs.
For...Loop with keys array took 23 ms for 5000 test runs.

That's way better than yesterday, so maybe this patch has landed?  For comparison, here's Chrome on my box:

For...In took 841 ms for 5000 test runs.
For...Loop with keys array took 15 ms for 5000 test runs.

And Safari:

For...In took 865 ms for 5000 test runs.
For...Loop with keys array took 639 ms for 5000 test runs.

Comment 14

[Guilherme Lima]

Nightly
For...In took 2003 ms for 5000 test runs.
For...Loop with keys array took 12 ms for 5000 test runs.

Chrome 31
For...In took 1778 ms for 5000 test runs.
For...Loop with keys array took 16 ms for 5000 test runs.

IE 10
For...In took 1129 ms for 5000 test runs.
For...Loop with keys array took 197 ms for 5000 test runs.

Comment 15

[Boris Zbarsky [:bzbarsky]]

Ok, so this fixed, in that 12ms is less than 16ms.  ;)