Bug 631139 - Put Shape::numSearches and Shape::table in a union. r=brendan, a=sayrer.
authorNicholas Nethercote <nnethercote@mozilla.com>
Wed, 09 Feb 2011 15:18:03 -0800
changeset 62399 85610aaf53cc46e1ea12718040f53fe3fc4faf9c
parent 62398 10ebc5ea11ac28b232ba48f562e23e6a4b3e0ad7
child 62400 c6465659390620d1ffceed0e2279cae58f5dc536
push id1
push userroot
push dateTue, 10 Dec 2013 15:46:25 +0000
reviewersbrendan, sayrer
bugs631139
milestone2.0b12pre
Bug 631139 - Put Shape::numSearches and Shape::table in a union. r=brendan, a=sayrer.
js/src/jsobj.cpp
js/src/jsscope.cpp
js/src/jsscope.h
js/src/jsscopeinlines.h
--- a/js/src/jsobj.cpp
+++ b/js/src/jsobj.cpp
@@ -4388,18 +4388,18 @@ JSObject::allocSlot(JSContext *cx, uint3
 {
     uint32 slot = slotSpan();
     JS_ASSERT(slot >= JSSLOT_FREE(clasp));
 
     /*
      * If this object is in dictionary mode and it has a property table, try to
      * pull a free slot from the property table's slot-number freelist.
      */
-    if (inDictionaryMode() && lastProp->table) {
-        uint32 &last = lastProp->table->freelist;
+    if (inDictionaryMode() && lastProp->hasTable()) {
+        uint32 &last = lastProp->getTable()->freelist;
         if (last != SHAPE_INVALID_SLOT) {
 #ifdef DEBUG
             JS_ASSERT(last < slot);
             uint32 next = getSlot(last).toPrivateUint32();
             JS_ASSERT_IF(next != SHAPE_INVALID_SLOT, next < slot);
 #endif
 
             *slotp = last;
@@ -4422,18 +4422,18 @@ JSObject::allocSlot(JSContext *cx, uint3
 
 bool
 JSObject::freeSlot(JSContext *cx, uint32 slot)
 {
     uint32 limit = slotSpan();
     JS_ASSERT(slot < limit);
 
     Value &vref = getSlotRef(slot);
-    if (inDictionaryMode() && lastProp->table) {
-        uint32 &last = lastProp->table->freelist;
+    if (inDictionaryMode() && lastProp->hasTable()) {
+        uint32 &last = lastProp->getTable()->freelist;
 
         /* Can't afford to check the whole freelist, but let's check the head. */
         JS_ASSERT_IF(last != SHAPE_INVALID_SLOT, last < limit && last != slot);
 
         /*
          * Freeing a slot other than the last one mapped by this object's
          * shape (and not a reserved slot; see bug 595230): push the slot onto
          * the dictionary property table's freelist. We want to let the last
@@ -4476,17 +4476,17 @@ js_UnbrandAndClearSlots(JSContext *cx, J
 
     /*
      * We just overwrote all slots to undefined, so the freelist has
      * been trashed. We need to clear the head pointer or else we will
      * crash later. This leaks slots but the object is all but dead
      * anyway.
      */
     if (obj->hasPropertyTable())
-        obj->lastProperty()->table->freelist = SHAPE_INVALID_SLOT;
+        obj->lastProperty()->getTable()->freelist = SHAPE_INVALID_SLOT;
 }
 
 /* JSBOXEDWORD_INT_MAX as a string */
 #define JSBOXEDWORD_INT_MAX_STRING "1073741823"
 
 /*
  * Convert string indexes that convert to int jsvals as ints to save memory.
  * Care must be taken to use this macro every time a property name is used, or
--- a/js/src/jsscope.cpp
+++ b/js/src/jsscope.cpp
@@ -181,22 +181,22 @@ PropertyTable::init(JSRuntime *rt, Shape
             SHAPE_STORE_PRESERVING_COLLISION(spp, &shape);
     }
     return true;
 }
 
 bool
 Shape::hashify(JSRuntime *rt)
 {
-    JS_ASSERT(!table);
+    JS_ASSERT(!hasTable());
     void* mem = rt->malloc(sizeof(PropertyTable));
     if (!mem)
         return false;
-    table = new(mem) PropertyTable(entryCount());
-    return table->init(rt, this);
+    setTable(new(mem) PropertyTable(entryCount()));
+    return getTable()->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
@@ -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;
 
         /*
          * Attempt to grow table if needed before extending *listp, rather than
          * risking OOM under table->grow after newDictionaryShape succeeds, and
          * then have to fix up *listp.
          */
         if (table && table->needsToGrow() && !table->grow(cx))
             return NULL;
@@ -488,17 +488,17 @@ Shape::getChild(JSContext *cx, const js:
                 if (!SHAPE_FETCH(spp))
                     ++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)
+                if (!newShape->hasTable())
                     newShape->hashify(cx->runtime);
             }
             return newShape;
         }
 
         return NULL;
     }
 
@@ -591,33 +591,16 @@ Shape::newDictionaryShape(JSContext *cx,
     dprop->listp = NULL;
     dprop->insertIntoDictionary(listp);
 
     JS_COMPARTMENT_METER(cx->compartment->liveDictModeNodes++);
     return dprop;
 }
 
 Shape *
-Shape::newDictionaryShapeForAddProperty(JSContext *cx, jsid id,
-                                        PropertyOp getter, StrictPropertyOp setter,
-                                        uint32 slot, uintN attrs, uintN flags, intN shortid)
-{
-    Shape *shape = JS_PROPERTY_TREE(cx).newShape(cx);
-    if (!shape)
-        return NULL;
-
-    new (shape) Shape(id, getter, setter, slot, attrs, (flags & ~FROZEN) | IN_DICTIONARY, shortid);
-    shape->parent = NULL;
-    shape->listp = NULL;
-
-    JS_COMPARTMENT_METER(cx->compartment->liveDictModeNodes++);
-    return shape;
-}
-
-Shape *
 Shape::newDictionaryList(JSContext *cx, Shape **listp)
 {
     Shape *shape = *listp;
     Shape *list = shape;
 
     Shape **childp = listp;
     *childp = NULL;
 
@@ -626,17 +609,17 @@ Shape::newDictionaryList(JSContext *cx, 
 
         Shape *dprop = Shape::newDictionaryShape(cx, *shape, childp);
         if (!dprop) {
             METER(toDictFails);
             *listp = list;
             return NULL;
         }
 
-        JS_ASSERT(!dprop->table);
+        JS_ASSERT(!dprop->hasTable());
         childp = &dprop->parent;
         shape = shape->parent;
     }
 
     list = *listp;
     JS_ASSERT(list->inDictionary());
     list->hashify(cx->runtime);
     return list;
@@ -703,49 +686,51 @@ JSObject::checkShapeConsistency()
         JS_ASSERT(objShape != lastProp->shape);
     else
         JS_ASSERT(objShape == lastProp->shape);
 
     Shape *shape = lastProp;
     Shape *prev = NULL;
 
     if (inDictionaryMode()) {
-        if (PropertyTable *table = shape->table) {
+        if (shape->hasTable()) {
+            PropertyTable *table = shape->getTable();
             for (uint32 fslot = table->freelist; fslot != SHAPE_INVALID_SLOT;
                  fslot = getSlotRef(fslot).toPrivateUint32()) {
                 JS_ASSERT(fslot < shape->slotSpan);
             }
 
             for (int n = throttle; --n >= 0 && shape->parent; shape = shape->parent) {
-                JS_ASSERT_IF(shape != lastProp, !shape->table);
+                JS_ASSERT_IF(shape != lastProp, !shape->hasTable());
 
                 Shape **spp = table->search(shape->id, false);
                 JS_ASSERT(SHAPE_FETCH(spp) == shape);
             }
         } else {
             shape = shape->parent;
             for (int n = throttle; --n >= 0 && shape; shape = shape->parent)
-                JS_ASSERT(!shape->table);
+                JS_ASSERT(!shape->hasTable());
         }
 
         shape = lastProp;
         for (int n = throttle; --n >= 0 && shape; shape = shape->parent) {
             JS_ASSERT_IF(shape->slot != SHAPE_INVALID_SLOT, shape->slot < shape->slotSpan);
             if (!prev) {
                 JS_ASSERT(shape == lastProp);
                 JS_ASSERT(shape->listp == &lastProp);
             } else {
                 JS_ASSERT(shape->listp == &prev->parent);
                 JS_ASSERT(prev->slotSpan >= shape->slotSpan);
             }
             prev = shape;
         }
     } else {
         for (int n = throttle; --n >= 0 && shape->parent; shape = shape->parent) {
-            if (PropertyTable *table = shape->table) {
+            if (shape->hasTable()) {
+                PropertyTable *table = shape->getTable();
                 JS_ASSERT(shape->parent);
                 for (Shape::Range r(shape); !r.empty(); r.popFront()) {
                     Shape **spp = table->search(r.front().id, false);
                     JS_ASSERT(SHAPE_FETCH(spp) == &r.front());
                 }
             }
             if (prev) {
                 JS_ASSERT(prev->slotSpan >= shape->slotSpan);
@@ -801,19 +786,20 @@ JSObject::addPropertyInternal(JSContext 
     JS_ASSERT_IF(inDictionaryMode(), !lastProp->frozen());
 
     PropertyTable *table = NULL;
     if (!inDictionaryMode()) {
         if (lastProp->entryCount() >= PropertyTree::MAX_HEIGHT) {
             if (!toDictionaryMode(cx))
                 return NULL;
             spp = nativeSearch(id, true);
-            table = lastProp->table;
+            table = lastProp->getTable();
         }
-    } else if ((table = lastProp->table) != NULL) {
+    } else if (lastProp->hasTable()) {
+        table = lastProp->getTable();
         if (table->needsToGrow()) {
             if (!table->grow(cx))
                 return NULL;
 
             METER(searches);
             METER(changeSearches);
             spp = table->search(id, true);
             JS_ASSERT(!SHAPE_FETCH(spp));
@@ -831,17 +817,17 @@ JSObject::addPropertyInternal(JSContext 
         JS_ASSERT(shape == lastProp);
 
         if (table) {
             /* Store the tree node pointer in the table entry for id. */
             SHAPE_STORE_PRESERVING_COLLISION(spp, shape);
             ++table->entryCount;
 
             /* Pass the table along to the new lastProp, namely shape. */
-            JS_ASSERT(shape->parent->table == table);
+            JS_ASSERT(shape->parent->getTable() == table);
             shape->parent->setTable(NULL);
             shape->setTable(table);
         }
 #ifdef DEBUG
         LIVE_SCOPE_METER(cx, ++cx->runtime->liveObjectProps);
 #endif
         CHECK_SHAPE_CONSISTENCY(this);
         METER(adds);
@@ -1131,17 +1117,17 @@ JSObject::changeProperty(JSContext *cx, 
         newShape = mutableShape;
     } else if (shape == lastProp) {
         Shape child(shape->id, getter, setter, shape->slot, attrs, shape->flags, shape->shortid);
 
         newShape = getChildProperty(cx, shape->parent, child);
 #ifdef DEBUG
         if (newShape) {
             JS_ASSERT(newShape == lastProp);
-            if (newShape->table) {
+            if (newShape->hasTable()) {
                 Shape **spp = nativeSearch(shape->id);
                 JS_ASSERT(SHAPE_FETCH(spp) == newShape);
             }
         }
 #endif
     } else {
         /*
          * Let JSObject::putProperty handle this |overwriting| case, including
@@ -1196,17 +1182,17 @@ JSObject::removeProperty(JSContext *cx, 
     }
 
     /*
      * A dictionary-mode object owns mutable, unique shapes on a non-circular
      * doubly linked list, optionally hashed by lastProp->table. So we can edit
      * the list and hash in place.
      */
     if (inDictionaryMode()) {
-        PropertyTable *table = lastProp->table;
+        PropertyTable *table = lastProp->hasTable() ? lastProp->getTable() : NULL;
 
         if (SHAPE_HAD_COLLISION(*spp)) {
             JS_ASSERT(table);
             *spp = SHAPE_REMOVED;
             ++table->removedCount;
             --table->entryCount;
         } else {
             METER(removeFrees);
@@ -1236,17 +1222,17 @@ JSObject::removeProperty(JSContext *cx, 
          * return get deleted DictionaryShapes! See bug 595365.
          */
         flags |= OWN_SHAPE;
 
         Shape *oldLastProp = lastProp;
         shape->removeFromDictionary(this);
         if (table) {
             if (shape == oldLastProp) {
-                JS_ASSERT(shape->table == table);
+                JS_ASSERT(shape->getTable() == table);
                 JS_ASSERT(shape->parent == lastProp);
                 JS_ASSERT(shape->slotSpan >= lastProp->slotSpan);
                 JS_ASSERT_IF(hadSlot, shape->slot + 1 <= shape->slotSpan);
 
                 /*
                  * Maintain slot freelist consistency. The only constraint we
                  * have is that slot numbers on the freelist are less than 
                  * lastProp->slotSpan. Thus, if the freelist is non-empty,
@@ -1286,17 +1272,18 @@ JSObject::removeProperty(JSContext *cx, 
             JS_ASSERT_IF(!lastProp->isEmptyShape() && lastProp->hasSlot(),
                          lastProp->slot == fixed - 1);
             revertToFixedSlots(cx);
         }
     }
     updateShape(cx);
 
     /* On the way out, consider shrinking table if its load factor is <= .25. */
-    if (PropertyTable *table = lastProp->table) {
+    if (lastProp->hasTable()) {
+        PropertyTable *table = lastProp->getTable();
         uint32 size = table->capacity();
         if (size > PropertyTable::MIN_SIZE && table->entryCount <= size >> 2) {
             METER(shrinks);
             (void) table->change(-1, cx);
         }
     }
 
     CHECK_SHAPE_CONSISTENCY(this);
--- a/js/src/jsscope.h
+++ b/js/src/jsscope.h
@@ -199,34 +199,34 @@
  * of child node pointer arrays ("kid chunks").  The details are isolated in
  * jspropertytree.h/.cpp; others must treat js::Shape.kids as opaque.
  *
  * One final twist (can you stand it?): the vast majority (~95% or more) of
  * scopes are looked up fewer than three times;  in these cases, initializing
  * scope->table isn't worth it.  So instead of always allocating scope->table,
  * we leave it null while initializing all the other scope members as if it
  * were non-null and minimal-length.  Until a scope is searched
- * HASH_MIN_SEARCHES times, we use linear search from obj->lastProp to find a
+ * MAX_LINEAR_SEARCHES times, we use linear search from obj->lastProp to find a
  * given id, and save on the time and space overhead of creating a hash table.
  */
 
 #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 been searched fewer than
- * HASH_MIN_SEARCHES times, we use linear search and avoid allocating
+ * MAX_LINEAR_SEARCHES times, we use linear search and avoid allocating
  * scope->table.
  */
 struct PropertyTable {
-    static const uint32 HASH_MIN_SEARCHES = 7;
-    static const uint32 MIN_SIZE_LOG2     = 4;
-    static const uint32 MIN_SIZE          = JS_BIT(MIN_SIZE_LOG2);
+    static const uint32 MAX_LINEAR_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 */
@@ -294,19 +294,28 @@ struct Shape : public JSObjectMap
 {
     friend struct ::JSObject;
     friend struct ::JSFunction;
     friend class js::PropertyTree;
     friend class js::Bindings;
     friend bool IsShapeAboutToBeFinalized(JSContext *cx, const js::Shape *shape);
     friend JS_FRIEND_API(void) ::js_UnbrandAndClearSlots(JSContext *cx, JSObject *obj);
 
-  protected:
-    mutable uint32 numSearches;     /* Only updated until it reaches HASH_MIN_SEARCHES. */
-    mutable js::PropertyTable *table;
+    /* 
+     * numLinearSearches starts at zero and is incremented initially on each
+     * search() call.  Once numLinearSearches reaches MAX_LINEAR_SEARCHES
+     * (which is a small integer), the table is created on the next search()
+     * call, and the table pointer will be easily distinguishable from a small
+     * integer.  The table can also be created when hashifying for dictionary
+     * mode.
+     */
+    union {
+        mutable size_t numLinearSearches;
+        mutable js::PropertyTable *table;
+    };
 
   public:
     inline void freeTable(JSContext *cx);
 
     static bool initEmptyShapes(JSCompartment *comp);
     static void finishEmptyShapes(JSCompartment *comp);
 
     jsid                id;
@@ -350,28 +359,34 @@ struct Shape : public JSObjectMap
                                            either to shape->parent if not last,
                                            else to obj->lastProp */
     };
 
     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);
-    static js::Shape *newDictionaryShapeForAddProperty(JSContext *cx, jsid id,
-                                                       PropertyOp getter, StrictPropertyOp setter,
-                                                       uint32 slot, uintN attrs,
-                                                       uintN flags, intN shortid);
 
     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 hashify(JSRuntime *rt);
 
+    bool hasTable() const {
+        /* A valid pointer should be much bigger than MAX_LINEAR_SEARCHES. */
+        return numLinearSearches > PropertyTable::MAX_LINEAR_SEARCHES;
+    }
+
+    js::PropertyTable *getTable() const {
+        JS_ASSERT(hasTable());
+        return table;
+    }
+
     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
      * the face of arbitrary slot order.
@@ -609,18 +624,18 @@ struct Shape : public JSObjectMap
      * the prototype property. See bug 552432.
      */
     bool shadowable() const {
         JS_ASSERT_IF(isDataDescriptor(), writable());
         return hasSlot() || (attrs & JSPROP_SHADOWABLE);
     }
 
     uint32 entryCount() const {
-        if (table)
-            return table->entryCount;
+        if (hasTable())
+            return getTable()->entryCount;
 
         const js::Shape *shape = this;
         uint32 count = 0;
         for (js::Shape::Range r = shape->all(); !r.empty(); r.popFront())
             ++count;
         return count;
     }
 
@@ -721,17 +736,17 @@ inline uint32
 JSObject::propertyCount() const
 {
     return lastProperty()->entryCount();
 }
 
 inline bool
 JSObject::hasPropertyTable() const
 {
-    return !!lastProperty()->table;
+    return lastProperty()->hasTable();
 }
 
 /*
  * FIXME: shape must not be null, should use a reference here and other places.
  */
 inline void
 JSObject::setLastProperty(const js::Shape *shape)
 {
@@ -854,33 +869,38 @@ extern JS_FRIEND_DATA(JSScopeStats) js_s
 
 namespace js {
 
 JS_ALWAYS_INLINE js::Shape **
 Shape::search(JSRuntime *rt, js::Shape **startp, jsid id, bool adding)
 {
     js::Shape *start = *startp;
     METER(searches);
-    if (start->table ||
-        (start->numSearches >= PropertyTable::HASH_MIN_SEARCHES && start->hashify(rt)))
-    {
-        return start->table->search(id, adding);
+
+    if (start->hasTable())
+        return start->getTable()->search(id, adding);
+
+    if (start->numLinearSearches == PropertyTable::MAX_LINEAR_SEARCHES) {
+        if (start->hashify(rt))
+            return start->getTable()->search(id, adding);
+        /* OOM!  Don't increment numLinearSearches, to keep hasTable() false. */
+        JS_ASSERT(!start->hasTable());
+    } else {
+        JS_ASSERT(start->numLinearSearches < PropertyTable::MAX_LINEAR_SEARCHES);
+        start->numLinearSearches++;
     }
 
     /*
      * 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);
--- a/js/src/jsscopeinlines.h
+++ b/js/src/jsscopeinlines.h
@@ -48,19 +48,19 @@
 #include "jsobj.h"
 #include "jsscope.h"
 
 #include "jscntxtinlines.h"
 
 inline void
 js::Shape::freeTable(JSContext *cx)
 {
-    if (table) {
-        cx->destroy(table);
-        table = NULL;
+    if (hasTable()) {
+        cx->destroy(getTable());
+        setTable(NULL);
     }
 }
 
 inline js::EmptyShape *
 JSObject::getEmptyShape(JSContext *cx, js::Class *aclasp,
                         /* gc::FinalizeKind */ unsigned kind)
 {
     JS_ASSERT(kind >= js::gc::FINALIZE_OBJECT0 && kind <= js::gc::FINALIZE_OBJECT_LAST);
@@ -165,30 +165,29 @@ JSObject::trace(JSTracer *trc)
 }
 
 namespace js {
 
 inline
 Shape::Shape(jsid id, js::PropertyOp getter, js::StrictPropertyOp setter, uint32 slot, uintN attrs,
              uintN flags, intN shortid, uint32 shape, uint32 slotSpan)
   : JSObjectMap(shape, slotSpan),
-    numSearches(0), table(NULL), id(id), rawGetter(getter), rawSetter(setter), slot(slot),
+    numLinearSearches(0), 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(JSCompartment *comp, Class *aclasp)
   : JSObjectMap(js_GenerateShape(comp->rt), JSSLOT_FREE(aclasp)),
-    numSearches(0),
-    table(NULL),
+    numLinearSearches(0),
     id(JSID_EMPTY),
     clasp(aclasp),
     rawSetter(NULL),
     slot(SHAPE_INVALID_SLOT),
     attrs(0),
     flags(SHARED_EMPTY),
     shortid(0),
     parent(NULL)