2008-10-06 Sam Weinig <sam@webkit.org>
authorweinig@apple.com <weinig@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 7 Oct 2008 05:43:06 +0000 (05:43 +0000)
committerweinig@apple.com <weinig@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 7 Oct 2008 05:43:06 +0000 (05:43 +0000)
        Reviewed by Cameron Zwarich.

        Fix for https://bugs.webkit.org/show_bug.cgi?id=21415
        Improve the division between PropertyStorageArray and PropertyMap

        - Rework ProperyMap to store offsets in the value so that they don't
          change when rehashing.  This allows us not to have to keep the
          PropertyStorageArray in sync and thus not have to pass it in.
        - Rename PropertyMap::getOffset -> PropertyMap::get since put/remove
          now also return offsets.
        - A Vector of deleted offsets is now needed since the storage is out of
          band.

        1% win on SunSpider.  Wash on V8 suite.

        * JavaScriptCore.exp:
        * VM/CTI.cpp:
        (JSC::transitionWillNeedStorageRealloc):
        * VM/Machine.cpp:
        (JSC::Machine::privateExecute):
        Transition logic can be greatly simplified by the fact that
        the storage capacity is always known, and is correct for the
        inline case.
        * kjs/JSObject.cpp:
        (JSC::JSObject::put): Rename getOffset -> get.
        (JSC::JSObject::deleteProperty): Ditto.
        (JSC::JSObject::getPropertyAttributes): Ditto.
        (JSC::JSObject::removeDirect): Use returned offset to
        clear the value in the PropertyNameArray.
        (JSC::JSObject::allocatePropertyStorage): Add assert.
        * kjs/JSObject.h:
        (JSC::JSObject::getDirect): Rename getOffset -> get
        (JSC::JSObject::getDirectLocation): Rename getOffset -> get
        (JSC::JSObject::putDirect): Use propertyStorageCapacity to determine whether
        or not to resize.  Also, since put now returns an offset (and thus
        addPropertyTransition does also) setting of the PropertyStorageArray is
        now done here.
        (JSC::JSObject::transitionTo):
        * kjs/PropertyMap.cpp:
        (JSC::PropertyMap::checkConsistency): PropertyStorageArray is no longer
        passed in.
        (JSC::PropertyMap::operator=): Copy the delete offsets vector.
        (JSC::PropertyMap::put): Instead of setting the PropertyNameArray
        explicitly, return the offset where the value should go.
        (JSC::PropertyMap::remove): Instead of removing from the PropertyNameArray
        explicitly, return the offset where the value should be removed.
        (JSC::PropertyMap::get): Switch to using the stored offset, instead
        of the implicit one.
        (JSC::PropertyMap::insert):
        (JSC::PropertyMap::expand): This is never called when m_table is null,
        so remove that branch and add it as an assertion.
        (JSC::PropertyMap::createTable): Consistency checks no longer take
        a PropertyNameArray.
        (JSC::PropertyMap::rehash): No need to rehash the PropertyNameArray
        now that it is completely out of band.
        * kjs/PropertyMap.h:
        (JSC::PropertyMapEntry::PropertyMapEntry): Store offset into PropertyNameArray.
        (JSC::PropertyMap::get): Switch to using the stored offset, instead
        of the implicit one.
        * kjs/StructureID.cpp:
        (JSC::StructureID::StructureID): Initialize the propertyStorageCapacity to
        JSObject::inlineStorageCapacity.
        (JSC::StructureID::growPropertyStorageCapacity): Grow the storage capacity as
        described below.
        (JSC::StructureID::addPropertyTransition): Copy the storage capacity.
        (JSC::StructureID::toDictionaryTransition): Ditto.
        (JSC::StructureID::changePrototypeTransition): Ditto.
        (JSC::StructureID::getterSetterTransition): Ditto.
        * kjs/StructureID.h:
        (JSC::StructureID::propertyStorageCapacity): Add propertyStorageCapacity
        which is the current capacity for the JSObjects PropertyStorageArray.
        It starts at the JSObject::inlineStorageCapacity (currently 2), then
        when it first needs to be resized moves to the JSObject::nonInlineBaseStorageCapacity
        (currently 16), and after that doubles each time.

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@37370 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JavaScriptCore/ChangeLog
JavaScriptCore/JavaScriptCore.exp
JavaScriptCore/VM/CTI.cpp
JavaScriptCore/VM/Machine.cpp
JavaScriptCore/kjs/JSObject.cpp
JavaScriptCore/kjs/JSObject.h
JavaScriptCore/kjs/PropertyMap.cpp
JavaScriptCore/kjs/PropertyMap.h
JavaScriptCore/kjs/StructureID.cpp
JavaScriptCore/kjs/StructureID.h

index da7944b5531fb84b5ac54b4571cd85567de56430..ebef1046f8dfd1fc89efbbd949eb62a5ac218abe 100644 (file)
@@ -1,3 +1,80 @@
+2008-10-06  Sam Weinig  <sam@webkit.org>
+
+        Reviewed by Cameron Zwarich.
+
+        Fix for https://bugs.webkit.org/show_bug.cgi?id=21415
+        Improve the division between PropertyStorageArray and PropertyMap
+
+        - Rework ProperyMap to store offsets in the value so that they don't
+          change when rehashing.  This allows us not to have to keep the 
+          PropertyStorageArray in sync and thus not have to pass it in.
+        - Rename PropertyMap::getOffset -> PropertyMap::get since put/remove
+          now also return offsets.
+        - A Vector of deleted offsets is now needed since the storage is out of
+          band.
+
+        1% win on SunSpider.  Wash on V8 suite.
+
+        * JavaScriptCore.exp:
+        * VM/CTI.cpp:
+        (JSC::transitionWillNeedStorageRealloc):
+        * VM/Machine.cpp:
+        (JSC::Machine::privateExecute):
+        Transition logic can be greatly simplified by the fact that
+        the storage capacity is always known, and is correct for the
+        inline case.
+        * kjs/JSObject.cpp:
+        (JSC::JSObject::put): Rename getOffset -> get.
+        (JSC::JSObject::deleteProperty): Ditto.
+        (JSC::JSObject::getPropertyAttributes): Ditto.
+        (JSC::JSObject::removeDirect): Use returned offset to
+        clear the value in the PropertyNameArray.
+        (JSC::JSObject::allocatePropertyStorage): Add assert.
+        * kjs/JSObject.h:
+        (JSC::JSObject::getDirect): Rename getOffset -> get
+        (JSC::JSObject::getDirectLocation): Rename getOffset -> get
+        (JSC::JSObject::putDirect): Use propertyStorageCapacity to determine whether
+        or not to resize.  Also, since put now returns an offset (and thus 
+        addPropertyTransition does also) setting of the PropertyStorageArray is
+        now done here.
+        (JSC::JSObject::transitionTo):
+        * kjs/PropertyMap.cpp:
+        (JSC::PropertyMap::checkConsistency): PropertyStorageArray is no longer 
+        passed in.
+        (JSC::PropertyMap::operator=): Copy the delete offsets vector.
+        (JSC::PropertyMap::put): Instead of setting the PropertyNameArray
+        explicitly, return the offset where the value should go.
+        (JSC::PropertyMap::remove): Instead of removing from the PropertyNameArray
+        explicitly, return the offset where the value should be removed.
+        (JSC::PropertyMap::get): Switch to using the stored offset, instead
+        of the implicit one.
+        (JSC::PropertyMap::insert):
+        (JSC::PropertyMap::expand): This is never called when m_table is null,
+        so remove that branch and add it as an assertion.
+        (JSC::PropertyMap::createTable): Consistency checks no longer take
+        a PropertyNameArray.
+        (JSC::PropertyMap::rehash): No need to rehash the PropertyNameArray
+        now that it is completely out of band.
+        * kjs/PropertyMap.h:
+        (JSC::PropertyMapEntry::PropertyMapEntry): Store offset into PropertyNameArray.
+        (JSC::PropertyMap::get): Switch to using the stored offset, instead
+        of the implicit one.
+        * kjs/StructureID.cpp:
+        (JSC::StructureID::StructureID): Initialize the propertyStorageCapacity to 
+        JSObject::inlineStorageCapacity.
+        (JSC::StructureID::growPropertyStorageCapacity): Grow the storage capacity as
+        described below.
+        (JSC::StructureID::addPropertyTransition): Copy the storage capacity.
+        (JSC::StructureID::toDictionaryTransition): Ditto.
+        (JSC::StructureID::changePrototypeTransition): Ditto.
+        (JSC::StructureID::getterSetterTransition): Ditto.
+        * kjs/StructureID.h:
+        (JSC::StructureID::propertyStorageCapacity): Add propertyStorageCapacity
+        which is the current capacity for the JSObjects PropertyStorageArray.
+        It starts at the JSObject::inlineStorageCapacity (currently 2), then
+        when it first needs to be resized moves to the JSObject::nonInlineBaseStorageCapacity
+        (currently 16), and after that doubles each time.
+
 2008-10-06  Cameron Zwarich  <zwarich@apple.com>
 
         Reviewed by Oliver Hunt.
index a558c4f2a4060b327711b3ca0af13525947b3d3b..20c7631f016ba2baa0ff245505f9906dd24e40ad 100644 (file)
@@ -108,13 +108,14 @@ __ZN3JSC11JSImmediate8toStringEPKNS_7JSValueE
 __ZN3JSC11JSImmediate9prototypeEPKNS_7JSValueEPNS_9ExecStateE
 __ZN3JSC11ProfileNode4sortEPFbRKN3WTF6RefPtrIS0_EES5_E
 __ZN3JSC11ProgramNode6createEPNS_12JSGlobalDataEPNS_14SourceElementsEPN3WTF6VectorISt4pairINS_10IdentifierEjELm16EEEPNS6_INS5_6RefPtrINS_12FuncDeclNodeEEELm16EEERKNS_10SourceCodeEji
-__ZN3JSC11PropertyMap3putERKNS_10IdentifierEPNS_7JSValueEjbPNS_8JSObjectERNS_15PutPropertySlotERPS5_
-__ZN3JSC11PropertyMap9getOffsetERKNS_10IdentifierERj
+__ZN3JSC11PropertyMap3getERKNS_10IdentifierERj
+__ZN3JSC11PropertyMap3putERKNS_10IdentifierEj
 __ZN3JSC11PropertyMapD1Ev
-__ZN3JSC11StructureID21addPropertyTransitionEPS0_RKNS_10IdentifierEPNS_7JSValueEjPNS_8JSObjectERNS_15PutPropertySlotERPS6_
+__ZN3JSC11StructureID21addPropertyTransitionEPS0_RKNS_10IdentifierEjRm
 __ZN3JSC11StructureID21clearEnumerationCacheEv
 __ZN3JSC11StructureID24fromDictionaryTransitionEPS0_
 __ZN3JSC11StructureID25changePrototypeTransitionEPS0_PNS_7JSValueE
+__ZN3JSC11StructureID27growPropertyStorageCapacityEv
 __ZN3JSC11StructureIDC1EPNS_7JSValueERKNS_8TypeInfoE
 __ZN3JSC11StructureIDD1Ev
 __ZN3JSC12DateInstance4infoE
index ea8263ad994eec12ba53cafe2387b4155d0e2698..e5ba06cad5b065d2868836808078c2f1045b0e1c 100644 (file)
@@ -2743,13 +2743,7 @@ extern "C" {
 
 static JSValue* SFX_CALL transitionObject(StructureID* newStructureID, size_t cachedOffset, JSObject* baseObject, JSValue* value)
 {
-    StructureID* oldStructureID = newStructureID->previousID();
-
     baseObject->transitionTo(newStructureID);
-
-    if (oldStructureID->propertyMap().storageSize() == JSObject::inlineStorageCapacity)
-        baseObject->allocatePropertyStorage(oldStructureID->propertyMap().storageSize(), oldStructureID->propertyMap().size());
-
     baseObject->putDirectOffset(cachedOffset, value);
     return baseObject;
 }
@@ -2758,16 +2752,7 @@ static JSValue* SFX_CALL transitionObject(StructureID* newStructureID, size_t ca
 
 static inline bool transitionWillNeedStorageRealloc(StructureID* oldStructureID, StructureID* newStructureID)
 {
-    if (oldStructureID->propertyMap().storageSize() == JSObject::inlineStorageCapacity)
-        return true;
-
-    if (oldStructureID->propertyMap().storageSize() < JSObject::inlineStorageCapacity)
-        return false;
-
-    if (oldStructureID->propertyMap().size() != newStructureID->propertyMap().size())
-        return true;
-
-    return false;
+    return oldStructureID->propertyStorageCapacity() != newStructureID->propertyStorageCapacity();
 }
 
 void CTI::privateCompilePutByIdTransition(StructureID* oldStructureID, StructureID* newStructureID, size_t cachedOffset, StructureIDChain* sIDC, void* returnAddress)
index 89306ce93cf48db59cadfb43f8f4ba79125f5b65..b9f0c997727830ad1a22372392126d408728027b 100644 (file)
@@ -2721,8 +2721,6 @@ JSValue* Machine::privateExecute(ExecutionFlag flag, RegisterFile* registerFile,
                 }
 
                 baseObject->transitionTo(newStructureID);
-                if (oldStructureID->propertyMap().storageSize() == JSObject::inlineStorageCapacity)
-                    baseObject->allocatePropertyStorage(oldStructureID->propertyMap().storageSize(), oldStructureID->propertyMap().size());
 
                 int value = vPC[3].u.operand;
                 unsigned offset = vPC[7].u.operand;
index cf5132e852a90d4796fcbf7bad46f9dc5effebb0..21ead06b3b0e66000784655f773ebdc257e6e5c4 100644 (file)
@@ -134,7 +134,7 @@ void JSObject::put(ExecState* exec, const Identifier& propertyName, JSValue* val
     }
     
     unsigned attributes;
-    if ((m_structureID->propertyMap().getOffset(propertyName, attributes) != WTF::notFound) && attributes & ReadOnly)
+    if ((m_structureID->propertyMap().get(propertyName, attributes) != WTF::notFound) && attributes & ReadOnly)
         return;
 
     for (JSObject* obj = this; ; obj = static_cast<JSObject*>(prototype)) {
@@ -200,7 +200,7 @@ bool JSObject::hasProperty(ExecState* exec, unsigned propertyName) const
 bool JSObject::deleteProperty(ExecState* exec, const Identifier& propertyName)
 {
     unsigned attributes;
-    if (m_structureID->propertyMap().getOffset(propertyName, attributes) != WTF::notFound) {
+    if (m_structureID->propertyMap().get(propertyName, attributes) != WTF::notFound) {
         if ((attributes & DontDelete))
             return false;
         removeDirect(propertyName);
@@ -412,7 +412,7 @@ bool JSObject::propertyIsEnumerable(ExecState* exec, const Identifier& propertyN
 
 bool JSObject::getPropertyAttributes(ExecState* exec, const Identifier& propertyName, unsigned& attributes) const
 {
-    if (m_structureID->propertyMap().getOffset(propertyName, attributes) != WTF::notFound)
+    if (m_structureID->propertyMap().get(propertyName, attributes) != WTF::notFound)
         return true;
     
     // Look in the static hashtable of properties
@@ -468,14 +468,20 @@ JSGlobalObject* JSObject::toGlobalObject(ExecState*) const
 
 void JSObject::removeDirect(const Identifier& propertyName)
 {
+    size_t offset;
     if (m_structureID->isDictionary()) {
-        m_structureID->propertyMap().remove(propertyName, m_propertyStorage);
-        m_structureID->clearEnumerationCache();
+        offset = m_structureID->propertyMap().remove(propertyName);
+        if (offset != WTF::notFound) {
+            m_propertyStorage[offset] = jsUndefined();
+            m_structureID->clearEnumerationCache();
+        }
         return;
     }
 
     RefPtr<StructureID> structureID = StructureID::toDictionaryTransition(m_structureID);
-    structureID->propertyMap().remove(propertyName, m_propertyStorage);
+    offset = structureID->propertyMap().remove(propertyName);
+    if (offset != WTF::notFound)
+        m_propertyStorage[offset] = jsUndefined();
     setStructureID(structureID.release());
 }
 
@@ -500,6 +506,8 @@ StructureID* JSObject::createInheritorID()
 
 void JSObject::allocatePropertyStorage(size_t oldSize, size_t newSize)
 {
+    ASSERT(newSize > oldSize);
+
     JSValue** oldPropertStorage = m_propertyStorage;
     m_propertyStorage = new JSValue*[newSize];
 
index c6c9cb99bdf62765fc7f3661f14d15ac8e01e3d7..9e313433901943855c0cf00be11d2a3c2eabbdb0 100644 (file)
@@ -122,19 +122,19 @@ namespace JSC {
         // This get function only looks at the property map.
         JSValue* getDirect(const Identifier& propertyName) const
         {
-            size_t offset = m_structureID->propertyMap().getOffset(propertyName);
+            size_t offset = m_structureID->propertyMap().get(propertyName);
             return offset != WTF::notFound ? m_propertyStorage[offset] : 0;
         }
 
         JSValue** getDirectLocation(const Identifier& propertyName)
         {
-            size_t offset = m_structureID->propertyMap().getOffset(propertyName);
+            size_t offset = m_structureID->propertyMap().get(propertyName);
             return offset != WTF::notFound ? locationForOffset(offset) : 0;
         }
 
         JSValue** getDirectLocation(const Identifier& propertyName, unsigned& attributes)
         {
-            size_t offset = m_structureID->propertyMap().getOffset(propertyName, attributes);
+            size_t offset = m_structureID->propertyMap().get(propertyName, attributes);
             return offset != WTF::notFound ? locationForOffset(offset) : 0;
         }
 
@@ -178,6 +178,7 @@ namespace JSC {
         bool usingInlineStorage() const { return m_propertyStorage == m_inlineStorage; }
 
         static const size_t inlineStorageCapacity = 2;
+        static const size_t nonInlineBaseStorageCapacity = 16;
 
         static PassRefPtr<StructureID> createStructureID(JSValue* proto) { return StructureID::create(proto, TypeInfo(ObjectType)); }
 
@@ -364,26 +365,32 @@ inline void JSObject::putDirect(const Identifier& propertyName, JSValue* value,
 {
     ASSERT(!Heap::heap(value) || Heap::heap(value) == Heap::heap(this));
 
-     if (m_structureID->isDictionary()) {
-         unsigned currentAttributes;
-         size_t offset = m_structureID->propertyMap().getOffset(propertyName, currentAttributes);
-         if (offset != WTF::notFound) {
-             if (checkReadOnly && currentAttributes & ReadOnly)
-                 return;
-             m_propertyStorage[offset] = value;
-             slot.setExistingProperty(this, offset);
-             return;
-         }
-
-         if (m_structureID->propertyMap().storageSize() == inlineStorageCapacity)
-             allocatePropertyStorage(m_structureID->propertyMap().storageSize(), m_structureID->propertyMap().size());
-         m_structureID->propertyMap().put(propertyName, value, attributes, checkReadOnly, this, slot, m_propertyStorage);
-         m_structureID->clearEnumerationCache();
-         return;
-     }
+    if (m_structureID->isDictionary()) {
+        unsigned currentAttributes;
+        size_t offset = m_structureID->propertyMap().get(propertyName, currentAttributes);
+        if (offset != WTF::notFound) {
+            if (checkReadOnly && currentAttributes & ReadOnly)
+                return;
+            m_propertyStorage[offset] = value;
+            slot.setExistingProperty(this, offset);
+            return;
+        }
+
+        size_t currentCapacity = m_structureID->propertyStorageCapacity();
+        offset = m_structureID->propertyMap().put(propertyName, attributes);
+        if (m_structureID->propertyMap().storageSize() > m_structureID->propertyStorageCapacity()) {
+            m_structureID->growPropertyStorageCapacity();
+            allocatePropertyStorage(currentCapacity, m_structureID->propertyStorageCapacity());
+        }
+
+        m_propertyStorage[offset] = value;
+        slot.setNewProperty(this, offset);
+        m_structureID->clearEnumerationCache();
+        return;
+    }
 
     unsigned currentAttributes;
-    size_t offset = m_structureID->propertyMap().getOffset(propertyName, currentAttributes);
+    size_t offset = m_structureID->propertyMap().get(propertyName, currentAttributes);
     if (offset != WTF::notFound) {
         if (checkReadOnly && currentAttributes & ReadOnly)
             return;
@@ -392,17 +399,22 @@ inline void JSObject::putDirect(const Identifier& propertyName, JSValue* value,
         return;
     }
 
-     if (m_structureID->propertyMap().storageSize() == inlineStorageCapacity)
-         allocatePropertyStorage(m_structureID->propertyMap().storageSize(), m_structureID->propertyMap().size());
+    size_t currentCapacity = m_structureID->propertyStorageCapacity();
+    RefPtr<StructureID> structureID = StructureID::addPropertyTransition(m_structureID, propertyName, attributes, offset);
+    if (currentCapacity != structureID->propertyStorageCapacity())
+        allocatePropertyStorage(currentCapacity, structureID->propertyStorageCapacity());
 
-     RefPtr<StructureID> structureID = StructureID::addPropertyTransition(m_structureID, propertyName, value, attributes, this, slot, m_propertyStorage);
-     slot.setWasTransition(true);
-     setStructureID(structureID.release());
+    ASSERT(offset < structureID->propertyStorageCapacity());
+    m_propertyStorage[offset] = value;
+    slot.setNewProperty(this, offset);
+    slot.setWasTransition(true);
+    setStructureID(structureID.release());
 }
 
 inline void JSObject::transitionTo(StructureID* newStructureID)
 {
-    StructureID::transitionTo(m_structureID, newStructureID, this);
+    if (m_structureID->propertyStorageCapacity() != newStructureID->propertyStorageCapacity())
+        allocatePropertyStorage(m_structureID->propertyStorageCapacity(), newStructureID->propertyStorageCapacity());
     setStructureID(newStructureID);
 }
 
index 85931d010852cfd55cc93d1ad265dbf7f5650a12..81c0964cc235a578e7a14ef28c01e64dc3836d50 100644 (file)
@@ -77,7 +77,7 @@ static const unsigned deletedSentinelIndex = 1;
 
 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
 
-inline void PropertyMap::checkConsistency(PropertyStorage&)
+inline void PropertyMap::checkConsistency()
 {
 }
 
@@ -97,6 +97,7 @@ PropertyMap& PropertyMap::operator=(const PropertyMap& other)
         }
     }
 
+    m_deletedOffsets = other.m_deletedOffsets;
     m_getterSetterFlag = other.m_getterSetterFlag;
     return *this;
 }
@@ -114,17 +115,17 @@ PropertyMap::~PropertyMap()
     fastFree(m_table);
 }
 
-size_t PropertyMap::put(const Identifier& propertyName, JSValue* value, unsigned attributes, bool checkReadOnly, JSObject* slotBase, PutPropertySlot& slot, PropertyStorage& propertyStorage)
+size_t PropertyMap::put(const Identifier& propertyName, unsigned attributes)
 {
     ASSERT(!propertyName.isNull());
-    ASSERT(value);
+    ASSERT(get(propertyName) == WTF::notFound);
 
-    checkConsistency(propertyStorage);
+    checkConsistency();
 
     UString::Rep* rep = propertyName._ustring.rep();
 
     if (!m_table)
-        expand(propertyStorage);
+        createTable();
 
     // FIXME: Consider a fast case for tables with no deleted sentinels.
 
@@ -142,15 +143,7 @@ size_t PropertyMap::put(const Identifier& propertyName, JSValue* value, unsigned
         if (entryIndex == emptyEntryIndex)
             break;
 
-        if (m_table->entries()[entryIndex - 1].key == rep) {
-            if (checkReadOnly && (m_table->entries()[entryIndex - 1].attributes & ReadOnly))
-                return WTF::notFound;
-            // Put a new value in an existing hash table entry.
-            propertyStorage[entryIndex - 2] = value;
-            // Attributes are intentionally not updated.
-            slot.setExistingProperty(slotBase, entryIndex - 2);
-            return entryIndex - 2;
-        } else if (entryIndex == deletedSentinelIndex) {
+        if (entryIndex == deletedSentinelIndex) {
             // If we find a deleted-element sentinel, remember it for use later.
             if (!foundDeletedElement) {
                 foundDeletedElement = true;
@@ -193,28 +186,35 @@ size_t PropertyMap::put(const Identifier& propertyName, JSValue* value, unsigned
     m_table->entries()[entryIndex - 1].key = rep;
     m_table->entries()[entryIndex - 1].attributes = attributes;
     m_table->entries()[entryIndex - 1].index = ++m_table->lastIndexUsed;
-    ++m_table->keyCount;
 
-    propertyStorage[entryIndex - 2] = value;
+    unsigned newOffset;
+    if (!m_deletedOffsets.isEmpty()) {
+        newOffset = m_deletedOffsets.last();
+        m_deletedOffsets.removeLast();
+    } else
+        newOffset = m_table->keyCount + m_table->deletedSentinelCount;
+    m_table->entries()[entryIndex - 1].offset = newOffset;
+
+    ++m_table->keyCount;
 
     if ((m_table->keyCount + m_table->deletedSentinelCount) * 2 >= m_table->size)
-        expand(propertyStorage);
+        expand();
 
-    checkConsistency(propertyStorage);
-    slot.setNewProperty(slotBase, entryIndex - 2);
-    return entryIndex - 2;
+    checkConsistency();
+    return newOffset;
 }
 
-void PropertyMap::remove(const Identifier& propertyName, PropertyStorage& propertyStorage)
+size_t PropertyMap::remove(const Identifier& propertyName)
 {
     ASSERT(!propertyName.isNull());
 
-    checkConsistency(propertyStorage);
+    checkConsistency();
 
     UString::Rep* rep = propertyName._ustring.rep();
 
     if (!m_table)
-        return;
+        return WTF::notFound;
+
 
 #if DUMP_PROPERTYMAP_STATS
     ++numProbes;
@@ -229,7 +229,7 @@ void PropertyMap::remove(const Identifier& propertyName, PropertyStorage& proper
     while (1) {
         entryIndex = m_table->entryIndices[i & m_table->sizeMask];
         if (entryIndex == emptyEntryIndex)
-            return;
+            return WTF::notFound;
 
         key = m_table->entries()[entryIndex - 1].key;
         if (rep == key)
@@ -252,23 +252,27 @@ void PropertyMap::remove(const Identifier& propertyName, PropertyStorage& proper
     // Replace this one element with the deleted sentinel. Also clear out
     // the entry so we can iterate all the entries as needed.
     m_table->entryIndices[i & m_table->sizeMask] = deletedSentinelIndex;
+
+    size_t offset = m_table->entries()[entryIndex - 1].offset;
+
     key->deref();
     m_table->entries()[entryIndex - 1].key = 0;
     m_table->entries()[entryIndex - 1].attributes = 0;
-
-    propertyStorage[entryIndex - 2] = jsUndefined();
+    m_table->entries()[entryIndex - 1].offset = 0;
+    m_deletedOffsets.append(offset);
 
     ASSERT(m_table->keyCount >= 1);
     --m_table->keyCount;
     ++m_table->deletedSentinelCount;
 
     if (m_table->deletedSentinelCount * 4 >= m_table->size)
-        rehash(propertyStorage);
+        rehash();
 
-    checkConsistency(propertyStorage);
+    checkConsistency();
+    return offset;
 }
 
-size_t PropertyMap::getOffset(const Identifier& propertyName, unsigned& attributes)
+size_t PropertyMap::get(const Identifier& propertyName, unsigned& attributes)
 {
     ASSERT(!propertyName.isNull());
 
@@ -289,7 +293,7 @@ size_t PropertyMap::getOffset(const Identifier& propertyName, unsigned& attribut
 
     if (rep == m_table->entries()[entryIndex - 1].key) {
         attributes = m_table->entries()[entryIndex - 1].attributes;
-        return entryIndex - 2;
+        return m_table->entries()[entryIndex - 1].offset;
     }
 
 #if DUMP_PROPERTYMAP_STATS
@@ -311,12 +315,12 @@ size_t PropertyMap::getOffset(const Identifier& propertyName, unsigned& attribut
 
         if (rep == m_table->entries()[entryIndex - 1].key) {
             attributes = m_table->entries()[entryIndex - 1].attributes;
-            return entryIndex - 2;
+            return m_table->entries()[entryIndex - 1].offset;
         }
     }
 }
 
-void PropertyMap::insert(const Entry& entry, JSValue* value, PropertyStorage& propertyStorage)
+void PropertyMap::insert(const Entry& entry)
 {
     ASSERT(m_table);
 
@@ -350,70 +354,62 @@ void PropertyMap::insert(const Entry& entry, JSValue* value, PropertyStorage& pr
     m_table->entryIndices[i & m_table->sizeMask] = entryIndex;
     m_table->entries()[entryIndex - 1] = entry;
 
-    propertyStorage[entryIndex - 2] = value;
-
     ++m_table->keyCount;
 }
 
-void PropertyMap::expand(PropertyStorage& propertyStorage)
-{
-    if (!m_table)
-        createTable(propertyStorage);
-    else
-        rehash(m_table->size * 2, propertyStorage);
-}
-
-void PropertyMap::rehash(PropertyStorage& propertyStorage)
+void PropertyMap::expand()
 {
     ASSERT(m_table);
-    ASSERT(m_table->size);
-    rehash(m_table->size, propertyStorage);
+    rehash(m_table->size * 2);
 }
 
-void PropertyMap::createTable(PropertyStorage& propertyStorage)
+void PropertyMap::createTable()
 {
     const unsigned newTableSize = 16;
 
     ASSERT(!m_table);
 
-    checkConsistency(propertyStorage);
+    checkConsistency();
 
     m_table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
     m_table->size = newTableSize;
     m_table->sizeMask = newTableSize - 1;
 
-    checkConsistency(propertyStorage);
+    checkConsistency();
+}
+
+void PropertyMap::rehash()
+{
+    ASSERT(m_table);
+    ASSERT(m_table->size);
+    rehash(m_table->size);
 }
 
-void PropertyMap::rehash(unsigned newTableSize, PropertyStorage& propertyStorage)
+void PropertyMap::rehash(unsigned newTableSize)
 {
     ASSERT(m_table);
 
-    checkConsistency(propertyStorage);
+    checkConsistency();
 
     Table* oldTable = m_table;
-    JSValue** oldPropertStorage = propertyStorage;
 
     m_table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
     m_table->size = newTableSize;
     m_table->sizeMask = newTableSize - 1;
 
-    propertyStorage = new JSValue*[m_table->size];
-
     unsigned lastIndexUsed = 0;
     unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
     for (unsigned i = 1; i <= entryCount; ++i) {
         if (oldTable->entries()[i].key) {
             lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
-            insert(oldTable->entries()[i], oldPropertStorage[i - 1], propertyStorage);
+            insert(oldTable->entries()[i]);
         }
     }
     m_table->lastIndexUsed = lastIndexUsed;
 
     fastFree(oldTable);
-    delete [] oldPropertStorage;
 
-    checkConsistency(propertyStorage);
+    checkConsistency();
 }
 
 static int comparePropertyMapEntryIndices(const void* a, const void* b)
@@ -485,7 +481,7 @@ void PropertyMap::getEnumerablePropertyNames(PropertyNameArray& propertyNames) c
 
 #if DO_PROPERTYMAP_CONSTENCY_CHECK
 
-void PropertyMap::checkConsistency(PropertyStorage& propertyStorage)
+void PropertyMap::checkConsistency()
 {
     if (!m_table)
         return;
@@ -525,10 +521,8 @@ void PropertyMap::checkConsistency(PropertyStorage& propertyStorage)
     unsigned nonEmptyEntryCount = 0;
     for (unsigned c = 1; c <= m_table->keyCount + m_table->deletedSentinelCount; ++c) {
         UString::Rep* rep = m_table->entries()[c].key;
-        if (!rep) {
-            ASSERT(propertyStorage[c - 1]->isUndefined());
+        if (!rep)
             continue;
-        }
         ++nonEmptyEntryCount;
         unsigned i = rep->computedHash();
         unsigned k = 0;
index b92a11e6d6fc1858f2f30903e22fa0d4571cbb77..efa76698ec295b0e50f803f9bcfa6b68ef77e10f 100644 (file)
@@ -42,11 +42,13 @@ namespace JSC {
 
     struct PropertyMapEntry {
         UString::Rep* key;
+        unsigned offset;
         unsigned attributes;
         unsigned index;
 
         PropertyMapEntry(UString::Rep* k, int a)
             : key(k)
+            , offset(0)
             , attributes(a)
             , index(0)
         {
@@ -94,11 +96,10 @@ namespace JSC {
 
         bool isEmpty() { return !m_table; }
 
-        size_t put(const Identifier& propertyName, JSValue*, unsigned attributes, bool checkReadOnly, JSObject* slotBase, PutPropertySlot&, PropertyStorage&);
-        void remove(const Identifier& propertyName, PropertyStorage&);
-
-        size_t getOffset(const Identifier& propertyName);
-        size_t getOffset(const Identifier& propertyName, unsigned& attributes);
+        size_t get(const Identifier& propertyName);
+        size_t get(const Identifier& propertyName, unsigned& attributes);
+        size_t put(const Identifier& propertyName, unsigned attributes);
+        size_t remove(const Identifier& propertyName);
 
         void getEnumerablePropertyNames(PropertyNameArray&) const;
 
@@ -114,16 +115,17 @@ namespace JSC {
         typedef PropertyMapEntry Entry;
         typedef PropertyMapHashTable Table;
 
-        void expand(PropertyStorage&);
-        void rehash(PropertyStorage&);
-        void rehash(unsigned newTableSize, PropertyStorage&);
-        void createTable(PropertyStorage&);
+        void expand();
+        void rehash();
+        void rehash(unsigned newTableSize);
+        void createTable();
 
-        void insert(const Entry&, JSValue*, PropertyStorage&);
+        void insert(const Entry&);
 
-        void checkConsistency(PropertyStorage&);
+        void checkConsistency();
 
         Table* m_table;
+        Vector<unsigned> m_deletedOffsets;
         bool m_getterSetterFlag : 1;
     };
 
@@ -133,7 +135,7 @@ namespace JSC {
     {
     }
 
-    inline size_t PropertyMap::getOffset(const Identifier& propertyName)
+    inline size_t PropertyMap::get(const Identifier& propertyName)
     {
         ASSERT(!propertyName.isNull());
 
@@ -153,7 +155,7 @@ namespace JSC {
             return WTF::notFound;
 
         if (rep == m_table->entries()[entryIndex - 1].key)
-            return entryIndex - 2;
+            return m_table->entries()[entryIndex - 1].offset;
 
 #if DUMP_PROPERTYMAP_STATS
         ++numCollisions;
@@ -173,7 +175,7 @@ namespace JSC {
                 return WTF::notFound;
 
             if (rep == m_table->entries()[entryIndex - 1].key)
-                return entryIndex - 2;
+                return m_table->entries()[entryIndex - 1].offset;
         }
     }
 
index dd419923c2951b06f55eeb98f7f7519fdea695c6..30f02a8e282b6ca32bae587f7bd0e6723a53b816 100644 (file)
@@ -44,6 +44,7 @@ StructureID::StructureID(JSValue* prototype, const TypeInfo& typeInfo)
     , m_previous(0)
     , m_nameInPrevious(0)
     , m_transitionCount(0)
+    , m_propertyStorageCapacity(JSObject::inlineStorageCapacity)
     , m_cachedTransistionOffset(WTF::notFound)
 {
     ASSERT(m_prototype);
@@ -102,32 +103,30 @@ void StructureID::clearEnumerationCache()
     m_cachedPropertyNameArrayData.clear();
 }
 
-void StructureID::transitionTo(StructureID* oldStructureID, StructureID* newStructureID, JSObject* slotBase)
+void StructureID::growPropertyStorageCapacity()
 {
-    if (!slotBase->usingInlineStorage() && oldStructureID->m_propertyMap.size() != newStructureID->m_propertyMap.size())
-        slotBase->allocatePropertyStorage(oldStructureID->m_propertyMap.size(), newStructureID->m_propertyMap.size());
+    if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity)
+        m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity;
+    else
+        m_propertyStorageCapacity *= 2;
 }
 
-PassRefPtr<StructureID> StructureID::addPropertyTransition(StructureID* structureID, const Identifier& propertyName, JSValue* value, unsigned attributes, JSObject* slotBase, PutPropertySlot& slot, PropertyStorage& propertyStorage)
+PassRefPtr<StructureID> StructureID::addPropertyTransition(StructureID* structureID, const Identifier& propertyName, unsigned attributes, size_t& offset)
 {
     ASSERT(!structureID->m_isDictionary);
     ASSERT(structureID->typeInfo().type() == ObjectType);
 
     if (StructureID* existingTransition = structureID->m_transitionTable.get(make_pair(propertyName.ustring().rep(), attributes))) {
-        if (!slotBase->usingInlineStorage() && structureID->m_propertyMap.size() != existingTransition->m_propertyMap.size())
-            slotBase->allocatePropertyStorage(structureID->m_propertyMap.size(), existingTransition->m_propertyMap.size());
-
-        size_t offset = existingTransition->cachedTransistionOffset();
+        offset = existingTransition->cachedTransistionOffset();
         ASSERT(offset != WTF::notFound);
-        propertyStorage[offset] = value;
-        slot.setNewProperty(slotBase, offset);
-
         return existingTransition;
     }
 
     if (structureID->m_transitionCount > s_maxTransitionLength) {
         RefPtr<StructureID> transition = toDictionaryTransition(structureID);
-        transition->m_propertyMap.put(propertyName, value, attributes, false, slotBase, slot, propertyStorage);
+        offset = transition->m_propertyMap.put(propertyName, attributes);
+        if (transition->m_propertyMap.storageSize() > transition->propertyStorageCapacity())
+            transition->growPropertyStorageCapacity();
         return transition.release();
     }
 
@@ -138,8 +137,12 @@ PassRefPtr<StructureID> StructureID::addPropertyTransition(StructureID* structur
     transition->m_attributesInPrevious = attributes;
     transition->m_transitionCount = structureID->m_transitionCount + 1;
     transition->m_propertyMap = structureID->m_propertyMap;
+    transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
+
+    offset = transition->m_propertyMap.put(propertyName, attributes);
+    if (transition->m_propertyMap.storageSize() > transition->propertyStorageCapacity())
+        transition->growPropertyStorageCapacity();
 
-    size_t offset = transition->m_propertyMap.put(propertyName, value, attributes, false, slotBase, slot, propertyStorage);
     transition->setCachedTransistionOffset(offset);
 
     structureID->m_transitionTable.add(make_pair(propertyName.ustring().rep(), attributes), transition.get());
@@ -153,6 +156,7 @@ PassRefPtr<StructureID> StructureID::toDictionaryTransition(StructureID* structu
     RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo());
     transition->m_isDictionary = true;
     transition->m_propertyMap = structureID->m_propertyMap;
+    transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
     return transition.release();
 }
 
@@ -172,6 +176,7 @@ PassRefPtr<StructureID> StructureID::changePrototypeTransition(StructureID* stru
     RefPtr<StructureID> transition = create(prototype, structureID->typeInfo());
     transition->m_transitionCount = structureID->m_transitionCount + 1;
     transition->m_propertyMap = structureID->m_propertyMap;
+    transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
     return transition.release();
 }
 
@@ -180,6 +185,7 @@ PassRefPtr<StructureID> StructureID::getterSetterTransition(StructureID* structu
     RefPtr<StructureID> transition = create(structureID->storedPrototype(), structureID->typeInfo());
     transition->m_transitionCount = structureID->m_transitionCount + 1;
     transition->m_propertyMap = structureID->m_propertyMap;
+    transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
     return transition.release();
 }
 
index fbbe4995fda2e1b557e982fde24c92ff7bd5e158..80e7a5e1429a51fe4f81f96b9c5cc756052b7da5 100644 (file)
@@ -83,7 +83,7 @@ namespace JSC {
         }
 
         static PassRefPtr<StructureID> changePrototypeTransition(StructureID*, JSValue* prototype);
-        static PassRefPtr<StructureID> addPropertyTransition(StructureID*, const Identifier& propertyName, JSValue*, unsigned attributes, JSObject* slotBase, PutPropertySlot&, PropertyStorage&);
+        static PassRefPtr<StructureID> addPropertyTransition(StructureID*, const Identifier& propertyName, unsigned attributes, size_t& offset);
         static PassRefPtr<StructureID> getterSetterTransition(StructureID*);
         static PassRefPtr<StructureID> toDictionaryTransition(StructureID*);
         static PassRefPtr<StructureID> fromDictionaryTransition(StructureID*);
@@ -118,11 +118,12 @@ namespace JSC {
         void setCachedTransistionOffset(size_t offset) { m_cachedTransistionOffset = offset; }
         size_t cachedTransistionOffset() const { return m_cachedTransistionOffset; }
 
+        void growPropertyStorageCapacity();
+        size_t propertyStorageCapacity() const { return m_propertyStorageCapacity; }
+
         void getEnumerablePropertyNames(ExecState*, PropertyNameArray&, JSObject*);
         void clearEnumerationCache();
 
-        static void transitionTo(StructureID* oldStructureID, StructureID* newStructureID, JSObject* slotBase);
-
     private:
         typedef std::pair<RefPtr<UString::Rep>, unsigned> TransitionTableKey;
         typedef HashMap<TransitionTableKey, StructureID*, TransitionTableHash, TransitionTableHashTraits> TransitionTable;
@@ -148,6 +149,7 @@ namespace JSC {
         RefPtr<PropertyNameArrayData> m_cachedPropertyNameArrayData;
 
         PropertyMap m_propertyMap;
+        size_t m_propertyStorageCapacity;
 
         size_t m_cachedTransistionOffset;
     };