Optmize filter list in elemHide.js for memory usage

lib/elemHide.js

Index: lib/elemHide.js
===================================================================
--- a/lib/elemHide.js
+++ b/lib/elemHide.js
@@ -25,26 +25,20 @@ 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");
 
 /**
- * Lookup table, filters by their associated key
+ * List of all filters. Index is used as key.
  * @type Object
  */
-let filterByKey = {__proto__: null};
-
-/**
- * Lookup table, keys of the filters by filter text
- * @type Object
- */
-let keyByFilter = {__proto__: null};
+let filters = [];
 
 /**
  * Lookup table, keys are known element hiding exceptions
  * @type Object
  */
 let knownExceptions = {__proto__: null};
 
 /**
@@ -103,18 +97,17 @@ let ElemHide = exports.ElemHide =
     TimeLine.leave("ElemHide.init() done");
   },
 
   /**
    * Removes all known filters
    */
   clear: function()
   {
-    filterByKey = {__proto__: null};
-    keyByFilter = {__proto__: null};
+    filters = [];
     knownExceptions = {__proto__: null};
     exceptions = {__proto__: null};
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
 
   /**
    * Add a new element hiding filter
@@ -130,26 +123,20 @@ let ElemHide = exports.ElemHide =
       let selector = filter.selector;
       if (!(selector in exceptions))
         exceptions[selector] = [];
       exceptions[selector].push(filter);
       knownExceptions[filter.text] = true;
     }
     else
     {
-      if (filter.text in keyByFilter)
-        return;
-
-      let key;
-      do {
-        key = Math.random().toFixed(15).substr(5);
-      } while (key in filterByKey);
-
-      filterByKey[key] = filter;
-      keyByFilter[filter.text] = key;
+      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 ...
       ElemHide.isDirty = true;
     }
   },
 
   /**
    * Removes an element hiding filter
    * @param {ElemHideFilter} filter
    */
@@ -163,22 +150,21 @@ let ElemHide = exports.ElemHide =
       let list = exceptions[filter.selector];
       let index = list.indexOf(filter);
       if (index >= 0)
         list.splice(index, 1);
       delete knownExceptions[filter.text];
     }
     else
     {
-      if (!(filter.text in keyByFilter))
+      let index = filters.indexOf(filter);
+      if (index < 0)
         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.

 
-      let key = keyByFilter[filter.text];
-      delete filterByKey[key];
-      delete keyByFilter[filter.text];
       ElemHide.isDirty = true;
     }
   },
 
   /**
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
    */
@@ -295,30 +281,42 @@ let ElemHide = exports.ElemHide =
   },
 
   _generateCSSContent: function()
   {
     // Grouping selectors by domains
     TimeLine.log("start grouping selectors");
     let domains = {__proto__: null};
     let hasFilters = false;
-    for (let key in filterByKey)
+    let seen = [];
+    for (let i = 0; i < filters.length; i++)
     {
-      let filter = filterByKey[key];
+      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);
+      }
+
       let domain = filter.selectorDomain || "";
 
       let list;
       if (domain in domains)
         list = domains[domain];
       else
       {
         list = {__proto__: null};
         domains[domain] = list;
       }
-      list[filter.selector] = key;
+      list[filter.selector] = i;
       hasFilters = true;
     }
     TimeLine.log("done grouping selectors");
 
     if (!hasFilters)
       throw Cr.NS_ERROR_NOT_AVAILABLE;
 
     function escapeChar(match)
@@ -374,29 +372,29 @@ let ElemHide = exports.ElemHide =
    */
   get styleURL() ElemHide.applied ? styleURL.spec : null,
 
   /**
    * Retrieves an element hiding filter by the corresponding protocol key
    */
   getFilterByKey: function(/**String*/ key) /**Filter*/
   {
-    return (key in filterByKey ? filterByKey[key] : null);
+    return 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 key in filterByKey)
+    for (let i = 0; i < filters.length; i++)
     {
-      let filter = filterByKey[key];
+      let filter = filters[i];
       if (specificOnly && (!filter.domains || filter.domains[""]))
         continue;
 
       if (filter.isActiveOnDomain(domain) && !this.getException(filter, domain))
         result.push(filter.selector);
     }
     return result;
   }