Make flat tree traversal faster (for host's children) |
|
Issue descriptionFlat tree traversal for host's children wouldn't be cheap. For example, in case of nextSibling: 1. It needs to lookup node's slotname to its assigned slot in shadow root's slot assignment hashmap 2. It needs to search an index of the given node in the slot's assigned nodes, or lookup an index in node-to-index-map 1. If we always use hashmap here, we always have to pay the cost of building hashmap even if there are only the small number of assigned nodes, where a simple liner search is much faster. My idea to improvement is: Let node have additional pointers to flat tree's parent, previous, next, to make flat tree traversal of host's children faster. These pointers are only used for host's children. So this shouldn't add any cost for other cases.
,
Nov 20
The following revision refers to this bug: https://chromium.googlesource.com/chromium/src.git/+/4377df6fcb5e5749cd359bf11656ef1ea53e99c6 commit 4377df6fcb5e5749cd359bf11656ef1ea53e99c6 Author: Hayato Ito <hayato@chromium.org> Date: Tue Nov 20 09:31:39 2018 Make flat tree traversal faster (2nd wave) The 1st wave is here: https://crrev.com/c/1337225. This CL makes flat tree traversal faster, again, by utilizing FlatTreeNodeData::assigned_slot_ field. This field is now set at the timing of reclc slot assignement. This filed is set to nullptr if host's child is not assigned to any slot there. In FlatTreeTraversal::TraverseSiblingsForV1HostChild, we check this field to avoid hashmap lookup there. BUG=906494 Change-Id: I4d5133821de1de2e58d08c7a31a7853017fd67ba Reviewed-on: https://chromium-review.googlesource.com/c/1341744 Commit-Queue: Hayato Ito <hayato@chromium.org> Reviewed-by: Kent Tamura <tkent@chromium.org> Cr-Commit-Position: refs/heads/master@{#609644} [modify] https://crrev.com/4377df6fcb5e5749cd359bf11656ef1ea53e99c6/third_party/blink/renderer/core/dom/flat_tree_node_data.h [modify] https://crrev.com/4377df6fcb5e5749cd359bf11656ef1ea53e99c6/third_party/blink/renderer/core/dom/flat_tree_traversal.cc [modify] https://crrev.com/4377df6fcb5e5749cd359bf11656ef1ea53e99c6/third_party/blink/renderer/core/dom/node.cc [modify] https://crrev.com/4377df6fcb5e5749cd359bf11656ef1ea53e99c6/third_party/blink/renderer/core/dom/node.h [modify] https://crrev.com/4377df6fcb5e5749cd359bf11656ef1ea53e99c6/third_party/blink/renderer/core/dom/shadow_root.h [modify] https://crrev.com/4377df6fcb5e5749cd359bf11656ef1ea53e99c6/third_party/blink/renderer/core/dom/slot_assignment.cc [modify] https://crrev.com/4377df6fcb5e5749cd359bf11656ef1ea53e99c6/third_party/blink/renderer/core/html/html_slot_element.cc [modify] https://crrev.com/4377df6fcb5e5749cd359bf11656ef1ea53e99c6/third_party/blink/renderer/core/html/html_slot_element.h
,
Nov 29
The following revision refers to this bug: https://chromium.googlesource.com/chromium/src.git/+/9cd83640849a69c50de2c4d8727cb9835dcee463 commit 9cd83640849a69c50de2c4d8727cb9835dcee463 Author: Hayato Ito <hayato@chromium.org> Date: Thu Nov 29 08:24:47 2018 Disallow recursive recalc slot assignment This CL is separated out from the wip CL, https://crrev.com/c/1350441, where recursive recalc slot assignment causes the tricky bug which is hard to debug. It would be better to detect recursive recalc slot assignment, which shouldn't happen. Change-Id: I07d2d22ea8e083ef1de5134d6879cb1a141ce183 BUG=906494 Change-Id: I07d2d22ea8e083ef1de5134d6879cb1a141ce183 Reviewed-on: https://chromium-review.googlesource.com/c/1354727 Reviewed-by: Kent Tamura <tkent@chromium.org> Reviewed-by: Yoshifumi Inoue <yosin@chromium.org> Commit-Queue: Hayato Ito <hayato@chromium.org> Cr-Commit-Position: refs/heads/master@{#612098} [modify] https://crrev.com/9cd83640849a69c50de2c4d8727cb9835dcee463/third_party/blink/renderer/core/dom/slot_assignment.cc
,
Nov 30
The following revision refers to this bug: https://chromium.googlesource.com/chromium/src.git/+/d9cba271a2ad1761f12731887bb4427fa7719da2 commit d9cba271a2ad1761f12731887bb4427fa7719da2 Author: Hayato Ito <hayato@chromium.org> Date: Fri Nov 30 03:44:24 2018 Guard fast flat tree traversal (fftt) by runtime flag While in working on the WIP CL, https://crrev.com/c/1350441, I've found that there is an edge case where fast flat tree traversal might return dirty result. So it would be safe to guard the feature of fast flat tree traversal by the runtime flag, and continue to develop under the flag. This CL is basically rewriting the following two CLs with runtime flag, - https://crrev.com/c/1337225 - https://crrev.com/c/1341744 and bring back old code which runs when the flag is disabled. BUG: 906494 Change-Id: I7a1940643925c1ef583cf55f1a79bfa0190ef40c Reviewed-on: https://chromium-review.googlesource.com/c/1356167 Reviewed-by: Kent Tamura <tkent@chromium.org> Commit-Queue: Hayato Ito <hayato@chromium.org> Cr-Commit-Position: refs/heads/master@{#612548} [modify] https://crrev.com/d9cba271a2ad1761f12731887bb4427fa7719da2/third_party/blink/renderer/core/dom/flat_tree_traversal.cc [modify] https://crrev.com/d9cba271a2ad1761f12731887bb4427fa7719da2/third_party/blink/renderer/core/dom/slot_assignment.cc [modify] https://crrev.com/d9cba271a2ad1761f12731887bb4427fa7719da2/third_party/blink/renderer/core/html/html_slot_element.cc [modify] https://crrev.com/d9cba271a2ad1761f12731887bb4427fa7719da2/third_party/blink/renderer/core/html/html_slot_element.h [modify] https://crrev.com/d9cba271a2ad1761f12731887bb4427fa7719da2/third_party/blink/renderer/platform/runtime_enabled_features.json5
,
Dec 3
The following revision refers to this bug: https://chromium.googlesource.com/chromium/src.git/+/f312bb2eb90f51f2d79933aa4836fa32bc75de5c commit f312bb2eb90f51f2d79933aa4836fa32bc75de5c Author: Hayato Ito <hayato@chromium.org> Date: Mon Dec 03 11:53:50 2018 [Fast flat tree traversal] Make AssignedSlot faster Make flat tree traversal's parent operation faster by avoiding a lookup of a hashmap (slotname-to-slot) (in ShadowRoot::AssignedSlotFor) if FlatTreeNodeData's assigned_slot_ can be used. The feature is under the FastFlatTreeTraversal flag. BUG=906494 Change-Id: Ia93b8a045146cdfb7008fc5e5914f19ecbd0fdc6 Reviewed-on: https://chromium-review.googlesource.com/c/1350441 Reviewed-by: Kent Tamura <tkent@chromium.org> Commit-Queue: Hayato Ito <hayato@chromium.org> Cr-Commit-Position: refs/heads/master@{#613052} [modify] https://crrev.com/f312bb2eb90f51f2d79933aa4836fa32bc75de5c/third_party/blink/renderer/core/dom/document.h [modify] https://crrev.com/f312bb2eb90f51f2d79933aa4836fa32bc75de5c/third_party/blink/renderer/core/dom/flat_tree_node_data.h [modify] https://crrev.com/f312bb2eb90f51f2d79933aa4836fa32bc75de5c/third_party/blink/renderer/core/dom/node.cc [modify] https://crrev.com/f312bb2eb90f51f2d79933aa4836fa32bc75de5c/third_party/blink/renderer/core/dom/slot_assignment.cc |
|
►
Sign in to add a comment |
|
Comment 1 by bugdroid1@chromium.org
, Nov 19