commit eaddcb2899f1120b8a8d4d30d3c2a2911e65d049
author Rakina Zata Amni <rakina@chromium.org> Fri Nov 09 07:56:45 2018
committer Commit Bot <commit-bot@chromium.org> Fri Nov 09 07:56:45 2018
tree 724c073c3d5b66f8ed1f853fb89a5780d4f1a8f4
parent d630de0987d6548a684ad742dad51ff8fb06fa55

Add assigned_nodes_index_ map for slot's assigned child

Currently when traversing to the next/prev sibling of a slot's assigned
child, we find the current node's position by looping through a list
of the slot's assigned child, taking O(N) time where N is the number of
assigned children in that slot. This means traversing through a slot's
children will take a total of O(N^2) time. This CL adds a node->index
map for slot's children so that we will instead take O(1) time to find
a node's position in the list.

The downside of this is in cases where there are only a small number
of children assigned to a slot, the performance will be slightly worse
because of the hashmap lookup.

Benchmarked with https://jsbin.com/ravolid/edit?html,output, comparing
shadow dom v0 vs v1, where v0 already uses maps.

For N = 500 (release build), v0 takes ~20ms, v1 without map takes ~200ms, so v0 is 10x
faster than v1.
For N = 500 (local build), v0 takes ~54ms, v1 with map takes ~90ms, so v0 is 1.8x
faster than v1.


Bug: 901063
Change-Id: Iec006fcafca1e368ab97f40d909362dbcf74a08e
Reviewed-on: https://chromium-review.googlesource.com/c/1328622
Reviewed-by: Hayato Ito <hayato@chromium.org>
Commit-Queue: Rakina Zata Amni <rakina@chromium.org>
Cr-Commit-Position: refs/heads/master@{#606764}