servo: Merge #18466 - Bug 1398957 - Make LRUCache use a linked list to reduce memmoves (from mbrubeck:cache); r=SimonSapin
authorMatt Brubeck <mbrubeck@limpet.net>
Thu, 14 Sep 2017 16:48:48 -0500
changeset 665367 7fc8dcc9330001298c7441c5197942d3f4ac79ea
parent 665366 3b514f20525296a9b6a623ba680fb027bc9e6cae
child 665368 e3a246b2ded697679514eddf06006a087bb0d75a
push id80026
push userbmo:ralin@mozilla.com
push dateFri, 15 Sep 2017 10:04:21 +0000
reviewersSimonSapin
bugs1398957
milestone57.0a1
servo: Merge #18466 - Bug 1398957 - Make LRUCache use a linked list to reduce memmoves (from mbrubeck:cache); r=SimonSapin https://bugzilla.mozilla.org/show_bug.cgi?id=1398957 Source-Repo: https://github.com/servo/servo Source-Revision: 49f753523ac0f062943923935ff6d1942554d2cc
servo/Cargo.lock
servo/components/style/Cargo.toml
servo/components/style/cache.rs
servo/components/style/context.rs
servo/components/style/sharing/mod.rs
--- a/servo/Cargo.lock
+++ b/servo/Cargo.lock
@@ -62,25 +62,16 @@ source = "registry+https://github.com/ru
 dependencies = [
  "heapsize 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "num-traits 0.1.37 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc-serialize 0.3.24 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 1.0.8 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
-name = "arraydeque"
-version = "0.2.3"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-dependencies = [
- "nodrop 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
- "odds 0.2.25 (registry+https://github.com/rust-lang/crates.io-index)",
-]
-
-[[package]]
 name = "arrayvec"
 version = "0.3.23"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "nodrop 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
  "odds 0.2.25 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -3116,17 +3107,16 @@ name = "strsim"
 version = "0.6.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "style"
 version = "0.0.1"
 dependencies = [
  "app_units 0.5.6 (registry+https://github.com/rust-lang/crates.io-index)",
- "arraydeque 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "arrayvec 0.3.23 (registry+https://github.com/rust-lang/crates.io-index)",
  "atomic_refcell 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "bindgen 0.29.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "bitflags 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "byteorder 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "cfg-if 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "cssparser 0.21.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "encoding 0.2.33 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -3766,17 +3756,16 @@ dependencies = [
 "checksum aho-corasick 0.6.3 (registry+https://github.com/rust-lang/crates.io-index)" = "500909c4f87a9e52355b26626d890833e9e1d53ac566db76c36faa984b889699"
 "checksum alloc-no-stdlib 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b21f6ad9c9957eb5d70c3dee16d31c092b3cab339628f821766b05e6833d72b8"
 "checksum android_glue 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "d8289e9637439939cc92b1995b0972117905be88bc28116c86b64d6e589bcd38"
 "checksum android_injected_glue 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7ec08bc5e100186b5223a24dcfe5655d1488aed9eafeb44fb9a0f67a4f53d0fc"
 "checksum angle 0.5.0 (git+https://github.com/servo/angle?branch=servo)" = "<none>"
 "checksum ansi_term 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "23ac7c30002a5accbf7e8987d0632fa6de155b7c3d39d0067317a391e00a2ef6"
 "checksum antidote 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "34fde25430d87a9388dadbe6e34d7f72a462c8b43ac8d309b42b0a8505d7e2a5"
 "checksum app_units 0.5.6 (registry+https://github.com/rust-lang/crates.io-index)" = "ed0a4de09a3b8449515e649f3bb84f72ea15fc2d10639beb0776a09b7d308074"
-"checksum arraydeque 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "96e774cadb24c2245225280c6799793f9802b918a58a79615e9490607489a717"
 "checksum arrayvec 0.3.23 (registry+https://github.com/rust-lang/crates.io-index)" = "699e63a93b79d717e8c3b5eb1b28b7780d0d6d9e59a72eb769291c83b0c8dc67"
 "checksum aster 0.41.0 (registry+https://github.com/rust-lang/crates.io-index)" = "4ccfdf7355d9db158df68f976ed030ab0f6578af811f5a7bb6dcf221ec24e0e0"
 "checksum atomic_refcell 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "fb2dcb6e6d35f20276943cc04bb98e538b348d525a04ac79c10021561d202f21"
 "checksum audio-video-metadata 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "3b6ef29ee98ad95a37f34547fd7fb40724772294110ed6ca0445fc2e964c29d1"
 "checksum azure 0.21.0 (git+https://github.com/servo/rust-azure)" = "<none>"
 "checksum backtrace 0.3.2 (registry+https://github.com/rust-lang/crates.io-index)" = "72f9b4182546f4b04ebc4ab7f84948953a118bd6021a1b6a6c909e3e94f6be76"
 "checksum backtrace-sys 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)" = "3a0d842ea781ce92be2bf78a9b38883948542749640b8378b3b2f03d1fd9f1ff"
 "checksum base64 0.5.2 (registry+https://github.com/rust-lang/crates.io-index)" = "30e93c03064e7590d0466209155251b90c22e37fab1daf2771582598b5827557"
--- a/servo/components/style/Cargo.toml
+++ b/servo/components/style/Cargo.toml
@@ -27,17 +27,16 @@ servo = ["serde", "heapsize", "heapsize_
          #"arrayvec/use_union"
 
          "servo_url"]
 gecko_debug = ["nsstring_vendor/gecko_debug"]
 
 [dependencies]
 app_units = "0.5.5"
 arrayvec = "0.3.20"
-arraydeque = "0.2.3"
 atomic_refcell = "0.1"
 bitflags = "0.7"
 byteorder = "1.0"
 cfg-if = "0.1.0"
 cssparser = "0.21.0"
 encoding = {version = "0.2", optional = true}
 euclid = "0.15"
 fallible = { path = "../fallible" }
--- a/servo/components/style/cache.rs
+++ b/servo/components/style/cache.rs
@@ -1,82 +1,210 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! A simple LRU cache.
 
-#![deny(missing_docs)]
-
-extern crate arraydeque;
-use self::arraydeque::Array;
-use self::arraydeque::ArrayDeque;
+use arrayvec::{Array, ArrayVec};
 
-/// A LRU cache used to store a set of at most `n` elements at the same time.
+/// A LRU cache using a statically-sized array for storage.
 ///
-/// The most-recently-used entry is at index zero.
-pub struct LRUCache <K: Array>{
-    entries: ArrayDeque<K>,
+/// The most-recently-used entry is at index `head`. The entries form a linked list, linked to each
+/// other by indices within the `entries` array.  After an entry is added to the array, its index
+/// never changes, so these links are never invalidated.
+pub struct LRUCache<T, A: Array<Item=Entry<T>>> {
+    entries: ArrayVec<A>,
+    /// Index of the first entry. If the cache is empty, ignore this field.
+    head: u16,
+    /// Index of the last entry. If the cache is empty, ignore this field.
+    tail: u16,
 }
 
-/// A iterator over the items of the LRU cache.
-pub type LRUCacheIterator<'a, K> = arraydeque::Iter<'a, K>;
-
-/// A iterator over the mutable items of the LRU cache.
-pub type LRUCacheMutIterator<'a, K> = arraydeque::IterMut<'a, K>;
+/// An opaque token used as an index into an LRUCache.
+pub struct CacheIndex(u16);
 
-impl<K: Array> LRUCache<K> {
-    /// Create a new LRU cache with `size` elements at most.
+/// An entry in an LRUCache.
+pub struct Entry<T> {
+    val: T,
+    /// Index of the previous entry. If this entry is the head, ignore this field.
+    prev: u16,
+    /// Index of the next entry. If this entry is the tail, ignore this field.
+    next: u16,
+}
+
+impl<T, A: Array<Item=Entry<T>>> LRUCache<T, A> {
+    /// Create an empty LRU cache.
     pub fn new() -> Self {
-        LRUCache {
-          entries: ArrayDeque::new(),
-        }
+        let cache = LRUCache {
+            entries: ArrayVec::new(),
+            head: 0,
+            tail: 0,
+        };
+        assert!(cache.entries.capacity() < u16::max_value() as usize, "Capacity overflow");
+        cache
     }
 
     /// Returns the number of elements in the cache.
     pub fn num_entries(&self) -> usize {
         self.entries.len()
     }
 
     #[inline]
     /// Touch a given entry, putting it first in the list.
-    pub fn touch(&mut self, pos: usize) {
-        if pos != 0 {
-            let entry = self.entries.remove(pos).unwrap();
-            self.entries.push_front(entry);
+    pub fn touch(&mut self, idx: CacheIndex) {
+        if idx.0 != self.head {
+            self.remove(idx.0);
+            self.push_front(idx.0);
         }
     }
 
     /// Returns the front entry in the list (most recently used).
-    pub fn front(&self) -> Option<&K::Item> {
-        self.entries.get(0)
+    pub fn front(&self) -> Option<&T> {
+        self.entries.get(self.head as usize).map(|e| &e.val)
     }
 
     /// Returns a mutable reference to the front entry in the list (most recently used).
-    pub fn front_mut(&mut self) -> Option<&mut K::Item> {
-        self.entries.get_mut(0)
+    pub fn front_mut(&mut self) -> Option<&mut T> {
+        self.entries.get_mut(self.head as usize).map(|e| &mut e.val)
     }
 
     /// Iterate over the contents of this cache, from more to less recently
     /// used.
-    pub fn iter(&self) -> arraydeque::Iter<K::Item> {
-        self.entries.iter()
+    pub fn iter(&self) -> LRUCacheIterator<T, A> {
+        LRUCacheIterator {
+            pos: self.head,
+            done: self.entries.len() == 0,
+            cache: self,
+        }
     }
 
     /// Iterate mutably over the contents of this cache.
-    pub fn iter_mut(&mut self) -> arraydeque::IterMut<K::Item> {
-        self.entries.iter_mut()
+    pub fn iter_mut(&mut self) -> LRUCacheMutIterator<T, A> {
+        LRUCacheMutIterator {
+            pos: self.head,
+            done: self.entries.len() == 0,
+            cache: self,
+        }
     }
 
     /// Insert a given key in the cache.
-    pub fn insert(&mut self, key: K::Item) {
-        if self.entries.len() == self.entries.capacity() {
-            self.entries.pop_back();
+    pub fn insert(&mut self, val: T) {
+        let entry = Entry { val, prev: 0, next: 0 };
+
+        // If the cache is full, replace the oldest entry. Otherwise, add an entry.
+        let new_head = if self.entries.len() == self.entries.capacity() {
+            let i = self.pop_back();
+            self.entries[i as usize] = entry;
+            i
+        } else {
+            self.entries.push(entry);
+            self.entries.len() as u16 - 1
+        };
+
+        self.push_front(new_head);
+    }
+
+    /// Remove an from the linked list.
+    ///
+    /// Note: This only unlinks the entry from the list; it does not remove it from the array.
+    fn remove(&mut self, i: u16) {
+        let prev = self.entries[i as usize].prev;
+        let next = self.entries[i as usize].next;
+
+        if i == self.head {
+            self.head = next;
+        } else {
+            self.entries[prev as usize].next = next;
         }
-        self.entries.push_front(key);
-        debug_assert!(self.entries.len() <= self.entries.capacity());
+
+        if i == self.tail {
+            self.tail = prev;
+        } else {
+            self.entries[next as usize].prev = prev;
+        }
+    }
+
+    /// Insert a new entry at the head of the list.
+    fn push_front(&mut self, i: u16) {
+        if self.entries.len() == 1 {
+            self.tail = i;
+        } else {
+            self.entries[i as usize].next = self.head;
+            self.entries[self.head as usize].prev = i;
+        }
+        self.head = i;
+    }
+
+    /// Remove the last entry from the linked list. Returns the index of the removed entry.
+    ///
+    /// Note: This only unlinks the entry from the list; it does not remove it from the array.
+    fn pop_back(&mut self) -> u16 {
+        let old_tail = self.tail;
+        let new_tail = self.entries[old_tail as usize].prev;
+        self.tail = new_tail;
+        old_tail
     }
 
     /// Evict all elements from the cache.
     pub fn evict_all(&mut self) {
         self.entries.clear();
     }
 }
+
+/// Immutable iterator over values in an LRUCache, from most-recently-used to least-recently-used.
+pub struct LRUCacheIterator<'a, T: 'a, A: 'a + Array<Item=Entry<T>>> {
+    cache: &'a LRUCache<T, A>,
+    pos: u16,
+    done: bool,
+}
+
+impl<'a, T, A> Iterator for LRUCacheIterator<'a, T, A>
+where T: 'a,
+      A: 'a + Array<Item=Entry<T>>
+{
+    type Item = (CacheIndex, &'a T);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.done { return None }
+
+        let entry = &self.cache.entries[self.pos as usize];
+
+        let index = CacheIndex(self.pos);
+        if self.pos == self.cache.tail {
+            self.done = true;
+        }
+        self.pos = entry.next;
+
+        Some((index, &entry.val))
+    }
+}
+
+/// Mutable iterator over values in an LRUCache, from most-recently-used to least-recently-used.
+pub struct LRUCacheMutIterator<'a, T: 'a, A: 'a + Array<Item=Entry<T>>> {
+    cache: &'a mut LRUCache<T, A>,
+    pos: u16,
+    done: bool,
+}
+
+impl<'a, T, A> Iterator for LRUCacheMutIterator<'a, T, A>
+where T: 'a,
+      A: 'a + Array<Item=Entry<T>>
+{
+    type Item = (CacheIndex, &'a mut T);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.done { return None }
+
+        // Use a raw pointer because the compiler doesn't know that subsequent calls can't alias.
+        let entry = unsafe {
+            &mut *(&mut self.cache.entries[self.pos as usize] as *mut Entry<T>)
+        };
+
+        let index = CacheIndex(self.pos);
+        if self.pos == self.cache.tail {
+            self.done = true;
+        }
+        self.pos = entry.next;
+
+        Some((index, &mut entry.val))
+    }
+}
--- a/servo/components/style/context.rs
+++ b/servo/components/style/context.rs
@@ -3,17 +3,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! The context within which style is calculated.
 
 #[cfg(feature = "servo")] use animation::Animation;
 #[cfg(feature = "servo")] use animation::PropertyAnimation;
 use app_units::Au;
 use bloom::StyleBloom;
-use cache::LRUCache;
+use cache::{Entry, LRUCache};
 use data::{EagerPseudoStyles, ElementData};
 use dom::{OpaqueNode, TNode, TElement, SendElement};
 use euclid::ScaleFactor;
 use euclid::Size2D;
 use fnv::FnvHashMap;
 use font_metrics::FontMetricsProvider;
 #[cfg(feature = "gecko")] use gecko_bindings::structs;
 use parallel::{STACK_SAFETY_MARGIN_KB, STYLE_THREAD_STACK_SIZE_KB};
@@ -517,24 +517,26 @@ impl<E: TElement> SequentialTask<E> {
         use self::SequentialTask::*;
         PostAnimation {
             el: unsafe { SendElement::new(el) },
             tasks: tasks,
         }
     }
 }
 
+type CacheItem<E> = (SendElement<E>, ElementSelectorFlags);
+
 /// Map from Elements to ElementSelectorFlags. Used to defer applying selector
 /// flags until after the traversal.
 pub struct SelectorFlagsMap<E: TElement> {
     /// The hashmap storing the flags to apply.
     map: FnvHashMap<SendElement<E>, ElementSelectorFlags>,
     /// An LRU cache to avoid hashmap lookups, which can be slow if the map
     /// gets big.
-    cache: LRUCache<[(SendElement<E>, ElementSelectorFlags); 4 + 1]>,
+    cache: LRUCache<CacheItem<E>, [Entry<CacheItem<E>>; 4 + 1]>,
 }
 
 #[cfg(debug_assertions)]
 impl<E: TElement> Drop for SelectorFlagsMap<E> {
     fn drop(&mut self) {
         debug_assert!(self.map.is_empty());
     }
 }
@@ -547,18 +549,18 @@ impl<E: TElement> SelectorFlagsMap<E> {
             cache: LRUCache::new(),
         }
     }
 
     /// Inserts some flags into the map for a given element.
     pub fn insert_flags(&mut self, element: E, flags: ElementSelectorFlags) {
         let el = unsafe { SendElement::new(element) };
         // Check the cache. If the flags have already been noted, we're done.
-        if self.cache.iter().find(|x| x.0 == el)
-               .map_or(ElementSelectorFlags::empty(), |x| x.1)
+        if self.cache.iter().find(|&(_, ref x)| x.0 == el)
+               .map_or(ElementSelectorFlags::empty(), |(_, x)| x.1)
                .contains(flags) {
             return;
         }
 
         let f = self.map.entry(el).or_insert(ElementSelectorFlags::empty());
         *f |= flags;
 
         // Insert into the cache. We don't worry about duplicate entries,
--- a/servo/components/style/sharing/mod.rs
+++ b/servo/components/style/sharing/mod.rs
@@ -63,17 +63,17 @@
 //! originating elements.  We ensure that the pseudo-element parts of all these
 //! selectors are effectively stripped off, so that matching them all against
 //! elements makes sense.
 
 use Atom;
 use applicable_declarations::ApplicableDeclarationBlock;
 use atomic_refcell::{AtomicRefCell, AtomicRefMut};
 use bloom::StyleBloom;
-use cache::LRUCache;
+use cache::{LRUCache, Entry};
 use context::{SelectorFlagsMap, SharedStyleContext, StyleContext};
 use dom::{TElement, SendElement};
 use matching::MatchMethods;
 use owning_ref::OwningHandle;
 use properties::ComputedValues;
 use rule_tree::StrongRuleNode;
 use selectors::matching::{ElementSelectorFlags, VisitedHandlingMode};
 use servo_arc::{Arc, NonZeroPtrMut};
@@ -404,17 +404,17 @@ impl<E: TElement> StyleSharingTarget<E> 
 
     /// Gets the validation data used to match against this target, if any.
     pub fn take_validation_data(&mut self) -> ValidationData {
         self.validation_data.take()
     }
 }
 
 struct SharingCacheBase<Candidate> {
-    entries: LRUCache<[Candidate; SHARING_CACHE_BACKING_STORE_SIZE]>,
+    entries: LRUCache<Candidate, [Entry<Candidate>; SHARING_CACHE_BACKING_STORE_SIZE]>,
 }
 
 impl<Candidate> Default for SharingCacheBase<Candidate> {
     fn default() -> Self {
         Self {
             entries: LRUCache::new(),
         }
     }
@@ -443,17 +443,17 @@ impl<E: TElement> SharingCache<E> {
         self.entries.insert(StyleSharingCandidate { element, validation_data });
     }
 
     fn lookup<F>(&mut self, mut is_match: F) -> Option<E>
     where
         F: FnMut(&mut StyleSharingCandidate<E>) -> bool
     {
         let mut index = None;
-        for (i, candidate) in self.entries.iter_mut().enumerate() {
+        for (i, candidate) in self.entries.iter_mut() {
             if is_match(candidate) {
                 index = Some(i);
                 break;
             }
         };
 
         match index {
             None => None,