Put Shape::numSearches and Shape::table in a union

RESOLVED FIXED

Status

()

Core
JavaScript Engine
RESOLVED FIXED
7 years ago
7 years ago

People

(Reporter: njn, Assigned: njn)

Tracking

unspecified
Points:
---

Firefox Tracking Flags

(blocking2.0 betaN+)

Details

(Whiteboard: fixed-in-tracemonkey [hardblocker] [has patch])

Attachments

(1 attachment, 1 obsolete attachment)

(Assignee)

Description

7 years ago
Lots of Shapes are allocated.  'numSearches' and 'table' should be put into a union, they shouldn't both be needed at the same time, because 'numSearches' is used to determine if 'table' should be created, and not touched after that point.
(Assignee)

Comment 1

7 years ago
Created attachment 510842 [details] [diff] [review]
patch (against TM 61845:53763d7e9e54)

This patch puts numSearches and table into a union.  It also augments the
existing setTable() with hasTable() and getTable(), and uses them as much as
possible instead of direct .table references.  It reduces the size of a
Shape from 48 to 44 bytes on 32-bit and from 80 to 72 bytes on 64-bit.
Given that it's easy to get Shape allocations of 20 or 30 MB or more,
typical savings will easily exceed one MB.

It changes behaviour subtly in one way -- there are three places where we
call setTable(NULL) because we're handing off a table from one Shape to
another Shape.  Prior to this patch, if the old Shape was searched again it
would immediately be hashified, because numSearches would already be set to
HASH_MIN_SEARCHES.  With this patch, numSearches effectively gets reset to
zero.  I have no intuition about this change so I measured the number of
hashify calls for both SS and V8, there was no change.  There was a
miniscule change in instruction counts for some of those benchmarks, I'm not
sure why.

I also removed newDictionaryShapeForAddProperty(), which is dead, and which
I failed to remove elsewhere after promising to do so.

Brendan, does this seem to you like reasonable 4.0 fodder?
Attachment #510842 - Flags: review?(brendan)
Comment on attachment 510842 [details] [diff] [review]
patch (against TM 61845:53763d7e9e54)

>@@ -454,17 +454,17 @@ PropertyTable::grow(JSContext *cx)
> Shape *
> Shape::getChild(JSContext *cx, const js::Shape &child, Shape **listp)
> {
>     JS_ASSERT(!JSID_IS_VOID(child.id));
>     JS_ASSERT(!child.inDictionary());
> 
>     if (inDictionary()) {
>         Shape *oldShape = *listp;
>-        PropertyTable *table = oldShape ? oldShape->table : NULL;
>+        PropertyTable *table = oldShape && oldShape->hasTable() ? oldShape->getTable() : NULL;

Nit: parenthesize condition of ?: expressions with precedence of unary or above, per old K&R style.

> Shape::search(JSRuntime *rt, js::Shape **startp, jsid id, bool adding)
> {
>     js::Shape *start = *startp;
>     METER(searches);
>+
>+    if (start->hasTable())
>+        return start->getTable()->search(id, adding);
>+
>+    JS_ASSERT(start->numSearches <= PropertyTable::HASH_MIN_SEARCHES);
>+    if (start->numSearches == PropertyTable::HASH_MIN_SEARCHES && start->hashify(rt))
>+        return start->getTable()->search(id, adding);
> 
>     /*
>      * Not enough searches done so far to justify hashing: search linearly
>      * from *startp.
>      *
>      * We don't use a Range here, or stop at null parent (the empty shape
>      * at the end), to avoid an extra load per iteration just to save a
>      * load and id test at the end (when missing).
>      */
>+    JS_ASSERT(!start->hasTable());
>     start->numSearches++;

(I snipped - lines above.)

Here is a bug: if start->hashify(rt) OOMs, we will have start->numSearches > HASH_MIN_SEARCHES at this point but without having allocated a table. This condition means start->hasTable(), so future uses will dereference the small-integer numSearches via start->getTable().

The simplest fix is to stick numSearches at HASH_MIN_SEARCHES on OOM, by compensating for the ++ in case of OOM:

..    if (start->numSearches == PropertyTable::HASH_MIN_SEARCHES) {
..        if (start->hashify(rt))
..            return start->getTable()->search(id, adding);
..        --start->numSearches;
..    }
> 
>     /*
>      * Not enough searches done so far to justify hashing: search linearly
>      * from *startp.
>      *
>      * We don't use a Range here, or stop at null parent (the empty shape
>      * at the end), to avoid an extra load per iteration just to save a
>      * load and id test at the end (when missing).
>      */
>+    JS_ASSERT(!start->hasTable());
>     start->numSearches++;

/be
(Assignee)

Comment 3

7 years ago
Created attachment 510884 [details] [diff] [review]
patch, v2 (against TM 61845:53763d7e9e54)

I fixed the parenthesizing and the OOM bug, the latter slightly differently to how you suggested.

I also renamed numSearches as numLinearSearches, and HASH_MIN_SEARCHES as MAX_LINEAR_SEARCHES.  Both new names are better, particularly when they are compared to each other.

Oh, and I see that Shape contains a debug-build-only pointer field.  So sizeof(Shape) with this patch is 40 bytes on 32-bit and 64 bytes on 64-bit, which means the proportional improvement is slightly higher than I thought.
Attachment #510842 - Attachment is obsolete: true
Attachment #510884 - Flags: review?(brendan)
Attachment #510842 - Flags: review?(brendan)
Comment on attachment 510884 [details] [diff] [review]
patch, v2 (against TM 61845:53763d7e9e54)

Egad, I didn't know there was a DEBUG-only compartment pointer in Shape. Can we lose it? I guess when we move Shape into the GC heap proper.

Nice fix, I was hacking with diff-code and not really recommending pre-decrement of numSearches to compensate :-P. Wasn't sure you wanted that !hasTable() assert in both (with the patch's if{if-return;}else structure) places.

/be
Attachment #510884 - Flags: review?(brendan) → review+
(Assignee)

Updated

7 years ago
Attachment #510842 - Flags: approval2.0?

Updated

7 years ago
blocking2.0: --- → betaN+

Updated

7 years ago
Attachment #510842 - Flags: approval2.0?

Updated

7 years ago
Attachment #510884 - Flags: approval2.0+
(Assignee)

Comment 5

7 years ago
http://hg.mozilla.org/tracemonkey/rev/85610aaf53cc
(Assignee)

Updated

7 years ago
Whiteboard: fixed-in-tracemonkey
Whiteboard: fixed-in-tracemonkey → fixed-in-tracemonkey [hardblocker]

Updated

7 years ago
Whiteboard: fixed-in-tracemonkey [hardblocker] → fixed-in-tracemonkey [hardblocker] [has patch]
cdleary-bot mozilla-central merge info:
http://hg.mozilla.org/mozilla-central/rev/85610aaf53cc
Status: ASSIGNED → RESOLVED
Last Resolved: 7 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.