Rework image_cache_task to avoid using `url` as key during the loading of an image.

A `url` can be very large, in particular if it is a data: url, so using it as a key for lookups whenever we load a few bytes is not a very good idea. This patch introduces an intermediate `LoadKey` (internally, an u64) that makes hashmap lookups faster. Somewhere along the way, we also get rid of a few calls to `url.clone()`.

1 files changed, 151 insertions, 41 deletions

diff --git a/components/net/image_cache_task.rs b/components/net/image_cache_task.rs
index 42e82006674..5fe9ed02e97 100644
--- a/components/net/image_cache_task.rs
+++ b/components/net/image_cache_task.rs
@@ -24,25 +24,34 @@ use util::taskpool::TaskPool;
 ///
 /// TODO(gw): Remaining work on image cache:
 ///     * Make use of the prefetch support in various parts of the code.
-///     * Experiment with changing the image 'key' from being a url to a resource id
-///         This might be a decent performance win and/or memory saving in some cases (esp. data urls)
 ///     * Profile time in GetImageIfAvailable - might be worth caching these results per paint / layout task.
 ///
+/// MAYBE(Yoric):
+///     * For faster lookups, it might be useful to store the LoadKey in the DOM once we have performed a first load.
 
 /// Represents an image that is either being loaded
 /// by the resource task, or decoded by a worker thread.
 struct PendingLoad {
+    // The bytes loaded so far. Reset to an empty vector once loading
+    // is complete and the buffer has been transmitted to the decoder.
     bytes: Vec<u8>,
+
+    // Once loading is complete, the result of the operation.
     result: Option<Result<(), String>>,
     listeners: Vec<ImageListener>,
+
+    // The url being loaded. Do not forget that this may be several Mb
+    // if we are loading a data: url.
+    url: Arc<Url>
 }
 
 impl PendingLoad {
-    fn new() -> PendingLoad {
+    fn new(url: Arc<Url>) -> PendingLoad {
         PendingLoad {
             bytes: vec!(),
             result: None,
             listeners: vec!(),
+            url: url,
         }
     }
 
@@ -51,6 +60,88 @@ impl PendingLoad {
     }
 }
 
+// Represents all the currently pending loads/decodings. For
+// performance reasons, loads are indexed by a dedicated load key.
+struct AllPendingLoads {
+    // The loads, indexed by a load key. Used during most operations,
+    // for performance reasons.
+    loads: HashMap<LoadKey, PendingLoad>,
+
+    // Get a load key from its url. Used ony when starting and
+    // finishing a load or when adding a new listener.
+    url_to_load_key: HashMap<Arc<Url>, LoadKey>,
+
+    // A counter used to generate instances of LoadKey
+    keygen: LoadKeyGenerator,
+}
+
+// Result of accessing a cache.
+#[derive(Eq, PartialEq)]
+enum CacheResult {
+    Hit,  // The value was in the cache.
+    Miss, // The value was not in the cache and needed to be regenerated.
+}
+
+impl AllPendingLoads {
+    fn new() -> AllPendingLoads {
+        AllPendingLoads {
+            loads: HashMap::new(),
+            url_to_load_key: HashMap::new(),
+            keygen: LoadKeyGenerator::new(),
+        }
+    }
+
+    // `true` if there is no currently pending load, `false` otherwise.
+    fn is_empty(&self) -> bool {
+        assert!(self.loads.is_empty() == self.url_to_load_key.is_empty());
+        self.loads.is_empty()
+    }
+
+    // get a PendingLoad from its LoadKey. Prefer this to `get_by_url`,
+    // for performance reasons.
+    fn get_by_key_mut(&mut self, key: &LoadKey) -> Option<&mut PendingLoad> {
+        self.loads.get_mut(key)
+    }
+
+    // get a PendingLoad from its url. When possible, prefer `get_by_key_mut`.
+    fn get_by_url(&self, url: &Url) -> Option<&PendingLoad> {
+        self.url_to_load_key.get(url).
+            and_then(|load_key|
+                self.loads.get(load_key)
+                )
+    }
+
+    fn remove(&mut self, key: &LoadKey) -> Option<PendingLoad> {
+        self.loads.remove(key).
+            and_then(|pending_load| {
+                self.url_to_load_key.remove(&pending_load.url).unwrap();
+                Some(pending_load)
+            })
+    }
+
+    fn get_cached(&mut self, url: Arc<Url>) -> (CacheResult, LoadKey, &mut PendingLoad) {
+        match self.url_to_load_key.entry(url.clone()) {
+            Occupied(url_entry) => {
+                let load_key = url_entry.get();
+                (CacheResult::Hit, *load_key, self.loads.get_mut(load_key).unwrap())
+            }
+            Vacant(url_entry) => {
+                let load_key = self.keygen.next();
+                url_entry.insert(load_key);
+
+                let pending_load = PendingLoad::new(url);
+                match self.loads.entry(load_key) {
+                    Occupied(_) => unreachable!(),
+                    Vacant(load_entry) => {
+                        let mut_load = load_entry.insert(pending_load);
+                        (CacheResult::Miss, load_key, mut_load)
+                    }
+                }
+            }
+        }
+    }
+}
+
 /// Represents an image that has completed loading.
 /// Images that fail to load (due to network or decode
 /// failure) are still stored here, so that they aren't
@@ -74,6 +165,26 @@ struct ImageListener {
     responder: Option<ImageResponder>,
 }
 
+// A key used to communicate during loading.
+#[derive(Eq, Hash, PartialEq, Clone, Copy)]
+struct LoadKey(u64);
+
+struct LoadKeyGenerator {
+    counter: u64
+}
+
+impl LoadKeyGenerator {
+    fn new() -> LoadKeyGenerator {
+        LoadKeyGenerator {
+            counter: 0
+        }
+    }
+    fn next(&mut self) -> LoadKey {
+        self.counter += 1;
+        LoadKey(self.counter)
+    }
+}
+
 impl ImageListener {
     fn new(sender: ImageCacheChan, responder: Option<ImageResponder>) -> ImageListener {
         ImageListener {
@@ -94,7 +205,7 @@ impl ImageListener {
 
 struct ResourceLoadInfo {
     action: ResponseAction,
-    url: Url,
+    key: LoadKey,
 }
 
 /// Implementation of the image cache
@@ -117,10 +228,10 @@ struct ImageCache {
     resource_task: ResourceTask,
 
     // Images that are loading over network, or decoding.
-    pending_loads: HashMap<Url, PendingLoad>,
+    pending_loads: AllPendingLoads,
 
     // Images that have finished loading (successful or not)
-    completed_loads: HashMap<Url, CompletedLoad>,
+    completed_loads: HashMap<Arc<Url>, CompletedLoad>,
 
     // The placeholder image used when an image fails to load
     placeholder_image: Option<Arc<Image>>,
@@ -128,7 +239,7 @@ struct ImageCache {
 
 /// Message that the decoder worker threads send to main image cache task.
 struct DecoderMsg {
-    url: Url,
+    key: LoadKey,
     image: Option<Image>,
 }
 
@@ -214,8 +325,8 @@ impl ImageCache {
                         }
                     }
                     None => {
-                        let pending_load = self.pending_loads.get(&url);
-                        Err(pending_load.map_or(ImageState::NotRequested, |_| ImageState::Pending))
+                        self.pending_loads.get_by_url(&url).
+                            map_or(Err(ImageState::NotRequested), |_| Err(ImageState::Pending))
                     }
                 };
                 consumer.send(result).unwrap();
@@ -227,26 +338,25 @@ impl ImageCache {
 
     // Handle progress messages from the resource task
     fn handle_progress(&mut self, msg: ResourceLoadInfo) {
-        match msg.action {
-            ResponseAction::HeadersAvailable(_) => {}
-            ResponseAction::DataAvailable(data) => {
-                let pending_load = self.pending_loads.get_mut(&msg.url).unwrap();
+        match (msg.action, msg.key) {
+            (ResponseAction::HeadersAvailable(_), _) => {}
+            (ResponseAction::DataAvailable(data), _) => {
+                let pending_load = self.pending_loads.get_by_key_mut(&msg.key).unwrap();
                 pending_load.bytes.push_all(&data);
             }
-            ResponseAction::ResponseComplete(result) => {
+            (ResponseAction::ResponseComplete(result), key) => {
                 match result {
                     Ok(()) => {
-                        let pending_load = self.pending_loads.get_mut(&msg.url).unwrap();
+                        let pending_load = self.pending_loads.get_by_key_mut(&msg.key).unwrap();
                         pending_load.result = Some(result);
 
                         let bytes = mem::replace(&mut pending_load.bytes, vec!());
-                        let url = msg.url.clone();
                         let sender = self.decoder_sender.clone();
 
                         self.task_pool.execute(move || {
                             let image = load_from_memory(&bytes);
                             let msg = DecoderMsg {
-                                url: url,
+                                key: key,
                                 image: image
                             };
                             sender.send(msg).unwrap();
@@ -255,10 +365,10 @@ impl ImageCache {
                     Err(_) => {
                         match self.placeholder_image.clone() {
                             Some(placeholder_image) => {
-                                self.complete_load(msg.url, ImageResponse::PlaceholderLoaded(
+                                self.complete_load(msg.key, ImageResponse::PlaceholderLoaded(
                                         placeholder_image))
                             }
-                            None => self.complete_load(msg.url, ImageResponse::None),
+                            None => self.complete_load(msg.key, ImageResponse::None),
                         }
                     }
                 }
@@ -272,50 +382,47 @@ impl ImageCache {
             None => ImageResponse::None,
             Some(image) => ImageResponse::Loaded(Arc::new(image)),
         };
-        self.complete_load(msg.url, image);
+        self.complete_load(msg.key, image);
     }
 
     // Change state of a url from pending -> loaded.
-    fn complete_load(&mut self, url: Url, image_response: ImageResponse) {
-        let pending_load = self.pending_loads.remove(&url).unwrap();
+    fn complete_load(&mut self, key: LoadKey, image_response: ImageResponse) {
+        let pending_load = self.pending_loads.remove(&key).unwrap();
 
         let completed_load = CompletedLoad::new(image_response.clone());
-        self.completed_loads.insert(url, completed_load);
+        self.completed_loads.insert(pending_load.url, completed_load);
 
         for listener in pending_load.listeners {
             listener.notify(image_response.clone());
         }
     }
 
-    // Request an image from the cache
+    // Request an image from the cache.  If the image hasn't been
+    // loaded/decoded yet, it will be loaded/decoded in the
+    // background.
     fn request_image(&mut self,
                      url: Url,
                      result_chan: ImageCacheChan,
                      responder: Option<ImageResponder>) {
         let image_listener = ImageListener::new(result_chan, responder);
+        // Let's avoid copying url everywhere.
+        let ref_url = Arc::new(url);
 
         // Check if already completed
-        match self.completed_loads.get(&url) {
+        match self.completed_loads.get(&ref_url) {
             Some(completed_load) => {
                 // It's already completed, return a notify straight away
                 image_listener.notify(completed_load.image_response.clone());
             }
             None => {
                 // Check if the load is already pending
-                match self.pending_loads.entry(url.clone()) {
-                    Occupied(mut e) => {
-                        // It's pending, so add the listener for state changes
-                        let pending_load = e.get_mut();
-                        pending_load.add_listener(image_listener);
-                    }
-                    Vacant(e) => {
-                        // A new load request! Add the pending load and request
-                        // it from the resource task.
-                        let mut pending_load = PendingLoad::new();
-                        pending_load.add_listener(image_listener);
-                        e.insert(pending_load);
-
-                        let load_data = LoadData::new(url.clone(), None);
+                let (cache_result, load_key, mut pending_load) = self.pending_loads.get_cached(ref_url.clone());
+                pending_load.add_listener(image_listener);
+                match cache_result {
+                    CacheResult::Miss => {
+                        // A new load request! Request the load from
+                        // the resource task.
+                        let load_data = LoadData::new((*ref_url).clone(), None);
                         let (action_sender, action_receiver) = ipc::channel().unwrap();
                         let response_target = AsyncResponseTarget {
                             sender: action_sender,
@@ -327,11 +434,14 @@ impl ImageCache {
                             let action: ResponseAction = message.to().unwrap();
                             progress_sender.send(ResourceLoadInfo {
                                 action: action,
-                                url: url.clone(),
+                                key: load_key,
                             }).unwrap();
                         });
                         self.resource_task.send(msg).unwrap();
                     }
+                    CacheResult::Hit => {
+                        // Request is already on its way.
+                    }
                 }
             }
         }
@@ -377,7 +487,7 @@ pub fn new_image_cache_task(resource_task: ResourceTask) -> ImageCacheTask {
             decoder_sender: decoder_sender,
             decoder_receiver: decoder_receiver,
             task_pool: TaskPool::new(4),
-            pending_loads: HashMap::new(),
+            pending_loads: AllPendingLoads::new(),
             completed_loads: HashMap::new(),
             resource_task: resource_task,
             placeholder_image: placeholder_image,