<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"

"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">

<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />

<title>[185078] trunk/Source/WebCore</title>

</head>

<body>

<style type="text/css"><!--

#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }

#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }

#msg dt:after { content:':';}

#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt;  }

#msg dl a { font-weight: bold}

#msg dl a:link    { color:#fc3; }

#msg dl a:active  { color:#ff0; }

#msg dl a:visited { color:#cc6; }

h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }

#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }

#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }

#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }

#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }

#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }

#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }

#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }

#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }

#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }

#logmsg pre { background: #eee; padding: 1em; }

#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}

#logmsg dl { margin: 0; }

#logmsg dt { font-weight: bold; }

#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }

#logmsg dd:before { content:'\00bb';}

#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }

#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }

#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }

#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }

#logmsg table th.Corner { text-align: left; }

#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }

#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }

#patch { width: 100%; }

#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}

#patch .propset h4, #patch .binary h4 {margin:0;}

#patch pre {padding:0;line-height:1.2em;margin:0;}

#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}

#patch .propset .diff, #patch .binary .diff  {padding:10px 0;}

#patch span {display:block;padding:0 10px;}

#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}

#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}

#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}

#patch .lines, .info {color:#888;background:#fff;}

--></style>

<div id="msg">

<dl class="meta">

<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/185078">185078</a></dd>

<dt>Author</dt> <dd>achristensen@apple.com</dd>

<dt>Date</dt> <dd>2015-06-01 15:29:37 -0700 (Mon, 01 Jun 2015)</dd>

</dl>

<h3>Log Message</h3>

<pre>[Content Extensions] Reduce DFA memory usage.

https://bugs.webkit.org/show_bug.cgi?id=145526

Reviewed by Benjamin Poulain.

* contentextensions/DFA.cpp:

(WebCore::ContentExtensions::DFA::memoryUsed):

(WebCore::ContentExtensions::DFANode::transitions):

(WebCore::ContentExtensions::DFANode::fallbackTransitionDestination):

(WebCore::ContentExtensions::DFANode::changeFallbackTransition):

(WebCore::ContentExtensions::DFANode::addFallbackTransition):

(WebCore::ContentExtensions::DFANode::containsTransition):

(WebCore::ContentExtensions::DFANode::kill):

* contentextensions/DFA.h:

* contentextensions/DFAMinimizer.cpp:

(WebCore::ContentExtensions::DFAMinimizer::minimize):

* contentextensions/NFAToDFA.cpp:

(WebCore::ContentExtensions::NFAToDFA::convert):

Use separate Vectors for the transition characters and destinations to avoid wasting memory to padding a std::pair.</pre>

<h3>Modified Paths</h3>

<ul>

<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>

<li><a href="#trunkSourceWebCorecontentextensionsDFAcpp">trunk/Source/WebCore/contentextensions/DFA.cpp</a></li>

<li><a href="#trunkSourceWebCorecontentextensionsDFAh">trunk/Source/WebCore/contentextensions/DFA.h</a></li>

<li><a href="#trunkSourceWebCorecontentextensionsDFAMinimizercpp">trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp</a></li>

<li><a href="#trunkSourceWebCorecontentextensionsNFAToDFAcpp">trunk/Source/WebCore/contentextensions/NFAToDFA.cpp</a></li>

</ul>

</div>

<div id="patch">

<h3>Diff</h3>

<a id="trunkSourceWebCoreChangeLog"></a>

<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (185077 => 185078)</h4>

<pre class="diff"><span>

<span class="info">--- trunk/Source/WebCore/ChangeLog        2015-06-01 22:26:20 UTC (rev 185077)

+++ trunk/Source/WebCore/ChangeLog        2015-06-01 22:29:37 UTC (rev 185078)

</span><span class="lines">@@ -1,3 +1,25 @@

</span><ins>+2015-06-01  Alex Christensen  &lt;achristensen@webkit.org&gt;

+

+        [Content Extensions] Reduce DFA memory usage.

+        https://bugs.webkit.org/show_bug.cgi?id=145526

+

+        Reviewed by Benjamin Poulain.

+

+        * contentextensions/DFA.cpp:

+        (WebCore::ContentExtensions::DFA::memoryUsed):

+        (WebCore::ContentExtensions::DFANode::transitions):

+        (WebCore::ContentExtensions::DFANode::fallbackTransitionDestination):

+        (WebCore::ContentExtensions::DFANode::changeFallbackTransition):

+        (WebCore::ContentExtensions::DFANode::addFallbackTransition):

+        (WebCore::ContentExtensions::DFANode::containsTransition):

+        (WebCore::ContentExtensions::DFANode::kill):

+        * contentextensions/DFA.h:

+        * contentextensions/DFAMinimizer.cpp:

+        (WebCore::ContentExtensions::DFAMinimizer::minimize):

+        * contentextensions/NFAToDFA.cpp:

+        (WebCore::ContentExtensions::NFAToDFA::convert):

+        Use separate Vectors for the transition characters and destinations to avoid wasting memory to padding a std::pair.

+

</ins><span class="cx"> 2015-06-01  Matt Rajca  &lt;mrajca@apple.com&gt;

</span><span class="cx"> 

</span><span class="cx">         Implemented the `eventTargetInterface` and `scriptExecutionContext` methods required by EventTarget, as well as

</span></span></pre></div>

<a id="trunkSourceWebCorecontentextensionsDFAcpp"></a>

<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (185077 => 185078)</h4>

<pre class="diff"><span>

<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.cpp        2015-06-01 22:26:20 UTC (rev 185077)

+++ trunk/Source/WebCore/contentextensions/DFA.cpp        2015-06-01 22:29:37 UTC (rev 185078)

</span><span class="lines">@@ -38,9 +38,10 @@

</span><span class="cx"> size_t DFA::memoryUsed() const

</span><span class="cx"> {

</span><span class="cx">     return sizeof(DFA)

</span><del>-        + actions.size() * sizeof(uint64_t)

-        + transitions.size() * sizeof(std::pair&lt;uint8_t, uint32_t&gt;)

-        + nodes.size() * sizeof(DFANode);

</del><ins>+        + actions.capacity() * sizeof(uint64_t)

+        + transitionCharacters.capacity() * sizeof(uint8_t)

+        + transitionDestinations.capacity() * sizeof(uint32_t)

+        + nodes.capacity() * sizeof(DFANode);

</ins><span class="cx"> }

</span><span class="cx"> 

<span class="cx"> // FIXME: Make DFANode.cpp.

</span><span class="lines">@@ -60,7 +61,7 @@

</span><span class="cx">     Vector&lt;std::pair&lt;uint8_t, uint32_t&gt;&gt; vector;

</span><span class="cx">     vector.reserveInitialCapacity(transitionsLength());

</span><span class="cx">     for (uint32_t i = m_transitionsStart; i &lt; m_transitionsStart + m_transitionsLength; ++i)

</span><del>-        vector.uncheckedAppend(dfa.transitions[i]);

</del><ins>+        vector.uncheckedAppend(std::make_pair(dfa.transitionCharacters[i], dfa.transitionDestinations[i]));

</ins><span class="cx">     return vector;

</span><span class="cx"> }

</span><span class="cx"> 

</span><span class="lines">@@ -69,21 +70,24 @@

</span><span class="cx">     RELEASE_ASSERT(hasFallbackTransition());

</span><span class="cx"> 

<span class="cx">     // If there is a fallback transition, it is just after the other transitions and has an invalid ASCII character to mark it as a fallback transition.

</span><del>-    ASSERT(dfa.transitions[m_transitionsStart + m_transitionsLength].first == std::numeric_limits&lt;uint8_t&gt;::max());

-    return dfa.transitions[m_transitionsStart + m_transitionsLength].second;

</del><ins>+    ASSERT(dfa.transitionCharacters[m_transitionsStart + m_transitionsLength] == std::numeric_limits&lt;uint8_t&gt;::max());

+    return dfa.transitionDestinations[m_transitionsStart + m_transitionsLength];

</ins><span class="cx"> }

</span><span class="cx"> 

</span><span class="cx"> void DFANode::changeFallbackTransition(DFA&amp; dfa, uint32_t newDestination)

</span><span class="cx"> {

</span><span class="cx">     RELEASE_ASSERT(hasFallbackTransition());

</span><del>-    ASSERT_WITH_MESSAGE(dfa.transitions[m_transitionsStart + m_transitionsLength].first == std::numeric_limits&lt;uint8_t&gt;::max(), &quot;When changing a fallback transition, the fallback transition should already be marked as such&quot;);

-    dfa.transitions[m_transitionsStart + m_transitionsLength] = std::pair&lt;uint8_t, uint32_t&gt;(std::numeric_limits&lt;uint8_t&gt;::max(), newDestination);

</del><ins>+    ASSERT_WITH_MESSAGE(dfa.transitionCharacters[m_transitionsStart + m_transitionsLength] == std::numeric_limits&lt;uint8_t&gt;::max(), &quot;When changing a fallback transition, the fallback transition should already be marked as such&quot;);

+    dfa.transitionCharacters[m_transitionsStart + m_transitionsLength] = std::numeric_limits&lt;uint8_t&gt;::max();

+    dfa.transitionDestinations[m_transitionsStart + m_transitionsLength] = newDestination;

</ins><span class="cx"> }

</span><span class="cx"> 

</span><span class="cx"> void DFANode::addFallbackTransition(DFA&amp; dfa, uint32_t destination)

</span><span class="cx"> {

</span><del>-    RELEASE_ASSERT_WITH_MESSAGE(dfa.transitions.size() == m_transitionsStart + m_transitionsLength, &quot;Adding a fallback transition should only happen if the node is at the end&quot;);

-    dfa.transitions.append(std::pair&lt;uint8_t, uint32_t&gt;(std::numeric_limits&lt;uint8_t&gt;::max(), destination));

</del><ins>+    RELEASE_ASSERT(dfa.transitionCharacters.size() == dfa.transitionDestinations.size());

+    RELEASE_ASSERT_WITH_MESSAGE(dfa.transitionCharacters.size() == m_transitionsStart + m_transitionsLength, &quot;Adding a fallback transition should only happen if the node is at the end&quot;);

+    dfa.transitionCharacters.append(std::numeric_limits&lt;uint8_t&gt;::max());

+    dfa.transitionDestinations.append(destination);

</ins><span class="cx">     ASSERT(!(m_flags &amp; HasFallbackTransition));

</span><span class="cx">     m_flags |= HasFallbackTransition;

</span><span class="cx"> }

</span><span class="lines">@@ -93,7 +97,7 @@

<span class="cx">     // Called from DFAMinimizer, this loops though a maximum of 128 transitions, so it's not too slow.

</span><span class="cx">     ASSERT(m_transitionsLength &lt;= 128);

</span><span class="cx">     for (unsigned i = m_transitionsStart; i &lt; m_transitionsStart + m_transitionsLength; ++i) {

</span><del>-        if (dfa.transitions[i].first == transition)

</del><ins>+        if (dfa.transitionCharacters[i] == transition)

</ins><span class="cx">             return true;

</span><span class="cx">     }

</span><span class="cx">     return false;

</span><span class="lines">@@ -105,8 +109,10 @@

<span class="cx">     m_flags = IsKilled; // Killed nodes don't have any other flags.

</span><span class="cx">     

<span class="cx">     // Invalidate the now-unused memory in the DFA to make finding bugs easier.

</span><del>-    for (unsigned i = m_transitionsStart; i &lt; m_transitionsStart + m_transitionsLength; ++i)

-        dfa.transitions[i] = std::make_pair(std::numeric_limits&lt;uint8_t&gt;::max(), std::numeric_limits&lt;uint32_t&gt;::max());

</del><ins>+    for (unsigned i = m_transitionsStart; i &lt; m_transitionsStart + m_transitionsLength; ++i) {

+        dfa.transitionCharacters[i] = std::numeric_limits&lt;uint8_t&gt;::max();

+        dfa.transitionDestinations[i] = std::numeric_limits&lt;uint32_t&gt;::max();

+    }

</ins><span class="cx">     for (unsigned i = m_actionsStart; i &lt; m_actionsStart + m_actionsLength; ++i)

</span><span class="cx">         dfa.actions[i] = std::numeric_limits&lt;uint64_t&gt;::max();

</span><span class="cx"> 

</span></span></pre></div>

<a id="trunkSourceWebCorecontentextensionsDFAh"></a>

<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFA.h (185077 => 185078)</h4>

<pre class="diff"><span>

<span class="info">--- trunk/Source/WebCore/contentextensions/DFA.h        2015-06-01 22:26:20 UTC (rev 185077)

+++ trunk/Source/WebCore/contentextensions/DFA.h        2015-06-01 22:29:37 UTC (rev 185078)

</span><span class="lines">@@ -46,8 +46,8 @@

</span><span class="cx"> #endif

</span><span class="cx">     

</span><span class="cx">     Vector&lt;uint64_t&gt; actions;

<del>-    // FIXME: transitions could be two Vectors to save even more memory.

-    Vector&lt;std::pair&lt;uint8_t, uint32_t&gt;&gt; transitions;

</del><ins>+    Vector&lt;uint8_t&gt; transitionCharacters;

+    Vector&lt;uint32_t&gt; transitionDestinations;

</ins><span class="cx">     Vector&lt;DFANode&gt; nodes;

</span><span class="cx">     unsigned root { 0 };

</span><span class="cx"> };

</span></span></pre></div>

<a id="trunkSourceWebCorecontentextensionsDFAMinimizercpp"></a>

<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp (185077 => 185078)</h4>

<pre class="diff"><span>

<span class="info">--- trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp        2015-06-01 22:26:20 UTC (rev 185077)

+++ trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp        2015-06-01 22:29:37 UTC (rev 185078)

</span><span class="lines">@@ -100,14 +100,19 @@

</span><span class="cx">         

</span><span class="cx">             unsigned firstSlot = dfaNode.transitionsStart();

</span><span class="cx">             dfaNode.resetTransitions(firstSlot, transitions.size());

</span><del>-            for (unsigned i = 0; i &lt; transitions.size(); ++i)

-                dfa.transitions[firstSlot + i] = transitions[i];

</del><ins>+            for (unsigned i = 0; i &lt; transitions.size(); ++i) {

+                dfa.transitionCharacters[firstSlot + i] = transitions[i].first;

+                dfa.transitionDestinations[firstSlot + i] = transitions[i].second;

+            }

</ins><span class="cx">             for (unsigned i = transitions.size(); i &lt; availableSlotCount; ++i) {

<span class="cx">                 // Invalidate now-unused memory to make finding bugs easier.

</span><del>-                dfa.transitions[firstSlot + i] = std::make_pair(std::numeric_limits&lt;uint8_t&gt;::max(), std::numeric_limits&lt;uint32_t&gt;::max());

</del><ins>+                dfa.transitionCharacters[firstSlot + i] = std::numeric_limits&lt;uint8_t&gt;::max();

+                dfa.transitionDestinations[firstSlot + i] = std::numeric_limits&lt;uint32_t&gt;::max();

</ins><span class="cx">             }

</span><del>-            if (willHaveFallback)

-                dfa.transitions[firstSlot + transitions.size()] = std::make_pair(std::numeric_limits&lt;uint8_t&gt;::max(), newFallbackDestination);

</del><ins>+            if (willHaveFallback) {

+                dfa.transitionCharacters[firstSlot + transitions.size()] = std::numeric_limits&lt;uint8_t&gt;::max();

+                dfa.transitionDestinations[firstSlot + transitions.size()] = newFallbackDestination;

+            }

</ins><span class="cx">         }

</span><span class="cx">     }

</span><span class="cx"> }

</span><span class="lines">@@ -541,7 +546,7 @@

</span><span class="cx">     for (DFANode&amp; node : dfa.nodes) {

</span><span class="cx">         auto nodeTransitions = node.transitions(dfa);

</span><span class="cx">         for (unsigned i = 0; i &lt; node.transitionsLength(); ++i)

</span><del>-            dfa.transitions[node.transitionsStart() + i].second = relocationVector[nodeTransitions[i].second];

</del><ins>+            dfa.transitionDestinations[node.transitionsStart() + i] = relocationVector[nodeTransitions[i].second];

</ins><span class="cx">         if (node.hasFallbackTransition())

</span><span class="cx">             node.changeFallbackTransition(dfa, relocationVector[node.fallbackTransitionDestination(dfa)]);

</span><span class="cx">     }

</span></span></pre></div>

<a id="trunkSourceWebCorecontentextensionsNFAToDFAcpp"></a>

<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.cpp (185077 => 185078)</h4>

<pre class="diff"><span>

<span class="info">--- trunk/Source/WebCore/contentextensions/NFAToDFA.cpp        2015-06-01 22:26:20 UTC (rev 185077)

+++ trunk/Source/WebCore/contentextensions/NFAToDFA.cpp        2015-06-01 22:29:37 UTC (rev 185078)

</span><span class="lines">@@ -373,7 +373,8 @@

</span><span class="cx">         NodeIdSet setFallbackTransition;

</span><span class="cx">         populateTransitions(transitionsFromClosedSet, setFallbackTransition, *uniqueNodeIdSetImpl, nfaGraph, nfaNodeClosures);

</span><span class="cx"> 

</span><del>-        unsigned transitionsStart = dfa.transitions.size();

</del><ins>+        unsigned transitionsStart = dfa.transitionCharacters.size();

+        ASSERT(dfa.transitionCharacters.size() == dfa.transitionDestinations.size());

</ins><span class="cx">         for (unsigned key = 0; key &lt; transitionsFromClosedSet.size(); ++key) {

</span><span class="cx">             NodeIdSet&amp; targetNodeSet = transitionsFromClosedSet[key];

</span><span class="cx"> 

</span><span class="lines">@@ -382,11 +383,13 @@

</span><span class="cx"> 

</span><span class="cx">             unsigned targetNodeId = getOrCreateDFANode(targetNodeSet, nfaGraph, dfa, uniqueNodeIdSetTable, unprocessedNodes);

</span><span class="cx">             RELEASE_ASSERT(key &lt;= 127);

</span><del>-            dfa.transitions.append(std::make_pair(static_cast&lt;uint8_t&gt;(key), targetNodeId));

</del><ins>+            dfa.transitionCharacters.append(static_cast&lt;uint8_t&gt;(key));

+            dfa.transitionDestinations.append(targetNodeId);

</ins><span class="cx"> 

</span><span class="cx">             targetNodeSet.clear();

</span><span class="cx">         }

</span><del>-        unsigned transitionsEnd = dfa.transitions.size();

</del><ins>+        unsigned transitionsEnd = dfa.transitionCharacters.size();

+        ASSERT(dfa.transitionCharacters.size() == dfa.transitionDestinations.size());

</ins><span class="cx">         unsigned transitionsLength = transitionsEnd - transitionsStart;

</span><span class="cx">         RELEASE_ASSERT(transitionsLength &lt;= 127);

</span><span class="cx">         dfa.nodes[dfaNodeId].setTransitions(transitionsStart, static_cast&lt;uint8_t&gt;(transitionsLength));

</span></span></pre>

</div>

</div>

</body>

</html>