Reviewed by Darin.
authormjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 2 Feb 2007 09:09:59 +0000 (09:09 +0000)
committermjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 2 Feb 2007 09:09:59 +0000 (09:09 +0000)
        - 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):

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

JavaScriptCore/ChangeLog
JavaScriptCore/wtf/ListHashSet.h

index ddd96ba1247a3a91485e6e4a031661dbd19d9d0f..7b0ec73b0ee2e76d194698fbb3191cd160693f4a 100644 (file)
@@ -1,3 +1,23 @@
+2007-02-01  Maciej Stachowiak  <mjs@apple.com>
+
+        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):
+
 2007-01-31  Maciej Stachowiak  <mjs@apple.com>
 
         Reviewed by Adam.
index 96e243084ff2b6fab4a7c8b484fb338e2bb143fc..7a252f721f214e5e7395ed8c380d42df61408dc0 100644 (file)
@@ -48,11 +48,13 @@ namespace WTF {
     template<typename ValueArg, typename HashArg> class ListHashSetConstIterator;
 
     template<typename ValueArg> struct ListHashSetNode;
+    template<typename ValueArg> struct ListHashSetNodeAllocator;
     template<typename ValueArg, typename HashArg> struct ListHashSetNodeHashFunctions;
 
     template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {
     private:
         typedef ListHashSetNode<ValueArg> Node;
+        typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;
 
         typedef HashTraits<Node*> NodeTraits;
         typedef ListHashSetNodeHashFunctions<ValueArg, HashArg> NodeHash;
@@ -106,11 +108,71 @@ namespace WTF {
         ImplType m_impl;
         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;
         ListHashSetNode* m_next;
@@ -241,12 +303,13 @@ namespace WTF {
     struct ListHashSetTranslator {
     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)
+        static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator, unsigned)
         {
-            location = new Node(key);
+            location = new (allocator) Node(key);
         }
     };
 
@@ -254,6 +317,7 @@ namespace WTF {
     inline ListHashSet<T, U>::ListHashSet()
         : m_head(0)
         , m_tail(0)
+        , m_allocator(new NodeAllocator)
     {
     }
 
@@ -279,6 +343,7 @@ namespace WTF {
     inline ListHashSet<T, U>::~ListHashSet()
     {
         deleteAllNodes();
+        delete m_allocator;
     }
 
     template<typename T, typename U>
@@ -355,7 +420,7 @@ namespace WTF {
     pair<typename ListHashSet<T, U>::iterator, bool> ListHashSet<T, U>::add(const ValueType &value)
     {
         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));
 
@@ -406,7 +471,7 @@ namespace WTF {
             node->m_next->m_prev = node->m_prev;
         }
 
-        delete node;
+        node->destroy(m_allocator);
     }
 
     template<typename T, typename U>
@@ -433,7 +498,7 @@ namespace WTF {
             return;
 
         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);
     }
 
     template<typename T, typename U>