Changeset 38016 in webkit for trunk/JavaScriptCore/runtime/StructureID.h

Timestamp:

Oct 30, 2008, 5:12:50 PM (17 years ago)

Author:

[email protected]

Message:

2008-10-30 Sam Weinig <​[email protected]>

Reviewed by Cameron Zwarich and Geoffrey Garen.

Fix for ​https://bugs.webkit.org/show_bug.cgi?id=21989
Merge PropertyMap and StructureID

• Move PropertyMap code into StructureID in preparation for lazily creating the map on gets.
• Make remove with transition explicit by adding removePropertyTransition.
• Make the put/remove without transition explicit.
• Make cache invalidation part of put/remove without transition.

1% speedup on SunSpider; 0.5% speedup on v8 suite.

• GNUmakefile.am:
• JavaScriptCore.exp:
• JavaScriptCore.pri:
• JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj:
• JavaScriptCore.xcodeproj/project.pbxproj:
• JavaScriptCoreSources.bkl:
• kjs/AllInOneFile.cpp:
• kjs/identifier.h:
• runtime/JSObject.cpp: (JSC::JSObject::removeDirect):
• runtime/JSObject.h: (JSC::JSObject::putDirect):
• runtime/PropertyMap.cpp: Removed.
• runtime/PropertyMap.h: Removed.
• runtime/PropertyMapHashTable.h: Copied from runtime/PropertyMap.h.
• runtime/StructureID.cpp: (JSC::StructureID::dumpStatistics): (JSC::StructureID::StructureID): (JSC::StructureID::~StructureID): (JSC::StructureID::getEnumerablePropertyNames): (JSC::StructureID::addPropertyTransition): (JSC::StructureID::removePropertyTransition): (JSC::StructureID::toDictionaryTransition): (JSC::StructureID::changePrototypeTransition): (JSC::StructureID::getterSetterTransition): (JSC::StructureID::addPropertyWithoutTransition): (JSC::StructureID::removePropertyWithoutTransition): (JSC::PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger): (JSC::StructureID::checkConsistency): (JSC::StructureID::copyPropertyTable): (JSC::StructureID::get): (JSC::StructureID::put): (JSC::StructureID::remove): (JSC::StructureID::insertIntoPropertyMapHashTable): (JSC::StructureID::expandPropertyMapHashTable): (JSC::StructureID::createPropertyMapHashTable): (JSC::StructureID::rehashPropertyMapHashTable): (JSC::comparePropertyMapEntryIndices): (JSC::StructureID::getEnumerablePropertyNamesInternal):
• runtime/StructureID.h: (JSC::StructureID::propertyStorageSize): (JSC::StructureID::isEmpty): (JSC::StructureID::get):

File:

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

trunk/JavaScriptCore/runtime/StructureID.h

@@ -1 @@
-// -*- mode: c++; c-basic-offset: 4 -*-
 /*
  * Copyright (C) 2008 Apple Inc. All rights reserved.
@@ -30 +29 @@
 #include "JSType.h"
 #include "JSValue.h"
-#include "PropertyMap.h"
+#include "PropertyMapHashTable.h"
 #include "StructureIDTransitionTable.h"
 #include "TypeInfo.h"
+#include "identifier.h"
 #include "ustring.h"
 #include <wtf/HashFunctions.h>
@@ -41 +41 @@
 
 #define DUMP_STRUCTURE_ID_STATISTICS 0
+
+#ifndef NDEBUG
+#define DUMP_PROPERTYMAP_STATS 0
+#else
+#define DUMP_PROPERTYMAP_STATS 0
+#endif
 
 namespace JSC {
@@ -65 +71 @@
         static PassRefPtr<StructureID> changePrototypeTransition(StructureID*, JSValue* prototype);
         static PassRefPtr<StructureID> addPropertyTransition(StructureID*, const Identifier& propertyName, unsigned attributes, size_t& offset);
+        static PassRefPtr<StructureID> removePropertyTransition(StructureID*, const Identifier& propertyName, size_t& offset);
         static PassRefPtr<StructureID> getterSetterTransition(StructureID*);
         static PassRefPtr<StructureID> toDictionaryTransition(StructureID*);
@@ -79 +86 @@
         // These should be used with caution.  
         size_t addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes);
+        size_t removePropertyWithoutTransition(const Identifier& propertyName);
         void setPrototypeWithoutTransition(JSValue* prototype) { m_prototype = prototype; }
 
@@ -102 +110 @@
         void growPropertyStorageCapacity();
         size_t propertyStorageCapacity() const { return m_propertyStorageCapacity; }
-        size_t propertyStorageSize() const { return m_propertyMap.storageSize(); }
-
-        size_t get(const Identifier& propertyName) const { return m_propertyMap.get(propertyName); }
-        size_t get(const Identifier& propertyName, unsigned& attributes) const { return m_propertyMap.get(propertyName, attributes); }
-        size_t put(const Identifier& propertyName, unsigned attributes) { return m_propertyMap.put(propertyName, attributes); }
-        size_t remove(const Identifier& propertyName) { return m_propertyMap.remove(propertyName); }
-
+        size_t propertyStorageSize() const { return m_propertyTable ? m_propertyTable->keyCount + m_deletedOffsets.size() : 0; }
+
+        size_t get(const Identifier& propertyName) const;
+        size_t get(const Identifier& propertyName, unsigned& attributes) const;
         void getEnumerablePropertyNames(ExecState*, PropertyNameArray&, JSObject*);
-        void clearEnumerationCache();
 
         bool hasGetterSetterProperties() const { return m_hasGetterSetterProperties; }
         void setHasGetterSetterProperties(bool hasGetterSetterProperties) { m_hasGetterSetterProperties = hasGetterSetterProperties; }
 
-        bool isEmpty() const { return m_propertyMap.isEmpty(); }
+        bool isEmpty() const { return !m_propertyTable; }
 
     private:
         StructureID(JSValue* prototype, const TypeInfo&);
 
+        size_t put(const Identifier& propertyName, unsigned attributes);
+        size_t remove(const Identifier& propertyName);
+        void getEnumerablePropertyNamesInternal(PropertyNameArray&) const;
+
+        void expandPropertyMapHashTable();
+        void rehashPropertyMapHashTable();
+        void rehashPropertyMapHashTable(unsigned newTableSize);
+        void createPropertyMapHashTable();
+        void insertIntoPropertyMapHashTable(const PropertyMapEntry&);
+        void checkConsistency();
+
+        PropertyMapHashTable* copyPropertyTable();
+
+        void clearEnumerationCache();
+
+        static const unsigned emptyEntryIndex = 0;
+    
         static const size_t s_maxTransitionLength = 64;
 
@@ -138 +159 @@
         RefPtr<PropertyNameArrayData> m_cachedPropertyNameArrayData;
 
-        PropertyMap m_propertyMap;
+        PropertyMapHashTable* m_propertyTable;
+        Vector<unsigned> m_deletedOffsets;
+
         size_t m_propertyStorageCapacity;
 
@@ -149 +172 @@
     };
 
+    inline size_t StructureID::get(const Identifier& propertyName) const
+    {
+        ASSERT(!propertyName.isNull());
+
+        if (!m_propertyTable)
+            return WTF::notFound;
+
+        UString::Rep* rep = propertyName._ustring.rep();
+
+        unsigned i = rep->computedHash();
+
+#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->computedHash());
+
+        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;
+        }
+    }
+
     class StructureIDChain : public RefCounted<StructureIDChain> {
     public: