<!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>[199583] 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/199583">199583</a></dd>
<dt>Author</dt> <dd>antti@apple.com</dd>
<dt>Date</dt> <dd>2016-04-15 00:54:20 -0700 (Fri, 15 Apr 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>AffectsNextSibling style relation marking is inefficient
https://bugs.webkit.org/show_bug.cgi?id=156593
Reviewed by Benjamin Poulain.
We currently add a Style::Relation entry for each sibling to mark. With long sibling lists this can be inefficient
in terms of both memory and speed. Instead make a single entry that includes the sibling count to mark.
* css/SelectorChecker.cpp:
(WebCore::addStyleRelation):
When adding AffectsNextSibling entry check if the last entry in the style relation vector has the
same type and is part of the same sibling chain. If so just update the existing entry.
* cssjit/SelectorCompiler.cpp:
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateAddStyleRelation):
The same thing in hand-crafted macro assembler.
* cssjit/SelectorCompiler.h:
Stop lying about the constness of the CheckingContext.
* style/StyleRelations.cpp:
(WebCore::Style::commitRelations):
Mark as many sibling elements as the value indicates.
* style/StyleRelations.h:
(WebCore::Style::Relation::Relation):
Make element a pointer so we can udpate it.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCorecssSelectorCheckercpp">trunk/Source/WebCore/css/SelectorChecker.cpp</a></li>
<li><a href="#trunkSourceWebCorecssjitSelectorCompilercpp">trunk/Source/WebCore/cssjit/SelectorCompiler.cpp</a></li>
<li><a href="#trunkSourceWebCorecssjitSelectorCompilerh">trunk/Source/WebCore/cssjit/SelectorCompiler.h</a></li>
<li><a href="#trunkSourceWebCorestyleStyleRelationscpp">trunk/Source/WebCore/style/StyleRelations.cpp</a></li>
<li><a href="#trunkSourceWebCorestyleStyleRelationsh">trunk/Source/WebCore/style/StyleRelations.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (199582 => 199583)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2016-04-15 07:26:40 UTC (rev 199582)
+++ trunk/Source/WebCore/ChangeLog 2016-04-15 07:54:20 UTC (rev 199583)
</span><span class="lines">@@ -1,3 +1,38 @@
</span><ins>+2016-04-14 Antti Koivisto <antti@apple.com>
+
+ AffectsNextSibling style relation marking is inefficient
+ https://bugs.webkit.org/show_bug.cgi?id=156593
+
+ Reviewed by Benjamin Poulain.
+
+ We currently add a Style::Relation entry for each sibling to mark. With long sibling lists this can be inefficient
+ in terms of both memory and speed. Instead make a single entry that includes the sibling count to mark.
+
+ * css/SelectorChecker.cpp:
+ (WebCore::addStyleRelation):
+
+ When adding AffectsNextSibling entry check if the last entry in the style relation vector has the
+ same type and is part of the same sibling chain. If so just update the existing entry.
+
+ * cssjit/SelectorCompiler.cpp:
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateAddStyleRelation):
+
+ The same thing in hand-crafted macro assembler.
+
+ * cssjit/SelectorCompiler.h:
+
+ Stop lying about the constness of the CheckingContext.
+
+ * style/StyleRelations.cpp:
+ (WebCore::Style::commitRelations):
+
+ Mark as many sibling elements as the value indicates.
+
+ * style/StyleRelations.h:
+ (WebCore::Style::Relation::Relation):
+
+ Make element a pointer so we can udpate it.
+
</ins><span class="cx"> 2016-04-15 Brady Eidson <beidson@apple.com>
</span><span class="cx">
</span><span class="cx"> Add the message property to DOMError.
</span></span></pre></div>
<a id="trunkSourceWebCorecssSelectorCheckercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/css/SelectorChecker.cpp (199582 => 199583)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/css/SelectorChecker.cpp 2016-04-15 07:26:40 UTC (rev 199582)
+++ trunk/Source/WebCore/css/SelectorChecker.cpp 2016-04-15 07:54:20 UTC (rev 199583)
</span><span class="lines">@@ -89,6 +89,14 @@
</span><span class="cx"> ASSERT(value == 1 || type == Style::Relation::NthChildIndex || type == Style::Relation::AffectedByEmpty);
</span><span class="cx"> if (checkingContext.resolvingMode != SelectorChecker::Mode::ResolvingStyle)
</span><span class="cx"> return;
</span><ins>+ if (type == Style::Relation::AffectsNextSibling && !checkingContext.styleRelations.isEmpty()) {
+ auto& last = checkingContext.styleRelations.last();
+ if (last.type == Style::Relation::AffectsNextSibling && last.element == element.nextElementSibling()) {
+ ++last.value;
+ last.element = &element;
+ return;
+ }
+ }
</ins><span class="cx"> checkingContext.styleRelations.append({ element, type, value });
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecssjitSelectorCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/cssjit/SelectorCompiler.cpp (199582 => 199583)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/cssjit/SelectorCompiler.cpp 2016-04-15 07:26:40 UTC (rev 199582)
+++ trunk/Source/WebCore/cssjit/SelectorCompiler.cpp 2016-04-15 07:54:20 UTC (rev 199583)
</span><span class="lines">@@ -2198,16 +2198,56 @@
</span><span class="cx"> {
</span><span class="cx"> ASSERT(m_selectorContext != SelectorContext::QuerySelector);
</span><span class="cx">
</span><ins>+ Assembler::Address vectorAddress(checkingContext, OBJECT_OFFSETOF(SelectorChecker::CheckingContext, styleRelations));
+ auto dataAddress = vectorAddress.withOffset(Style::Relations::dataMemoryOffset());
+ auto sizeAddress = vectorAddress.withOffset(Style::Relations::sizeMemoryOffset());
+
+ // For AffectsNextSibling we just increment the count if the previous added relation was in the same sibling chain.
+ Assembler::JumpList mergeSuccess;
+ if (relationType == Style::Relation::AffectsNextSibling) {
+ Assembler::JumpList mergeFailure;
+
+ LocalRegister lastRelation(m_registerAllocator);
+ m_assembler.load32(sizeAddress, lastRelation);
+
+ // if (!checkingContext.styleRelations.isEmpty())
+ mergeFailure.append(m_assembler.branchTest32(Assembler::Zero, lastRelation));
+
+ // Style::Relation& lastRelation = checkingContext.styleRelations.last();
+ m_assembler.sub32(Assembler::TrustedImm32(1), lastRelation);
+ m_assembler.mul32(Assembler::TrustedImm32(sizeof(Style::Relation)), lastRelation, lastRelation);
+ m_assembler.addPtr(dataAddress, lastRelation);
+
+ // if (lastRelation.type == Style::Relation::AffectsNextSibling)
+ Assembler::Address typeAddress(lastRelation, OBJECT_OFFSETOF(Style::Relation, type));
+ mergeFailure.append(m_assembler.branch32(Assembler::NotEqual, typeAddress, Assembler::TrustedImm32(Style::Relation::AffectsNextSibling)));
+
+ Assembler::Address elementAddress(lastRelation, OBJECT_OFFSETOF(Style::Relation, element));
+ {
+ // if (element.nextSiblingElement() == lastRelation.element)
+ LocalRegister nextSiblingElement(m_registerAllocator);
+ m_assembler.move(element, nextSiblingElement);
+ generateWalkToNextAdjacentElement(mergeFailure, nextSiblingElement);
+ mergeFailure.append(m_assembler.branchPtr(Assembler::NotEqual, nextSiblingElement, elementAddress));
+ }
+
+ // ++lastRelation.value;
+ Assembler::Address valueAddress(lastRelation, OBJECT_OFFSETOF(Style::Relation, value));
+ m_assembler.add32(Assembler::TrustedImm32(1), valueAddress);
+
+ // lastRelation.element = &element;
+ m_assembler.storePtr(element, elementAddress);
+
+ mergeSuccess.append(m_assembler.jump());
+ mergeFailure.link(&m_assembler);
+ }
+
</ins><span class="cx"> // FIXME: Append to vector without a function call at least when there is sufficient capacity.
</span><span class="cx"> FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
</span><span class="cx"> functionCall.setFunctionAddress(addStyleRelationFunction);
</span><span class="cx"> functionCall.setTwoArguments(checkingContext, element);
</span><span class="cx"> functionCall.call();
</span><span class="cx">
</span><del>- Assembler::Address vectorAddress(checkingContext, OBJECT_OFFSETOF(SelectorChecker::CheckingContext, styleRelations));
- auto dataAddress = vectorAddress.withOffset(Style::Relations::dataMemoryOffset());
- auto sizeAddress = vectorAddress.withOffset(Style::Relations::sizeMemoryOffset());
-
</del><span class="cx"> LocalRegister relationPointer(m_registerAllocator);
</span><span class="cx"> m_assembler.load32(sizeAddress, relationPointer);
</span><span class="cx"> m_assembler.sub32(Assembler::TrustedImm32(1), relationPointer);
</span><span class="lines">@@ -2221,6 +2261,8 @@
</span><span class="cx"> Assembler::Address valueAddress(relationPointer, OBJECT_OFFSETOF(Style::Relation, value));
</span><span class="cx"> m_assembler.store32(*value, valueAddress);
</span><span class="cx"> }
</span><ins>+
+ mergeSuccess.link(&m_assembler);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> Assembler::JumpList SelectorCodeGenerator::jumpIfNoPreviousAdjacentElement()
</span></span></pre></div>
<a id="trunkSourceWebCorecssjitSelectorCompilerh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/cssjit/SelectorCompiler.h (199582 => 199583)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/cssjit/SelectorCompiler.h 2016-04-15 07:26:40 UTC (rev 199582)
+++ trunk/Source/WebCore/cssjit/SelectorCompiler.h 2016-04-15 07:54:20 UTC (rev 199583)
</span><span class="lines">@@ -80,7 +80,7 @@
</span><span class="cx"> typedef unsigned (*RuleCollectorSimpleSelectorChecker)(const Element*, unsigned*);
</span><span class="cx"> typedef unsigned (*QuerySelectorSimpleSelectorChecker)(const Element*);
</span><span class="cx">
</span><del>-typedef unsigned (*RuleCollectorSelectorCheckerWithCheckingContext)(const Element*, const SelectorChecker::CheckingContext*, unsigned*);
</del><ins>+typedef unsigned (*RuleCollectorSelectorCheckerWithCheckingContext)(const Element*, SelectorChecker::CheckingContext*, unsigned*);
</ins><span class="cx"> typedef unsigned (*QuerySelectorSelectorCheckerWithCheckingContext)(const Element*, const SelectorChecker::CheckingContext*);
</span><span class="cx">
</span><span class="cx"> SelectorCompilationStatus compileSelector(const CSSSelector*, JSC::VM*, SelectorContext, JSC::MacroAssemblerCodeRef& outputCodeRef);
</span></span></pre></div>
<a id="trunkSourceWebCorestyleStyleRelationscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/style/StyleRelations.cpp (199582 => 199583)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/style/StyleRelations.cpp 2016-04-15 07:26:40 UTC (rev 199582)
+++ trunk/Source/WebCore/style/StyleRelations.cpp 2016-04-15 07:54:20 UTC (rev 199583)
</span><span class="lines">@@ -45,7 +45,7 @@
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> for (auto& relation : relations) {
</span><del>- if (&relation.element != &element) {
</del><ins>+ if (relation.element != &element) {
</ins><span class="cx"> appendStyleRelation(relation);
</span><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="lines">@@ -91,7 +91,7 @@
</span><span class="cx"> if (!relations)
</span><span class="cx"> return;
</span><span class="cx"> for (auto& relation : *relations) {
</span><del>- auto& element = const_cast<Element&>(relation.element);
</del><ins>+ auto& element = const_cast<Element&>(*relation.element);
</ins><span class="cx"> switch (relation.type) {
</span><span class="cx"> case Relation::AffectedByActive:
</span><span class="cx"> element.setChildrenAffectedByActive();
</span><span class="lines">@@ -108,9 +108,12 @@
</span><span class="cx"> case Relation::AffectedByPreviousSibling:
</span><span class="cx"> element.setStyleIsAffectedByPreviousSibling();
</span><span class="cx"> break;
</span><del>- case Relation::AffectsNextSibling:
- element.setAffectsNextSiblingElementStyle();
</del><ins>+ case Relation::AffectsNextSibling: {
+ auto* sibling = &element;
+ for (unsigned i = 0; i < relation.value && sibling; ++i, sibling = sibling->nextElementSibling())
+ sibling->setAffectsNextSiblingElementStyle();
</ins><span class="cx"> break;
</span><ins>+ }
</ins><span class="cx"> case Relation::ChildrenAffectedByBackwardPositionalRules:
</span><span class="cx"> element.setChildrenAffectedByBackwardPositionalRules();
</span><span class="cx"> break;
</span></span></pre></div>
<a id="trunkSourceWebCorestyleStyleRelationsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/style/StyleRelations.h (199582 => 199583)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/style/StyleRelations.h 2016-04-15 07:26:40 UTC (rev 199582)
+++ trunk/Source/WebCore/style/StyleRelations.h 2016-04-15 07:54:20 UTC (rev 199583)
</span><span class="lines">@@ -44,6 +44,7 @@
</span><span class="cx"> AffectedByEmpty,
</span><span class="cx"> AffectedByHover,
</span><span class="cx"> AffectedByPreviousSibling,
</span><ins>+ // For AffectsNextSibling 'value' tells how many element siblings to mark starting with 'element'.
</ins><span class="cx"> AffectsNextSibling,
</span><span class="cx"> ChildrenAffectedByBackwardPositionalRules,
</span><span class="cx"> ChildrenAffectedByFirstChildRules,
</span><span class="lines">@@ -54,12 +55,12 @@
</span><span class="cx"> NthChildIndex,
</span><span class="cx"> Unique,
</span><span class="cx"> };
</span><del>- const Element& element;
</del><ins>+ const Element* element;
</ins><span class="cx"> Type type;
</span><span class="cx"> unsigned value;
</span><span class="cx">
</span><span class="cx"> Relation(const Element& element, Type type, unsigned value = 1)
</span><del>- : element(element)
</del><ins>+ : element(&element)
</ins><span class="cx"> , type(type)
</span><span class="cx"> , value(value)
</span><span class="cx"> { }
</span></span></pre>
</div>
</div>
</body>
</html>