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}
25 files changed