Changeset 27176 in webkit for trunk/JavaScriptCore/wtf/HashTable.h

Timestamp:

Oct 28, 2007, 1:17:39 AM (18 years ago)

Author:

mjs

Message:

Reviewed by Oliver.

• numerous HashTable performance improvements

This does not quite add up to a measurable win on SunSpider, but it allows a
follow-on > 3% improvement and probably helps WebCore too.

I made the following improvements, among others:

• Made HashFunctions note whether it is ok to compare a real value with the equal() function to the empty or deleted value, and used this to optimize the comparisons done in hash lookup.

• Specialized lookup so it doesn't have to do so many extra branches and build so many extra std::pairs for cases that don't need them. There are now four versions, one for read-only access, two for writing, and one folded directly into add() (these all were improvments).

• Made HashMap::get() use lookup() directly instead of find() to avoid having to build iterators.

• Made a special constructor for iterators that knows it points to a valid filled cell and so skips updating itself.

• Reordered memory accesses in the various lookup functions for better codegetion

• Made simple translators avoid passing a hash code around

• Other minor tweaks

• wtf/HashTable.h: (WTF::): (WTF::HashTableConstIterator::HashTableConstIterator): (WTF::HashTableIterator::HashTableIterator): (WTF::IdentityHashTranslator::translate): (WTF::HashTable::end): (WTF::HashTable::lookup): (WTF::HashTable::lookupForWriting): (WTF::HashTable::makeKnownGoodIterator): (WTF::HashTable::makeKnownGoodConstIterator): (WTF::::lookup): (WTF::::lookupForWriting): (WTF::::fullLookupForWriting): (WTF::::add): (WTF::::addPassingHashCode): (WTF::::reinsert): (WTF::::find): (WTF::::contains):
• kjs/identifier.cpp: (WTF::):
• wtf/HashFunctions.h: (WTF::):
• wtf/HashMap.h: (WTF::): (WTF::::get):
• wtf/HashSet.h: (WTF::): (WTF::::add):
• wtf/ListHashSet.h: (WTF::ListHashSetTranslator::translate):

File:

• trunk/JavaScriptCore/wtf/HashTable.h (modified) (18 diffs)

trunk/JavaScriptCore/wtf/HashTable.h

@@ -78 +78 @@
 #endif
 
+    typedef enum { HashItemKnownGood } HashItemKnownGoodTag;
+
+
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     class HashTableConstIterator {
@@ -104 +107 @@
         }
 
+        HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition, HashItemKnownGoodTag)
+            : m_position(position), m_endPosition(endPosition)
+        {
+            addIterator(table, this);
+        }
+
     public:
         HashTableConstIterator()
@@ -211 +220 @@
 
         HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { }
+        HashTableIterator(HashTableType* table, PointerType pos, PointerType end, HashItemKnownGoodTag tag) : m_iterator(table, pos, end, tag) { }
 
     public:
@@ -256 +266 @@
         static unsigned hash(const Key& key) { return HashFunctions::hash(key); }
         static bool equal(const Key& a, const Key& b) { return HashFunctions::equal(a, b); }
-        static void translate(Value& location, const Key&, const Value& value, unsigned) { location = value; }
+        static void translate(Value& location, const Key&, const Value& value) { location = value; }
     };
 
@@ -277 +287 @@
 
         iterator begin() { return makeIterator(m_table); }
-        iterator end() { return makeIterator(m_table + m_tableSize); }
+        iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
         const_iterator begin() const { return makeConstIterator(m_table); }
-        const_iterator end() const { return makeConstIterator(m_table + m_tableSize); }
+        const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
 
         int size() const { return m_keyCount; }
@@ -291 +301 @@
         // in the table.
         template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> add(const T& key, const Extra&);
+        template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> addPassingHashCode(const T& key, const Extra&);
 
         iterator find(const KeyType& key) { return find<KeyType, IdentityTranslatorType>(key); }
@@ -308 +319 @@
         static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
 
+        ValueType* lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key); }
+
     private:
         static ValueType* allocateTable(int size);
@@ -315 +328 @@
         typedef pair<LookupType, unsigned> FullLookupType;
 
-        LookupType lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key).first; }
-        template<typename T, typename HashTranslator> FullLookupType lookup(const T&);
+        template<typename T, typename HashTranslator> ValueType* lookup(const T&);
+        LookupType lookupForWriting(const Key& key) { return lookupForWriting<Key, IdentityTranslatorType>(key); };
+        template<typename T, typename HashTranslator> FullLookupType fullLookupForWriting(const T&);
+        template<typename T, typename HashTranslator> LookupType lookupForWriting(const T&);
 
         void remove(ValueType*);
@@ -337 +352 @@
         iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
         const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
+        iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
+        const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
 
 #if CHECK_HASHTABLE_CONSISTENCY
@@ -383 +400 @@
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     template<typename T, typename HashTranslator>
-    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
+    inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
     {
         ASSERT(m_table);
 
+        int k = 0;
+        int sizeMask = m_tableSizeMask;
+        ValueType* table = m_table;
         unsigned h = HashTranslator::hash(key);
-        int sizeMask = m_tableSizeMask;
         int i = h & sizeMask;
-        int k = 0;
 
 #if DUMP_HASHTABLE_STATS
@@ -397 +415 @@
 #endif
 
-        ValueType* table = m_table;
-        ValueType* deletedEntry = 0;
-
         while (1) {
             ValueType* entry = table + i;
-
-            if (isEmptyBucket(*entry))
-                return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
-            
-            if (isDeletedBucket(*entry))
-                deletedEntry = entry;
-            else if (HashTranslator::equal(Extractor::extract(*entry), key))
-                return makeLookupResult(entry, true, h);
-
+                
+            // we count on the compiler to optimize out this branch
+            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
+                if (HashTranslator::equal(Extractor::extract(*entry), key))
+                    return entry;
+                
+                if (isEmptyBucket(*entry))
+                    return 0;
+            } else {
+                if (isEmptyBucket(*entry))
+                    return 0;
+                
+                if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
+                    return entry;
+            }
 #if DUMP_HASHTABLE_STATS
             ++probeCount;
@@ -422 +443 @@
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
+    template<typename T, typename HashTranslator>
+    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key)
+    {
+        ASSERT(m_table);
+
+        int k = 0;
+        ValueType* table = m_table;
+        int sizeMask = m_tableSizeMask;
+        unsigned h = HashTranslator::hash(key);
+        int i = h & sizeMask;
+
+#if DUMP_HASHTABLE_STATS
+        ++HashTableStats::numAccesses;
+        int probeCount = 0;
+#endif
+
+        ValueType* deletedEntry = 0;
+
+        while (1) {
+            ValueType* entry = table + i;
+            
+            // we count on the compiler to optimize out this branch
+            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
+                if (isEmptyBucket(*entry))
+                    return LookupType(deletedEntry ? deletedEntry : entry, false);
+                
+                if (HashTranslator::equal(Extractor::extract(*entry), key))
+                    return LookupType(entry, true);
+                
+                if (isDeletedBucket(*entry))
+                    deletedEntry = entry;
+            } else {
+                if (isEmptyBucket(*entry))
+                    return LookupType(deletedEntry ? deletedEntry : entry, false);
+            
+                if (isDeletedBucket(*entry))
+                    deletedEntry = entry;
+                else if (HashTranslator::equal(Extractor::extract(*entry), key))
+                    return LookupType(entry, true);
+            }
+#if DUMP_HASHTABLE_STATS
+            ++probeCount;
+            HashTableStats::recordCollisionAtCount(probeCount);
+#endif
+            if (k == 0)
+                k = 1 | (h % sizeMask);
+            i = (i + k) & sizeMask;
+        }
+    }
+
+    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
+    template<typename T, typename HashTranslator>
+    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key)
+    {
+        ASSERT(m_table);
+
+        int k = 0;
+        ValueType* table = m_table;
+        int sizeMask = m_tableSizeMask;
+        unsigned h = HashTranslator::hash(key);
+        int i = h & sizeMask;
+
+#if DUMP_HASHTABLE_STATS
+        ++HashTableStats::numAccesses;
+        int probeCount = 0;
+#endif
+
+        ValueType* deletedEntry = 0;
+
+        while (1) {
+            ValueType* entry = table + i;
+            
+            // we count on the compiler to optimize out this branch
+            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
+                if (isEmptyBucket(*entry))
+                    return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
+                
+                if (HashTranslator::equal(Extractor::extract(*entry), key))
+                    return makeLookupResult(entry, true, h);
+                
+                if (isDeletedBucket(*entry))
+                    deletedEntry = entry;
+            } else {
+                if (isEmptyBucket(*entry))
+                    return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
+            
+                if (isDeletedBucket(*entry))
+                    deletedEntry = entry;
+                else if (HashTranslator::equal(Extractor::extract(*entry), key))
+                    return makeLookupResult(entry, true, h);
+            }
+#if DUMP_HASHTABLE_STATS
+            ++probeCount;
+            HashTableStats::recordCollisionAtCount(probeCount);
+#endif
+            if (k == 0)
+                k = 1 | (h % sizeMask);
+            i = (i + k) & sizeMask;
+        }
+    }
+
+    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     template<typename T, typename Extra, typename HashTranslator>
-    inline pair<typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(const T& key, const Extra &extra)
+    inline pair<typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(const T& key, const Extra& extra)
     {
         invalidateIterators();
@@ -432 +555 @@
         checkTableConsistency();
 
-        FullLookupType lookupResult = lookup<T, HashTranslator>(key);
-
-        ValueType *entry = lookupResult.first.first;
-        bool found = lookupResult.first.second;
-        unsigned h = lookupResult.second;
-
-        if (found)
-            return std::make_pair(makeIterator(entry), false);
-
-        if (isDeletedBucket(*entry))
-            --m_deletedCount;
-
-        HashTranslator::translate(*entry, key, extra, h);
+        ASSERT(m_table);
+
+        int k = 0;
+        ValueType* table = m_table;
+        int sizeMask = m_tableSizeMask;
+        unsigned h = HashTranslator::hash(key);
+        int i = h & sizeMask;
+
+#if DUMP_HASHTABLE_STATS
+        ++HashTableStats::numAccesses;
+        int probeCount = 0;
+#endif
+
+        ValueType* deletedEntry = 0;
+        ValueType* entry;
+        while (1) {
+            entry = table + i;
+            
+            // we count on the compiler to optimize out this branch
+            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
+                if (isEmptyBucket(*entry))
+                    break;
+                
+                if (HashTranslator::equal(Extractor::extract(*entry), key))
+                    return std::make_pair(makeKnownGoodIterator(entry), false);
+                
+                if (isDeletedBucket(*entry))
+                    deletedEntry = entry;
+            } else {
+                if (isEmptyBucket(*entry))
+                    break;
+            
+                if (isDeletedBucket(*entry))
+                    deletedEntry = entry;
+                else if (HashTranslator::equal(Extractor::extract(*entry), key))
+                    return std::make_pair(makeKnownGoodIterator(entry), false);
+            }
+#if DUMP_HASHTABLE_STATS
+            ++probeCount;
+            HashTableStats::recordCollisionAtCount(probeCount);
+#endif
+            if (k == 0)
+                k = 1 | (h % sizeMask);
+            i = (i + k) & sizeMask;
+        }
+
+        if (deletedEntry) {
+            entry = deletedEntry;
+            --m_deletedCount; 
+        }
+
+        HashTranslator::translate(*entry, key, extra);
+
         ++m_keyCount;
-
+        
         if (shouldExpand()) {
             // FIXME: this makes an extra copy on expand. Probably not that bad since
@@ -455 +618 @@
             return std::make_pair(find(enteredKey), true);
         }
-
+        
         checkTableConsistency();
-
-        return std::make_pair(makeIterator(entry), true);
+        
+        return std::make_pair(makeKnownGoodIterator(entry), true);
+    }
+
+    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
+    template<typename T, typename Extra, typename HashTranslator>
+    inline pair<typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addPassingHashCode(const T& key, const Extra& extra)
+    {
+        invalidateIterators();
+
+        if (!m_table)
+            expand();
+
+        checkTableConsistency();
+
+        FullLookupType lookupResult = fullLookupForWriting<T, HashTranslator>(key);
+
+        ValueType *entry = lookupResult.first.first;
+        bool found = lookupResult.first.second;
+        unsigned h = lookupResult.second;
+        
+        if (found)
+            return std::make_pair(makeKnownGoodIterator(entry), false);
+        
+        if (isDeletedBucket(*entry))
+            --m_deletedCount;
+        
+        HashTranslator::translate(*entry, key, extra, h);
+        ++m_keyCount;
+        if (shouldExpand()) {
+            // FIXME: this makes an extra copy on expand. Probably not that bad since
+            // expand is rare, but would be better to have a version of expand that can
+            // follow a pivot entry and return the new position
+            KeyType enteredKey = Extractor::extract(*entry);
+            expand();
+            return std::make_pair(find(enteredKey), true);
+        }
+
+        checkTableConsistency();
+
+        return std::make_pair(makeKnownGoodIterator(entry), true);
     }
 
@@ -465 +667 @@
     {
         ASSERT(m_table);
-        ASSERT(!lookup(Extractor::extract(entry)).second);
-        ASSERT(!isDeletedBucket(*(lookup(Extractor::extract(entry)).first)));
+        ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
+        ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
 #if DUMP_HASHTABLE_STATS
         ++HashTableStats::numReinserts;
 #endif
 
-        Mover<ValueType, Traits::needsDestruction>::move(entry, *(lookup(Extractor::extract(entry)).first));
+        Mover<ValueType, Traits::needsDestruction>::move(entry, *(lookupForWriting(Extractor::extract(entry)).first));
     }
 
@@ -481 +683 @@
             return end();
 
-        LookupType result = lookup<T, HashTranslator>(key).first;
-        if (!result.second)
+        ValueType* entry = lookup<T, HashTranslator>(key);
+        if (!entry)
             return end();
-        return makeIterator(result.first);
+
+        return makeKnownGoodIterator(entry);
     }
 
@@ -494 +697 @@
             return end();
 
-        LookupType result = const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key).first;
-        if (!result.second)
+        ValueType* entry = const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key);
+        if (!entry)
             return end();
-        return makeConstIterator(result.first);
+
+        return makeKnownGoodConstIterator(entry);
     }
 
@@ -507 +711 @@
             return false;
 
-        return const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key).first.second;
+        return const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key);
     }