3rd-gen HNTrie

[gorhill]

A placeholder reference issue to document the code change related to 3rd-generation HNTrie -- will flesh out as time allow.

The main goal of 3rd-generation HNTrie is to be usable as a replacement of Set() for large collection of hostnames -- the 1st- and 2nd-gen versions of HNTrie were not designed to replace the use of Set() in FilterHostnameDict.

Pure-hostname filters -- stored in FilterHostnameDict -- are the most common static network filters. For instance, all filters in a hosts file are pure hostname ones. With default filter lists, there are many instances of FilterHostnameDict, with the largest holding over 34,000 distinct hostnames.

[gorhill]

Forgot to reference the issue in the commit message: gorhill/uBlock@1b6fea1

New benchmark page for the 3rd-gen hntrie which is suitable to be used for large set of hostnames -- thus can be used in place of a Set(): https://raw.githack.com/gorhill/uBlock/master/docs/tests/hnbigset-benchmark.html.

Transcribing results from my side, the dictionary creation benchmark:

Create dictionaries

Firefox 65.0 on Linux 64-bit:
  -                         Set-based x 209 ops/sec ±5.17% (57 runs sampled)
  -           Trie-based JS (3rd-gen) x 32.71 ops/sec ±0.46% (44 runs sampled)
  -         Trie-based WASM (3rd-gen) x 40.64 ops/sec ±0.71% (43 runs sampled)
  - Trie-based unserialized (3rd-gen) x 1,955 ops/sec ±0.24% (66 runs sampled)

Chrome 70.0.3538.77 on Ubuntu Chromium 64-bit.
  -                         Set-based x 187 ops/sec ±3.35% (56 runs sampled)
  -           Trie-based JS (3rd-gen) x 37.14 ops/sec ±0.69% (49 runs sampled)
  -         Trie-based WASM (3rd-gen) x 42.01 ops/sec ±0.55% (45 runs sampled)
  - Trie-based unserialized (3rd-gen) x 2,320 ops/sec ±0.73% (16 runs sampled)

Firefox Mobile 65.0 on Mobile (Android 8.0.0):
  -                         Set-based x 27.61 ops/sec ±13.22% (30 runs sampled)
  -           Trie-based JS (3rd-gen) x 11.87 ops/sec ±1.16% (30 runs sampled)
  -         Trie-based WASM (3rd-gen) x 13.03 ops/sec ±0.38% (32 runs sampled)
  - Trie-based unserialized (3rd-gen) x 1,425 ops/sec ±2.50% (50 runs sampled)

Reminder: creation occurs at filter list load time, thus a one-time sort of event. Look-up operations (below) occur multiple time for every single network request being inspected.

Regarding "Trie-based unserialized": it is meant to be used in the selfie-loading code, which will be a big improvement compared to the current use of a Set() object to hold all the hostnames.

The "look-up" benchmark:

Test 100 needles against 8 dictionaries with size between 2 and 45752 hostnames

Firefox 65.0 on Linux 64-bit:
 -                     Set-based x 3,468 ops/sec ±1.57% (61 runs sampled)
 -       Trie-based JS (3rd-gen) x 8,709 ops/sec ±1.06% (64 runs sampled)
 -     Trie-based WASM (3rd-gen) x 11,929 ops/sec ±1.10% (64 runs sampled)

Chrome 70.0.3538.77 on Ubuntu Chromium 64-bit.
  -                     Set-based x 6,972 ops/sec ±1.83% (63 runs sampled)
  -       Trie-based JS (3rd-gen) x 8,829 ops/sec ±2.87% (55 runs sampled)
  -     Trie-based WASM (3rd-gen) x 10,899 ops/sec ±1.60% (65 runs sampled)

Firefox Mobile 65.0 on Mobile (Android 8.0.0):
  -                     Set-based x 1,122 ops/sec ±19.63% (31 runs sampled)
  -       Trie-based JS (3rd-gen) x 3,581 ops/sec ±0.42% (54 runs sampled)
  -     Trie-based WASM (3rd-gen) x 4,446 ops/sec ±0.45% (54 runs sampled)

I expect memory usage benefits as well, I will look into this below as time allow.

[gorhill]

I would like to keep the comments section for developer notes focused on noteworthy information. Unless the relative results in your benchmarks differ significantly from my posted relative results, there is no point posting your results, this will just end up drowning key information for whoever come here from the release notes to inquire about the details of the issue.

[joey04]

This looks to be a very good change, expanding the use of Hntrie from just $domain= fields to a large collection of pure hostname rules.

Are you also planning on using 3rd-gen tries for the many hostname rules of EasyList and EasyPrivacy? Almost all of them have some sort of field, including the large collection of $third-party hostnames.

(And sorry for my off-topic posts last night. I now realize that the other benchmark test is not that relevant here, since it's only for buckets up to 1000 hostnames.)

[gorhill]

including the large collection of $third-party hostnames

There are many instances of FilterHostnameDict in uBO, including one specifically for pure hostnames with third-party option. Anything that can be reduced to a pure hostname from a pattern-matching perspective will be put into one of the FilterHostnameDict instances (third-party, script, important, etc. or a combination of any of these options).

[joey04]

I patched your commits from yesterday into my fork, including the new Hntrie JS version (Wasm disabled). I decided to do a stress test in a throwaway profile to ensure it's working properly. And it does indeed. I imported several large Hosts lists resulting in about 130k total of these rules, all stored in a very large trie. (Plus another 70k rules from the Easys, uAssets, and Adguard.) I went to a number of request-heavy sites and everything worked well. No problems.

(Note to readers: My real static rulesets are only about 50k total. I don't use any Hosts lists. That was purely for testing this new 3rd-gen trie.)

I'm now running the new JS hntrie in both of my real Firefox profiles. Everything is good. You do excellent quality work, gorhill!

[gorhill]

Baseline memory usage improvements after launch (waited 3 minutes with browser idle) -- I used Chromium (linux 64-bit) as it makes it easy to measure.

No selfie, default filter lists -- uBO 1.17.4 vs. uBO 1.17.5b2 ("dev" in pic):

Selfie, default filter lists -- uBO 1.17.4 vs. uBO 1.17.5b2 ("dev" in pic):

So roughly more than 4MB saved with the new FilterHostnameDict.

The peak memory at launch (transient) appears higher with the new HNTrie. However this settles quickly (within seconds) to the baseline memory usage seen in pics. uBO will remember the size of the HNTrie from the last session and will re-allocate that size for the next session, so as to avoid costly numerous re-allocations as the HNTrie buffer grows.

Expect larger memory saving with larger FilterHostnameDict instances, i.e. with more filter lists, especially the ones which are solely list of hostnames (like hosts files) -- but probably also higher transient peak usage at launch due to larger HNTrie buffer.

There is still place for performance improvement in 3rd-gen HNTrie (ordering of cells in the OR branch), but that is for the future.