Issue 7267 - Optimize memory layout of filter domain maps in matcher

lib/matcher.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 222 matching lines @@
 
     for (let type of nonDefaultTypes(filter.contentType))
     {
       let map = this._filterMapsByType.get(type);
       if (!map)
         this._filterMapsByType.set(type, map = new Map());
 
       addFilterByKeyword(filter, keyword, map);
     }
 
+    let {domains} = filter;
+
     let filtersByDomain = this._filterDomainMapsByKeyword.get(keyword);
     if (!filtersByDomain)
-      this._filterDomainMapsByKeyword.set(keyword, filtersByDomain = new Map());
+    {
+      // In most cases, there is only one pure generic filter to a keyword.
+      // Instead of Map { "foo" => Map { "" => Map { filter => true } } }, we
+      // can just reduce it to Map { "foo" => filter } and save a lot of
+      // memory.
+      if (!domains)
+      {
+        this._filterDomainMapsByKeyword.set(keyword, filter);
+        return;
+      }
 
-    for (let [domain, include] of filter.domains || defaultDomains)
+      filtersByDomain = new Map();
+      this._filterDomainMapsByKeyword.set(keyword, filtersByDomain);
+    }
+    else if (!(filtersByDomain instanceof Map))
+    {
+      filtersByDomain = new Map([["", filtersByDomain]]);
+      this._filterDomainMapsByKeyword.set(keyword, filtersByDomain);
+    }
+
+    for (let [domain, include] of domains || defaultDomains)
     {
       if (!include && domain == "")
         continue;
 
       let map = filtersByDomain.get(domain);
       if (!map)
       {
         filtersByDomain.set(domain, include ? filter :
-                              map = new Map([[filter, false]]));
+                                      map = new Map([[filter, false]]));
       }
       else if (map.size == 1 && !(map instanceof Map))
       {
         if (filter != map)
         {
           filtersByDomain.set(domain, new Map([[map, true],
                                                [filter, include]]));
         }
       }
       else
@@ skipping 27 matching lines @@
     for (let type of nonDefaultTypes(filter.contentType))
     {
       let map = this._filterMapsByType.get(type);
       if (map)
         removeFilterByKeyword(filter, keyword, map);
     }
 
     let filtersByDomain = this._filterDomainMapsByKeyword.get(keyword);
     if (filtersByDomain)
     {
+      // Because of the memory optimization in the add function, most of the
+      // time this will be a filter rather than a map.
+      if (!(filtersByDomain instanceof Map))
+      {
+        this._filterDomainMapsByKeyword.delete(keyword);
+        return;
+      }
+
       let domains = filter.domains || defaultDomains;
       for (let domain of domains.keys())
       {
         let map = filtersByDomain.get(domain);
         if (map)
         {
           if (map.size > 1 || map instanceof Map)
           {
             map.delete(filter);
 
             if (map.size == 0)
+            {
               filtersByDomain.delete(domain);
+            }
+            else if (map.size == 1)
+            {
+              for (let [lastFilter, include] of map)
+              {
+                // Reduce Map { "example.com" => Map { filter => true } } to
+                // Map { "example.com" => filter }
+                if (include)
+                  filtersByDomain.set(domain, lastFilter);
+
+                break;
+              }
+            }
           }
           else if (filter == map)
           {
             filtersByDomain.delete(domain);
           }
         }
       }
+
+      if (filtersByDomain.size == 0)
+      {
+        this._filterDomainMapsByKeyword.delete(keyword);
+      }
+      else if (filtersByDomain.size == 1)
+      {
+        for (let [lastDomain, map] of filtersByDomain)
+        {
+          // Reduce Map { "foo" => Map { "" => filter } } to
+          // Map { "foo" => filter }
+          if (lastDomain == "" && !(map instanceof Map))
+            this._filterDomainMapsByKeyword.set(keyword, map);
+
+          break;
+        }
+      }
     }
   }
 
   /**
    * Chooses a keyword to be associated with the filter
    * @param {Filter} filter
    * @returns {string} keyword or an empty string if no keyword could be found
    * @protected
    */
   findKeyword(filter)
@@ skipping 84 matching lines @@
 
     return null;
   }
 
   _checkEntryMatchByDomain(keyword, location, typeMask, docDomain, thirdParty,
                            sitekey, specificOnly, collection)
   {
     let filtersByDomain = this._filterDomainMapsByKeyword.get(keyword);
     if (filtersByDomain)
     {
-      // The code in this block is similar to the generateStyleSheetForDomain
-      // function in lib/elemHide.js.
+      // Because of the memory optimization in the add function, most of the
+      // time this will be a filter rather than a map.
+      if (!(filtersByDomain instanceof Map))
+      {
+        if (filtersByDomain.matchesWithoutDomain(location, typeMask,
+                                                 thirdParty, sitekey))
+        {
+          if (!collection)
+            return filtersByDomain;
+
+          collection.push(filtersByDomain);
+        }
+
+        return null;
+      }
 
       if (docDomain)
       {
         if (docDomain[docDomain.length - 1] == ".")
           docDomain = docDomain.replace(/\.+$/, "");
 
         docDomain = docDomain.toLowerCase();
       }
 
       let excluded = new Set();
@@ skipping 382 matching lines @@
 
 exports.CombinedMatcher = CombinedMatcher;
 
 /**
  * Shared {@link CombinedMatcher} instance that should usually be used.
  * @type {CombinedMatcher}
  */
 let defaultMatcher = new CombinedMatcher();
 
 exports.defaultMatcher = defaultMatcher;