Open
Bug 1401855
Opened 7 years ago
Updated 2 years ago
stylo: weigh the tradeoffs of LRUCache vs HashMap as a backend for the nth-index cache
Categories
(Core :: CSS Parsing and Computation, enhancement, P4)
Core
CSS Parsing and Computation
Tracking
()
NEW
People
(Reporter: bholley, Unassigned)
References
Details
In bug 1334730, I implemented an nth-index cache for stylo. I originally used a HashMap, but then switched to an LRUCache out of concerns about the map getting too big.
Emilio made some good points in favor of skipping eviction and just using a HashMap instead. I'm a bit tired to weigh the tradeoffs right now, but we can discuss here and make any resulting changes as a followup to bug 1334730.
Comment 2•7 years ago
|
||
I just commented in bug 1334730. Seems like the Blink team has measured this before, and its measurements seem pretty reasonable.
Flags: needinfo?(emilio)
Comment 3•7 years ago
|
||
The Blink cache seems to be somewhat different from the cache bug 1334730 implements, at first glance.
The cache in bug 1334730 (and Gecko) records indices for particular elements that we tried to actually match index stuff against. Basically, it memoizes the results of computations we had to do for matching anyway, then aims to use them to speed up new computations.
The cache in Blink, on the other hand, seems to work like this:
1) If the parent has < 32 kids, don't use a cache at all; just keep walking the child list.
2) If there are >32 kids, then as soon as we end up doing an index computation for something after the 32nd
kid, walk the _entire_ child list for the parent, and cache indices for every third element in the list
(matching the given qualified name in the of-type case).
So it's doing somewhat more eager work. It's also using a hashtable of hashtables or so (hash of parents to NthIndexData, and then within each NthIndexData hash from kids to indices), not a single hashtable.
Fwiw, Gecko just uses a hashtable (well, four hashtables for the four of-type/all x from-start/from-end cases) and just scopes down its lifetime to the lifetime of a TreeMatchContext. No eviction, but also any memory usage is pretty transient.
Reporter | ||
Comment 4•7 years ago
|
||
I just matched gecko in bug 1334730. Leaving this bug open in case we want to revisit the gecko-vs-blink tradeoff.
Priority: -- → P4
Updated•7 years ago
|
status-firefox57:
--- → wontfix
status-firefox58:
--- → fix-optional
Comment 5•7 years ago
|
||
status-firefox59:
--- → ?
Updated•2 years ago
|
Severity: normal → S3
You need to log in
before you can comment on or make changes to this bug.
Description
•