Note: There are a few cases of duplicates in user autocompletion which are being worked on.

Shapes that should be hashed don't seem to be

RESOLVED FIXED in mozilla2.0b8

Status

()

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

People

(Reporter: bz, Assigned: brendan)

Tracking

(Blocks: 1 bug)

Trunk
mozilla2.0b8
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(blocking2.0 betaN+)

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(1 attachment, 3 obsolete attachments)

(Reporter)

Description

7 years ago
On the testcase in bug 610296, we end up spending a huge amount of time in the loop in Shape::search.  In fact, we sometimes run it for thousands of iterations for a single call to search().  Why aren't we hashing this?

Data (the second column is the
iteration count; the first column is the number of times we saw that iteration
count):

   4  3
   4  4
   4  5
  11  2
  11  6
  19  100
  29  136
  63  184
  64  230
  73  202
  94  3744
  99  182
 144  83
 166  524
 213  147
 323  80
22649 1
(Reporter)

Updated

7 years ago
Blocks: 610296
(Reporter)

Comment 1

7 years ago
And in particular, on entry to search() I see things like:

(gdb) p (*startp)->entryCount()
$4 = 523
(gdb) p (*startp)->table
$5 = ('js::PropertyTable' *) 0x0
(Reporter)

Comment 2

7 years ago
The Shape in question comes from u.i.names in JSFunction::lookupLocal.
(Reporter)

Comment 3

7 years ago
So JSFunction::addLocal adds locals using Shape::getChild, but getChild can skip calling maybeHash when it ends up calling newDictionaryShape.

Fixing that speeds up the testcase in bug 610296 by a good bit, and gives me these statistics:

   4   4
   6   3
   6   5
  11   2
  11   6
22649  1

as expected.
(Reporter)

Comment 4

7 years ago
Seems to be fallout from bug 558451.
Blocks: 558451
(Reporter)

Comment 5

7 years ago
Created attachment 488867 [details] [diff] [review]
Like so
Attachment #488867 - Flags: review?(jorendorff)
(Reporter)

Updated

7 years ago
Assignee: general → bzbarsky
blocking2.0: --- → ?
Priority: -- → P1
Whiteboard: [need review]
(Assignee)

Comment 6

7 years ago
Comment on attachment 488867 [details] [diff] [review]
Like so

Thanks, this should get into Mozilla 2.0.

What was causing the switch to dictionary mode for such deep shapes?

/be
Attachment #488867 - Flags: review?(jorendorff)
Attachment #488867 - Flags: review+
Attachment #488867 - Flags: approval2.0?
(Reporter)

Comment 7

7 years ago
> What was causing the switch to dictionary mode for such deep shapes?

PropertyTree::MAX_HEIGHT is 64.  Shape::getChild and JSObject::addPropertyInternal both go into dictionary mode if entryCount() >= MAX_HEIGHT.

If the question is _why_ they do this, I have no idea!  ;)
(Reporter)

Updated

7 years ago
Whiteboard: [need review] → [need approval]
(Assignee)

Comment 8

7 years ago
Sure, I didn't study the code -- the MAX_HEIGHT cutover is to avoid over-deep (and likely-unshareable) shape tree paths. JSC does likewise. It certainly could be relaxed if we thought there was too much lost sharing in real-world code. But anyway, it seems incidental here.

Thanks for patching this!

/be
(Assignee)

Comment 9

7 years ago
In particular, if nested functions with tons of upvars/vars/args would actually share better with a deeper MAX_HEIGHT, let's see the case. The problem is that inner functions' shape paths end with common upvars, rather than starting with them, so they don't share outer function's shape paths.

function f(a, b) {
  function g(c, d) {
    var e = a*c + b*d;
    return Math.sqrt(e);
  }
  return g;
}

This suggests ordering upvars before args and vars, but that could bite code with many functions that use common arg and var names. Also it's awkward given the two-pass ordering we take advantage of now: args come before local vars, and upvars come after both once we've analyzed.

Just noting as an extended aside, not as evidence for doing anything atm.

/be
(Assignee)

Comment 10

7 years ago
bz, you are go to land in tm AFAIK. Thanks again,

/be
OS: Mac OS X → All
Hardware: x86 → All
(Reporter)

Comment 11

7 years ago
I thought this still needed a= or blocking+ to land... are the rules different on tm?
Comment on attachment 488867 [details] [diff] [review]
Like so

a=shaver, but obviously needs a test
Attachment #488867 - Flags: approval2.0? → approval2.0+
bz and I have discussed the difficulty in effectively instrumenting this for test purposes, I relent.
(Assignee)

Comment 14

7 years ago
Not sure about tm policy but I've seen stuff land there without pre-approval. By the time it's in m-c, it has approval (when I've checked -- honest, I'm not doing much checking!).

/be
(Reporter)

Comment 15

7 years ago
Pushed http://hg.mozilla.org/tracemonkey/rev/298e753a1726
Whiteboard: [need approval] → fixed-in-tracemonkey
(Reporter)

Comment 16

7 years ago
Backed out; this causes js1_5/Regress/regress-290575.js to fail.  The test is effectively calling new Function() on a string that uses a lot of arguments (0x8001 or 0x10000 depending on the test in there).

On 32-bit, we end up with a malloc failure when doing the calloc for entries in js::PropertyTable::init.  The allocation size is 262KB.

On 64-bit debug, we just hang.

Looking at this a bit, it looks like with my change we hashify every shape on the path from the empty shape to the function's final shape.  Which means that by the time we're doing that 262KB allocation (which happens when entryCount() is 22509), we've done 22500 allocations averaging 130KB (say), which is almost 3GB.  So we're legitimately OOM (or at least out of adddress space) on a 32-bit build.  A 64-bit build probably starts swapping or whatnot, hence the hang.

I think this should be fixable if we change things so that for functions in particular we don't maybeHash until we've added all the locals.

But this shows another problem: no one checks the return value of maybeHash, and it can fail quite easily.  Furthermore, it seems to me like the same exact situation can arise by just adding a few tens of thousands of properties to an object, so maybe the lack of hashifying when in dictionary mode was on purpose...

One other thing.  It looks like each hashification attempt is O(N) in entryCount(): in PropertyTable::init we walk all the shapes.  Which means that if we hashify on each step we end up with O(N^2) cost to produce the final shape (N being the number of properties).  This also suggests that we want to hashify lazily or something.  That won't protect against adding a bajillion properties _and_ doing a property get after each add, though.

Assigning to brendan per his request.
Assignee: bzbarsky → brendan
Whiteboard: fixed-in-tracemonkey
(Reporter)

Comment 17

7 years ago
So a question.  In dictionary mode, are the shapes shared with anyone else?  If not, would it be safe to just move the hashtable from the old lastProp to the new one and add the one entry for the new lastProp?
(Assignee)

Comment 18

7 years ago
As discussed on IRC, table *must* move to lastProp and grow to include that new shape among its entries. No optionality other than leaving lastProp->table null for small dicitonaries.

/be
(Assignee)

Updated

7 years ago
Status: NEW → ASSIGNED
Target Milestone: --- → mozilla2.0b8
(Reporter)

Updated

7 years ago
Blocks: 610240
(Reporter)

Comment 19

7 years ago
Created attachment 491754 [details] [diff] [review]
Make sure to hash shapes in dictionary lists too, if they need it.
(Reporter)

Updated

7 years ago
Attachment #491754 - Flags: review?(brendan)
(Reporter)

Updated

7 years ago
Blocks: 467263
(Assignee)

Comment 20

7 years ago
Created attachment 491985 [details] [diff] [review]
avoid inconsistent state on OOM; maybeHash only if !table; nits picked

Thanks for drafting this, I hadn't gotten near it in my queue, but since you did, here's my version. Co-credits on landing!

/be
Attachment #491754 - Attachment is obsolete: true
Attachment #491985 - Flags: review?(bzbarsky)
Attachment #491754 - Flags: review?(brendan)
(Assignee)

Comment 21

7 years ago
Created attachment 492024 [details] [diff] [review]
proposed fix, v2

Thanks to bz for excellent IRC review comments/questions.

/be
Attachment #488867 - Attachment is obsolete: true
Attachment #491985 - Attachment is obsolete: true
Attachment #492024 - Flags: review?(bzbarsky)
Attachment #491985 - Flags: review?(bzbarsky)
(Reporter)

Comment 22

7 years ago
Comment on attachment 492024 [details] [diff] [review]
proposed fix, v2

r=me
Attachment #492024 - Flags: review?(bzbarsky) → review+
(Assignee)

Comment 23

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

/be
Whiteboard: fixed-in-tracemonkey

Comment 24

7 years ago
http://hg.mozilla.org/mozilla-central/rev/298e753a1726
Status: ASSIGNED → RESOLVED
Last Resolved: 7 years ago
Resolution: --- → FIXED

Updated

7 years ago
blocking2.0: ? → betaN+

Comment 25

7 years ago
wrong cset: REOPENED
Status: RESOLVED → REOPENED
Resolution: FIXED → ---

Comment 26

7 years ago
http://hg.mozilla.org/mozilla-central/rev/b7ffbcf89604
Status: REOPENED → RESOLVED
Last Resolved: 7 years ago7 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.