578756 - JM: Make iteration over properties fast

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[David Mandelin [:dmandelin]]

A microbenchmark:

  var o = { a: 1, b: 2, c: 3, d: 4 };
  for (var i = 0; i < 1000000; ++i) {
      for (var k in o) {}
  }

JSC is 2x as fast as JM is on this. (FTR, JM is currently 15% faster than TM on this benchmark.) It's probably kind of hard, but obviously iteration is big feature of JS, so we should be faster. So far I know this is affecting us a bit on fasta.

JM wanted SS win: 5 ms

Comment 1

[Brendan Eich [:brendan]]

So this is the "fast-path iterator that moves along enumerable property list" bug, I hear.

/be

Comment 2

[Brian Hackett [Laid off!]]

Should this bug encompass just making 'for (var k in o) {}' fast, or also 'for (var k in o) { o[k] }'? (certainly lots of overlap, don't know how much though).

Comment 3

[David Mandelin [:dmandelin]]

(In reply to comment #2)
> Should this bug encompass just making 'for (var k in o) {}' fast, or also 'for
> (var k in o) { o[k] }'? (certainly lots of overlap, don't know how much
> though).

We do need both. This one was originally filed for the version with the empty body, and comment 0 has the corresponding microbenchmark, so I guess we should file a new bug for making the property access inside said loop fast. I created a little confusion because I originally thought that you were working on a patch that would speed up the empty loop as well.

Anyway, please file a new bug for making the getelem faster.

Comment 4

[Brian Hackett [Laid off!]]

Cool, the new bug is 580138.  I'll look at this one too.

Comment 5

[Brian Hackett [Laid off!]]

Attachment: fast paths for ITER and ENDITER, cache streamlining

This patch adds fast paths for ITER and ENDITER, and changes the native iterator cache to accommodate these paths.  For this microbenchmark (if I use the one in comment 0 straight up the global accesses are really slow):

function foo() {
  var o = { a: 1, b: 2, c: 3, d: 4 };
  for (var i = 0; i < 1000000; ++i) {
      for (var k in o) {}
  }
}
foo();

I get times:

JSC: 43ms
JM (old): 107ms
JM (new): 37ms

I get a 4.5ms improvement on string-fasta (33.5ms -> 29ms).

Cache changes: add a flag to NativeIterator indicating whether it is in active use; iterators are not evicted from the cache when they are active, so they do not need to be added back when finished.  Additionally, keep a lastNativeIterator in JSThreadData for the most recently used iterator.  The fast path will only match against this one, fortunately it is hit by the iterators in string-fasta and string-tagcloud (the only ones which seem to do repeated iteration).

Comment 6

[David Mandelin [:dmandelin]]

Looks great. Let's get it reviewed and landed!

Comment 7

[Brian Hackett [Laid off!]]

Who should review this?  It's touching both JM and iterator stuff.

Comment 8

[David Mandelin [:dmandelin]]

How about dvander for JM and gal for iterators?

Comment 9

[Brian Hackett [Laid off!]]

Attachment: bugfix for nested iterators

Fix a regression on trace-test.  This now has the same baseline failures on trace-test as jaegermonkey, and all jstests pass.

Comment 10

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

Comment on attachment 458835 [details] [diff] [review]
bugfix for nested iterators


>+    /* Stub the call if this is not a simple 'for in' loop or if the iterated
>+     * value is known to not be an object. */

House style for multi-lines is:

      /*
       * Stub the call if this is not a simple 'for in' loop or if the iterated
       * value is known to not be an object.
       */

>+    /* Compare shape of object with iterator. TODO: shapeless objects? */

Andreas should say something - I think it's safe as long as you don't cache non-native objects.

>+    masm.loadData32(Address(reg, offsetof(JSObject, map)), T1);
>+    masm.loadData32(Address(T1, offsetof(JSObjectMap, shape)), T1);

Prefer masm.loadShape() helper here, and

>+    masm.loadData32(Address(T1, offsetof(JSObject, map)), T1);
>+    masm.loadData32(Address(T1, offsetof(JSObjectMap, shape)), T1);

here.

>+    /* Compare object's prototype's prototype with NULL. */

Is the idea that you don't cache objects with deep proto chains? Is this to avoid the proto walk? If so, quick comment to explain would be good.

>+    /* Push the iterator object. */
>+    frame.pop();
>+    frame.pushTypedPayload(JSVAL_TYPE_OBJECT, ioreg);

These frame changes must occur after...

>+    stubcc.leave();
>+    stubcc.masm.move(Imm32(flags), Registers::ArgReg1);
>+    stubcc.call(stubs::Iter);

... here, because leave() and call() expect the same stack depth as linkExit(). It doesn't matter in this case but I try to keep it consistent everywhere to avoid mistakes in new ops. Note that the freeReg() calls are okay (they can go anywhere, though the sooner the better because linkExit can do a better job with more registers).

>+    stubcc.rejoin(Changes(1));
>+}

This is in the right place too (pattern is: linkExits ; leave ; call ; pops/pushes ; rejoin).

>+    stubcc.leave();
>+    stubcc.call(stubs::EndIter);
>+    stubcc.rejoin(Changes(1));
>+
>+    frame.pop();
>+}

Same re-arrangement needed.

r+ for JM side w/ those fixed

Comment 11

[Brian Hackett [Laid off!]]

Attachment: patch fixing issues in comment 10

Comment 12

[Brian Hackett [Laid off!]]

Attachment: patch fixing GC hazard

This patch should fix the GC hazard described in bug 585749.  Shapes are regenerated for the native iterator before its initial insertion into the cache, and (as in earlier patches) it is not removed/reinserted into the cache so will be flushed at the next GC.

Comment 13

[David Mandelin [:dmandelin]]

Comment on attachment 464444 [details] [diff] [review]
patch fixing GC hazard

Looks OK. A couple of things, though:

- my first try at fixing the GC issue caused a huge perf regression, so make extra sure perf comes out OK.

- GetIterator is getting pretty gross, with 2 open-coded caches. I would prefer 0. It is maybe not an urgent issue, but if it can be fixed easily now, it's probably a good idea. Otherwise we can do a followup for when there is more time.

Comment 14

[Brian Hackett [Laid off!]]

This is in moo now.

- This should improve string-fasta by 4-5ms.

- As we discussed last week, this could be improved by using a PIC.  I'm not convinced this is any better for code complexity (instead of a gross centralized cache, the caches would be spread around the generated code making GC interaction trickier etc.), but it would be faster on certain workloads that don't show up on SS (multiple hot sites, each repeatedly iterating over objects with the same shape).

Comment 15

[David Mandelin [:dmandelin]]

(In reply to comment #14)
> - This should improve string-fasta by 4-5ms.

Great. Looks like you got about 9 total.

> This is in moo now.

Side note: custom is to post a comment like this:

http://hg.mozilla.org/users/danderson_mozilla.com/moo/rev/3a6f645100eb

Evolving convention is also to mark JM bugs fixed once they land in moo.

Comment 16

[David Mandelin [:dmandelin]]

I had to back this out due to tinderbox failures. A quick one is this, which asserts right away:

TEST_PATH=MochiKit-1.4.2/tests/test_MochiKit-Visual.html make mochitest-plain

See also our new TBPL at 

  http://tests.themasta.com/tinderboxpushlog/?tree=Jaegermonkey 

for the full list. Also check out 

  http://hg.mozilla.org/projects/jaegermonkey/rev/a58469686294

which fixed some x64 build bustage.

Comment 17

[Brian Hackett [Laid off!]]

Attachment: patch fixing tinderbox failures

This patch fixes the xpcshell and jsreftests failures on my machine, the problem was an assert tripping on shapeless objects in a place where shapeless objects are OK.

This also incorporates sstangl's fix a58469686294 disabling for x64.

Comment 18

[Brian Hackett [Laid off!]]

Second try:

http://hg.mozilla.org/projects/jaegermonkey/rev/7767b9e50bfa

Comment 19

[Jan de Mooij [:jandem]]

Seems to have stuck.

http://hg.mozilla.org/mozilla-central/rev/7767b9e50bfa