Bug 610070 - Large amount of heap allocation from js::PropertyTable::init. r=brendan.
☠☠ backed out by 5bab73449e39 ☠ ☠
authorNicholas Nethercote <nnethercote@mozilla.com>
Mon, 13 Dec 2010 16:43:39 -0800
changeset 59237 0343557b0c7ac5580b9fdaea0d02f0c60faf3f33
parent 59236 421dafd0878e5ed3d5a92ac1d565261cd458be2b
child 59238 5bab73449e39637544d9459cc140ebd85e6aaed5
push id1
push usershaver@mozilla.com
push dateTue, 04 Jan 2011 17:58:04 +0000
reviewersbrendan
bugs610070
milestone2.0b8pre
Bug 610070 - Large amount of heap allocation from js::PropertyTable::init. r=brendan.
js/src/jsfun.cpp
js/src/jsscope.cpp
js/src/jsscope.h
js/src/jsscopeinlines.h
--- a/js/src/jsfun.cpp
+++ b/js/src/jsfun.cpp
@@ -3195,17 +3195,17 @@ JSFunction::addLocal(JSContext *cx, JSAt
     return true;
 }
 
 JSLocalKind
 JSFunction::lookupLocal(JSContext *cx, JSAtom *atom, uintN *indexp)
 {
     JS_ASSERT(FUN_INTERPRETED(this));
 
-    Shape *shape = SHAPE_FETCH(Shape::search(&u.i.names, ATOM_TO_JSID(atom)));
+    Shape *shape = SHAPE_FETCH(Shape::search(cx->runtime, &u.i.names, ATOM_TO_JSID(atom)));
     if (shape) {
         JSLocalKind localKind;
 
         if (shape->getter() == GetCallArg)
             localKind = JSLOCAL_ARG;
         else if (shape->getter() == GetFlatUpvar)
             localKind = JSLOCAL_UPVAR;
         else if (!shape->writable())
--- a/js/src/jsscope.cpp
+++ b/js/src/jsscope.cpp
@@ -134,39 +134,34 @@ JSObject::ensureClassReservedSlotsForEmp
 JS_FRIEND_DATA(JSScopeStats) js_scope_stats = {0};
 
 # define METER(x)       JS_ATOMIC_INCREMENT(&js_scope_stats.x)
 #else
 # define METER(x)       /* nothing */
 #endif
 
 bool
-PropertyTable::init(Shape *lastProp, JSContext *cx)
+PropertyTable::init(JSRuntime *rt, Shape *lastProp)
 {
-    int sizeLog2;
-
-    if (entryCount > HASH_THRESHOLD) {
-        /*
-         * Either we're creating a table for a large scope that was populated
-         * via property cache hit logic under JSOP_INITPROP, JSOP_SETNAME, or
-         * JSOP_SETPROP; or else calloc failed at least once already. In any
-         * event, let's try to grow, overallocating to hold at least twice the
-         * current population.
-         */
-        sizeLog2 = JS_CeilingLog2(2 * entryCount);
-    } else {
-        JS_ASSERT(hashShift == JS_DHASH_BITS - MIN_SIZE_LOG2);
+    /*
+     * Either we're creating a table for a large scope that was populated
+     * via property cache hit logic under JSOP_INITPROP, JSOP_SETNAME, or
+     * JSOP_SETPROP; or else calloc failed at least once already. In any
+     * event, let's try to grow, overallocating to hold at least twice the
+     * current population.
+     */
+    uintN sizeLog2 = JS_CeilingLog2(2 * entryCount);
+    if (sizeLog2 < MIN_SIZE_LOG2)
         sizeLog2 = MIN_SIZE_LOG2;
-    }
 
     /*
-     * Use cx->runtime->calloc for memory accounting and overpressure handling
+     * Use rt->calloc for memory accounting and overpressure handling
      * without OOM reporting. See PropertyTable::change.
      */
-    entries = (Shape **) cx->runtime->calloc(JS_BIT(sizeLog2) * sizeof(Shape *));
+    entries = (Shape **) rt->calloc(JS_BIT(sizeLog2) * sizeof(Shape *));
     if (!entries) {
         METER(tableAllocFails);
         return false;
     }
 
     hashShift = JS_DHASH_BITS - sizeLog2;
     for (Shape::Range r = lastProp->all(); !r.empty(); r.popFront()) {
         const Shape &shape = r.front();
@@ -180,25 +175,24 @@ PropertyTable::init(Shape *lastProp, JSC
          */
         if (!SHAPE_FETCH(spp))
             SHAPE_STORE_PRESERVING_COLLISION(spp, &shape);
     }
     return true;
 }
 
 bool
-Shape::maybeHash(JSContext *cx)
+Shape::hashify(JSRuntime *rt)
 {
     JS_ASSERT(!table);
-    uint32 nentries = entryCount();
-    if (nentries >= PropertyTable::HASH_THRESHOLD) {
-        table = cx->create<PropertyTable>(nentries);
-        return table && table->init(this, cx);
-    }
-    return true;
+    void* mem = rt->malloc(sizeof(PropertyTable));
+    if (!mem)
+        return false;
+    table = new(mem) PropertyTable(entryCount());
+    return table->init(rt, this);
 }
 
 #ifdef DEBUG
 # include "jsprf.h"
 # define LIVE_SCOPE_METER(cx,expr) JS_LOCK_RUNTIME_VOID(cx->runtime,expr)
 #else
 # define LIVE_SCOPE_METER(cx,expr) /* nothing */
 #endif
@@ -500,17 +494,17 @@ Shape::getChild(JSContext *cx, const js:
                     ++table->entryCount;
                 SHAPE_STORE_PRESERVING_COLLISION(spp, newShape);
 
                 /* Hand the table off from oldShape to newShape. */
                 oldShape->setTable(NULL);
                 newShape->setTable(table);
             } else {
                 if (!newShape->table)
-                    newShape->maybeHash(cx);
+                    newShape->hashify(cx->runtime);
             }
             return newShape;
         }
 
         return NULL;
     }
 
     if ((*listp)->entryCount() >= PropertyTree::MAX_HEIGHT) {
@@ -519,18 +513,16 @@ Shape::getChild(JSContext *cx, const js:
             return NULL;
         return dprop->getChild(cx, child, listp);
     }
 
     Shape *shape = JS_PROPERTY_TREE(cx).getChild(cx, this, child);
     if (shape) {
         JS_ASSERT(shape->parent == this);
         JS_ASSERT(this == *listp);
-        if (!shape->table)
-            shape->maybeHash(cx);
         *listp = shape;
     }
     return shape;
 }
 
 /*
  * Get or create a property-tree or dictionary child property of parent, which
  * must be lastProp if inDictionaryMode(), else parent must be one of lastProp
@@ -629,17 +621,17 @@ Shape::newDictionaryList(JSContext *cx, 
 
         JS_ASSERT(!dprop->table);
         childp = &dprop->parent;
         shape = shape->parent;
     }
 
     list = *listp;
     JS_ASSERT(list->inDictionary());
-    list->maybeHash(cx);
+    list->hashify(cx->runtime);
     return list;
 }
 
 bool
 JSObject::toDictionaryMode(JSContext *cx)
 {
     JS_ASSERT(!inDictionaryMode());
     if (!Shape::newDictionaryList(cx, &lastProp))
@@ -841,28 +833,16 @@ JSObject::addPropertyInternal(JSContext 
             JS_ASSERT(shape->parent->table == table);
             shape->parent->setTable(NULL);
             shape->setTable(table);
         }
 #ifdef DEBUG
         LIVE_SCOPE_METER(cx, ++cx->runtime->liveObjectProps);
         JS_RUNTIME_METER(cx->runtime, totalObjectProps);
 #endif
-
-        /*
-         * If we reach the hashing threshold, try to allocate lastProp->table.
-         * If we can't (a rare event, preceded by swapping to death on most
-         * modern OSes), stick with linear search rather than whining about
-         * this little set-back.  Therefore we must test !lastProp->table and
-         * entry count >= PropertyTable::HASH_THRESHOLD, not merely whether the
-         * entry count just reached the threshold.
-         */
-        if (!lastProp->table)
-            lastProp->maybeHash(cx);
-
         CHECK_SHAPE_CONSISTENCY(this);
         METER(adds);
         return shape;
     }
 
     CHECK_SHAPE_CONSISTENCY(this);
     METER(addFails);
     return NULL;
@@ -1014,21 +994,16 @@ JSObject::putProperty(JSContext *cx, jsi
         if (!newShape) {
             setLastProperty(shape);
             CHECK_SHAPE_CONSISTENCY(this);
             METER(putFails);
             return NULL;
         }
 
         shape = newShape;
-
-        if (!shape->table) {
-            /* See JSObject::addPropertyInternal comment about ignoring OOM. */
-            shape->maybeHash(cx);
-        }
     }
 
     /*
      * Can't fail now, so free the previous incarnation's slot if the new shape
      * has no slot. But we do not need to free oldSlot (and must not, as trying
      * to will botch an assertion in JSObject::freeSlot) if the new lastProp
      * (shape here) has a slotSpan that does not cover it.
      */
@@ -1255,17 +1230,17 @@ JSObject::removeProperty(JSContext *cx, 
             /* Hand off table from old to new lastProp. */
             oldLastProp->setTable(NULL);
             lastProp->setTable(table);
         }
     } else {
         /*
          * Non-dictionary-mode property tables are shared immutables, so all we
          * need do is retract lastProp and we'll either get or else lazily make
-         * via a later maybeHash the exact table for the new property lineage.
+         * via a later hashify the exact table for the new property lineage.
          */
         JS_ASSERT(shape == lastProp);
         removeLastProperty();
 
         /*
          * Revert to fixed slots if this was the first dynamically allocated slot,
          * preserving invariant that objects with the same shape use the fixed
          * slots in the same way.
--- a/js/src/jsscope.h
+++ b/js/src/jsscope.h
@@ -45,16 +45,17 @@
  */
 #include <new>
 #ifdef DEBUG
 #include <stdio.h>
 #endif
 
 #include "jstypes.h"
 #include "jscntxt.h"
+#include "jscompartment.h"
 #include "jshashtable.h"
 #include "jsobj.h"
 #include "jsprvtd.h"
 #include "jspubtd.h"
 #include "jspropertytree.h"
 #include "jsstrinlines.h"
 
 #ifdef _MSC_VER
@@ -208,25 +209,24 @@
  */
 
 #define SHAPE_INVALID_SLOT              0xffffffff
 
 namespace js {
 
 /*
  * Shapes use multiplicative hashing, _a la_ jsdhash.[ch], but specialized to
- * minimize footprint.  But if a Shape lineage has fewer than HASH_THRESHOLD
- * entries, we use linear search and avoid allocating scope->table.
+ * minimize footprint.  But if a Shape lineage has been searched fewer than
+ * HASH_MIN_SEARCHES times, we use linear search and avoid allocating
+ * scope->table.
  */
 struct PropertyTable {
-    enum {
-        HASH_THRESHOLD  = 6,
-        MIN_SIZE_LOG2   = 4,
-        MIN_SIZE        = JS_BIT(MIN_SIZE_LOG2)
-    };
+    static const uint32 HASH_MIN_SEARCHES = 7;
+    static const uint32 MIN_SIZE_LOG2     = 4;
+    static const uint32 MIN_SIZE          = JS_BIT(MIN_SIZE_LOG2);
 
     int             hashShift;          /* multiplicative hash shift */
 
     uint32          entryCount;         /* number of entries in table */
     uint32          removedCount;       /* removed entry sentinels in table */
     uint32          freelist;           /* SHAPE_INVALID_SLOT or head of slot
                                            freelist in owning dictionary-mode
                                            object */
@@ -261,17 +261,17 @@ struct PropertyTable {
      */
     bool grow(JSContext *cx);
 
     /*
      * NB: init and change are fallible but do not report OOM, so callers can
      * cope or ignore. They do however use JSRuntime's calloc method in order
      * to update the malloc counter on success.
      */
-    bool            init(js::Shape *lastProp, JSContext *cx);
+    bool            init(JSRuntime *rt, js::Shape *lastProp);
     bool            change(int log2Delta, JSContext *cx);
     js::Shape       **search(jsid id, bool adding);
 };
 
 } /* namespace js */
 
 struct JSObject;
 
@@ -288,16 +288,17 @@ CastAsPropertyOp(js::Class *clasp)
 struct Shape : public JSObjectMap
 {
     friend struct ::JSObject;
     friend struct ::JSFunction;
     friend class js::PropertyTree;
     friend bool HasUnreachableGCThings(TreeFragment *f);
 
   protected:
+    mutable uint32 numSearches;     /* Only updated until it reaches HASH_MIN_SEARCHES. */
     mutable js::PropertyTable *table;
 
   public:
     inline void freeTable(JSContext *cx);
 
     static bool initRuntimeState(JSContext *cx);
     static void finishRuntimeState(JSContext *cx);
 
@@ -344,26 +345,27 @@ struct Shape : public JSObjectMap
         mutable js::KidsPointer kids;   /* null, single child, or a tagged ptr
                                            to many-kids data structure */
         mutable js::Shape **listp;      /* dictionary list starting at lastProp
                                            has a double-indirect back pointer,
                                            either to shape->parent if not last,
                                            else to obj->lastProp */
     };
 
-    static inline js::Shape **search(js::Shape **startp, jsid id, bool adding = false);
+    static inline js::Shape **search(JSRuntime *rt, js::Shape **startp, jsid id,
+                                     bool adding = false);
     static js::Shape *newDictionaryShape(JSContext *cx, const js::Shape &child, js::Shape **listp);
     static js::Shape *newDictionaryList(JSContext *cx, js::Shape **listp);
 
     inline void removeFromDictionary(JSObject *obj) const;
     inline void insertIntoDictionary(js::Shape **dictp);
 
     js::Shape *getChild(JSContext *cx, const js::Shape &child, js::Shape **listp);
 
-    bool maybeHash(JSContext *cx);
+    bool hashify(JSRuntime *rt);
 
     void setTable(js::PropertyTable *t) const {
         JS_ASSERT_IF(t && t->freelist != SHAPE_INVALID_SLOT, t->freelist < slotSpan);
         table = t;
     }
 
     /*
      * Setter for parent. The challenge is to maintain JSObjectMap::slotSpan in
@@ -645,17 +647,17 @@ struct EmptyShape : public js::Shape
     ((js::Shape *) (jsuword(shape) & ~SHAPE_COLLISION))
 
 #define SHAPE_STORE_PRESERVING_COLLISION(spp, shape)                          \
     (*(spp) = (js::Shape *) (jsuword(shape) | SHAPE_HAD_COLLISION(*(spp))))
 
 inline js::Shape **
 JSObject::nativeSearch(jsid id, bool adding)
 {
-    return js::Shape::search(&lastProp, id, adding);
+    return js::Shape::search(compartment()->rt, &lastProp, id, adding);
 }
 
 inline const js::Shape *
 JSObject::nativeLookup(jsid id)
 {
     JS_ASSERT(isNative());
     return SHAPE_FETCH(nativeSearch(id));
 }
@@ -825,39 +827,46 @@ extern JS_FRIEND_DATA(JSScopeStats) js_s
 # define METER(x)       JS_ATOMIC_INCREMENT(&js_scope_stats.x)
 #else
 # define METER(x)       /* nothing */
 #endif
 
 namespace js {
 
 JS_ALWAYS_INLINE js::Shape **
-Shape::search(js::Shape **startp, jsid id, bool adding)
+Shape::search(JSRuntime *rt, js::Shape **startp, jsid id, bool adding)
 {
+    js::Shape *start = *startp;
     METER(searches);
-    if (!(*startp)->table) {
-        /*
-         * Not enough properties to justify hashing: search 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::Shape **spp;
+    if (start->table ||
+        (start->numSearches >= PropertyTable::HASH_MIN_SEARCHES && start->hashify(rt)))
+    {
+        return start->table->search(id, adding);
+    }
 
-        for (spp = startp; js::Shape *shape = *spp; spp = &shape->parent) {
-            if (shape->id == id) {
-                METER(hits);
-                return spp;
-            }
+    /*
+     * 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->table);
+    start->numSearches++;
+
+    js::Shape **spp;
+    for (spp = startp; js::Shape *shape = *spp; spp = &shape->parent) {
+        if (shape->id == id) {
+            METER(hits);
+            return spp;
         }
-        METER(misses);
-        return spp;
     }
-    return (*startp)->table->search(id, adding);
+    METER(misses);
+    return spp;
 }
 
 #undef METER
 
 inline bool
 Shape::isSharedPermanent() const
 {
     return (~attrs & (JSPROP_SHARED | JSPROP_PERMANENT)) == 0;
--- a/js/src/jsscopeinlines.h
+++ b/js/src/jsscopeinlines.h
@@ -165,28 +165,28 @@ JSObject::trace(JSTracer *trc)
 }
 
 namespace js {
 
 inline
 Shape::Shape(jsid id, js::PropertyOp getter, js::PropertyOp setter, uint32 slot, uintN attrs,
              uintN flags, intN shortid, uint32 shape, uint32 slotSpan)
   : JSObjectMap(shape, slotSpan),
-    table(NULL), id(id), rawGetter(getter), rawSetter(setter), slot(slot), attrs(uint8(attrs)),
-    flags(uint8(flags)), shortid(int16(shortid)), parent(NULL)
+    numSearches(0), table(NULL), id(id), rawGetter(getter), rawSetter(setter), slot(slot),
+    attrs(uint8(attrs)), flags(uint8(flags)), shortid(int16(shortid)), parent(NULL)
 {
     JS_ASSERT_IF(slotSpan != SHAPE_INVALID_SLOT, slotSpan < JSObject::NSLOTS_LIMIT);
     JS_ASSERT_IF(getter && (attrs & JSPROP_GETTER), getterObj->isCallable());
     JS_ASSERT_IF(setter && (attrs & JSPROP_SETTER), setterObj->isCallable());
     kids.setNull();
 }
 
 inline
 Shape::Shape(JSContext *cx, Class *aclasp)
-  : JSObjectMap(js_GenerateShape(cx, false), JSSLOT_FREE(aclasp)), table(NULL),
+  : JSObjectMap(js_GenerateShape(cx, false), JSSLOT_FREE(aclasp)), numSearches(0), table(NULL),
     id(JSID_EMPTY), clasp(aclasp), rawSetter(NULL), slot(SHAPE_INVALID_SLOT), attrs(0),
     flags(SHARED_EMPTY), shortid(0), parent(NULL)
 {
     kids.setNull();
 }
 
 inline JSDHashNumber
 Shape::hash() const