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");
 
 /**
- * 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};
 
 /**
  * Lookup table, lists of element hiding exceptions by selector
  * @type Object
@@ skipping 48 matching lines @@
     TimeLine.log("done determining stylesheet URL");
 
     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
    * @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
     {
-      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
    */
   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
     {
-      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.
    */
   getException: function(/**Filter*/ filter, /**String*/ docDomain) /**ElemHideException*/
   {
@@ skipping 106 matching lines @@
 
     TimeLine.leave("ElemHide.apply() done", "ElemHideWrite");
   },
 
   _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)
     {
       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 (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;
   }
 };