Changeset 79963 in webkit for trunk/Source/JavaScriptCore/runtime/Structure.h

Timestamp:

Feb 28, 2011, 7:53:09 PM (14 years ago)

Author:

[email protected]

Message:

Bug 55423 - Clean up property tables in Structure

Reviewed by Sam Weinig & Darin Adler.

Encapsulate, reduce duplication of table search code,
and reduce the size of the tables (remove the index,
just maintain the tables in the correct order).

Shows a 0.5% - 1% progression on sunspider.

../JavaScriptCore:

• JavaScriptCore.exp:
• runtime/PropertyMapHashTable.h:

(JSC::isPowerOf2):
(JSC::nextPowerOf2):

bit ops used to calculate table size.

(JSC::PropertyMapEntry::PropertyMapEntry):
(JSC::PropertyTable::ordered_iterator::operator++):
(JSC::PropertyTable::ordered_iterator::operator==):
(JSC::PropertyTable::ordered_iterator::operator!=):
(JSC::PropertyTable::ordered_iterator::operator*):
(JSC::PropertyTable::ordered_iterator::operator->):
(JSC::PropertyTable::ordered_iterator::ordered_iterator):

implementation of the iterator types

(JSC::PropertyTable::PropertyTable):
(JSC::PropertyTable::~PropertyTable):

constructors take an initial capacity for the table,
a table to copy, or both.

(JSC::PropertyTable::begin):
(JSC::PropertyTable::end):

create in-order iterators.

(JSC::PropertyTable::find):

search the hash table

(JSC::PropertyTable::add):

add a value to the hash table

(JSC::PropertyTable::remove):

remove a value from the hash table

(JSC::PropertyTable::size):
(JSC::PropertyTable::isEmpty):

accessors.

(JSC::PropertyTable::propertyStorageSize):
(JSC::PropertyTable::clearDeletedOffsets):
(JSC::PropertyTable::hasDeletedOffset):
(JSC::PropertyTable::getDeletedOffset):
(JSC::PropertyTable::addDeletedOffset):

cache deleted (available) offsets in the property storage array.

(JSC::PropertyTable::copy):

take a copy of the PropertyTable, potentially expanding the capacity.

(JSC::PropertyTable::sizeInMemory):

used for DEBUG build statistics

(JSC::PropertyTable::reinsert):
(JSC::PropertyTable::rehash):
(JSC::PropertyTable::tableCapacity):
(JSC::PropertyTable::deletedEntryIndex):
(JSC::PropertyTable::skipDeletedEntries):
(JSC::PropertyTable::table):
(JSC::PropertyTable::usedCount):
(JSC::PropertyTable::dataSize):
(JSC::PropertyTable::sizeForCapacity):
(JSC::PropertyTable::canInsert):

these methods provide internal implementation.

• runtime/Structure.cpp:

(JSC::Structure::dumpStatistics):
(JSC::Structure::~Structure):
(JSC::Structure::materializePropertyMap):
(JSC::Structure::despecifyDictionaryFunction):
(JSC::Structure::addPropertyTransition):
(JSC::Structure::flattenDictionaryStructure):
(JSC::Structure::copyPropertyTable):
(JSC::Structure::get):
(JSC::Structure::despecifyFunction):
(JSC::Structure::despecifyAllFunctions):
(JSC::Structure::put):
(JSC::Structure::remove):
(JSC::Structure::createPropertyMap):
(JSC::Structure::getPropertyNames):
(JSC::PropertyTable::checkConsistency):
(JSC::Structure::checkConsistency):

factored out code to PropertyMapHashTable.h

• runtime/Structure.h:

(JSC::Structure::propertyStorageSize):
(JSC::Structure::isEmpty):
(JSC::Structure::get):

factored out code to PropertyMapHashTable.h

../JavaScriptGlue:

• ForwardingHeaders/wtf/HashTable.h: Added.

File:

• trunk/Source/JavaScriptCore/runtime/Structure.h (modified) (8 diffs)

trunk/Source/JavaScriptCore/runtime/Structure.h

@@ -41 +41 @@
 #include <wtf/RefCounted.h>
 
-#ifndef NDEBUG
-#define DUMP_PROPERTYMAP_STATS 0
-#else
-#define DUMP_PROPERTYMAP_STATS 0
-#endif
 
 namespace JSC {
@@ -106 +101 @@
         void growPropertyStorageCapacity();
         unsigned propertyStorageCapacity() const { return m_propertyStorageCapacity; }
-        unsigned propertyStorageSize() const { return m_anonymousSlotCount + (m_propertyTable ? m_propertyTable->keyCount + (m_propertyTable->deletedOffsets ? m_propertyTable->deletedOffsets->size() : 0) : static_cast<unsigned>(m_offset + 1)); }
+        unsigned propertyStorageSize() const { return m_anonymousSlotCount + (m_propertyTable ? m_propertyTable->propertyStorageSize() : static_cast<unsigned>(m_offset + 1)); }
         bool isUsingInlineStorage() const;
 
         size_t get(const Identifier& propertyName);
-        size_t get(const StringImpl* rep, unsigned& attributes, JSCell*& specificValue);
+        size_t get(StringImpl* propertyName, unsigned& attributes, JSCell*& specificValue);
         size_t get(const Identifier& propertyName, unsigned& attributes, JSCell*& specificValue)
         {
@@ -125 +120 @@
         unsigned anonymousSlotCount() const { return m_anonymousSlotCount; }
         
-        bool isEmpty() const { return m_propertyTable ? !m_propertyTable->keyCount : m_offset == noOffset; }
+        bool isEmpty() const { return m_propertyTable ? m_propertyTable->isEmpty() : m_offset == noOffset; }
 
         void despecifyDictionaryFunction(const Identifier& propertyName);
@@ -158 +153 @@
         size_t remove(const Identifier& propertyName);
 
-        void expandPropertyMapHashTable();
-        void rehashPropertyMapHashTable();
-        void rehashPropertyMapHashTable(unsigned newTableSize);
-        void createPropertyMapHashTable();
-        void createPropertyMapHashTable(unsigned newTableSize);
-        void insertIntoPropertyMapHashTable(const PropertyMapEntry&);
+        void createPropertyMap(unsigned keyCount = 0);
         void checkConsistency();
 
@@ -169 +159 @@
         void despecifyAllFunctions();
 
-        PropertyMapHashTable* copyPropertyTable();
+        PropertyTable* copyPropertyTable();
         void materializePropertyMap();
         void materializePropertyMapIfNecessary()
         {
-            if (m_propertyTable || !m_previous)             
-                return;
-            materializePropertyMap();
+            if (!m_propertyTable && m_previous)
+                materializePropertyMap();
         }
 
@@ -186 +175 @@
         bool isValid(ExecState*, StructureChain* cachedPrototypeChain) const;
 
-        static const unsigned emptyEntryIndex = 0;
-    
         static const signed char s_maxTransitionLength = 64;
 
@@ -209 +196 @@
         WeakGCPtr<JSPropertyNameIterator> m_enumerationCache;
 
-        PropertyMapHashTable* m_propertyTable;
+        OwnPtr<PropertyTable> m_propertyTable;
 
         uint32_t m_propertyStorageCapacity;
@@ -235 +222 @@
     inline size_t Structure::get(const Identifier& propertyName)
     {
-        ASSERT(!propertyName.isNull());
-
         materializePropertyMapIfNecessary();
         if (!m_propertyTable)
-            return WTF::notFound;
-
-        StringImpl* rep = propertyName.impl();
-
-        unsigned i = rep->existingHash();
-
-#if DUMP_PROPERTYMAP_STATS
-        ++numProbes;
-#endif
-
-        unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
-        if (entryIndex == emptyEntryIndex)
-            return WTF::notFound;
-
-        if (rep == m_propertyTable->entries()[entryIndex - 1].key)
-            return m_propertyTable->entries()[entryIndex - 1].offset;
-
-#if DUMP_PROPERTYMAP_STATS
-        ++numCollisions;
-#endif
-
-        unsigned k = 1 | WTF::doubleHash(rep->existingHash());
-
-        while (1) {
-            i += k;
-
-#if DUMP_PROPERTYMAP_STATS
-            ++numRehashes;
-#endif
-
-            entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
-            if (entryIndex == emptyEntryIndex)
-                return WTF::notFound;
-
-            if (rep == m_propertyTable->entries()[entryIndex - 1].key)
-                return m_propertyTable->entries()[entryIndex - 1].offset;
-        }
+            return notFound;
+
+        PropertyMapEntry* entry = m_propertyTable->find(propertyName.impl()).first;
+        ASSERT(!entry || entry->offset >= m_anonymousSlotCount);
+        return entry ? entry->offset : notFound;
     }