1295898 - Potential optimization to tree position comparison

Status: NEW

(Core :: Layout, defect, P3)

Description

[Xidorn Quan [:xidorn] UTC+10]

(I open this bug just to record what I thought about this topic. If we really need to do those optimizations in the future (doubtful), this can probably help a bit. I guess it isn't worth the code complexity for now, actually.)


There are various places we use nsLayoutUtils::DoCompareTreePosition to determine the order of nodes / frames.

Those functions are implemented straightforward, and it doesn't seem to me there is any big thing can be optimized on the functions themselves.

However, some of the callsites can call the functions lots of times, and we may be able to optimize the algorithm for those cases.

Two usual patterns of calling DoCompareTreePosition many times are binary search and sorting in tree order.

For both cases, we can cache all nodes visited (including the siblings) with some additional data to improve the overall time complexity.

For binary search, the additional data would be whether a node is before or after the target node in tree order. Following bisect lookups would benefit from previous ones with an early return when we find one of its ancestor's order is already figured out.

For ordering, the additional data would be whether a node is in the list, and whether it has any descendant in the list. After caching all nodes in our input list, we can do a restricted tree traversal to generate the sorted list.

The overall time complexity of the algorithms descibed above should be lower than what we currently have. But as far as we cannot attach those kinds of information to nsIContent and nsIFrame directly, those algorithms would need extensive hashtable lookup (for mapping from node pointer to corresponding cache data), so it's hard to predict the practical performance.