Changeset 19352 in webkit for trunk/JavaScriptCore/wtf

Timestamp:

Feb 2, 2007, 1:09:59 AM (18 years ago)

Author:

mjs

Message:

Reviewed by Darin.

• use a custom allocator for ListHashSet, to fix ~1% per regression using it for form control

• wtf/ListHashSet.h: (WTF::ListHashSetNodeAllocator::ListHashSetNodeAllocator): (WTF::ListHashSetNodeAllocator::allocate): (WTF::ListHashSetNodeAllocator::deallocate): (WTF::ListHashSetNode::operator new): (WTF::ListHashSetNode::operator delete): (WTF::ListHashSetNode::destroy): (WTF::ListHashSetTranslator::translate): (WTF::::ListHashSet): (WTF::::~ListHashSet): (WTF::::add): (WTF::::unlinkAndDelete): (WTF::::deleteAllNodes):

File:

• trunk/JavaScriptCore/wtf/ListHashSet.h (modified) (9 diffs)

trunk/JavaScriptCore/wtf/ListHashSet.h

@@ -49 +49 @@
 
     template<typename ValueArg> struct ListHashSetNode;
+    template<typename ValueArg> struct ListHashSetNodeAllocator;
     template<typename ValueArg, typename HashArg> struct ListHashSetNodeHashFunctions;
 
@@ -54 +55 @@
     private:
         typedef ListHashSetNode<ValueArg> Node;
+        typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;
 
         typedef HashTraits<Node*> NodeTraits;
@@ -107 +109 @@
         Node* m_head;
         Node* m_tail;
+        NodeAllocator* m_allocator;
+    };
+
+
+    template<typename ValueArg> struct ListHashSetNodeAllocator {
+        typedef ListHashSetNode<ValueArg> Node;
+        typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;
+
+        ListHashSetNodeAllocator() 
+            : m_freeList(pool())
+        { 
+            memset(m_pool, 0, sizeof(m_pool));  
+        }
+
+        Node* allocate() 
+        { 
+            Node* result = m_freeList;
+
+            if (!result)
+                return static_cast<Node*>(fastMalloc(sizeof(Node)));
+
+            Node* next = result->m_next;
+            if (!next && inPool(result + 1))
+                next = result + 1;
+            m_freeList = next;
+            
+            return result;
+        }
+
+        void deallocate(Node* node) 
+        {
+            if (inPool(node)) {
+                node->m_next = m_freeList;
+                m_freeList = node;
+                return;
+            }
+
+            fastFree(node);
+        }
+        
+
+    private:
+        Node* pool() { return reinterpret_cast<Node*>(m_pool.pool); }
+        bool inPool(Node* node) 
+        { 
+            return reinterpret_cast<char*>(node) >= m_pool.pool && reinterpret_cast<char*>(node) < m_pool.pool + sizeof(m_pool.pool); 
+        }
+
+        Node* m_freeList;
+        static const size_t m_poolSize = 256;
+        union {
+            char pool[sizeof(Node) * m_poolSize];
+            double forAlignment;
+        } m_pool;
     };
 
     template<typename ValueArg> struct ListHashSetNode {
-        // FIXME: arguably this should use a recycling custom allocator
+        typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;
+
         ListHashSetNode(ValueArg value) : m_value(value), m_prev(0), m_next(0) {}
+
+        void* operator new(size_t s, NodeAllocator* allocator) { return allocator->allocate(); }
+        void operator delete(void* p) { }
+        void destroy(NodeAllocator* allocator) { delete this; allocator->deallocate(this); }
+        
         ValueArg m_value;
         ListHashSetNode* m_prev;
@@ -242 +304 @@
     private:
         typedef ListHashSetNode<ValueType> Node;
+        typedef ListHashSetNodeAllocator<ValueType> NodeAllocator;
     public:
         static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
         static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); }
-        static void translate(Node*& location, const ValueType& key, const ValueType&, unsigned)
-        {
-            location = new Node(key);
+        static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator, unsigned)
+        {
+            location = new (allocator) Node(key);
         }
     };
@@ -255 +318 @@
         : m_head(0)
         , m_tail(0)
+        , m_allocator(new NodeAllocator)
     {
     }
@@ -280 +344 @@
     {
         deleteAllNodes();
+        delete m_allocator;
     }
 
@@ -356 +421 @@
     {
         typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
-        pair<typename ImplType::iterator, bool> result =  m_impl.template add<ValueType, ValueType, Translator>(value, value);
+        pair<typename ImplType::iterator, bool> result =  m_impl.template add<ValueType, NodeAllocator*, Translator>(value, m_allocator);
         if (result.second)
             appendNode(*(result.first));
@@ -407 +472 @@
         }
 
-        delete node;
+        node->destroy(m_allocator);
     }
 
@@ -434 +499 @@
 
         for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0)
-            delete node;
+            node->destroy(m_allocator);
     }