Issue 3673 - Merge closely matching rules

abp2blocklist.js

Index: abp2blocklist.js
===================================================================
--- a/abp2blocklist.js
+++ b/abp2blocklist.js
@@ -17,17 +17,17 @@
 
 "use strict";
 
 let readline = require("readline");
 let Filter = require("filterClasses").Filter;
 let ContentBlockerList = require("./lib/abp2blocklist.js").ContentBlockerList;
 
 var rl = readline.createInterface({input: process.stdin, terminal: false});
-var blockerList = new ContentBlockerList();
+var blockerList = new ContentBlockerList({merge: true, exhaustiveMerge: true});

[Sebastian Noack, 2017/05/21 21:07:29]

Any particular reason why we even make these configurable, and not always merge
the rules as good as we can?

[kzar, 2017/05/22 08:47:01]

Well the exhaustiveMerge option makes sense, since turning that on slows things
down quite a bit and we probably don't want to do that for Safari users where
the rules are being generated on their end. I agree about the merge option
however, I can't see why wouldn't ever want it. I guess maybe it's useful for
the tests?

[Manish Jethani, 2017/05/22 09:28:28]

Yes, the exhaustive merge gives us 5-10% extra gains, but at a significant cost,
it's not feasible to run that in the browser as it freezes the browser (the user
sees the beachball icon and can't do anything for a while).

The merge being an option, that's useful for the unit tests for now (we can fix
this), but also the Safari client might want to pass false here if the rule set
is already going to be within the 50,000-rule limit. This is true for the
default option (EasyList+AA) already. Skipping the merge just makes it a snappy
user experience.

I still think we can do more in terms of user experience by doing the merge in
stages, using a generator for example.

  function* mergeRules(rules)
  {
    // Merge some rules
    yield rules;
    // Merge some more rules
    yield rules;
    ...
  }

  ...

  let iterator = mergeRules(rules);
  setTimeout(function iterate() {
    let next = mergeRules.next();
    rules = next.value;
    if (!next.done)
      setTimeout(iterate, interval);
    else
      addRulesToSafari(rules);
  }, interval);

This will do it in stages so it won't freeze the browser.

[Sebastian Noack, 2017/05/22 09:39:25]

On the other hand, the Safari extension is currently mostly effected by the 50k
rules limit, hence would mostly benefit from these improvements, since we don't
even offer other filter lists in the iOS app yet.

As for the performance, it would be helpful if somebody could share some
benchmarks comparing the performance with an without (exhaustive) merging.
Well, if we'd always merge the rules, I suppose, there is no reason to consider
not merging rules in the tests.

[Sebastian Noack, 2017/05/22 09:54:57]

Oh, if Safari entirely freezes, that should be avoided of course. I already
thought about doing the conversion into a WebWorker, but the problem with that
approach would be to get the bulk of filter data into the worker. Using stages
seems like a better idea.

On the other hand, we are plan to replace the Safari extension with a different
product which downloads the pre-generated lists from the server anyway. So any
improvements that are limited to the current Safari extension might not be worth
it. But I guess I leave it up to you.

[Manish Jethani, 2017/05/22 17:39:52]

EasyList+AA

Non-exhaustive:

 *  Rule merging took 1530ms
 *  Before: 49,198 rules
 *  After: 43,668 rules

Exhaustive:

 *  Rule merging took 29667ms
 *  Before: 49,198 rules
 *  After: 42,794 rules

So the results improve by ~16% here if we do an exhaustive merge, but it's
totally not feasible in the browser. I mean ~1.5s vs. ~30s.

[Sebastian Noack, 2017/05/23 11:59:09]

Yeah, I think I agree. Even if we can avoid the freezing issue through using
timeouts, a delay of 30s (potentially more on slower hardware) on browser start,
extension installation, and filter change before the filters take effect would
be rather bad. So let's keep this behavior behind an option which we only use on
the server, not sure if we need two different options though.

 
 rl.on("line", line =>
 {
   if (/^\s*[^\[\s]/.test(line))
     blockerList.addFilter(Filter.fromText(Filter.normalize(line)));
 });
 
 rl.on("close", () =>