JM: Make iteration over properties fast

RESOLVED FIXED

Status

()

RESOLVED FIXED
8 years ago
8 years ago

People

(Reporter: dmandelin, Assigned: bhackett)

Tracking

Trunk
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 4 obsolete attachments)

(Reporter)

Description

8 years ago
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
So this is the "fast-path iterator that moves along enumerable property list" bug, I hear.

/be
Assignee: general → bhackett1024
(Assignee)

Comment 2

8 years ago
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).
(Reporter)

Comment 3

8 years ago
(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.
(Assignee)

Comment 4

8 years ago
Cool, the new bug is 580138.  I'll look at this one too.
(Assignee)

Comment 5

8 years ago
Created attachment 458816 [details] [diff] [review]
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).
(Reporter)

Comment 6

8 years ago
Looks great. Let's get it reviewed and landed!
(Assignee)

Comment 7

8 years ago
Who should review this?  It's touching both JM and iterator stuff.
(Reporter)

Comment 8

8 years ago
How about dvander for JM and gal for iterators?
(Assignee)

Comment 9

8 years ago
Created attachment 458835 [details] [diff] [review]
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.
Attachment #458816 - Attachment is obsolete: true
Attachment #458835 - Flags: review?(gal)
Attachment #458835 - Flags: review?(dvander)
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
Attachment #458835 - Flags: review?(dvander) → review+
(Assignee)

Comment 11

8 years ago
Created attachment 459107 [details] [diff] [review]
patch fixing issues in comment 10
Attachment #458835 - Attachment is obsolete: true
Attachment #459107 - Flags: review?(gal)
Attachment #459107 - Flags: review?(dvander)
Attachment #458835 - Flags: review?(gal)
Attachment #459107 - Flags: review?(dvander) → review+
(Assignee)

Comment 12

8 years ago
Created attachment 464444 [details] [diff] [review]
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.
Attachment #459107 - Attachment is obsolete: true
Attachment #464444 - Flags: review?(dmandelin)
Attachment #459107 - Flags: review?(gal)

Updated

8 years ago
Attachment #464444 - Flags: review+
(Reporter)

Comment 13

8 years ago
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.
Attachment #464444 - Flags: review?(dmandelin) → review+
(Assignee)

Comment 14

8 years ago
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).
(Reporter)

Comment 15

8 years ago
(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.
Status: NEW → RESOLVED
Last Resolved: 8 years ago
Resolution: --- → FIXED
(Reporter)

Comment 16

8 years ago
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.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
(Assignee)

Comment 17

8 years ago
Created attachment 464810 [details] [diff] [review]
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.
Attachment #464444 - Attachment is obsolete: true
Attachment #464810 - Flags: review?(dmandelin)
(Reporter)

Updated

8 years ago
Attachment #464810 - Flags: review?(dmandelin) → review+
Seems to have stuck.

http://hg.mozilla.org/mozilla-central/rev/7767b9e50bfa
Status: REOPENED → RESOLVED
Last Resolved: 8 years ago8 years ago
Resolution: --- → FIXED
(Reporter)

Updated

8 years ago
Duplicate of this bug: 585749
You need to log in before you can comment on or make changes to this bug.