Closed Bug 1355347 Opened 7 years ago Closed 6 years ago

Expensive hashtable lookup from RuleHash::EnumerateAllRules() during style flush

Categories

(Core :: Layout, enhancement, P3)

enhancement

Tracking

()

RESOLVED INCOMPLETE

People

(Reporter: ehsan.akhgari, Unassigned)

References

(Blocks 1 open bug)

Details

So the point of these hashtable lookups is really to avoid an O(elements * selectors) algorithm as much as we can, so they're actually a very effective use of hashtables related to the obvious alternatives.  My understanding is that basically every browser engine has the same optimization here.

Maybe we should change the namespace one from a hashtable to a linked list, though, since in 99% of cases that will be faster.

Or, alteratively, we could change all of them to a binary tree rather than a hashtable, although we'd have to figure out how to do the case-insensitive comparisons for quirks mode.

And this is a case where a tree may well be faster than a hashtable, especially if we do all the operations on atoms.

The flip side is that this code goes away with stylo (and gets replaced with rust code that does the same thing, although servo apparently doesn't have the namespace bucket), so it's not clear how much effort it's worth putting in here.


Also, the URL you shared doesn't seem to point to a 67ms thing that shows time spent in the hashtable lookups.  In that view I see 11ms in EnumerateAllRules.  And I also can't figure out how to use the profiler to look at the time spent inside all of the EnumerateAllRules work in a slice of the profile rather than just one callstack to EnumerateAllRules.
Priority: -- → P3
This code has now gone away, so I'm inclined to close this bug and open a new one if we find that Servo's rule bucket hash table usage can be improved.
Status: NEW → RESOLVED
Closed: 6 years ago
Resolution: --- → INCOMPLETE
You need to log in before you can comment on or make changes to this bug.