servo: Merge #17142 - Move LRUCache to ArrayDeque crate (from kenan-rhoton:LRUCacheArrayVecDeque); r=emilio
authorKenan Rhoton <kenan.rhoton@gmail.com>
Sun, 04 Jun 2017 13:29:24 -0700
changeset 1147567 3427626e7f2636a87dd5d35ef98974df45a45235
parent 1147566 eb8b2638f96a3f73340a5b436de8013ef0d0613d
child 1147568 520b32ed6ba822d40687a2d9859697b8c0bbae36
push id195281
push userhshih@mozilla.com
push dateMon, 05 Jun 2017 09:40:16 +0000
treeherdertry@17a699c3a79b [default view] [failures only]
reviewersemilio
milestone55.0a1
servo: Merge #17142 - Move LRUCache to ArrayDeque crate (from kenan-rhoton:LRUCacheArrayVecDeque); r=emilio We move LRUCache from using VecDeque to ArrayDeque to avoid using heap allocations. This relies on the fix in goandylok/arraydeque#4. --- <!-- Thank you for contributing to Servo! Please replace each `[ ]` by `[X]` when the step is complete, and replace `__` with appropriate data: --> - [X] `./mach build -d` does not report any errors - [X] `./mach test-tidy` does not report any errors - [X] These changes fix #17054 (github issue number if applicable). <!-- Either: --> - [ ] There are tests for these changes OR - [X] These changes do not require tests because the use cases are the same, only minimal implementation changes have been made <!-- Also, please make sure that "Allow edits from maintainers" checkbox is checked, so that we can help you if you get stuck somewhere along the way.--> <!-- Pull requests that do not address these steps are welcome, but they will require additional verification as part of the review process. --> --- I additionally ran test-unit, because I'm paranoid. Source-Repo: https://github.com/servo/servo Source-Revision: 2dd67a94971bf562e2eed90582f28ef78a70cf70
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,16 +62,25 @@ source = "registry+https://github.com/ru
 dependencies = [
  "heapsize 0.3.9 (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 0.9.15 (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)",
 ]
 
@@ -2865,16 +2874,17 @@ 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.4.1 (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.25.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "bit-vec 0.4.3 (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.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "cssparser 0.13.7 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -3494,16 +3504,17 @@ 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.2.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.4.1 (registry+https://github.com/rust-lang/crates.io-index)" = "c89beb28482985f88b312de4021d748f45b3eecec6cc8dbaf0c2b3c3d1ce6da5"
+"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.15.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,16 +27,17 @@ servo = ["serde", "serde_derive", "heaps
 
          "rayon/unstable", "servo_url"]
 testing = []
 gecko_debug = ["nsstring_vendor/gecko_debug"]
 
 [dependencies]
 app_units = "0.4.1"
 arrayvec = "0.3.20"
+arraydeque = "0.2.3"
 atomic_refcell = "0.1"
 bitflags = "0.7"
 bit-vec = "0.4.3"
 byteorder = "1.0"
 cfg-if = "0.1.0"
 cssparser = "0.13.7"
 encoding = {version = "0.2", optional = true}
 euclid = "0.11"
--- a/servo/components/style/cache.rs
+++ b/servo/components/style/cache.rs
@@ -1,39 +1,38 @@
 /* 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)]
 
-use std::collections::VecDeque;
-use std::collections::vec_deque;
+extern crate arraydeque;
+use self::arraydeque::Array;
+use self::arraydeque::ArrayDeque;
 
 /// A LRU cache used to store a set of at most `n` elements at the same time.
 ///
 /// The most-recently-used entry is at index zero.
-pub struct LRUCache<K> {
-    entries: VecDeque<K>,
-    cache_size: usize,
+pub struct LRUCache <K: Array>{
+    entries: ArrayDeque<K>,
 }
 
 /// A iterator over the items of the LRU cache.
-pub type LRUCacheIterator<'a, K> = vec_deque::Iter<'a, K>;
+pub type LRUCacheIterator<'a, K> = arraydeque::Iter<'a, K>;
 
 /// A iterator over the mutable items of the LRU cache.
-pub type LRUCacheMutIterator<'a, K> = vec_deque::IterMut<'a, K>;
+pub type LRUCacheMutIterator<'a, K> = arraydeque::IterMut<'a, K>;
 
-impl<K: PartialEq> LRUCache<K> {
+impl<K: Array> LRUCache<K> {
     /// Create a new LRU cache with `size` elements at most.
-    pub fn new(size: usize) -> Self {
+    pub fn new() -> Self {
         LRUCache {
-          entries: VecDeque::with_capacity(size),
-          cache_size: size,
+          entries: ArrayDeque::new(),
         }
     }
 
     /// Returns the number of elements in the cache.
     pub fn num_entries(&self) -> usize {
         self.entries.len()
     }
 
@@ -44,31 +43,31 @@ impl<K: PartialEq> LRUCache<K> {
         if pos != last_index {
             let entry = self.entries.remove(pos).unwrap();
             self.entries.push_front(entry);
         }
     }
 
     /// Iterate over the contents of this cache, from more to less recently
     /// used.
-    pub fn iter(&self) -> vec_deque::Iter<K> {
+    pub fn iter(&self) -> arraydeque::Iter<K::Item> {
         self.entries.iter()
     }
 
     /// Iterate mutably over the contents of this cache.
-    pub fn iter_mut(&mut self) -> vec_deque::IterMut<K> {
+    pub fn iter_mut(&mut self) -> arraydeque::IterMut<K::Item> {
         self.entries.iter_mut()
     }
 
     /// Insert a given key in the cache.
-    pub fn insert(&mut self, key: K) {
-        if self.entries.len() == self.cache_size {
+    pub fn insert(&mut self, key: K::Item) {
+        if self.entries.len() == self.entries.capacity() {
             self.entries.pop_back();
         }
         self.entries.push_front(key);
-        debug_assert!(self.entries.len() <= self.cache_size);
+        debug_assert!(self.entries.len() <= self.entries.capacity());
     }
 
     /// Evict all elements from the cache.
     pub fn evict_all(&mut self) {
         self.entries.clear();
     }
 }
--- a/servo/components/style/context.rs
+++ b/servo/components/style/context.rs
@@ -344,32 +344,32 @@ impl<E: TElement> SequentialTask<E> {
 
 /// 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)>,
+    cache: LRUCache<[(SendElement<E>, ElementSelectorFlags); 4 + 1]>,
 }
 
 #[cfg(debug_assertions)]
 impl<E: TElement> Drop for SelectorFlagsMap<E> {
     fn drop(&mut self) {
         debug_assert!(self.map.is_empty());
     }
 }
 
 impl<E: TElement> SelectorFlagsMap<E> {
     /// Creates a new empty SelectorFlagsMap.
     pub fn new() -> Self {
         SelectorFlagsMap {
             map: FnvHashMap::default(),
-            cache: LRUCache::new(4),
+            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)
--- a/servo/components/style/sharing/mod.rs
+++ b/servo/components/style/sharing/mod.rs
@@ -304,24 +304,24 @@ pub enum StyleSharingResult {
 }
 
 /// An LRU cache of the last few nodes seen, so that we can aggressively try to
 /// reuse their styles.
 ///
 /// Note that this cache is flushed every time we steal work from the queue, so
 /// storing nodes here temporarily is safe.
 pub struct StyleSharingCandidateCache<E: TElement> {
-    cache: LRUCache<StyleSharingCandidate<E>>,
+    cache: LRUCache<[StyleSharingCandidate<E>; STYLE_SHARING_CANDIDATE_CACHE_SIZE + 1]>,
 }
 
 impl<E: TElement> StyleSharingCandidateCache<E> {
     /// Create a new style sharing candidate cache.
     pub fn new() -> Self {
         StyleSharingCandidateCache {
-            cache: LRUCache::new(STYLE_SHARING_CANDIDATE_CACHE_SIZE),
+            cache: LRUCache::new(),
         }
     }
 
     /// Returns the number of entries in the cache.
     pub fn num_entries(&self) -> usize {
         self.cache.num_entries()
     }