Closed Bug 1398957 Opened 4 years ago Closed 4 years ago

stylo: touching the LRUCache does a bunch of memmoving


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




Tracking Status
firefox-esr52 --- wontfix
firefox55 --- wontfix
firefox56 --- wontfix
firefox57 --- fixed


(Reporter: bholley, Assigned: mbrubeck)


In, we have a simple LRU cache backed by an ArrayDeque. This is used for the style sharing cache.

When we get a hit, we call touch() to move the entry to the front of the list. ArrayDeque tries to be smart about this, but there is fundamentally some memmoving to rearrange things.

The entries that we put in the cache include a ValidationData, which weighs ~250 bytes. With a cache size of 30 bytes, this can mean several kilobytes of memmoving on every touch().

We basically want linked list semantics here, but without all the heap churn.

My proposal is as follows:
* LRUCache<K> Stores an ArrayVec of Entry<K>. We don't need ArrayDeque anymore.
* Entry<K> has a K, as well as |prev| and |next|, both of which are u16 indices into the array.
* LRUCache<K> also stores |head| and |tail| indices.

The above is sufficient to provide linked-list semantics, so long as a given entry's index never changes. This constraint forbids compaction on removal, which would get tricky if we needed to support general-purpose remove(). Luckily, we don't need to support that, since LRUCache just needs to support clear() (which wipes all the entries), and insert() (which only removes if the cache is full, in which case we can just reuse the location of the evicted entry).
Matt is going to take this when he recovers from the stomach flu. Probably doesn't block shipping, but would be nice to have.
Assignee: nobody → mbrubeck
Flags: needinfo?(mbrubeck)
Priority: -- → P3
Flags: needinfo?(mbrubeck)
Closed: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla57
You need to log in before you can comment on or make changes to this bug.