[webkit-changes] [183499] trunk/Source

Tue, 28 Apr 2015 12:40:59 -0700

Title: [183499] trunk/Source
Revision
183499
Author
[email protected]
Date
2015-04-28 12:40:19 -0700 (Tue, 28 Apr 2015)

Log Message

[Content Extensions] Use less memory for CombinedURLFilters.
https://bugs.webkit.org/show_bug.cgi?id=144290

Patch by Alex Christensen <[email protected]> on 2015-04-28
Reviewed by Andreas Kling.

Source/WebCore:

* contentextensions/CombinedURLFilters.cpp:
(WebCore::ContentExtensions::recursiveMemoryUsed):
(WebCore::ContentExtensions::CombinedURLFilters::addPattern):
(WebCore::ContentExtensions::generateNFAForSubtree):
(WebCore::ContentExtensions::CombinedURLFilters::createNFAs):
* contentextensions/NFA.cpp:
(WebCore::ContentExtensions::NFA::memoryUsed):
(WebCore::ContentExtensions::NFA::setActions):
* contentextensions/NFA.h:
* contentextensions/NFANode.h:
* contentextensions/Term.h:
(WebCore::ContentExtensions::Term::Term::generateGraph):
(WebCore::ContentExtensions::Term::generateSubgraphForAtom):
Use Vectors instead of HashTables in PrefixTreeVertex because the sets stay small and need to be more memory efficient.

Source/WTF:

* wtf/Forward.h:
* wtf/Vector.h:
Added a minCapacity template parameter to allow changing the minimum size of an
allocated buffer. The default minCapacity is kept at 16 unless otherwise specified
to have no change on existing code, but this could be changed later. A smaller
default minCapacity would use less memory with small Vectors but spend more time
copying when expanding to large Vectors.

Modified Paths

Diff

Modified: trunk/Source/WTF/ChangeLog (183498 => 183499)


--- trunk/Source/WTF/ChangeLog	2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WTF/ChangeLog	2015-04-28 19:40:19 UTC (rev 183499)
@@ -1,3 +1,18 @@
+2015-04-28  Alex Christensen  <[email protected]>
+
+        [Content Extensions] Use less memory for CombinedURLFilters.
+        https://bugs.webkit.org/show_bug.cgi?id=144290
+
+        Reviewed by Andreas Kling.
+
+        * wtf/Forward.h:
+        * wtf/Vector.h:
+        Added a minCapacity template parameter to allow changing the minimum size of an 
+        allocated buffer. The default minCapacity is kept at 16 unless otherwise specified 
+        to have no change on existing code, but this could be changed later. A smaller 
+        default minCapacity would use less memory with small Vectors but spend more time 
+        copying when expanding to large Vectors.
+
 2015-04-27  Brent Fulgham  <[email protected]>
 
         [Win] Deactivate WebGL until Windows tests work properly

Modified: trunk/Source/WTF/wtf/Forward.h (183498 => 183499)


--- trunk/Source/WTF/wtf/Forward.h	2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WTF/wtf/Forward.h	2015-04-28 19:40:19 UTC (rev 183499)
@@ -33,7 +33,7 @@
 template<typename T> class Ref;
 template<typename T> class StringBuffer;
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler> class Vector;
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> class Vector;
 
 class AtomicString;
 class AtomicStringImpl;

Modified: trunk/Source/WTF/wtf/Vector.h (183498 => 183499)


--- trunk/Source/WTF/wtf/Vector.h	2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WTF/wtf/Vector.h	2015-04-28 19:40:19 UTC (rev 183499)
@@ -581,7 +581,7 @@
     }
 };
 
-template<typename T, size_t inlineCapacity = 0, typename OverflowHandler = CrashOnOverflow>
+template<typename T, size_t inlineCapacity = 0, typename OverflowHandler = CrashOnOverflow, size_t minCapacity = 16>
 class Vector : private VectorBuffer<T, inlineCapacity> {
     WTF_MAKE_FAST_ALLOCATED;
 private:
@@ -754,7 +754,7 @@
 
     MallocPtr<T> releaseBuffer();
 
-    void swap(Vector<T, inlineCapacity, OverflowHandler>& other)
+    void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
     {
 #if ASAN_ENABLED
         if (this == std::addressof(other)) // ASan will crash if we try to restrict access to the same buffer twice.
@@ -804,8 +804,8 @@
 #endif
 };
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-Vector<T, inlineCapacity, OverflowHandler>::Vector(const Vector& other)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector& other)
     : Base(other.capacity(), other.size())
 {
     asanSetInitialBufferSizeTo(other.size());
@@ -814,9 +814,9 @@
         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
 template<size_t otherCapacity, typename otherOverflowBehaviour>
-Vector<T, inlineCapacity, OverflowHandler>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
+Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
     : Base(other.capacity(), other.size())
 {
     asanSetInitialBufferSizeTo(other.size());
@@ -825,8 +825,8 @@
         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(const Vector<T, inlineCapacity, OverflowHandler>& other)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
 {
     if (&other == this)
         return *this;
@@ -850,9 +850,9 @@
 
 inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
 template<size_t otherCapacity, typename otherOverflowBehaviour>
-Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
+Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
 {
     // If the inline capacities match, we should call the more specific
     // template.  If the inline capacities don't match, the two objects
@@ -876,29 +876,29 @@
     return *this;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline Vector<T, inlineCapacity, OverflowHandler>::Vector(Vector<T, inlineCapacity, OverflowHandler>&& other)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
 {
     swap(other);
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(Vector<T, inlineCapacity, OverflowHandler>&& other)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
 {
     swap(other);
     return *this;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
 template<typename U>
-bool Vector<T, inlineCapacity, OverflowHandler>::contains(const U& value) const
+bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::contains(const U& value) const
 {
     return find(value) != notFound;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
 template<typename U>
-size_t Vector<T, inlineCapacity, OverflowHandler>::find(const U& value) const
+size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::find(const U& value) const
 {
     for (size_t i = 0; i < size(); ++i) {
         if (at(i) == value)
@@ -907,9 +907,9 @@
     return notFound;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
 template<typename U>
-size_t Vector<T, inlineCapacity, OverflowHandler>::reverseFind(const U& value) const
+size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverseFind(const U& value) const
 {
     for (size_t i = 1; i <= size(); ++i) {
         const size_t index = size() - i;
@@ -919,8 +919,8 @@
     return notFound;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::fill(const T& val, size_t newSize)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::fill(const T& val, size_t newSize)
 {
     if (size() > newSize)
         shrink(newSize);
@@ -937,22 +937,22 @@
     m_size = newSize;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
 template<typename Iterator>
-void Vector<T, inlineCapacity, OverflowHandler>::appendRange(Iterator start, Iterator end)
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendRange(Iterator start, Iterator end)
 {
     for (Iterator it = start; it != end; ++it)
         append(*it);
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity)
 {
-    reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
+    reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-T* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, T* ptr)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, T* ptr)
 {
     if (ptr < begin() || ptr >= end()) {
         expandCapacity(newMinCapacity);
@@ -963,14 +963,14 @@
     return begin() + index;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-bool Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity)
 {
-    return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
+    return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-const T* Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+const T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
 {
     if (ptr < begin() || ptr >= end()) {
         if (!tryExpandCapacity(newMinCapacity))
@@ -983,15 +983,15 @@
     return begin() + index;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-inline U* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, U* ptr)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+inline U* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
 {
     expandCapacity(newMinCapacity);
     return ptr;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::resize(size_t size)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resize(size_t size)
 {
     if (size <= m_size) {
         TypeOperations::destruct(begin() + size, end());
@@ -1007,15 +1007,15 @@
     m_size = size;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::resizeToFit(size_t size)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resizeToFit(size_t size)
 {
     reserveCapacity(size);
     resize(size);
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::shrink(size_t size)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrink(size_t size)
 {
     ASSERT(size <= m_size);
     TypeOperations::destruct(begin() + size, end());
@@ -1023,8 +1023,8 @@
     m_size = size;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::grow(size_t size)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::grow(size_t size)
 {
     ASSERT(size >= m_size);
     if (size > capacity())
@@ -1035,8 +1035,8 @@
     m_size = size;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::asanSetInitialBufferSizeTo(size_t size)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetInitialBufferSizeTo(size_t size)
 {
 #if ASAN_ENABLED
     if (!buffer())
@@ -1051,8 +1051,8 @@
 #endif
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::asanSetBufferSizeToFullCapacity()
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetBufferSizeToFullCapacity()
 {
 #if ASAN_ENABLED
     if (!buffer())
@@ -1063,8 +1063,8 @@
 #endif
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::asanBufferSizeWillChangeTo(size_t newSize)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanBufferSizeWillChangeTo(size_t newSize)
 {
 #if ASAN_ENABLED
     if (!buffer())
@@ -1077,8 +1077,8 @@
 #endif
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::reserveCapacity(size_t newCapacity)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveCapacity(size_t newCapacity)
 {
     if (newCapacity <= capacity())
         return;
@@ -1096,8 +1096,8 @@
     Base::deallocateBuffer(oldBuffer);
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-bool Vector<T, inlineCapacity, OverflowHandler>::tryReserveCapacity(size_t newCapacity)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryReserveCapacity(size_t newCapacity)
 {
     if (newCapacity <= capacity())
         return true;
@@ -1119,8 +1119,8 @@
     return true;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::reserveInitialCapacity(size_t initialCapacity)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveInitialCapacity(size_t initialCapacity)
 {
     ASSERT(!m_size);
     ASSERT(capacity() == inlineCapacity);
@@ -1128,8 +1128,8 @@
         Base::allocateBuffer(initialCapacity);
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-void Vector<T, inlineCapacity, OverflowHandler>::shrinkCapacity(size_t newCapacity)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrinkCapacity(size_t newCapacity)
 {
     if (newCapacity >= capacity())
         return;
@@ -1162,8 +1162,8 @@
 // Templatizing these is better than just letting the conversion happen implicitly,
 // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
 // without refcount thrash.
-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-void Vector<T, inlineCapacity, OverflowHandler>::append(const U* data, size_t dataSize)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(const U* data, size_t dataSize)
 {
     size_t newSize = m_size + dataSize;
     if (newSize > capacity()) {
@@ -1178,8 +1178,8 @@
     m_size = newSize;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-bool Vector<T, inlineCapacity, OverflowHandler>::tryAppend(const U* data, size_t dataSize)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryAppend(const U* data, size_t dataSize)
 {
     size_t newSize = m_size + dataSize;
     if (newSize > capacity()) {
@@ -1197,8 +1197,8 @@
     return true;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler>::append(U&& value)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(U&& value)
 {
     if (size() != capacity()) {
         asanBufferSizeWillChangeTo(m_size + 1);
@@ -1210,8 +1210,8 @@
     appendSlowCase(std::forward<U>(value));
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-void Vector<T, inlineCapacity, OverflowHandler>::appendSlowCase(U&& value)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendSlowCase(U&& value)
 {
     ASSERT(size() == capacity());
 
@@ -1227,8 +1227,8 @@
 // This version of append saves a branch in the case where you know that the
 // vector's capacity is large enough for the append to succeed.
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-inline void Vector<T, inlineCapacity, OverflowHandler>::uncheckedAppend(U&& value)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::uncheckedAppend(U&& value)
 {
     ASSERT(size() < capacity());
 
@@ -1239,14 +1239,14 @@
     ++m_size;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t otherCapacity>
-inline void Vector<T, inlineCapacity, OverflowHandler>::appendVector(const Vector<U, otherCapacity>& val)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U, size_t otherCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendVector(const Vector<U, otherCapacity>& val)
 {
     append(val.begin(), val.size());
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, const U* data, size_t dataSize)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, const U* data, size_t dataSize)
 {
     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
     size_t newSize = m_size + dataSize;
@@ -1263,8 +1263,8 @@
     m_size = newSize;
 }
  
-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
-inline void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, U&& value)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, U&& value)
 {
     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
 
@@ -1282,14 +1282,14 @@
     ++m_size;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t c>
-inline void Vector<T, inlineCapacity, OverflowHandler>::insertVector(size_t position, const Vector<U, c>& val)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U, size_t c>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insertVector(size_t position, const Vector<U, c>& val)
 {
     insert(position, val.begin(), val.size());
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position)
 {
     ASSERT_WITH_SECURITY_IMPLICATION(position < size());
     T* spot = begin() + position;
@@ -1299,8 +1299,8 @@
     --m_size;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position, size_t length)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position, size_t length)
 {
     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
     ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
@@ -1312,18 +1312,18 @@
     m_size -= length;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
 template<typename U>
-inline bool Vector<T, inlineCapacity, OverflowHandler>::removeFirst(const U& value)
+inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirst(const U& value)
 {
     return removeFirstMatching([&value] (const T& current) {
         return current == value;
     });
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
 template<typename MatchFunction>
-inline bool Vector<T, inlineCapacity, OverflowHandler>::removeFirstMatching(const MatchFunction& matches)
+inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirstMatching(const MatchFunction& matches)
 {
     for (size_t i = 0; i < size(); ++i) {
         if (matches(at(i))) {
@@ -1334,18 +1334,18 @@
     return false;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
 template<typename U>
-inline unsigned Vector<T, inlineCapacity, OverflowHandler>::removeAll(const U& value)
+inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAll(const U& value)
 {
     return removeAllMatching([&value] (const T& current) {
         return current == value;
     });
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
 template<typename MatchFunction>
-inline unsigned Vector<T, inlineCapacity, OverflowHandler>::removeAllMatching(const MatchFunction& matches)
+inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAllMatching(const MatchFunction& matches)
 {
     iterator holeBegin = end();
     iterator holeEnd = end();
@@ -1370,15 +1370,15 @@
     return matchCount;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::reverse()
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverse()
 {
     for (size_t i = 0; i < m_size / 2; ++i)
         std::swap(at(i), at(m_size - 1 - i));
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler>::releaseBuffer()
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler, minCapacity>::releaseBuffer()
 {
     // FIXME: Find a way to preserve annotations on the returned buffer.
     // ASan requires that all annotations are removed before deallocation,
@@ -1399,8 +1399,8 @@
     return buffer;
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void Vector<T, inlineCapacity, OverflowHandler>::checkConsistency()
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::checkConsistency()
 {
 #if !ASSERT_DISABLED
     for (size_t i = 0; i < size(); ++i)
@@ -1408,14 +1408,14 @@
 #endif
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline void swap(Vector<T, inlineCapacity, OverflowHandler>& a, Vector<T, inlineCapacity, OverflowHandler>& b)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
 {
     a.swap(b);
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-bool operator==(const Vector<T, inlineCapacity, OverflowHandler>& a, const Vector<T, inlineCapacity, OverflowHandler>& b)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+bool operator==(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
 {
     if (a.size() != b.size())
         return false;
@@ -1423,8 +1423,8 @@
     return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
 }
 
-template<typename T, size_t inlineCapacity, typename OverflowHandler>
-inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler>& a, const Vector<T, inlineCapacity, OverflowHandler>& b)
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
+inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
 {
     return !(a == b);
 }

Modified: trunk/Source/WebCore/ChangeLog (183498 => 183499)


--- trunk/Source/WebCore/ChangeLog	2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WebCore/ChangeLog	2015-04-28 19:40:19 UTC (rev 183499)
@@ -1,3 +1,25 @@
+2015-04-28  Alex Christensen  <[email protected]>
+
+        [Content Extensions] Use less memory for CombinedURLFilters.
+        https://bugs.webkit.org/show_bug.cgi?id=144290
+
+        Reviewed by Andreas Kling.
+
+        * contentextensions/CombinedURLFilters.cpp:
+        (WebCore::ContentExtensions::recursiveMemoryUsed):
+        (WebCore::ContentExtensions::CombinedURLFilters::addPattern):
+        (WebCore::ContentExtensions::generateNFAForSubtree):
+        (WebCore::ContentExtensions::CombinedURLFilters::createNFAs):
+        * contentextensions/NFA.cpp:
+        (WebCore::ContentExtensions::NFA::memoryUsed):
+        (WebCore::ContentExtensions::NFA::setActions):
+        * contentextensions/NFA.h:
+        * contentextensions/NFANode.h:
+        * contentextensions/Term.h:
+        (WebCore::ContentExtensions::Term::Term::generateGraph):
+        (WebCore::ContentExtensions::Term::generateSubgraphForAtom):
+        Use Vectors instead of HashTables in PrefixTreeVertex because the sets stay small and need to be more memory efficient.
+
 2015-04-28  Brady Eidson  <[email protected]>
 
         Consolidate most "frame load" arguments into FrameLoadRequest.

Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp (183498 => 183499)


--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp	2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp	2015-04-28 19:40:19 UTC (rev 183499)
@@ -29,17 +29,17 @@
 #if ENABLE(CONTENT_EXTENSIONS)
 
 #include "Term.h"
-#include <wtf/HashMap.h>
+#include <wtf/Vector.h>
 
 namespace WebCore {
 
 namespace ContentExtensions {
 
-typedef HashMap<Term, std::unique_ptr<PrefixTreeVertex>, TermHash, TermHashTraits> PrefixTreeEdges;
+typedef Vector<std::pair<Term, std::unique_ptr<PrefixTreeVertex>>, 0, WTF::CrashOnOverflow, 1> PrefixTreeEdges;
 
 struct PrefixTreeVertex {
     PrefixTreeEdges edges;
-    ActionSet finalActions;
+    ActionList finalActions;
     bool inVariableLengthPrefix { false };
 };
 
@@ -48,8 +48,8 @@
     size_t size = sizeof(PrefixTreeVertex)
         + node->edges.capacity() * sizeof(std::pair<Term, std::unique_ptr<PrefixTreeVertex>>)
         + node->finalActions.capacity() * sizeof(uint64_t);
-    for (const auto& child : node->edges.values())
-        size += recursiveMemoryUsed(child);
+    for (const auto& child : node->edges)
+        size += recursiveMemoryUsed(child.second);
     return size;
 }
 
@@ -88,23 +88,30 @@
     prefixTreeVerticesForPattern.append(lastPrefixTree);
 
     for (const Term& term : pattern) {
-        auto nextEntry = lastPrefixTree->edges.find(term);
-        if (nextEntry != lastPrefixTree->edges.end())
-            lastPrefixTree = nextEntry->value.get();
+        size_t nextEntryIndex = WTF::notFound;
+        for (size_t i = 0; i < lastPrefixTree->edges.size(); ++i) {
+            if (lastPrefixTree->edges[i].first == term) {
+                nextEntryIndex = i;
+                break;
+            }
+        }
+        if (nextEntryIndex != WTF::notFound)
+            lastPrefixTree = lastPrefixTree->edges[nextEntryIndex].second.get();
         else {
             hasNewTerm = true;
 
             std::unique_ptr<PrefixTreeVertex> nextPrefixTreeVertex = std::make_unique<PrefixTreeVertex>();
 
-            auto addResult = lastPrefixTree->edges.set(term, WTF::move(nextPrefixTreeVertex));
-            ASSERT(addResult.isNewEntry);
-
-            lastPrefixTree = addResult.iterator->value.get();
+            ASSERT(lastPrefixTree->edges.find(std::make_pair(term, std::make_unique<PrefixTreeVertex>())) == WTF::notFound);
+            lastPrefixTree->edges.append(std::make_pair(term, WTF::move(nextPrefixTreeVertex)));
+            lastPrefixTree = lastPrefixTree->edges.last().second.get();
         }
         prefixTreeVerticesForPattern.append(lastPrefixTree);
     }
 
-    prefixTreeVerticesForPattern.last()->finalActions.add(actionId);
+    ActionList& actions = prefixTreeVerticesForPattern.last()->finalActions;
+    if (actions.find(actionId) == WTF::notFound)
+        actions.append(actionId);
 
     if (!hasNewTerm)
         return;
@@ -142,13 +149,13 @@
     while (true) {
     ProcessSubtree:
         for (ActiveNFASubtree& activeSubtree = activeStack.last(); activeSubtree.iterator != activeSubtree.vertex->edges.end(); ++activeSubtree.iterator) {
-            if (activeSubtree.iterator->value->inVariableLengthPrefix)
+            if (activeSubtree.iterator->second->inVariableLengthPrefix)
                 continue;
 
-            const Term& term = activeSubtree.iterator->key;
-            unsigned newEndNodeIndex = term.generateGraph(nfa, activeSubtree.lastNodeIndex, activeSubtree.iterator->value->finalActions);
+            const Term& term = activeSubtree.iterator->first;
+            unsigned newEndNodeIndex = term.generateGraph(nfa, activeSubtree.lastNodeIndex, activeSubtree.iterator->second->finalActions);
 
-            PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->value.get();
+            PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->second.get();
             if (!prefixTreeVertex->edges.isEmpty()) {
                 activeStack.append(ActiveNFASubtree(prefixTreeVertex, prefixTreeVertex->edges.begin(), newEndNodeIndex));
                 goto ProcessSubtree;
@@ -175,7 +182,7 @@
 
         // We go depth first into the subtrees with variable prefix. Find the next subtree.
         for (; activeSubtree.iterator != activeSubtree.vertex->edges.end(); ++activeSubtree.iterator) {
-            PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->value.get();
+            PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->second.get();
             if (prefixTreeVertex->inVariableLengthPrefix) {
                 activeStack.append(ActiveSubtree({ prefixTreeVertex, prefixTreeVertex->edges.begin() }));
                 goto ProcessSubtree;
@@ -187,7 +194,7 @@
         bool needToGenerate = activeSubtree.vertex->edges.isEmpty() && !activeSubtree.vertex->finalActions.isEmpty();
         if (!needToGenerate) {
             for (const auto& edge : activeSubtree.vertex->edges) {
-                if (!edge.value->inVariableLengthPrefix) {
+                if (!edge.second->inVariableLengthPrefix) {
                     needToGenerate = true;
                     break;
                 }
@@ -201,15 +208,15 @@
             unsigned prefixEnd = generatingNFA.root();
 
             for (unsigned i = 0; i < activeStack.size() - 1; ++i) {
-                const Term& term = activeStack[i].iterator->key;
-                prefixEnd = term.generateGraph(generatingNFA, prefixEnd, activeStack[i].iterator->value->finalActions);
+                const Term& term = activeStack[i].iterator->first;
+                prefixEnd = term.generateGraph(generatingNFA, prefixEnd, activeStack[i].iterator->second->finalActions);
             }
 
             for (const auto& edge : activeSubtree.vertex->edges) {
-                if (!edge.value->inVariableLengthPrefix) {
-                    const Term& term = edge.key;
-                    unsigned newSubtreeStart = term.generateGraph(generatingNFA, prefixEnd, edge.value->finalActions);
-                    generateNFAForSubtree(generatingNFA, newSubtreeStart, *edge.value);
+                if (!edge.second->inVariableLengthPrefix) {
+                    const Term& term = edge.first;
+                    unsigned newSubtreeStart = term.generateGraph(generatingNFA, prefixEnd, edge.second->finalActions);
+                    generateNFAForSubtree(generatingNFA, newSubtreeStart, *edge.second);
                 }
             }
         }

Modified: trunk/Source/WebCore/contentextensions/NFA.cpp (183498 => 183499)


--- trunk/Source/WebCore/contentextensions/NFA.cpp	2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WebCore/contentextensions/NFA.cpp	2015-04-28 19:40:19 UTC (rev 183499)
@@ -51,6 +51,8 @@
 {
     size_t size = 0;
     for (const NFANode& node : m_nodes) {
+        for (const auto& transition : node.transitions)
+            size += transition.value.capacity() * sizeof(unsigned);
         size += sizeof(node)
             + node.transitions.capacity() * sizeof(std::pair<uint16_t, NFANodeIndexSet>)
             + node.transitionsOnAnyCharacter.capacity() * sizeof(unsigned)
@@ -93,7 +95,7 @@
         transitionSlot.value.remove(to);
 }
 
-void NFA::setActions(unsigned node, const ActionSet& actions)
+void NFA::setActions(unsigned node, const ActionList& actions)
 {
     ASSERT_WITH_MESSAGE(m_nodes[node].finalRuleIds.isEmpty(), "The final state should only be defined once.");
     copyToVector(actions, m_nodes[node].finalRuleIds);

Modified: trunk/Source/WebCore/contentextensions/NFA.h (183498 => 183499)


--- trunk/Source/WebCore/contentextensions/NFA.h	2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WebCore/contentextensions/NFA.h	2015-04-28 19:40:19 UTC (rev 183499)
@@ -38,8 +38,6 @@
 
 class NFAToDFA;
 
-typedef HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> ActionSet;
-
 // The NFA provides a way to build a NFA graph with characters or epsilon as transitions.
 // The nodes are accessed through an identifier.
 class NFA {
@@ -51,13 +49,13 @@
     void addTransition(unsigned from, unsigned to, char character);
     void addEpsilonTransition(unsigned from, unsigned to);
     void addTransitionsOnAnyCharacter(unsigned from, unsigned to);
-    void setActions(unsigned node, const ActionSet& finalActions);
+    void setActions(unsigned node, const ActionList& finalActions);
 
     unsigned graphSize() const;
     void restoreToGraphSize(unsigned);
 
 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
-    void addRuleId(unsigned node, const ActionSet& ruleIds);
+    void addRuleId(unsigned node, const ActionList& ruleIds);
 
     void debugPrintDot() const;
 #else

Modified: trunk/Source/WebCore/contentextensions/NFANode.h (183498 => 183499)


--- trunk/Source/WebCore/contentextensions/NFANode.h	2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WebCore/contentextensions/NFANode.h	2015-04-28 19:40:19 UTC (rev 183499)
@@ -39,6 +39,7 @@
 
 // A NFANode abstract the transition table out of a NFA state.
 
+typedef Vector<uint64_t, 0, WTF::CrashOnOverflow, 1> ActionList;
 typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> NFANodeIndexSet;
 typedef HashMap<uint16_t, NFANodeIndexSet, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>> NFANodeTransitions;
 
@@ -47,7 +48,7 @@
     HashMap<uint16_t, NFANodeIndexSet, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>> transitions;
     NFANodeIndexSet transitionsOnAnyCharacter;
 
-    Vector<uint64_t> finalRuleIds;
+    ActionList finalRuleIds;
 };
 
 }

Modified: trunk/Source/WebCore/contentextensions/Term.h (183498 => 183499)


--- trunk/Source/WebCore/contentextensions/Term.h	2015-04-28 19:38:13 UTC (rev 183498)
+++ trunk/Source/WebCore/contentextensions/Term.h	2015-04-28 19:40:19 UTC (rev 183499)
@@ -83,7 +83,7 @@
 
     void quantify(const AtomQuantifier&);
 
-    unsigned generateGraph(NFA&, unsigned start, const ActionSet& finalActions) const;
+    unsigned generateGraph(NFA&, unsigned start, const ActionList& finalActions) const;
 
     bool isEndOfLineAssertion() const;
 
@@ -335,7 +335,7 @@
     m_quantifier = quantifier;
 }
 
-inline unsigned Term::Term::generateGraph(NFA& nfa, unsigned start, const ActionSet& finalActions) const
+inline unsigned Term::Term::generateGraph(NFA& nfa, unsigned start, const ActionList& finalActions) const
 {
     ASSERT(isValid());
 
@@ -581,7 +581,7 @@
     case TermType::Group: {
         unsigned lastTarget = source;
         for (const Term& term : m_atomData.group.terms)
-            lastTarget = term.generateGraph(nfa, lastTarget, ActionSet());
+            lastTarget = term.generateGraph(nfa, lastTarget, ActionList());
         return lastTarget;
     }
     }

_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes

Reply via email to