Optmize filter list in elemHide.js for memory usage

lib/elemHide.js

 /*
  * This file is part of Adblock Plus <http://adblockplus.org/>,
  * Copyright (C) 2006-2014 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
@@ skipping 12 matching lines @@
 
 let {Utils} = require("utils");
 let {IO} = require("io");
 let {Prefs} = require("prefs");
 let {ElemHideException} = require("filterClasses");
 let {FilterNotifier} = require("filterNotifier");
 let {AboutHandler} = require("elemHideHitRegistration");
 let {TimeLine} = require("timeline");
 
 /**
- * List of all filters. Index is used as key.
+ * Array of filters, index as "key".
+ * @type Array
+ */
+let filters = [];
+/**
+ * Lookup table, keys of the filters by filter text.
+ * Can be null.
  * @type Object
  */
-let filters = [];
+let keyByFilter = new Map();
 
 /**
  * Lookup table, keys are known element hiding exceptions
  * @type Object
  */
 let knownExceptions = {__proto__: null};
 
 /**
  * Lookup table, lists of element hiding exceptions by selector
  * @type Object
  */
 let exceptions = {__proto__: null};
 
 /**
  * Currently applied stylesheet URL
  * @type nsIURI
  */
 let styleURL = null;
+
+/**
+ * Filters removed since last compact operation
+ * @type number
+ */
+let filtersRemoved = 0;
 
 /**
  * Element hiding component
  * @class
  */
 let ElemHide = exports.ElemHide =
 {
   /**
    * Indicates whether filters have been added or removed since the last apply() call.
    * @type Boolean
@@ skipping 30 matching lines @@
     TimeLine.log("done determining stylesheet URL");
 
     TimeLine.leave("ElemHide.init() done");
   },
 
   /**
    * Removes all known filters
    */
   clear: function()
   {
+    dump("clear\n");
+    keyByFilter = null;
     filters = [];
     knownExceptions = {__proto__: null};
     exceptions = {__proto__: null};
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
   add: function(filter)
   {
     if (filter instanceof ElemHideException)
     {
       if (filter.text in knownExceptions)
         return;
 
       let selector = filter.selector;
       if (!(selector in exceptions))
         exceptions[selector] = [];
       exceptions[selector].push(filter);
       knownExceptions[filter.text] = true;
     }
     else
     {
+      this._ensureFilterMap();
+
+      if (keyByFilter.has(filter.text))
+        return;
+
       filters.push(filter);
-      // XXX: Maybe check for duplicate filters?
-      // That would require searching through all filters,
-      // and in almost all cases there won't be any duplicates ...
+      keyByFilter.set(filter.text, filters.length - 1);
+
       ElemHide.isDirty = true;
     }
   },
 
   /**
    * Removes an element hiding filter
    * @param {ElemHideFilter} filter
    */
   remove: function(filter)
   {
     if (filter instanceof ElemHideException)
     {
       if (!(filter.text in knownExceptions))
         return;
 
       let list = exceptions[filter.selector];
       let index = list.indexOf(filter);
       if (index >= 0)
         list.splice(index, 1);
       delete knownExceptions[filter.text];
     }
     else
     {
-      let index = filters.indexOf(filter);
-      if (index < 0)
+      this._ensureFilterMap();
+
+      let key = keyByFilter.get(filter.text);
+      if (key === undefined)
         return;
-      filters[index] = undefined; // Indicates deleted.

[Wladimir Palant, 2014/04/08 11:24:53]

This won't work correctly if the filter is duplicated.

I'm also concerned that the array length might get very large after a bunch of
filter subscription updates (each update removes all existing filters and adds
the new filters). Not sure about the impact it would have on memory but it would
definitely increase the time required to iterate over that array.

-
+
+      keyByFilter.delete(filter.text);
+      filters[key] = null;
       ElemHide.isDirty = true;
-    }
+      filtersRemoved += 1;
+    }
+  },
+
+  /**
+   * Clean up and compact memory after filters
+   * are removed.
+   */
+  compact: function()
+  {
+    if (filtersRemoved == 0) {
+      return;
+    }
+
+    if (filtersRemoved == 1) {
+      for (let i = 0; i < filters; i++) {
+        if (filters[i] === null)
+          filters.splice(i, 1);
+      }
+    } else {
+      let newList = [];
+      for (let filter in filters) {
+        if (filter)
+          newList.push(filter);
+      }
+      filters = newList;
+    }
+
+    filtersRemoved = 0;
+  },
+
+  /**
+   * Ensure that we have a map of filter text to key.
+   * Might have to recreate it from the array of filters.
+   */
+  _ensureFilterMap: function()
+  {
+    if (keyByFilter)
+      return;
+
+    keyByFilter = new Map();
+    for (let i = 0; i < filters.length; i++)
+      keyByFilter.set(filters[i].text, i);
   },
 
   /**
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
    */
   getException: function(/**Filter*/ filter, /**String*/ docDomain) /**ElemHideException*/
   {
     let selector = filter.selector;
     if (!(filter.selector in exceptions))
@@ skipping 52 matching lines @@
       else if (!Prefs.enabled && ElemHide.applied)
       {
         ElemHide.unapply();
         TimeLine.log("ElemHide.unapply() finished");
       }
 
       TimeLine.leave("ElemHide.apply() done (no file changes)");
       return;
     }
 
-    IO.writeToFile(styleURL.file, false, this._generateCSSContent(), function(e)
+    IO.writeToFile(styleURL.file, this._generateCSSContent(), function(e)
     {
       TimeLine.enter("ElemHide.apply() write callback");
       this._applying = false;
 
-      if (e && e.result == Cr.NS_ERROR_NOT_AVAILABLE)
-        IO.removeFile(styleURL.file, function(e2) {});
+      // _generateCSSContent is throwing NS_ERROR_NOT_AVAILABLE to indicate that
+      // there are no filters. If that exception is passed through XPCOM we will
+      // see a proper exception here, otherwise a number.
+      let noFilters = (e == Cr.NS_ERROR_NOT_AVAILABLE || (e && e.result == Cr.NS_ERROR_NOT_AVAILABLE));
+      if (noFilters)
+      {
+        e = null;
+        IO.removeFile(styleURL.file, function(e) {});
+      }
       else if (e)
         Cu.reportError(e);
 
       if (this._needsApply)
       {
         this._needsApply = false;
         this.apply();
       }
-      else if (!e || e.result == Cr.NS_ERROR_NOT_AVAILABLE)
+      else if (!e)
       {
         ElemHide.isDirty = false;
 
         ElemHide.unapply();
         TimeLine.log("ElemHide.unapply() finished");
 
-        if (!e)
+        if (!noFilters)
         {
           try
           {
             Utils.styleService.loadAndRegisterSheet(styleURL, Ci.nsIStyleSheetService.USER_SHEET);
             ElemHide.applied = true;
           }
           catch (e)
           {
             Cu.reportError(e);
           }
           TimeLine.log("Applying stylesheet finished");
         }
 
         FilterNotifier.triggerListeners("elemhideupdate");
       }
       TimeLine.leave("ElemHide.apply() write callback done");
     }.bind(this), "ElemHideWrite");
 
     this._applying = true;
 
     TimeLine.leave("ElemHide.apply() done", "ElemHideWrite");
   },
 
   _generateCSSContent: function()
   {
+    // We don't need keyByFilter anymore now, if we need it again,
+    // e.g. because of a subscription change, we will regenerate it.
+    keyByFilter = null;
+
     // Grouping selectors by domains
     TimeLine.log("start grouping selectors");
     let domains = {__proto__: null};
     let hasFilters = false;
-    let seen = [];
-    for (let i = 0; i < filters.length; i++)
-    {
-      let filter = filters[i];
-      if (!filter)
-        continue;
-
-      // Lazily de-duplicate filters.
-      if (seen.indexOf(filter) >= 0) {

[tschuster, 2014/04/04 13:17:45]

I am afraid this piece of code is causing noticeable problems when enabling
adblock. We might actually never get duplicates because of the way
Filter.fromText works. (It always looks up in knownFilters first)

[Wladimir Palant, 2014/04/08 11:24:53]

In fact, we are very likely to see duplicates - the same filter will be added
multiple times. An example scenario: somebody has EasyList Germany+EasyList and
EasyPrivacy+EasyList as filter subscriptions. This means that each filter from
EasyList is duplicated in both subscriptions and will be added twice.

Why not use an object or map for seen here? It will be freed immediately anyway.

-        filters[i] = undefined;
-        continue;
-      } else {
-        seen.push(filter);
-      }
-
+    for (let key = 0; key < filters.length; key++)
+    {
+      let filter = filters[key];
       let domain = filter.selectorDomain || "";
 
       let list;
       if (domain in domains)
         list = domains[domain];
       else
       {
         list = {__proto__: null};
         domains[domain] = list;
       }
-      list[filter.selector] = i;
+      list[filter.selector] = key;
       hasFilters = true;
     }
     TimeLine.log("done grouping selectors");
 
     if (!hasFilters)
       throw Cr.NS_ERROR_NOT_AVAILABLE;
 
     function escapeChar(match)
     {
       return "\\" + match.charCodeAt(0).toString(16) + " ";
@@ skipping 45 matching lines @@
    * Retrieves the currently applied stylesheet URL
    * @type String
    */
   get styleURL() ElemHide.applied ? styleURL.spec : null,
 
   /**
    * Retrieves an element hiding filter by the corresponding protocol key
    */
   getFilterByKey: function(/**String*/ key) /**Filter*/
   {
-    return filters[key] || null;
+    return (key < filters.length ? filters[key] : null);
   },
 
   /**
    * Returns a list of all selectors active on a particular domain (currently
    * used only in Chrome).
    */
   getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly)
   {
     let result = [];
-    for (let i = 0; i < filters.length; i++)
-    {
-      let filter = filters[i];
+    for (let filter of filters)
+    {
+      if (!filter)
+        continue
+
       if (specificOnly && (!filter.domains || filter.domains[""]))
         continue;
 
       if (filter.isActiveOnDomain(domain) && !this.getException(filter, domain))
         result.push(filter.selector);
     }
     return result;
   }
 };