servo: Merge #16037 - Reduce cloning of FrameState (from cbrewster:reduce_framestate_clones); r=asajeffrey
authorConnor Brewster <connor.brewster@eagles.oc.edu>
Thu, 06 Apr 2017 21:22:14 -0500
changeset 558318 69c70ee0d199cc5130d0728ba8b74ff80f4b1bc1
parent 558317 5fcfe069fc1d87978ec024ebfc75ed787a0f5fea
child 558319 372117f8e19a1d71a67be32332d42fa8608ebe0e
push id52860
push userbmo:walkingice0204@gmail.com
push dateFri, 07 Apr 2017 13:29:26 +0000
reviewersasajeffrey
milestone55.0a1
servo: Merge #16037 - Reduce cloning of FrameState (from cbrewster:reduce_framestate_clones); r=asajeffrey <!-- Please describe your changes on the following line: --> This uses `kmerge` from itertools to construct the jsh future and past iterators without having to do a collect/sort. This allows us to reduce cloning of `FrameState`. --- <!-- 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 - [ ] These changes fix #__ (github issue number if applicable). <!-- Either: --> - [ ] There are tests for these changes OR - [X] These changes do not require tests because refactoring <!-- Pull requests that do not address these steps are welcome, but they will require additional verification as part of the review process. --> Source-Repo: https://github.com/servo/servo Source-Revision: c87d0c671c2ae20a97099f3f369e81eb0ce5e403
servo/Cargo.lock
servo/components/constellation/Cargo.toml
servo/components/constellation/constellation.rs
servo/components/constellation/lib.rs
--- a/servo/Cargo.lock
+++ b/servo/Cargo.lock
@@ -447,16 +447,17 @@ dependencies = [
  "compositing 0.0.1",
  "debugger 0.0.1",
  "devtools_traits 0.0.1",
  "euclid 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "gaol 0.0.1 (git+https://github.com/servo/gaol)",
  "gfx 0.0.1",
  "gfx_traits 0.0.1",
  "ipc-channel 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "itertools 0.5.10 (registry+https://github.com/rust-lang/crates.io-index)",
  "layout_traits 0.0.1",
  "log 0.3.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "msg 0.0.1",
  "net 0.0.1",
  "net_traits 0.0.1",
  "offscreen_gl_context 0.8.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "profile_traits 0.0.1",
  "script_traits 0.0.1",
@@ -684,16 +685,21 @@ dependencies = [
  "lazy_static 0.2.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "libc 0.2.21 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 0.9.11 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_derive 0.9.11 (registry+https://github.com/rust-lang/crates.io-index)",
  "winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
+name = "either"
+version = "1.0.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "embedding"
 version = "0.0.1"
 dependencies = [
  "cocoa 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "compositing 0.0.1",
  "devtools 0.0.1",
  "euclid 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "gleam 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1285,16 +1291,24 @@ dependencies = [
  "libc 0.2.21 (registry+https://github.com/rust-lang/crates.io-index)",
  "mio 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand 0.3.15 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 0.9.11 (registry+https://github.com/rust-lang/crates.io-index)",
  "uuid 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
+name = "itertools"
+version = "0.5.10"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "either 1.0.3 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "itoa"
 version = "0.3.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "jpeg-decoder"
 version = "0.1.11"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -3340,16 +3354,17 @@ dependencies = [
 "checksum dbus 0.5.2 (registry+https://github.com/rust-lang/crates.io-index)" = "47f881971824401c27bc1ff9f641d54ac66e0f409631806fa7be8cad8e6be450"
 "checksum debug_unreachable 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "9a032eac705ca39214d169f83e3d3da290af06d8d1d344d1baad2fd002dca4b3"
 "checksum deflate 0.7.5 (registry+https://github.com/rust-lang/crates.io-index)" = "ebb02aaf4b775afc96684b8402510a338086974e38570a1f65bea8c202eb77a7"
 "checksum deque 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "1614659040e711785ed8ea24219140654da1729f3ec8a47a9719d041112fe7bf"
 "checksum device 0.0.1 (git+https://github.com/servo/devices)" = "<none>"
 "checksum dtoa 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)" = "80c8b71fd71146990a9742fc06dcbbde19161a267e0ad4e572c35162f4578c90"
 "checksum dwmapi-sys 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "07c4c7cc7b396419bc0a4d90371d0cee16cb5053b53647d287c0b728000c41fe"
 "checksum dwrote 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "74114b6b49d6731835da7a28a3642651451e315f7f9b9d04e907e65a45681796"
+"checksum either 1.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "63f94a35a9ca0d4178e85f0250373f2cea55c5d603e6993778d68a99b3d8071c"
 "checksum encoding 0.2.33 (registry+https://github.com/rust-lang/crates.io-index)" = "6b0d943856b990d12d3b55b359144ff341533e516d94098b1d3fc1ac666d36ec"
 "checksum encoding-index-japanese 1.20141219.5 (registry+https://github.com/rust-lang/crates.io-index)" = "04e8b2ff42e9a05335dbf8b5c6f7567e5591d0d916ccef4e0b1710d32a0d0c91"
 "checksum encoding-index-korean 1.20141219.5 (registry+https://github.com/rust-lang/crates.io-index)" = "4dc33fb8e6bcba213fe2f14275f0963fd16f0a02c878e3095ecfdf5bee529d81"
 "checksum encoding-index-simpchinese 1.20141219.5 (registry+https://github.com/rust-lang/crates.io-index)" = "d87a7194909b9118fc707194baa434a4e3b0fb6a5a757c73c3adb07aa25031f7"
 "checksum encoding-index-singlebyte 1.20141219.5 (registry+https://github.com/rust-lang/crates.io-index)" = "3351d5acffb224af9ca265f435b859c7c01537c0849754d3db3fdf2bfe2ae84a"
 "checksum encoding-index-tradchinese 1.20141219.5 (registry+https://github.com/rust-lang/crates.io-index)" = "fd0e20d5688ce3cab59eb3ef3a2083a5c77bf496cb798dc6fcdb75f323890c18"
 "checksum encoding_index_tests 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)" = "a246d82be1c9d791c5dfde9a2bd045fc3cbba3fa2b11ad558f27d01712f00569"
 "checksum energy-monitor 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "fe872d0664f1cc60db36349af245d892ee67d3c8f78055df0ebc43271fd4e05c"
@@ -3391,16 +3406,17 @@ dependencies = [
 "checksum hyper_serde 0.6.2 (registry+https://github.com/rust-lang/crates.io-index)" = "a43d985c58afed6b59991932e1d9b5f2629472849f0062c0078d82fdc0b788bb"
 "checksum idna 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "1053236e00ce4f668aeca4a769a09b3bf5a682d802abd6f3cb39374f6b162c11"
 "checksum image 0.12.3 (registry+https://github.com/rust-lang/crates.io-index)" = "979bad0502082fd60053a490282e87d6c89650942e3a270e0d4c83569c7f5899"
 "checksum immeta 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)" = "0b9260463a221bfe3f02100c56e2d14c050d5ffe7e44a43d0a1b2b1f2b523502"
 "checksum inflate 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "e7e0062d2dc2f17d2f13750d95316ae8a2ff909af0fda957084f5defd87c43bb"
 "checksum io-surface 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "c35a3278fa52fb070fdc874dfd057163e6c21e0a9295f87f54daee9dd5530b43"
 "checksum iovec 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "29d062ee61fccdf25be172e70f34c9f6efc597e1fb8f6526e8437b2046ab26be"
 "checksum ipc-channel 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "f1e8d7f511a1e2dae4e26efac30a85d2376b67d7c6f2c691ea95ebd850b017da"
+"checksum itertools 0.5.10 (registry+https://github.com/rust-lang/crates.io-index)" = "4833d6978da405305126af4ac88569b5d71ff758581ce5a987dbfa3755f694fc"
 "checksum itoa 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "eb2f404fbc66fd9aac13e998248505e7ecb2ad8e44ab6388684c5fb11c6c251c"
 "checksum jpeg-decoder 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)" = "5c4ff3d14e7ef3522471ab712832c3dd50001f7fb7aa4cdc48af811d63b531e9"
 "checksum js 0.1.4 (git+https://github.com/servo/rust-mozjs)" = "<none>"
 "checksum kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7507624b29483431c0ba2d82aece8ca6cdba9382bff4ddd0f7490560c056098d"
 "checksum khronos_api 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "09c9d3760673c427d46f91a0350f0a84a52e6bc5a84adf26dc610b6c52436630"
 "checksum language-tags 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "a91d884b6667cd606bb5a69aa0c99ba811a115fc68915e7056ec08a46e93199a"
 "checksum lazy_static 0.2.4 (registry+https://github.com/rust-lang/crates.io-index)" = "7291b1dd97d331f752620b02dfdbc231df7fc01bf282a00769e1cdb963c460dc"
 "checksum lazycell 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ce12306c4739d86ee97c23139f3a34ddf0387bbf181bc7929d287025a8c3ef6b"
--- a/servo/components/constellation/Cargo.toml
+++ b/servo/components/constellation/Cargo.toml
@@ -16,16 +16,17 @@ canvas = {path = "../canvas"}
 canvas_traits = {path = "../canvas_traits"}
 compositing = {path = "../compositing"}
 debugger = {path = "../debugger"}
 devtools_traits = {path = "../devtools_traits"}
 euclid = "0.11"
 gfx = {path = "../gfx"}
 gfx_traits = {path = "../gfx_traits"}
 ipc-channel = "0.7"
+itertools = "0.5"
 layout_traits = {path = "../layout_traits"}
 log = "0.3.5"
 msg = {path = "../msg"}
 net = {path = "../net"}
 net_traits = {path = "../net_traits"}
 offscreen_gl_context = "0.8"
 profile_traits = {path = "../profile_traits"}
 script_traits = {path = "../script_traits"}
--- a/servo/components/constellation/constellation.rs
+++ b/servo/components/constellation/constellation.rs
@@ -76,16 +76,17 @@ use euclid::scale_factor::ScaleFactor;
 use euclid::size::{Size2D, TypedSize2D};
 use event_loop::EventLoop;
 use frame::{Frame, FrameChange, FrameState, FrameTreeIterator, FullFrameTreeIterator};
 use gfx::font_cache_thread::FontCacheThread;
 use gfx_traits::Epoch;
 use ipc_channel::{Error as IpcError};
 use ipc_channel::ipc::{self, IpcSender, IpcReceiver};
 use ipc_channel::router::ROUTER;
+use itertools::Itertools;
 use layout_traits::LayoutThreadFactory;
 use log::{Log, LogLevel, LogLevelFilter, LogMetadata, LogRecord};
 use msg::constellation_msg::{FrameId, FrameType, PipelineId};
 use msg::constellation_msg::{Key, KeyModifiers, KeyState};
 use msg::constellation_msg::{PipelineNamespace, PipelineNamespaceId, TraversalDirection};
 use net_traits::{self, IpcSend, ResourceThreads};
 use net_traits::pub_domains::reg_host;
 use net_traits::storage_thread::{StorageThreadMsg, StorageType};
@@ -104,25 +105,25 @@ use script_traits::{SWManagerMsg, ScopeT
 use script_traits::WebVREventMsg;
 use serde::{Deserialize, Serialize};
 use servo_config::opts;
 use servo_config::prefs::PREFS;
 use servo_rand::{Rng, SeedableRng, ServoRng, random};
 use servo_remutex::ReentrantMutex;
 use servo_url::{Host, ImmutableOrigin, ServoUrl};
 use std::borrow::ToOwned;
+use std::cmp::Ordering;
 use std::collections::{HashMap, VecDeque};
 use std::iter::once;
 use std::marker::PhantomData;
 use std::process;
 use std::rc::{Rc, Weak};
 use std::sync::Arc;
 use std::sync::mpsc::{Receiver, Sender, channel};
 use std::thread;
-use std::time::Instant;
 use style_traits::CSSPixel;
 use style_traits::cursor::Cursor;
 use style_traits::viewport::ViewportConstraints;
 use timer_scheduler::TimerScheduler;
 use webrender_traits;
 use webvr_traits::WebVRMsg;
 
 /// The `Constellation` itself. In the servo browser, there is one
@@ -698,48 +699,39 @@ impl<Message, LTF, STF> Constellation<Me
             stack: vec!(frame_id_root),
             pipelines: &self.pipelines,
             frames: &self.frames,
         }
     }
 
     /// The joint session future is the merge of the session future of every
     /// frame in the frame tree, sorted chronologically.
-    fn joint_session_future<'a>(&'a self, frame_id_root: FrameId) -> impl Iterator<Item=FrameState> {
-        let mut future: Vec<FrameState> = self.full_frame_tree_iter(frame_id_root)
-            .flat_map(|frame| frame.next.iter().cloned())
-            .collect();
-
-        // Sort the joint session future by the timestamp that the pipeline was navigated to
-        // in chronological order
-        future.sort_by(|a, b| a.instant.cmp(&b.instant));
-        future.into_iter()
+    fn joint_session_future<'a>(&'a self, frame_id_root: FrameId) -> impl Iterator<Item = &'a FrameState> + 'a {
+        self.full_frame_tree_iter(frame_id_root)
+            .map(|frame| frame.next.iter().rev())
+            .kmerge_by(|a, b| a.instant.cmp(&b.instant) == Ordering::Less)
     }
 
     /// Is the joint session future empty?
     fn joint_session_future_is_empty(&self, frame_id_root: FrameId) -> bool {
         self.full_frame_tree_iter(frame_id_root)
             .all(|frame| frame.next.is_empty())
     }
 
     /// The joint session past is the merge of the session past of every
     /// frame in the frame tree, sorted reverse chronologically.
-    fn joint_session_past<'a>(&self, frame_id_root: FrameId) -> impl Iterator<Item=FrameState> {
-        let mut past: Vec<(Instant, FrameState)> = self.full_frame_tree_iter(frame_id_root)
-            .flat_map(|frame| frame.prev.iter().rev().scan(frame.instant, |prev_instant, entry| {
+    fn joint_session_past<'a>(&'a self, frame_id_root: FrameId) -> impl Iterator<Item = &'a FrameState> + 'a {
+        self.full_frame_tree_iter(frame_id_root)
+            .map(|frame| frame.prev.iter().rev().scan(frame.instant, |prev_instant, entry| {
                 let instant = *prev_instant;
                 *prev_instant = entry.instant;
-                Some((instant, entry.clone()))
+                Some((instant, entry))
             }))
-            .collect();
-
-        // Sort the joint session past by the timestamp that the pipeline was navigated from
-        // in reverse chronological order
-        past.sort_by(|a, b| b.0.cmp(&a.0));
-        past.into_iter().map(|(_, entry)| entry)
+            .kmerge_by(|a, b| a.0.cmp(&b.0) == Ordering::Greater)
+            .map(|(_, entry)| entry)
     }
 
     /// Is the joint session past empty?
     fn joint_session_past_is_empty(&self, frame_id_root: FrameId) -> bool {
         self.full_frame_tree_iter(frame_id_root)
             .all(|frame| frame.prev.is_empty())
     }
 
@@ -1709,26 +1701,26 @@ impl<Message, LTF, STF> Constellation<Me
 
         let mut size = 0;
         let mut table = HashMap::new();
 
         match direction {
             TraversalDirection::Forward(delta) => {
                 for entry in self.joint_session_future(top_level_frame_id).take(delta) {
                     size = size + 1;
-                    table.insert(entry.frame_id, entry);
+                    table.insert(entry.frame_id, entry.clone());
                 }
                 if size < delta {
                     return debug!("Traversing forward too much.");
                 }
             },
             TraversalDirection::Back(delta) => {
                 for entry in self.joint_session_past(top_level_frame_id).take(delta) {
                     size = size + 1;
-                    table.insert(entry.frame_id, entry);
+                    table.insert(entry.frame_id, entry.clone());
                 }
                 if size < delta {
                     return debug!("Traversing back too much.");
                 }
             },
         }
 
         for (_, entry) in table {
--- a/servo/components/constellation/lib.rs
+++ b/servo/components/constellation/lib.rs
@@ -15,16 +15,17 @@ extern crate compositing;
 extern crate debugger;
 extern crate devtools_traits;
 extern crate euclid;
 #[cfg(not(target_os = "windows"))]
 extern crate gaol;
 extern crate gfx;
 extern crate gfx_traits;
 extern crate ipc_channel;
+extern crate itertools;
 extern crate layout_traits;
 #[macro_use]
 extern crate log;
 extern crate msg;
 extern crate net;
 extern crate net_traits;
 extern crate offscreen_gl_context;
 extern crate profile_traits;