Changeset 201520 in webkit

Timestamp:

May 31, 2016, 12:45:10 PM (10 years ago)

Author:

sbarati@apple.com

Message:

Web Inspector: capturing with Allocations timeline causes GC to take 100x longer and cause frame drops
​https://bugs.webkit.org/show_bug.cgi?id=158054
<rdar://problem/25280762>

Reviewed by Joseph Pecoraro.

HeapSnapshot::sweepCell was taking a long time on
​http://bl.ocks.org/syntagmatic/6c149c08fc9cde682635
because it has to do a binary search to find if
an item is or is not in the list. 90% of the binary searches
would not find anything. This resulted in a lot of wasted time.

This patch adds a TinyBloomFilter member variable to HeapSnapshot.
We use this filter to try to bypass doing a binary search when the
filter tells us that a particular JSCell is definitely not in our
list. This is a 2x speedup on the steady state GC of the above
website.

• heap/HeapSnapshot.cpp:

(JSC::HeapSnapshot::appendNode):
(JSC::HeapSnapshot::sweepCell):
(JSC::HeapSnapshot::shrinkToFit):
(JSC::HeapSnapshot::nodeForCell):

• heap/HeapSnapshot.h:

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• heap/HeapSnapshot.cpp (modified) (4 diffs)
• heap/HeapSnapshot.h (modified) (2 diffs)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2016-05-31  Saam Barati  <sbarati@apple.com>
+
+        Web Inspector: capturing with Allocations timeline causes GC to take 100x longer and cause frame drops
+        https://bugs.webkit.org/show_bug.cgi?id=158054
+        <rdar://problem/25280762>
+
+        Reviewed by Joseph Pecoraro.
+
+        HeapSnapshot::sweepCell was taking a long time on 
+        http://bl.ocks.org/syntagmatic/6c149c08fc9cde682635
+        because it has to do a binary search to find if
+        an item is or is not in the list. 90% of the binary searches
+        would not find anything. This resulted in a lot of wasted time.
+
+        This patch adds a TinyBloomFilter member variable to HeapSnapshot.
+        We use this filter to try to bypass doing a binary search when the
+        filter tells us that a particular JSCell is definitely not in our
+        list. This is a 2x speedup on the steady state GC of the above
+        website.
+
+        * heap/HeapSnapshot.cpp:
+        (JSC::HeapSnapshot::appendNode):
+        (JSC::HeapSnapshot::sweepCell):
+        (JSC::HeapSnapshot::shrinkToFit):
+        (JSC::HeapSnapshot::nodeForCell):
+        * heap/HeapSnapshot.h:
+
 2016-05-29  Saam barati  <sbarati@apple.com>
 

trunk/Source/JavaScriptCore/heap/HeapSnapshot.cpp

@@ -46 +46 @@
 
     m_nodes.append(node);
+    m_filter.add(bitwise_cast<uintptr_t>(node.cell));
 }
 
@@ -52 +53 @@
     ASSERT(cell);
 
-    if (m_finalized && !isEmpty()) {
+    if (m_finalized && !m_filter.ruleOut(bitwise_cast<uintptr_t>(cell))) {
+        ASSERT_WITH_MESSAGE(!isEmpty(), "Our filter should have ruled us out if we are empty.");
         unsigned start = 0;
         unsigned end = m_nodes.size();
@@ -80 +82 @@
 {
     if (m_finalized && m_hasCellsToSweep) {
+        m_filter.reset();
         m_nodes.removeAllMatching(
             [&] (const HeapSnapshotNode& node) -> bool {
-                return reinterpret_cast<intptr_t>(node.cell) & CellToSweepTag;
+                bool willRemoveCell = bitwise_cast<intptr_t>(node.cell) & CellToSweepTag;
+                if (!willRemoveCell)
+                    m_filter.add(bitwise_cast<uintptr_t>(node.cell));
+                return willRemoveCell;
             });
         m_nodes.shrinkToFit();
@@ -127 +133 @@
     ASSERT(m_finalized);
 
-    if (!isEmpty()) {
+    if (!m_filter.ruleOut(bitwise_cast<uintptr_t>(cell))) {
+        ASSERT_WITH_MESSAGE(!isEmpty(), "Our filter should have ruled us out if we are empty.");
         unsigned start = 0;
         unsigned end = m_nodes.size();

trunk/Source/JavaScriptCore/heap/HeapSnapshot.h

@@ -28 +28 @@
 
 #include "HeapSnapshotBuilder.h"
+#include "TinyBloomFilter.h"
 #include <wtf/Optional.h>
 
@@ -54 +55 @@
 
     Vector<HeapSnapshotNode> m_nodes;
+    TinyBloomFilter m_filter;
     HeapSnapshot* m_previous { nullptr };
     unsigned m_firstObjectIdentifier { 0 };