Make querySelectorAll execution parallelized

[tetsuharuohzeki]

The current our implementation works selector matching parallely in layout code.

However, in script task, we don't make it. Thus ParentNode.querySelectorAll() works sequentially as oldie. This is not good taste.

Parallelized ParentNode.querySelectorAll() will achieve good performance.

[tetsuharuohzeki]

I thought of the implementation design.

Abstract

If we implement this parallelism, we need to know a tree order of matched elements to return an ordered list. Therefore:

• We would need to add an ordered id (will be uint64) to every elements in Document/DocumentFragment.
• But if we add an id to every elements on every times which we modify node (document) tree, it will be very high cost.
• I think that it might be efficient that we add an ordered id to every elements when we traverse an all of nodes in it at the first time after we finished to modify the document.
  • At the first traversing time, we would traverse a tree as sequentially.
  • However, after we added an ordered ids, we would be able to do parallelized selector matching.

This approach will be good if ParentNode.querySelectorAll() is called:

• at the same point (e.g. document) between the first time and later.
• at document -> any of elements in the document.
  • We would have added ordered ids to every elements.

But this approach will fail if ParentNode.querySelectorAll() is called:

• at any of elements in the document -> at the document.
  • We wouldn’t able to add ordered id to every elements, because we need not traverse all elements in the document. If we do so, it would get needless cost :(

In coclusion, this approach will achieve in some speciefed case. But it might be very limited case…

Questions

• Does this approach have a benefit enough to implement this specified parallel optimization?
  _ Do we have any other good ideas to implement paralleled ParentNode.querySelectorAll()?

[frewsxcv]

Potential idea here: Use https://github.com/nikomatsakis/rayon to iterate through the child nodes. Specifically, use the 'parallel iterators' strategy, having one iterator start from firstChild and have one iterator start from lastChild and halting iteration when they reach each other.