Implement partial synchronous distribution algorithm for Shadow DOM v0 and v1 |
|||
Issue descriptionShadow DOM's distribution algorithm needs a huge rewrite because: - We have to support slotchange events for Shadow DOM v1, which require synchronous distribution calculation in each DOM mutation - Blink has to continue to support Shadow DOM v0, where distribution is calculated asynchronously I might write a design document later, explaining how to achieve *both* efficiently with minimum scarification of the performance. Note that this can not be done with zero-overhead. The performance impact is my biggest concern. The following is the rough idea, copy and pasted from my mail in another thread. --- Anne@Mozilla and I have finally finished spec-ing "slotchange" events [1] formally in the DOM Standard [2]. The following sections are relevant: 4.2.2 Shadow tree 4.2.2.1 Slots 4.2.2.2 Slotables 4.2.2.3 Finding slots and slotables 4.2.2.4 Assigning slotables and slots 4.2.2.5 Signaling slot change 4.2.3 Mutation algorithms (We have to *patch* each steps in Mutation algorithms, to define the condition of slotchange events formally.) I appreciate if you could take a look at it, and check whether it meets Polymer's expectation. I guess Polymer might not be interested in the details, but just in case. I am happy to answer any questions! [1]: https://github.com/w3c/webcomponents/issues/288 [2]: https://dom.spec.whatwg.org/ --- Yeah, I guess it is difficult to read the DOM standard because it is scattered. Let me explain the basic idea behind the scene, roughly here. - We fire (at most) one slotchange event / per each slot / per microtask checkpoint. - Basically, we have to calculate distributions at each DOM mutations, synchronously, to detect a slotchange for each slot, so that we do not miss any slotchange on any slot at each DOM mutation. We have to check it, regardless a slotchange event listener is registered or not, because a slotchange event listener will be registered *after* slotchange happens, but before the microtask checkpoint. I know that's nightmare for an engine to calculate a full distribution at each DOM mutation. But we have a hope. Optimization. We do not have to calculate full distributions on all node trees in each DOM mutation. In most cases, all we have to do is *one hash table lookup*. We do not have to calculate full distributions, top-down recursively, as the current V0 does. My ideas behind the spec: - In each DOM mutation, an engine calculates only *assigned nodes* for a slot in *one* node tree, basically. That's local effect in most cases (with an exception). - Thus, an engine omits the calculation of *distributed nodes* for each slot. - You might be wondering why that's enough? Because slotchange events are for the change of distributed nodes. It's not for the change of assigned nodes. Here is the answer: - If one slot's assigned node changes, that means the slot's distributed nodes also changes. We can tell it without calculating the distributed nodes of the slot. - But, what happens if such a slot, call it A, is assigned to other slot, B? Should we calculate B's distributed nodes to detect a slotchange on B? Yeah, B might have a *slotchage*, but we do not have to calculate the actual distributed nodes of B! That can be delayed. If A is assigned to B, and A's assigned node changes, that means B's distributed node also changes. We can tell it without calculating the actual distributed nodes of B. That can be recursively checked. Thus, we have to do at most K-times hash map lookup, if a redistribution spans K slots. - Thus, an engine does not have to know the distributed nodes of a slot even when a engine fires a slotchange event for that.
,
May 20 2016
,
May 27 2016
The following revision refers to this bug: https://chromium.googlesource.com/chromium/src.git/+/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a commit 6310c024c916f3f7ea89eb3ffabbc94e59a3c29a Author: hayato <hayato@chromium.org> Date: Fri May 27 11:59:39 2016 Rewrite Shadow DOM distribution engine to support partial synchronous distribution for v1 This is a huge engine rewrite to support slotchange [1] events more strictly and more efficiently. The summary of the changes is: 1. Make Blink be more spec compliant, regarding slotchange event. 2. Get significant performance improvements. Now SlotAssignment has |slotname|-to-|slot| HashMap, via DocumentOrderedMap. This HashMap is updated in each insertion/removal/renaming of slots. Though DOM Standard [2] requires synchronous calculation of slot assignments in each DOM mutation to fire a slotchagne event at the end of microtask, this CL does not calculate it synchronously, as an important optimization, if we can be sure to delay it. Instead, we do a minimum necessary check to detect a slotchange, using the characteristics of slot assignments. Especially, appending a child to a shadow host, which happens a lot in Polymer, becomes much faster. 3. Make HTMLSlotElement a much smaller footprint element. The following member variables are removed: m_oldAssignedNodes, m_oldDistributedNodes, m_fallbackNodes, m_oldFallbackNodes, m_distributionState and m_assignmentState. 4. Make SlotAssignment::resolveDistribution much simpler because slotchange is already detected at early stage. See the bug 610961 for details to know the basic ideas behind the scene. The results of micro benchmarks are: - PerformanceTests/ShadowDOM/v1-distribution.html => About 1.8x faster Time: Before: avg 3190.3 runs/s After: avg 5885.6 runs/s - PerformanceTests/ShadowDOM/v1-host-child-append.html => About 6.0x faster Time: Before: avg 51.6 runs/s After: avg 306.4 runs/s - PerformanceTests/ShadowDOM/v1-slot-append.html => About 3.4x faster Time: Before: avg 1647.4 runs/s After: avg 5645.0 runs/s This CL also reduced the memory usage in micro benchmarks because a slot element becomes a smaller footprint element. - PerformanceTests/ShadowDOM/v1-distribution.html JS Heap: Before: avg 21357790.4 bytes After: avg 3136606.4 bytes - PerformanceTests/ShadowDOM/v1-host-child-append.html JS Heap: Before: avg 5860745.6 bytes After: avg 4165614.4 bytes - PerformanceTests/ShadowDOM/v1-slot-append.html JS Heap: Before: avg 13256016 bytes After: avg 3540172.8 bytes Notes: - Reducing the memory usage is not the primary motivation of this CL. - These performance tests are being marked skipped. See crbug.com/579107 - This CL also fixes the following bugs. These tests no longer fail. - crbug.com/610588 - imported/wpt/shadow-dom/HTMLSlotElement-interface.html The future works are: 1. There is a still false-positive case for slotchange event. e.g. A preceding slot is inserted together with a following slot. This would not be a significant issue, but should be fixed. As of now, we must pay a performance penalty to remove this kind of false-positive. 2. Add more layout tests and add W3C Web Platform tests to be upstreamed. 3. Optimize the performance more and more. e.g. It might be possible to optimize HTMLSlotElement::hasAssignedNodesSynchronously by using yet another data structure. 4. Support SlotAssignment for non shadow trees. e.g. a document tree. This is a low-priority task because a document tree is unlikely to have a slot. 5. Isolate NeedsRecalDistribution flag for v0 and v1. Currently, the same flag is used in both kinds of shadow trees, v0 and v1, to support both together in one page. 6. DocumentOrderedMap might not be optimized for our purpose. e.g. DocumentOrderedMap has to travers DOM Tree if conflicts happen. Just using Document::compareDocumentPosition() might be better, given that conflicts is unlikely to happen. Links: [1] slotchange event: https://github.com/w3c/webcomponents/issues/288 [2] Relevant DOM Standard sections: https://dom.spec.whatwg.org/ 4.2.2 Shadow tree 4.2.2.1 Slots 4.2.2.2 Slotables 4.2.2.3 Finding slots and slotables 4.2.2.4 Assigning slotables and slots 4.2.2.5 Signaling slot changes 4.2.3 Mutation algorithms BUG= 531990 , 595287 , 610588 , 610961 , 579107 Review-Url: https://codereview.chromium.org/1995203002 Cr-Commit-Position: refs/heads/master@{#396443} [delete] https://crrev.com/42b137d8600104c1853de10626f6ef1e15e972ab/third_party/WebKit/LayoutTests/imported/wpt/shadow-dom/HTMLSlotElement-interface-expected.txt [add] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/LayoutTests/shadow-dom/slotchange-host-child-appended.html [add] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/LayoutTests/shadow-dom/slotchange-node-removed.html [add] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/LayoutTests/shadow-dom/slotchange-slotname-renamed.html [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/PerformanceTests/ShadowDOM/v1-distribution.html [add] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/PerformanceTests/ShadowDOM/v1-host-child-append.html [add] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/PerformanceTests/ShadowDOM/v1-slot-append.html [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/PerformanceTests/Skipped [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/ContainerNode.cpp [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/Document.cpp [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/Document.h [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/DocumentOrderedMap.cpp [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/DocumentOrderedMap.h [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/Element.cpp [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/Element.h [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/Node.cpp [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/Node.h [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/shadow/ElementShadow.cpp [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/shadow/FlatTreeTraversal.h [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/shadow/ShadowRoot.cpp [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/shadow/ShadowRoot.h [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/shadow/SlotAssignment.cpp [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/shadow/SlotAssignment.h [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/html/HTMLSlotElement.cpp [modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/html/HTMLSlotElement.h
,
Jun 22 2016
|
|||
►
Sign in to add a comment |
|||
Comment 1 by hayato@chromium.org
, May 20 2016