The default bug view has changed. See this FAQ.

Fix v8-regexp regression in wake of patch for bug 558451

RESOLVED FIXED in mozilla2.0b7

Status

()

Core
JavaScript Engine
P1
major
RESOLVED FIXED
7 years ago
7 years ago

People

(Reporter: brendan, Assigned: brendan)

Tracking

Trunk
mozilla2.0b7
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: fixed-in-tracemonkey, URL)

Attachments

(2 attachments, 2 obsolete attachments)

(Assignee)

Description

7 years ago
Created attachment 470514 [details] [diff] [review]
proposed fix

We maybeHash too soon (HASH_THRESHOLD = 6), and worse, we maybeHash when adding shapes that may never be subject to property lookups.

The HASH_THRESHOLD value of 6 is ancient, and I don't propose to change it for this bug. It's always more space-efficient to avoid creating a PropertyTable for a shape-path, but if script actually does lookup properties by name, one could argue it's worth the space overhead for O(1) time complexity.

But as David Bacon likes to point out, O(k) where k != 1 can differ measurably from O(1), asymptote aside. Obviously if there's only one property mapped by the shape path, you don't need a double hashtable to speed up the linear search done under Shape::search.

When there's time, it would be informative to measure benchmark performance with different HASH_THRESHOLD values and see where the O(n^2) compounding complexity of linear search starts to be noticeable.

For now, this patch does the trick:

TEST        COMPARISON            FROM                 TO             DETAILS

=============================================================================

** TOTAL **: 1.067x as fast    610.9ms +/- 2.3%   572.4ms +/- 2.1%     significant

=============================================================================

  v8:       1.067x as fast    610.9ms +/- 2.3%   572.4ms +/- 2.1%     significant
    regexp: 1.067x as fast    610.9ms +/- 2.3%   572.4ms +/- 2.1%     significant

/be
Attachment #470514 - Flags: review?(jorendorff)
(Assignee)

Updated

7 years ago
Blocks: 558451
(Assignee)

Updated

7 years ago
Attachment #470514 - Flags: review?(jorendorff) → review?(gal)

Comment 1

7 years ago
Comment on attachment 470514 [details] [diff] [review]
proposed fix

The malloc counting accounting here is really lame. Time to revive the memory pressure accounting bug.
Attachment #470514 - Flags: review?(gal) → review+
(Assignee)

Comment 2

7 years ago
http://hg.mozilla.org/tracemonkey/rev/34a07da93976

If this doesn't win back all the lost perf, I'll take a new bug.

/be
Whiteboard: fixed-in-tracemonkey
(Assignee)

Comment 3

7 years ago
Backed out:

http://hg.mozilla.org/tracemonkey/rev/801ea8bd0d06

Didn't win and broke a jsreftest :-(. Taking the longer path.

/be
Whiteboard: fixed-in-tracemonkey
I did some analyzing with Callgrind.  The only things that really struck me were: 

- PropertyTable::init() is called a lot;  it and its children account for almost 12% of instructions executed (many of them in malloc).

- PropertyTree:sweepShapes() is called a lot;  it and its children account for almost 8% of instructions executed (many of them in free).  This matches cdleary's Shark result in bug 558451 comment 153.

The Shape::Shape() with 7 args is called 1,727,129 times.  The Shape::Shape() with 3 args is called 110,080 times.  That's a lot of shapes.

Comment 5

7 years ago
(In reply to comment #4)
> - PropertyTable::init() is called a lot;  it and its children account for
> almost 12% of instructions executed (many of them in malloc).
> 
> - PropertyTree:sweepShapes() is called a lot;

We should really change the shape allocation to the GC and make the GC to sweep them in the background. That should help.
(Assignee)

Comment 6

7 years ago
Created attachment 470780 [details] [diff] [review]
fix

The new-instance vs. proto-emptyShape class mismatch misfeature got me again.

Jorendorff and I have discussed it before (it's in InitScopeForObject, which now needs a new name, post-scope-ectomy). I'll file a followup bug.

This patch more than settles the score:

TEST        COMPARISON            FROM                 TO             DETAILS

=============================================================================

** TOTAL **: 1.83x as fast     638.6ms +/- 2.0%   349.1ms +/- 2.0%     significant

=============================================================================

  v8:       1.83x as fast     638.6ms +/- 2.0%   349.1ms +/- 2.0%     significant
    regexp: 1.83x as fast     638.6ms +/- 2.0%   349.1ms +/- 2.0%     significant

Sayrer was right, it was an "easy" fix (or a small fix, anyway -- took me too long to find, sorry).

/be
Attachment #470514 - Attachment is obsolete: true
Attachment #470780 - Flags: review?(gal)
(Assignee)

Comment 7

7 years ago
Created attachment 470784 [details] [diff] [review]
fix

Igor kindly agreed to review.

/be
Attachment #470780 - Attachment is obsolete: true
Attachment #470784 - Flags: review?(igor)
Attachment #470780 - Flags: review?(gal)
(Assignee)

Comment 8

7 years ago
(In reply to comment #5)
> (In reply to comment #4)
> > - PropertyTable::init() is called a lot;  it and its children account for
> > almost 12% of instructions executed (many of them in malloc).
> > 
> > - PropertyTree:sweepShapes() is called a lot;
> 
> We should really change the shape allocation to the GC and make the GC to sweep
> them in the background. That should help.

That is bug 569422, on my list now.

/be
(Assignee)

Comment 9

7 years ago
igor: brendan: what about passing SlowArrayClass to js_InitClass ?
brendan: igor: gal tried that, it results in missing length property, believe it or not
brendan: igor: this is a minimal patch -- 7 chars if you ignore comments and asserts
brendan: igor: we may retry using slow array class but that is for later
igor: brendan: ok, but the patch should assert in js_InitClass something like JS_ASSERT_IF(proto->clasp != clasp, clasp == js_ArrayClass && proto->clasp == js_SlowArrayClass) with fixme pointing to the new bug.
[08:41am] igor: brendan: r+ with that.

/be
(Assignee)

Comment 10

7 years ago
http://hg.mozilla.org/tracemonkey/rev/e80892986b11

Filed bug 592296 on initializing so Array.prototype is slow from the start.

/be
Whiteboard: fixed-in-tracemonkey
(Assignee)

Updated

7 years ago
Attachment #470784 - Flags: review?(igor) → review+

Comment 11

7 years ago
Comment on attachment 470780 [details] [diff] [review]
fix

Thanks for the follow-up bug.
Attachment #470780 - Flags: review+
(Assignee)

Comment 12

7 years ago
Created attachment 470905 [details]
woohoo!
(Assignee)

Comment 13

7 years ago
http://hg.mozilla.org/mozilla-central/rev/e80892986b11

/be
Status: ASSIGNED → RESOLVED
Last Resolved: 7 years ago
Resolution: --- → FIXED
Target Milestone: mozilla2.0b5 → mozilla2.0b6
You need to log in before you can comment on or make changes to this bug.