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 68 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);

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

I think we should change this to:

  if (domain || isIncluded)
    filters.set(filter, isIncluded);

I don't see why we would add an entry if the key is an empty string and the
value is false. It is not necessary, it doesn't do anything.

[kzar, 2018/05/01 16:13:59]

Good point, you're right and I checked and this applies to quite a lot of
filters in practice. Done, except I've made it explicit + avoided a pointless
filtersByDomain lookup.

     }
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideBase} filter
    */
   add(filter)
   {
     if (knownFilters.has(filter))
@@ skipping 46 matching lines @@
 
     // 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/30 17:55:21]

So your comment about included vs excluded filters makes me wonder why we should
add included filters to the seenFilters set. Isn't it really just about keeping
track of exceptions on a subdomain? e.g. ~no.example.com,example.com##foo.
Should we really care if there's a filter like cool.example.com,example.com##foo
and it ends up causing the function to slow down and have the selector included
more than once?

I think maybe it's a good idea to change it to this:

  for (let [filter, isIncluded] of filters)
  {
    if (!isIncluded)
    {
      seenFilters.add(filter);
    }
    else if (!seenFilters.has(filter) &&
             !this.getException(filter, domain))
    {
      selectors.push(filter.selector);
    }
  }

Can you think of a case where this would break?

[kzar, 2018/05/01 16:13:59]

This is pretty much the same point you made on your review[1]. It's interesting,
but I'm not sure either way about it yet. Regardless I don't see the point of
making this change here, I'd rather save that discussion for your review.

[1] -
https://codereview.adblockplus.org/29764555/diff/29764556/lib/elemHide.js#new...

[Manish Jethani, 2018/05/02 12:28:11]

Fair enough.

In that case, do you think it makes sense to check if currentDomain is non-empty
before adding the filter to the seenFilters set?

  if (currentDomain != "")
    seenFilters.add(filter);

Adding to a set also has some cost, we're not going to look up those entries
since we'll be exiting the loop. Since there are so many generic filters
typically, it should help if we skipped that operation for generic filters. It
might also make the lookup faster. Think about it, for a random domain there are
no domain-specific filters and no exceptions, it's just a bunch of generic
filters. A lookup in an empty set should be instantaneous.

[Manish Jethani, 2018/05/02 12:57:34]

I just checked here and with just EasyList enabled the set is populated with
~1,100 entries that are then never looked up. By adding that check we reduce the
size of the set to 0.

I also checked if it helps to check the size before doing a lookup:

  (function ()
  {
    let set = new Set();

    let count = 0;
    let start = Date.now();

    for (let i = 0; i < 10000000; i++)
    {
      if (set.size > 0 && set.has("foo"))
        count++;

      //if (Math.random() < .01)
      //  set.add("foo");
    }

    console.log("time:", Date.now() - start);
    console.log("count:", count);
  })();

The performance improves drastically if we check the value of the size property
before doing a lookup, if the set is empty. If the set is not empty, the
performance doesn't seem to degrade if we check the size property (uncomment the
two lines so the set gets populated).

So I think our checks should be:

  if (seenFilters.size > 0 && seenFilters.has(filter))
    continue;

  if (currentDomain != "")
    seenFilters.add(filter);

[kzar, 2018/05/02 16:45:38]

You make some good points and I think on reflection you're probably right about
there not being much use in ignoring filters that were previously included.
Done.

         {
-          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 == "")

[Manish Jethani, 2018/05/02 12:57:34]

I'm wondering if we should update these checks:

  if (!currentDomain)
    break;

[kzar, 2018/05/02 16:45:39]

Well I think it's generally a good idea to check the value you mean rather than
just falsey... not that I always do that to be honest. Anyway I've tweaked the
logic here so we're checking the domain string much less now.

[Manish Jethani, 2018/05/02 18:11:40]

OK, the Mozilla style guide, which we refer to, advises to do truthy/falsey
checks unless there's a chance of confusion [1] and I think we've pretty much
followed this everywhere else in the code.

[1]:
https://developer.mozilla.org/en-US/docs/Mozilla/Developer_guide/Coding_Style...

[kzar, 2018/05/03 15:36:00]

I prefer checking for an empty string specifically in this code, I think it
makes it easier to grok.

[Manish Jethani, 2018/05/04 11:59:55]

Acknowledged.

         break;
 
       let nextDot = currentDomain.indexOf(".");
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
     return selectors;
   }
 };