Closed Bug 610370 Opened 9 years ago Closed 9 years ago

Shapes that should be hashed don't seem to be


(Core :: JavaScript Engine, defect, P1)




Tracking Status
blocking2.0 --- betaN+


(Reporter: bzbarsky, Assigned: brendan)


(Blocks 1 open bug)


(Whiteboard: fixed-in-tracemonkey)


(1 file, 3 obsolete files)

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

   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
Blocks: 610296
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
The Shape in question comes from u.i.names in JSFunction::lookupLocal.
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.
Seems to be fallout from bug 558451.
Blocks: 558451
Attached patch Like so (obsolete) — Splinter Review
Attachment #488867 - Flags: review?(jorendorff)
Assignee: general → bzbarsky
blocking2.0: --- → ?
Priority: -- → P1
Whiteboard: [need review]
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?

Attachment #488867 - Flags: review?(jorendorff)
Attachment #488867 - Flags: review+
Attachment #488867 - Flags: approval2.0?
> 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!  ;)
Whiteboard: [need review] → [need approval]
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!

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.

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

OS: Mac OS X → All
Hardware: x86 → All
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.
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!).

Whiteboard: [need approval] → fixed-in-tracemonkey
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
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?
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.

Target Milestone: --- → mozilla2.0b8
Blocks: 610240
Attachment #491754 - Flags: review?(brendan)
Blocks: 467263
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!

Attachment #491754 - Attachment is obsolete: true
Attachment #491985 - Flags: review?(bzbarsky)
Attachment #491754 - Flags: review?(brendan)
Attached patch proposed fix, v2Splinter Review
Thanks to bz for excellent IRC review comments/questions.

Attachment #488867 - Attachment is obsolete: true
Attachment #491985 - Attachment is obsolete: true
Attachment #492024 - Flags: review?(bzbarsky)
Attachment #491985 - Flags: review?(bzbarsky)
Comment on attachment 492024 [details] [diff] [review]
proposed fix, v2

Attachment #492024 - Flags: review?(bzbarsky) → review+

Whiteboard: fixed-in-tracemonkey
Closed: 9 years ago
Resolution: --- → FIXED
blocking2.0: ? → betaN+
wrong cset: REOPENED
Resolution: FIXED → ---
Closed: 9 years ago9 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.