5 ms·

> The original prototype was to develop an idea I had about using jump indices in a TypedArray for quickly matching hostnames (or more generally strings)[1]. On

> The original prototype was to develop an idea I had about using jump indices in a TypedArray for quickly matching hostnames (or more generally strings)[1]. Once I had a working, un-optimized prototype, I realized I had ended up with something formally named a "trie": <https://en.wikipedia.org/wiki/Trie> https://en.wikipedia.org/wiki/Trie>, hence the name. I have no idea whether the implementation here or one resembling it has been done elsewhere. So I heavily experimented with squeezing performance out of a JS-based trie-implementation for LZString[0]. Back then some early experimentation suggested that using TypedArrays was likely to be slower than using objects with numerical keys, and for non-degenerate input using a trie based on plain arrays and indexOf calls was the fastest[1]. However, it's been a while since I looked at those numbers (and I suspect that with uBlock's use case look-up performance matters more than insertion performance, which makes it very different from LZString's). But it should be obvious that HNTrie's implementation[2] is something I'm very interested in ;). [0] https://github.com/pieroxy/lz-string/pull/98 https://github.com/pieroxy/lz-string/pull/98 [1] https://github.com/pieroxy/lz-string/blob/ba8988028d78962ebadee42cc6d4b17581605e2d/lz-string-unsafe.js https://github.com/pieroxy/lz-string/blob/ba8988028d78962eba... [2] https://github.com/gorhill/uBlock/blob/2a91a685ce3d2dae5d3c285cff1bc74a1982be74/src/js/hntrie.js https://github.com/gorhill/uBlock/blob/2a91a685ce3d2dae5d3c2...

vanderZwan 8y ago
Addendum: to clarify, with "non-degenerate input" I mean that for the vast majority of nodes in the resulting trie we have a handful of charCodes to search through at most. This holds true for most normal types of text. It is however trivial to create string that breaks this assumption: make one that features every legal UTF16 charCode. Throwing this at lzstring-unsafe.js will freeze it. So this could be another assumption that does not hold for uBlock's use case.
kodablah 8y ago
The idea I had a year ago [0] was to bake the host names inside of WASM with hardcoded character lookups. You can build WASM from inside JS easily enough, or in other ways, and just ship hostnames.wasm with the product. Maybe I should revisit the idea with benchmarks. 0 - https://github.com/cretz/software-ideas/issues/68 https://github.com/cretz/software-ideas/issues/68
gorhill 8y ago
> So I heavily experimented with squeezing performance out of a JS-based trie-implementation for LZString. Incidentally, I did write a JS/WASM version of LZ4 block encoding[1] (also used in uBO). I do wonder if it could be of interest for the LZString project. My understanding is that the output of LZ4 compression would need to be further processed to make it JS string-friendly (for localStorage purpose). Maybe worth exploring if even with that extra step[2], the performance gain if any is worth it? [1] https://github.com/gorhill/lz4-wasm https://github.com/gorhill/lz4-wasm [2] Encode 7 bytes into 8 valid ASCII characters?
- vanderZwan 8y ago
  Dman. So how many awesome things do you casually do on the side just in the name of improving uBlock?
  - vanderZwan 8y ago
    *Damn.
mazirian 8y ago
I believe I saw similar results comparing typed arrays vs simple objects with numerical keys when doing this refactor[0] at least in V8. In my case case multiple child keys may match so I need to scan them instead of indexOf but otherwise it sounds similar. Also didn't see benefits from turning non-branching paths into arrays, maybe due to fairly shallow trees. I've also used a very simple trie implementation for public-suffix tree matching in my own extension[1] so interested in what the current best way to implement this sort of thing is in JS. [0]https://github.com/yahoo/ycb/pull/54 https://github.com/yahoo/ycb/pull/54 [1]https://github.com/billdorn/cookiekiller https://github.com/billdorn/cookiekiller

vanderZwan 8y ago

Addendum: to clarify, with "non-degenerate input" I mean that for the vast majority of nodes in the resulting trie we have a handful of charCodes to search through at most. This holds true for most normal types of text. It is however trivial to create string that breaks this assumption: make one that features every legal UTF16 charCode. Throwing this at lzstring-unsafe.js will freeze it. So this could be another assumption that does not hold for uBlock's use case.

kodablah 8y ago

The idea I had a year ago [0] was to bake the host names inside of WASM with hardcoded character lookups. You can build WASM from inside JS easily enough, or in other ways, and just ship hostnames.wasm with the product. Maybe I should revisit the idea with benchmarks. 0 - https://github.com/cretz/software-ideas/issues/68 https://github.com/cretz/software-ideas/issues/68

gorhill 8y ago

> So I heavily experimented with squeezing performance out of a JS-based trie-implementation for LZString. Incidentally, I did write a JS/WASM version of LZ4 block encoding[1] (also used in uBO). I do wonder if it could be of interest for the LZString project. My understanding is that the output of LZ4 compression would need to be further processed to make it JS string-friendly (for localStorage purpose). Maybe worth exploring if even with that extra step[2], the performance gain if any is worth it? [1] https://github.com/gorhill/lz4-wasm https://github.com/gorhill/lz4-wasm [2] Encode 7 bytes into 8 valid ASCII characters?

vanderZwan 8y ago
Dman. So how many awesome things do you casually do on the side just in the name of improving uBlock?
- vanderZwan 8y ago
  *Damn.

mazirian 8y ago

I believe I saw similar results comparing typed arrays vs simple objects with numerical keys when doing this refactor[0] at least in V8. In my case case multiple child keys may match so I need to scan them instead of indexOf but otherwise it sounds similar. Also didn't see benefits from turning non-branching paths into arrays, maybe due to fairly shallow trees. I've also used a very simple trie implementation for public-suffix tree matching in my own extension[1] so interested in what the current best way to implement this sort of thing is in JS. [0]https://github.com/yahoo/ycb/pull/54 https://github.com/yahoo/ycb/pull/54 [1]https://github.com/billdorn/cookiekiller https://github.com/billdorn/cookiekiller