1401855 - stylo: weigh the tradeoffs of LRUCache vs HashMap as a backend for the nth-index cache

Status: NEW

(Core :: CSS Parsing and Computation, enhancement, P4)

Description

[Bobby Holley (:bholley)]

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 1

[Bobby Holley (:bholley)]

NI emilio to weigh the tradeoffs.

Comment 2

[Emilio Cobos Álvarez (:emilio)]

I just commented in bug 1334730. Seems like the Blink team has measured this before, and its measurements seem pretty reasonable.

Comment 3

[Boris Zbarsky [:bzbarsky]]

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.

Comment 4

[Bobby Holley (:bholley)]

I just matched gecko in bug 1334730. Leaving this bug open in case we want to revisit the gecko-vs-blink tradeoff.

Comment 5

[Firefox Bug Husbandry Bot]

https://wiki.mozilla.org/Bug_Triage/Projects/Bug_Handling/Bug_Husbandry#Move_fix-optionals