1398957 - stylo: touching the LRUCache does a bunch of memmoving

Status: RESOLVED FIXED

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

Description

[Bobby Holley (:bholley)]

In cache.rs, 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).

Comment 1

[Bobby Holley (:bholley)]

Matt is going to take this when he recovers from the stomach flu. Probably doesn't block shipping, but would be nice to have.

Comment 2

[Matt Brubeck (:mbrubeck)]

https://github.com/servo/servo/pull/18466

Comment 3

[Ekanan Ketunuti]

https://hg.mozilla.org/mozilla-central/rev/7fc8dcc93300