7 ms·
It just so happens that I've been working on trying to build the fastest possible trie implementation in JavaScript to speed up `lz-string` and potentially `js-
by vanderZwan 9y ago
It just so happens that I've been working on trying to build the fastest possible trie implementation in JavaScript to speed up `lz-string` and potentially `js-search`. The whole process I went through is too much to write down here, but you can basically read it here:
https://github.com/pieroxy/lz-string/pull/98 https://github.com/pieroxy/lz-string/pull/98
https://github.com/bvaughn/js-search/issues/42 https://github.com/bvaughn/js-search/issues/42
The short version is: replace those single-char strings with the result of `charCodeAt()`, and then use `charCodeAt()` during search too. The reason is that integer key lookup is much faster than string key lookup:
https://stackoverflow.com/questions/10639488/faster-to-access-numeric-property-by-string-or-integer/10639526#10639526 https://stackoverflow.com/questions/10639488/faster-to-acces...
It's important that all of your keys are integers though, so the trick is to actually store/look up `charCodeAt()+1`, and then store the indices at key 0.
If you feel like taking a risk, you can make a slightly more complicated data structure where you replace the object with an array and do a linear search:
https://jsfiddle.net/vanderZwan/ccfxv4sg/1/ https://jsfiddle.net/vanderZwan/ccfxv4sg/1/
For most data this is the fastest, because the array will only be a handful of characters (except at the root). However, in certain special cases (specifically, if you have a lot of unique characters at the root) it becomes prohibitively slow.
- kbr 9y agoYou're right, there are still a ton of optimizations I can do. I'll check out all of these links, thanks for the great tips!
- olivernn 9y agoUsing `charCodeAt()` for numeric keys is an interesting optimisation, I'm definitely going to try that out with Lunr.js. I'm also interested in _why_ that is quicker though, aren't all object keys converted to strings anyway?
- tomsmeding 9y agoNot if they can reasonably be an array. I believe that the integer keys of an object are usually stored in an array in V8 unless they grow really large, or something.
- vanderZwan 9y agoThat is what the spec says, but one way to interpret that is to say that they only have to behave as if they were. Hashing an integer or double can be much simpler than hashing a string, and like the other comment said: for small enough keys you might even get away with using an array. edit: to give another example, the spec also says all number are doubles, and yet all JS modern engines use optimisations in places where it can guarantee a value is a 32-bit integer; in some cases adding `|0` (a forced truncation by bitmask-or zero) as a compiler hint can speed up code. edit2: this is also part of why you want your objects to be as type-stable as possible (it also makes code less bug-prone that way because easier to reason about). This includes the shape of objects. See these slides from 2011: https://www.slideshare.net/newmovie/know-yourengines-velocity2011/126-Typestable_JS_examples_Typestable_NOT https://www.slideshare.net/newmovie/know-yourengines-velocit...