Issue 6562 - Remove filter keys from the element hiding code

lib/elemHide.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-present 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 34 matching lines @@
  */
 let unconditionalSelectors = null;
 
 /**
  * Map to be used instead when a filter has a blank domains property.
  */
 let defaultDomains = new Map([["", true]]);
 
 /**
  * Set containing known element hiding and exception filters
- * @type {Set.<string>}

[Manish Jethani, 2018/04/27 12:39:36]

This is really {Set.<ElemHideBase>}

[kzar, 2018/04/30 10:11:46]

Done.

+ * @type {Set.<ElemHideBase>}
  */
 let knownFilters = new Set();

[Manish Jethani, 2018/04/27 12:39:36]

I wonder if we should make this a WeakSet since we never need to iterate over
it. We are holding on to the filter references elsewhere?

[kzar, 2018/04/30 10:11:46]

I considered that as well but we keep a reference to exceptions in the
exceptions lookup, the rest in filtersByDomain and filtersBySelector anyway. If
we remove the filter from those lookups but not from this one then we've got a
bug.

(We do iterate over this in the tests, not that that's a good reason to avoid
making this a WeakSet.)

 
 /**
  * Lookup table, lists of element hiding exceptions by selector
  * @type {Map.<string,Filter>}
  */
 let exceptions = new Map();
 
 /**
  * Container for element hiding filters
  * @class
@@ skipping 11 matching lines @@
     }
     unconditionalSelectors = null;
     FilterNotifier.emit("elemhideupdate");
   },
 
   _addToFiltersByDomain(filter)
   {
     let domains = filter.domains || defaultDomains;
     for (let [domain, isIncluded] of domains)
     {
+      // There's no need to note that a filter is generically disabled.
+      if (!isIncluded && domain == "")
+        continue;
+
       let filters = filtersByDomain.get(domain);
       if (!filters)
         filtersByDomain.set(domain, filters = new Map());
       filters.set(filter, isIncluded);
     }
   },
 
   /**
    * Add a new element hiding filter
-   * @param {ElemHideFilter} filter

[Manish Jethani, 2018/04/27 12:39:36]

This is really {ElemHideBase}

[kzar, 2018/04/30 10:11:46]

Well spotted, Done.

+   * @param {ElemHideBase} filter
    */
   add(filter)
   {
     if (knownFilters.has(filter))
       return;
 
     if (filter instanceof ElemHideException)
     {
       let {selector} = filter;
       let list = exceptions.get(selector);
@@ skipping 24 matching lines @@
       // The new filter's selector only applies to some domains
       this._addToFiltersByDomain(filter);
     }
 
     knownFilters.add(filter);
     FilterNotifier.emit("elemhideupdate");
   },
 
   /**
    * Removes an element hiding filter
-   * @param {ElemHideFilter} filter

[Manish Jethani, 2018/04/27 12:39:36]

This is really {ElemHideBase}

+   * @param {ElemHideBase} filter
    */
   remove(filter)
   {
     if (!knownFilters.has(filter))
       return;
 
     // Whitelisting filters
     if (filter instanceof ElemHideException)
     {
       let list = exceptions.get(filter.selector);
       let index = list.indexOf(filter);
       if (index >= 0)
         list.splice(index, 1);
     }
     // Unconditially applied element hiding filters
-    else if (filterBySelector.get(filter.selector) === filter)
+    else if (filterBySelector.get(filter.selector) == filter)
     {
       filterBySelector.delete(filter.selector);
       unconditionalSelectors = null;
     }
     // Conditionally applied element hiding filters
     else
     {
       let domains = filter.domains || defaultDomains;
       for (let domain of domains.keys())
       {
@@ skipping 71 matching lines @@
   getSelectorsForDomain(domain, criteria)
   {
     let selectors = [];
 
     if (typeof criteria == "undefined")
       criteria = ElemHide.ALL_MATCHING;
     if (criteria < ElemHide.NO_UNCONDITIONAL)
       selectors = this.getUnconditionalSelectors();
 
     let specificOnly = (criteria >= ElemHide.SPECIFIC_ONLY);
-    let seenFilters = new Set();
+    let excluded = new Set();
     let currentDomain = domain ? domain.toUpperCase() : "";
+
+    // This code is a performance hot-spot, which is why we've made certain
+    // micro-optimisations. Please be careful before making changes.
     while (true)
     {
       if (specificOnly && currentDomain == "")
         break;
 
       let filters = filtersByDomain.get(currentDomain);
       if (filters)
       {
         for (let [filter, isIncluded] of filters)

[Manish Jethani, 2018/04/27 12:39:36]

Just a thought, but I wonder if we could do this (I haven't thought this
through):

  let excludedFilterSets = [];
  while (true)
  {
    excludedFilterSets.push(excludedFiltersByDomain.get(currentDomain));

    for (let filter of includedFiltersByDomain.get(currentDomain))
    {
      for (let set of excludedFilterSets)
      {
        if (set.has(filter))
        {
          filter = null;
          break;
        }
      }

      if (filter && !this.getException(filter, domain))
        selectors.push(filter.selector);
    }

    ...
  }

So I think this is the idea you were toying with, I see it now. We could have
two sets, one for excluded and one for included. I'm not sure if this is better
though. It would mean fewer iterations but more set lookups. Ultimately it
depends on the kinds of filters we have.

[Manish Jethani, 2018/04/27 12:41:58]

Anyway, I'm all for not changing things here as part of this patch.

[kzar, 2018/04/27 17:01:50]

On 2018/04/27 12:39:36, Manish Jethani wrote: 
Exactly, that's what I was playing with. Except perhaps we would have to keep
track of the already seen included filters as well if we want to keep behaviour
the same... but not sure it matters.

I'm also not clear this is a change worth making, I could see aspects of both
which are nicer. Maintaining two sets would also have (even) more complexity for
the filter adding and removing code.
Yea, I don't want to do it for now I think. Well unless I can be convinced it's
clearly better! What do you think?

[Manish Jethani, 2018/04/28 16:22:17]

That's what excludedFilterSets in the above code snippet was.

Anyway, I did some tests, the performance seems to improve for EasyList. Here's
the patch I tested:

https://codereview.adblockplus.org/29764555/
So I think filter adding and removing happens less often than lookups for
filters by domain, which means the lookup code should perform better.
It seems to be better. Let's take this discussion to the other patch that I've
uploaded. This one can focus on the original issue.

[kzar, 2018/04/30 10:11:46]

Well no, excludedFilterSets contained the excluded filters so far. I was talking
about the included filters so far.
 
Thanks for looking into it some more. You mention the performance improving,
could you share how you tested and the numbers?
 
Interesting insight.

[Manish Jethani, 2018/04/30 17:55:21]

Let's do that as part of the other patch.

         {
-          if (seenFilters.has(filter))
-            continue;
-          seenFilters.add(filter);
-
-          if (isIncluded && !this.getException(filter, domain))
+          if (!isIncluded)
+          {
+            excluded.add(filter);
+          }
+          else if ((excluded.size == 0 || !excluded.has(filter)) &&
+                   !this.getException(filter, domain))
+          {
             selectors.push(filter.selector);
+          }
         }
       }
 
       if (currentDomain == "")
         break;
 
       let nextDot = currentDomain.indexOf(".");
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
     return selectors;
   }
 };