Issue 5161 - Use maps and sets where appropriate

ext/background.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-2017 eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 "use strict";
 
 (function()
 {
-  let nonEmptyPageMaps = Object.create(null);
-  let pageMapCounter = 0;
+  let nonEmptyPageMaps = new Set();
 
   let PageMap = ext.PageMap = function()
   {
-    this._map = Object.create(null);
-    this._id = ++pageMapCounter;
+    this._map = new Map();
   };
   PageMap.prototype = {
     _delete(id)
     {
-      delete this._map[id];
-
-      if (Object.keys(this._map).length == 0)
-        delete nonEmptyPageMaps[this._id];
+      if (this._map.delete(id) && this._map.size == 0)
+        nonEmptyPageMaps.delete(this);
     },
     keys()
     {
-      return Object.keys(this._map).map(ext.getPage);
+      return this._map.keys();
     },
     get(page)
     {
-      return this._map[page.id];
+      return this._map.get(page.id);
     },
     set(page, value)
     {
-      this._map[page.id] = value;
-      nonEmptyPageMaps[this._id] = this;
+      let prevSize = this._map.size;
+
+      this._map.set(page.id, value);
+
+      if (prevSize == 0)

[Sebastian Noack, 2017/05/17 06:46:48]

Why not just calling nonEmptyPageMaps.add() no matter what? The behavior will be
the same.

[Manish Jethani, 2017/05/17 21:53:24]

Well, add could be an expensive operation, depending on the way the Set object
has been implemented.

I actually looked this up. Both Chrome and Firefox use the Close table
implementation:

https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables

https://github.com/jorendorff/dht/blob/2d8cf136bad0fa92aeb2b7898cc59b46b471ab...

https://cs.chromium.org/chromium/src/v8/src/js/collection.js?q=generichash+pa...

https://hg.mozilla.org/mozilla-central/file/261a33fad371/js/src/ds/OrderedHas...

The add operation is "O(1)", but basically it involves a hash operation and a
lookup. The speed of the lookup depends on how many items are in the bucket,
that's a linear search at some point, but given the parameters used it's going
to be ~2.67 iterations on average and N iterations in the unlikely worst case (N
being the number of entries in the set).

I don't know how they hash an object reference, but Firefox for example will try
to "scramble" the output of the hash function if it's based on a pointer in
memory, for security reasons:

https://dxr.mozilla.org/mozilla-beta/rev/8bf3d5c1b4b0de2673a74d56c7399a80c543...

Anyway, so it's probably not too bad in the grand scheme of things. On the other
hand, these things can easily add up to a bad user experience.

Does it hurt to avoid calling that method?

nonEmptyPageMaps is a bit of a micro-optimization to begin with. I don't know if
it adds much value. It's only used in ext._removeFromAllPageMaps, which is only
called for top-level frames.

[Sebastian Noack, 2017/05/18 12:23:00]

It seems there will be up to 7 PageMap objects at any given time. So I suppose
even a linear search over all entries would still be ridicolous fast.
It's additional logic, which makes the code harder to maintain.

Also notice that checking the size of the map isn't for free either. So perhaps
you want to benchmark this code with and without checking for the map being
empty, with a realistic number of entries in nonEmptyPageMaps (i.e. 7).
nonEmptyPageMaps is not a micro-optimization, but was an attempt to mitigate
memory leaks. But it seems we could just use a WeakSet() that holds all active
instances now.

[Manish Jethani, 2017/05/18 21:16:37]

Fair enough.
The size of the map is a value in memory, it's practically free.

Also equally relevant to the number of PageMap objects is the number of times
the set method is called.
What I really meant here was that nonEmptyPageMaps could just have been
allPageMaps, then it would only have to be updated in the constructor (a total
of about 7 times?). The only reason the program keeps track of the empty status
is to avoid calling delete on empty maps, which is exactly the kind of
optimization I'm trying to do here, only far less useful. Why not just make it
allPageMaps? Then we don't have to keep track of the empty status, hence code
that's easier to maintain.

Since there are only about 7 PageMap objects, we could just keep all of them in
memory, whether they're empty or not. We could also just make allPageMaps a
WeakSet object.

Now that I look at the code again, we could simply replace ext.PageMap with
ext.createPageMap, a function that would look like this:

  let allPageMaps = new Set(); // or WeakSet
  function createPageMap()
  {
    let pageMap = new Map();
    allPageMaps.add(pageMap);
    return pageMap;
  }

Instead of "new ext.PageMap()" you would do "ext.createPageMap()" and that would
be it.

[Sebastian Noack, 2017/05/18 21:42:12]

That is basically what I meant to suggest. However, I don't quite get why you
want to introduce a factory function, rather than having the constructor
register the instance? Also please use a WeakSet, as it doesn't add any
complexity, but is memory-safe in case we create temporary instances.

For reference, the reason I didn't do so when I initially wrote this code, and
the reason for keeping track of the non-empty PageMaps (with an array), was that
back then WeakSet wasn't there yet, and this way at least empty instances
wouldn't be leaked. Not calling delete() for these was a mere side-effect.

[Manish Jethani, 2017/05/18 22:39:09]

I was hoping to get rid of all the methods entirely since they seemed to be mere
passthroughs to the underlying Map object, but it turns out it's not that simple
because ext.PageMap deals with page objects where the underlying Map object
deals with their IDs.
We forgot that WeakSet doesn't allow iteration. We can't use it here.

JavaScript still doesn't have weak references, that's sad. We had this in AS3. I
think I had a blog post about it back in the day. Anyway, looks like weak
references are coming in ES2017 or something.

[Sebastian Noack, 2017/05/19 12:01:14]

Hmm, perhaps we should have stayed with the nonEmptyPageMap approach then. This
way we at least make sure that temporary instances get eventually cleaned up
when all pages they held are gone.

I just carefully checked all places that use a PageMap and it seems all
instances are created once and never go out of scope. So while this shouldn't
cause a memory leaks with the current code base, I'm mildly concerned we might
have a use case for temporary instances in the future, and whoever might
introduce these might not be aware that PageMaps are leaked.

Eventually, I want to get rid of the abstraction layer, i.e. ext.*, including
PageMaps, all together, and have all code use the chrome.* (or browser.*) API
and tabIds directly. The only reason we have this abstraction layer was so that
we could support Safari, however, we no longer support anything else than
Chrome, Firefox and Edge which all have roughly the same API, with this code.

[Manish Jethani, 2017/05/19 16:20:34]

Yeah, I wasn't too excited about this change either after I learnt that we
couldn't use a WeakSet. I've reverted it now and removed the unnecessary logic
as well.
I see, thanks.

When I feel like I know enough about the code, I'll see if I can come up with
something for this.

[Sebastian Noack, 2017/05/19 17:33:14]

That'd be awesome. :)

+        nonEmptyPageMaps.add(this);
     },
     has(page)
     {
-      return page.id in this._map;
+      return this._map.has(page.id);
     },
     clear()
     {
-      for (let id in this._map)
-        this._delete(id);
+      if (this._map.size == 0)
+        return;
+
+      this._map.clear();
+      nonEmptyPageMaps.delete(this);
     },
     delete(page)
     {
       this._delete(page.id);
     }
   };
 
   ext._removeFromAllPageMaps = pageId =>
   {
-    for (let pageMapId in nonEmptyPageMaps)
-      nonEmptyPageMaps[pageMapId]._delete(pageId);
+    for (let pageMap of nonEmptyPageMaps)
+      pageMap._delete(pageId);
   };
 
   /* Pages */
 
   let Page = ext.Page = function(tab)
   {
     this.id = tab.id;
     this._url = tab.url && new URL(tab.url);
 
     this.browserAction = new BrowserAction(tab.id);
     this.contextMenus = new ContextMenus(this);
   };
   Page.prototype = {
     get url()
     {
       // usually our Page objects are created from Chrome's Tab objects, which
       // provide the url. So we can return the url given in the constructor.
       if (this._url)
         return this._url;
 
       // but sometimes we only have the tab id when we create a Page object.
       // In that case we get the url from top frame of the tab, recorded by
       // the onBeforeRequest handler.
-      let frames = framesOfTabs[this.id];
+      let frames = framesOfTabs.get(this.id);
       if (frames)
       {
-        let frame = frames[0];
+        let frame = frames.get(0);
         if (frame)
           return frame.url;
       }
     },
     sendMessage(message, responseCallback)
     {
       chrome.tabs.sendMessage(this.id, message, responseCallback);
     }
   };
 
@@ skipping 44 matching lines @@
   };
 
   chrome.tabs.onUpdated.addListener((tabId, changeInfo, tab) =>
   {
     if (changeInfo.status == "loading")
       ext.pages.onLoading._dispatch(new Page(tab));
   });
 
   function createFrame(tabId, frameId)
   {
-    let frames = framesOfTabs[tabId];
+    let frames = framesOfTabs.get(tabId);
     if (!frames)
-      frames = framesOfTabs[tabId] = Object.create(null);
+    {
+      frames = new Map();
+      framesOfTabs.set(tabId, frames);
+    }
 
-    let frame = frames[frameId];
+    let frame = frames.get(frameId);
     if (!frame)
-      frame = frames[frameId] = {};
+    {
+      frame = {};
+      frames.set(frameId, frame);
+    }
 
     return frame;
   }
 
   function updatePageFrameStructure(frameId, tabId, url, parentFrameId)
   {
     if (frameId == 0)
     {
       let page = new Page({id: tabId, url});
 
       ext._removeFromAllPageMaps(tabId);
 
       chrome.tabs.get(tabId, () =>
       {
         // If the tab is prerendered, chrome.tabs.get() sets
         // chrome.runtime.lastError and we have to dispatch the onLoading event,
         // since the onUpdated event isn't dispatched for prerendered tabs.
         // However, we have to keep relying on the unUpdated event for tabs that
         // are already visible. Otherwise browser action changes get overridden
         // when Chrome automatically resets them on navigation.
         if (chrome.runtime.lastError)
           ext.pages.onLoading._dispatch(page);
       });
     }
 
-    // Update frame parent and URL in frame structure
+    // Update frame URL and parent in frame structure
     let frame = createFrame(tabId, frameId);
     frame.url = new URL(url);
-    frame.parent = framesOfTabs[tabId][parentFrameId] || null;
+
+    let parentFrame = framesOfTabs.get(tabId).get(parentFrameId);
+    if (parentFrame)
+      frame.parent = parentFrame;
   }
 
   chrome.webRequest.onHeadersReceived.addListener(details =>
   {
     // We have to update the frame structure when switching to a new
     // document, so that we process any further requests made by that
     // document in the right context. Unfortunately, we cannot rely
     // on webNavigation.onCommitted since it isn't guaranteed to fire
     // before any subresources start downloading[1]. As an
     // alternative we use webRequest.onHeadersReceived for HTTP(S)
@@ skipping 78 matching lines @@
       updatePageFrameStructure(details.frameId, details.tabId, details.url,
                                details.parentFrameId);
     }
   });
 
   function forgetTab(tabId)
   {
     ext.pages.onRemoved._dispatch(tabId);
 
     ext._removeFromAllPageMaps(tabId);
-    delete framesOfTabs[tabId];
+    framesOfTabs.delete(tabId);
   }
 
   chrome.tabs.onReplaced.addListener((addedTabId, removedTabId) =>
   {
     forgetTab(removedTabId);
   });
 
   chrome.tabs.onRemoved.addListener(forgetTab);
 
   chrome.tabs.onActivated.addListener(details =>
@@ skipping 177 matching lines @@
 
   chrome.windows.onFocusChanged.addListener(windowId =>
   {
     if (windowId != chrome.windows.WINDOW_ID_NONE)
       updateContextMenu();
   });
 
 
   /* Web requests */
 
-  let framesOfTabs = Object.create(null);
+  let framesOfTabs = new Map();
 
   ext.getFrame = (tabId, frameId) =>
   {
-    return (framesOfTabs[tabId] || {})[frameId];
+    let frames = framesOfTabs.get(tabId);
+    return frames && frames.get(frameId);
   };
 
   let handlerBehaviorChangedQuota =
     chrome.webRequest.MAX_HANDLER_BEHAVIOR_CHANGED_CALLS_PER_10_MINUTES;
 
   function propagateHandlerBehaviorChange()
   {
     // Make sure to not call handlerBehaviorChanged() more often than allowed
     // by chrome.webRequest.MAX_HANDLER_BEHAVIOR_CHANGED_CALLS_PER_10_MINUTES.
     // Otherwise Chrome notifies the user that this extension is causing issues.
@@ skipping 24 matching lines @@
   };
 
   chrome.tabs.query({}, tabs =>
   {
     tabs.forEach(tab =>
     {
       chrome.webNavigation.getAllFrames({tabId: tab.id}, details =>
       {
         if (details && details.length > 0)
         {
-          let frames = framesOfTabs[tab.id] = Object.create(null);
+          let frames = new Map();
+          framesOfTabs.set(tab.id, frames);
 
-          for (let i = 0; i < details.length; i++)
+          for (let detail of details)
+            frames.set(detail.frameId, {url: new URL(detail.url)});
+
+          for (let detail of details)
           {
-            frames[details[i].frameId] = {
-              url: new URL(details[i].url),
-              parent: null
-            };
-          }
-
-          for (let i = 0; i < details.length; i++)
-          {
-            let {parentFrameId} = details[i];
+            let {parentFrameId} = detail;
 
             if (parentFrameId != -1)
-              frames[details[i].frameId].parent = frames[parentFrameId];
+              frames.get(detail.frameId).parent = frames.get(parentFrameId);
           }
         }
       });
     });
   });
 
   chrome.webRequest.onBeforeRequest.addListener(details =>
   {
     // The high-level code isn't interested in requests that aren't
     // related to a tab or requests loading a top-level document,
@@ skipping 36 matching lines @@
 
     // Add "page" and "frame" if the message was sent by a content script.
     // If sent by popup or the background page itself, there is no "tab".
     if ("tab" in rawSender)
     {
       sender.page = new Page(rawSender.tab);
       sender.frame = {
         url: new URL(rawSender.url),
         get parent()
         {
-          let frames = framesOfTabs[rawSender.tab.id];
+          let frames = framesOfTabs.get(rawSender.tab.id);
 
           if (!frames)
             return null;
 
-          let frame = frames[rawSender.frameId];
+          let frame = frames.get(rawSender.frameId);
           if (frame)
-            return frame.parent;
+            return frame.parent || null;

[Sebastian Noack, 2017/05/17 06:46:48]

Any particular reason you force the return value to be null rather than
undefined?

[Manish Jethani, 2017/05/17 21:53:24]

Just for consistency, nothing else.

 
-          return frames[0];
+          return frames.get(0) || null;
         }
       };
     }
 
     return ext.onMessage._dispatch(
       message, sender, sendResponse
     ).indexOf(true) != -1;
   });
 
 
@@ skipping 90 matching lines @@
   ext.windows = {
     create(createData, callback)
     {
       chrome.windows.create(createData, createdWindow =>
       {
         afterTabLoaded(callback)(createdWindow.tabs[0]);
       });
     }
   };
 }());