Optimize memory layout of filter domain maps in matcher

[mjethani]

Background

In #7265 we started organizing request blocking filters by domain in lib/matcher.js. We made an optimization: if a domain has only one filter that applies to the domain, we reduce Map { "foo" => Map { "example.com" => Map { filter => true } } } to Map { "foo" => Map { "example.com" => filter } }. This optimization reduced the memory requirements for EasyList by ~10 MB.

Now we can take this a step further:

1. Out of ~19,000 blocking filters in EasyList that end up in the _filterDomainMapsByKeyword data structure, ~18,000 are pure generic filters that are the only entries for their respective keywords. For such filters, we can reduce the nesting by one more level. In other words, we can reduce Map { "foo" => Map { "" => Map { filter => true } } } all the way to Map { "foo" => filter }.
2. When a filter is removed, we can similarly readjust the data structure to minimize memory usage. For example, in Map { "foo" => Map { "" => Map { filter => true, filter => true } } }, if one of the filters is removed, the new structure should be Map { "foo" => filter }.

This change reduces the memory footprint of the extension by a further ~5 MB (EasyList only).

What to change

The changes as described above, in lib/matcher.js, in the add and remove methods of the Matcher class.

Also see ​patch.

Hints for testers

Same as #7265.

[abpbot]

A commit referencing this issue has landed:
​Issue 7267 - Optimize memory layout of filter domain maps in matcher

[mjethani]

This changed caused a regression. I have filed #7312.

[Ross]

Done. Working as described in #7265.

ABP 0.9.15.2340
Microsoft Edge 44.17763.1.0 / Windows 10 1809

ABP 3.5.2.2340
Chrome 49.0.2623.75 / Windows 10 1809
Chrome 75.0.3770.142 / Windows 10 1809
Opera 36.0.2130.65 / Windows 10 1809
Opera 62.0.3331.72 / Windows 10 1809
Firefox 51.0 / Windows 10 1809
Firefox 68.0 / Windows 10 1809
Firefox Mobile 68.0 / Android 7.2.2