Created attachment 153161 [details] Patch

run-perf-tests html-parser.html * Before kseo@kseo:WebKitLatest (master)> ./Tools/Scripts/run-perf-tests --platform=chromium PerformanceTests/Parser/html-parser.html Running 1 tests Running Parser/html-parser.html (1 of 1) RESULT Parser: html-parser= 2143.35 ms median= 2143.0 ms, stdev= 5.57023338829 ms, min= 2132.0 ms, max= 2152.0 ms * After kseo@kseo:WebKitLatest (master)> ./Tools/Scripts/run-perf-tests --platform=chromium PerformanceTests/Parser/html-parser.html Running 1 tests Running Parser/html-parser.html (1 of 1) RESULT Parser: html-parser= 2197.95 ms median= 2197.0 ms, stdev= 6.65187943366 ms, min= 2186.0 ms, max= 2210.0 ms

Created attachment 153174 [details] Patch

(In reply to comment #3) > Created an attachment (id=153174) [details] > Patch Fixed a typo in the change log.

Comment on attachment 153174 [details] Patch I expect this to be a slowdown of the HTML5 parser benchmark. This is a per-token malloc...

(In reply to comment #5) > (From update of attachment 153174 [details]) > I expect this to be a slowdown of the HTML5 parser benchmark. This is a per-token malloc... That's right. What do you think of the PerfTest result above?

So, a 2.5% slowdown? I'm not sure this bug is worth fixing.

(In reply to comment #7) > So, a 2.5% slowdown? I'm not sure this bug is worth fixing. I worked on this bug because this is a prerequisite for Bug 90751. To proceed parsing speculatively while waiting for the parser blocking script to be loaded and executed, the parser must be able to query the stack of open elements and the active formatting elements without actually creating elements. To do so, the stack of open elements and the active formatting elements must have the original token of each element. Firefox does not have this bug because it stores the original token of each element in the stack of open elements and the active formatting elements. Each entry in these data structures is of type nsHtml5StackNode.

Interesting. Unblocking speculative parsing would be a good reason to fix this bug (assuming speculative parsing is a win).

2.5% slowdown is not a performance regression because this patch actually fixes a bug. Let me ask this in another way. Are we willing make an intentional violation of HTML5 spec if that gives us 2.5% speedup in HTML parser benchmarks and the bug is minor? Of course, I know it depends on how minor the bug is :)

I found another FIXME that mentions about running the parser off the main thread: bool HTMLElementStack::isHTMLIntegrationPoint(ContainerNode* node) { if (!node->isElementNode()) return false; Element* element = static_cast<Element*>(node); if (element->hasTagName(MathMLNames::annotation_xmlTag)) { // FIXME: Technically we shouldn't read back from the DOM here. // Instead, we're supposed to track this information in the element // stack, which lets the parser run on its own thread. String encoding = element->fastGetAttribute(MathMLNames::encodingAttr); return equalIgnoringCase(encoding, "text/html") || equalIgnoringCase(encoding, "application/xhtml+xml"); } return element->hasTagName(SVGNames::foreignObjectTag) || element->hasTagName(SVGNames::descTag) || element->hasTagName(SVGNames::titleTag); } Once we keep tokens in the element stack, we don't need to read back from the DOM tree.

I am working on the next patch which changes HTMLElementStack, HTMLFormattingElementList and HTMLTreeBuilder to perform operations using tokens instead of elements. My work-in-progress patch shows slight performance improvement: kseo@kseo:WebKitLatest (master)> ./Tools/Scripts/run-perf-tests --platform=chromium PerformanceTests/Parser/html-parser.html Running 1 tests Running Parser/html-parser.html (1 of 1) RESULT Parser: html-parser= 2165.55 ms median= 2176.5 ms, stdev= 49.750854264 ms, min= 1950.0 ms, max= 2187.0 ms I will upload the patch and share the test result again once it is done.

(In reply to comment #12) Oops. stddev is quite large here. I don't know why.

> 2.5% slowdown is not a performance regression because this patch actually fixes a bug. That's not an accurate statement. Every slowdown is a performance regression. We can decide whether the benefits of the patch outweigh the performance costs, but the performance costs are real. > Let me ask this in another way. Are we willing make an intentional violation of HTML5 spec if that gives us 2.5% speedup in HTML parser benchmarks and the bug is minor? Yes. > Of course, I know it depends on how minor the bug is :) Correct. If everyone in the world will live a happy life and never encounter the bug, then they will live (slightly) happier lives with a parser that's 2.5% faster.

(In reply to comment #14) > That's not an accurate statement. Every slowdown is a performance regression. We can decide whether the benefits of the patch outweigh the performance costs, but the performance costs are real. Okay. I agree! It seems I have a few options: 1) Reduce the performance costs of this patch. e.g., try to avoid per token malloc or bring up an efficient way to do per token malloc 2) Explain more about the potential benefits of this patch. e.g., show the real performance benefits of speculative HTML parsing (or off the main thread parsing) that is possible thanks to this change. 3) Show the real harms caused by the bug. e.g., browser compatibility. At least Gecko does not have this bug. I am currently working on 2), but I will see if I can do 1). Maybe someone can comment more on 3).

Created attachment 153375 [details] Patch

(In reply to comment #16) > Created an attachment (id=153375) [details] > Patch Avoid allocating a HTMLStackNode in HTMLConstructionSite::insertFormattingElement. Minor performance improvement. No observable change in HTML5 parser benchmark. diff --git a/Source/WebCore/html/parser/HTMLConstructionSite.cpp b/Source/WebCore/html/parser/HTMLConstructionSite.cpp index 4fc498a..6727e9c 100644 --- a/Source/WebCore/html/parser/HTMLConstructionSite.cpp +++ b/Source/WebCore/html/parser/HTMLConstructionSite.cpp @@ -331,7 +331,7 @@ void HTMLConstructionSite::insertFormattingElement(AtomicHTMLToken& token) // Possible active formatting elements include: // a, b, big, code, em, font, i, nobr, s, small, strike, strong, tt, and u. insertHTMLElement(token); - m_activeFormattingElements.append(HTMLStackNode::create(currentElement(), token)); + m_activeFormattingElements.append(currentElementRecord()->stackNode()); } void HTMLConstructionSite::insertScriptElement(AtomicHTMLToken& token) diff --git a/Source/WebCore/html/parser/HTMLConstructionSite.h b/Source/WebCore/html/parser/HTMLConstructionSite.h index aafefdf..06d5165 100644 --- a/Source/WebCore/html/parser/HTMLConstructionSite.h +++ b/Source/WebCore/html/parser/HTMLConstructionSite.h @@ -118,6 +118,7 @@ public: void generateImpliedEndTagsWithExclusion(const AtomicString& tagName); bool isEmpty() const { return !m_openElements.stackDepth(); } + HTMLElementStack::ElementRecord* currentElementRecord() const { return m_openElements.topRecord(); } Element* currentElement() const { return m_openElements.top(); } ContainerNode* currentNode() const { return m_openElements.topNode(); } Element* oneBelowTop() const { return m_openElements.oneBelowTop(); }

Please forget the previous reported perf tests. I've just found that perf tests vary so much from one test run to another on my machine (Ubuntu, Intel Xeon 6-core). So I ran perf tests again on my MacBook pro. perf tests results are quite stable on MacBook. Before kseo@cat:WebKit (master)> ./Tools/Scripts/run-perf-tests Parser/html-parser.html Running 1 tests Running Parser/html-parser.html (1 of 1) RESULT Parser: html-parser= 2725.5 ms median= 2727.0 ms, stdev= 9.3139680051 ms, min= 2713.0 ms, max= 2740.0 ms After kseo@cat:WebKit (master)> ./Tools/Scripts/run-perf-tests Parser/html-parser.html Running 1 tests Running Parser/html-parser.html (1 of 1) RESULT Parser: html-parser= 2769.0 ms median= 2772.5 ms, stdev= 9.66436754268 ms, min= 2755.0 ms, max= 2783.0 ms So it's a 1.6% slowdown.

Created attachment 153450 [details] Patch

I avoided copying tokens by ref counting AtomicHTMLToken. Now it's a 0.5-0.6% slowdown! * Before kseo@cat:WebKit (master)> ./Tools/Scripts/run-perf-tests Parser/html-parser.html Running 1 tests Running Parser/html-parser.html (1 of 1) RESULT Parser: html-parser= 2725.5 ms median= 2727.0 ms, stdev= 9.3139680051 ms, min= 2713.0 ms, max= 2740.0 ms * After kseo@cat:WebKit (master)> ./Tools/Scripts/run-perf-tests Parser/html-parser.html Running 1 tests Running Parser/html-parser.html (1 of 1) RESULT Parser: html-parser= 2740.7 ms median= 2740.5 ms, stdev= 4.16052881254 ms, min= 2734.0 ms, max= 2749.0 ms

> Now it's a 0.5-0.6% slowdown! Awesome. We usually don't worry about slowdowns in that range. The benchmark is precise enough to measure them, but things bounce around +/- 1% based on cache lines and silly things like that. Thanks for iterating on the patch!

There is another FIXME comment in HTMLFormattingElementList::ensureNoahsArkCondition(Element*). // FIXME: Technically we shouldn't read this information back from // the DOM. Instead, the parser should keep a copy of the information. // This isn't really much of a problem for our implementation because // we run the parser on the main thread, but the spec is written so // that implementations can run off the main thread. If JavaScript // changes the attributes values, we could get a slightly wrong // output here. if (candidate->fastGetAttribute(attribute->name()) == attribute->value()) remainingCandidates.append(candidate); I will fix this after this patch is landed.

Created attachment 153658 [details] Patch

(In reply to comment #23) > Created an attachment (id=153658) [details] > Patch Rebased to the latest revision because the previous patch conflicts with r123289: <http://trac.webkit.org/changeset/123289>.

Comment on attachment 153658 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=153658&action=review This patch is so large! Can we break it up into some smaller steps? For example, one step might be to make the token refcounted and change all the method types. That's a large part of this change but it's all mechanical. Then we can look at the behavior changing part of the patch in more detail. I've left a few minor comments below. Thanks for working on this patch. I think we just need to work on landing this carefully now. > Source/WebCore/html/parser/HTMLConstructionSite.h:109 > + PassRefPtr<HTMLStackNode> createElementFromSavedToken(PassRefPtr<HTMLStackNode>); PassRefPtr<HTMLStackNode> -> HTMLStackNode* There no transfer of ownership here and so no need to use PassRefPtr. > Source/WebCore/html/parser/HTMLElementStack.cpp:330 > -void HTMLElementStack::pushHTMLHeadElement(PassRefPtr<Element> element) > +void HTMLElementStack::pushHTMLHeadElement(PassRefPtr<HTMLStackNode> node) I might have picked a different name than |node| for these variables since node means something in the context of the DOM. It's confusing to have elements and nodes with the nodes not actually being DOM nodes... Perhaps |item| ? > Source/WebCore/html/parser/HTMLElementStack.h:60 > + ContainerNode* node() const { return m_node->node(); } m_node->node is another indication that this name isn't optimum. > Source/WebCore/html/parser/HTMLStackNode.h:47 > + RefPtr<AtomicHTMLToken> fakeToken = AtomicHTMLToken::create(HTMLTokenTypes::StartTag, ""); > + return adoptRef(new HTMLStackNode(node, fakeToken.get())); This is strange. What does it mean to have an AtomicHTMLToken with an empty tag name... I wonder if there's a better way to represent this state. Also, presumably fakeToken.release(). > Source/WebCore/html/parser/HTMLStackNode.h:69 > + HTMLStackNode(PassRefPtr<ContainerNode> node, AtomicHTMLToken* token, const AtomicString& namespaceURI = HTMLNames::xhtmlNamespaceURI) AtomicHTMLToken -> PassRefPtr<AtomicHTMLToken> because we're taking a reference. > Source/WebCore/html/parser/HTMLStackNode.h:76 > + HTMLStackNode(Element* element, AtomicHTMLToken* token, const AtomicString& namespaceURI = HTMLNames::xhtmlNamespaceURI) ditto

Comment on attachment 153658 [details] Patch r- for size. Let's land this change in smaller pieces.

(In reply to comment #26) > (From update of attachment 153658 [details]) > r- for size. Let's land this change in smaller pieces. Thanks for your review! I will split the patch into smaller pieces.

Created attachment 153780 [details] Patch

(In reply to comment #25) > This patch is so large! Can we break it up into some smaller steps? I split the patch into two pieces. Bug 91981 makes the token ref-counted and changes all the method types. > > Source/WebCore/html/parser/HTMLConstructionSite.h:109 > > + PassRefPtr<HTMLStackNode> createElementFromSavedToken(PassRefPtr<HTMLStackNode>); > > PassRefPtr<HTMLStackNode> -> HTMLStackNode* > > There no transfer of ownership here and so no need to use PassRefPtr. Done. > > Source/WebCore/html/parser/HTMLElementStack.cpp:330 > > -void HTMLElementStack::pushHTMLHeadElement(PassRefPtr<Element> element) > > +void HTMLElementStack::pushHTMLHeadElement(PassRefPtr<HTMLStackNode> node) > > I might have picked a different name than |node| for these variables since node means something in the context of the DOM. It's confusing to have elements and nodes with the nodes not actually being DOM nodes... Perhaps |item| ? Okay. I renamed HTMLStackNode to HTMLStackItem and used |item| for these variables. > > Source/WebCore/html/parser/HTMLElementStack.h:60 > > + ContainerNode* node() const { return m_node->node(); } > > m_node->node is another indication that this name isn't optimum. Now it's m_item->node. > > Source/WebCore/html/parser/HTMLStackNode.h:47 > > + RefPtr<AtomicHTMLToken> fakeToken = AtomicHTMLToken::create(HTMLTokenTypes::StartTag, ""); > > + return adoptRef(new HTMLStackNode(node, fakeToken.get())); > > This is strange. What does it mean to have an AtomicHTMLToken with an empty tag name... I wonder if there's a better way to represent this state. I created another HTMLStackItem constructor for this. m_isDocumentFragmentNode is used to mark this. Currently, there is no use of this member, but it will be used in the following patches. > Also, presumably fakeToken.release(). No fakeToken anymore. > > Source/WebCore/html/parser/HTMLStackNode.h:69 > > + HTMLStackNode(PassRefPtr<ContainerNode> node, AtomicHTMLToken* token, const AtomicString& namespaceURI = HTMLNames::xhtmlNamespaceURI) > > AtomicHTMLToken -> PassRefPtr<AtomicHTMLToken> because we're taking a reference. Done. > > Source/WebCore/html/parser/HTMLStackNode.h:76 > > + HTMLStackNode(Element* element, AtomicHTMLToken* token, const AtomicString& namespaceURI = HTMLNames::xhtmlNamespaceURI) > > ditto Done.

Created attachment 153783 [details] Patch

(In reply to comment #30) > Created an attachment (id=153783) [details] > Patch Change HTMLStackNode to HTMLStackItem in the change log.

Comment on attachment 153783 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=153783&action=review Thanks. This is so much easier to read. A couple minor points below, but this looks great. > Source/WebCore/html/parser/HTMLFormattingElementList.cpp:92 > + RefPtr<HTMLStackItem> newItem = prpNewItem; Ideally we would call newItem.release() at some point in this function to save a ref()/deref() pair. Can we call release on line 103? > Source/WebCore/html/parser/HTMLFormattingElementList.h:76 > - bool operator==(Element* element) const { return m_element == element; } > - bool operator!=(Element* element) const { return m_element != element; } > + bool operator==(Element* element) const { return !m_item ? !element : m_item->element() == element; } > + bool operator!=(Element* element) const { return !m_item ? !!element : m_item->element() != element; } This looks slightly complicated, but it seems to make sense. > Source/WebCore/html/parser/HTMLFormattingElementList.h:115 > - void swapTo(Element* oldElement, Element* newElement, const Bookmark&); > + void swapTo(Element* oldElement, PassRefPtr<HTMLStackItem> prpNewItem, const Bookmark&); Normally we skip the "prp" prefix in the header. It's useful in the implementation because the PassRefPtr variables can become null easily. > Source/WebCore/html/parser/HTMLStackItem.h:50 > + static PassRefPtr<HTMLStackItem> create(PassRefPtr<ContainerNode> node, AtomicHTMLToken* token, const AtomicString& namespaceURI = HTMLNames::xhtmlNamespaceURI) This should be PassRefPtr<AtomicHTMLToken> because we're going to end up taking a reference to token. The point of using PassRefPtr in these cases is so that our caller can donate a reference (using release()) if they don't need their reference anymore. That saves us a ref()/deref() pair. > Source/WebCore/html/parser/HTMLStackItem.h:56 > + static PassRefPtr<HTMLStackItem> create(Element* element, AtomicHTMLToken* token, const AtomicString& namespaceURI = HTMLNames::xhtmlNamespaceURI) |element| and |AtomicHTMLToken| should use PassRefPtr. > Source/WebCore/html/parser/HTMLStackItem.h:61 > + Element* element() const { return toElement(m_node.get()); } Does toElement have any cost? It it just an ASSERT plus a static_cast?

(In reply to comment #32) > > Source/WebCore/html/parser/HTMLFormattingElementList.cpp:92 > > + RefPtr<HTMLStackItem> newItem = prpNewItem; > > Ideally we would call newItem.release() at some point in this function to save a ref()/deref() pair. Can we call release on line 103? Ideally, we won't need |newItem| because prpNewItem is simply passed to either replaceElement or insert. (but never both.) 96 if (!bookmark.hasBeenMoved()) { 97 ASSERT(bookmark.mark()->element() == oldElement); 98 bookmark.mark()->replaceElement(newItem); // <- here 99 return; 100 } 101 size_t index = bookmark.mark() - first(); 102 ASSERT(index < size()); 103 m_entries.insert(index + 1, newItem); <- or here 104 remove(oldElement); > > Source/WebCore/html/parser/HTMLStackItem.h:61 > > + Element* element() const { return toElement(m_node.get()); } > > Does toElement have any cost? It it just an ASSERT plus a static_cast? It is just an ASSERT plus a static_cast. inline Element* toElement(Node* node) { ASSERT(!node || node->isElementNode()); return static_cast<Element*>(node); }

(In reply to comment #32) > > Source/WebCore/html/parser/HTMLStackItem.h:56 > > + static PassRefPtr<HTMLStackItem> create(Element* element, AtomicHTMLToken* token, const AtomicString& namespaceURI = HTMLNames::xhtmlNamespaceURI) > > |element| and |AtomicHTMLToken| should use PassRefPtr. Okay. I tried to follow the existing code, but if that's case we can remove this constructor entirely because we can use the constructor which takes PassRefPtr<ContainerNode> instead.

(In reply to comment #34) > (In reply to comment #32) > > > Source/WebCore/html/parser/HTMLStackItem.h:56 > > > + static PassRefPtr<HTMLStackItem> create(Element* element, AtomicHTMLToken* token, const AtomicString& namespaceURI = HTMLNames::xhtmlNamespaceURI) > > > > |element| and |AtomicHTMLToken| should use PassRefPtr. > > Okay. I tried to follow the existing code, but if that's case we can remove this constructor entirely because we can use the constructor which takes PassRefPtr<ContainerNode> instead. Sounds good.

(In reply to comment #35) > > Okay. I tried to follow the existing code, but if that's case we can remove this constructor entirely because we can use the constructor which takes PassRefPtr<ContainerNode> instead. > > Sounds good. Thanks. I will land the patch after reflecting your comments. I really appreciate your kind review!

Committed r123399: <http://trac.webkit.org/changeset/123399>