News for hackers. Stuff that matters.
Re:Inside Wade, a 1kb search library by vanderZwan on Wednesday July 19, 2017 @02:25PM (#14806615)
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/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-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/

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.

Re:Inside Wade, a 1kb search library by kbr on Wednesday July 19, 2017 @03:43PM (#14807282)
You'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!
Re:Inside Wade, a 1kb search library by olivernn on Wednesday July 19, 2017 @04:21PM (#14807545)
Using `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?

Re:Inside Wade, a 1kb search library by vanderZwan on Wednesday July 19, 2017 @05:08PM (#14807954)
That 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-velocit...

Re:Inside Wade, a 1kb search library by tomsmeding on Wednesday July 19, 2017 @04:55PM (#14807817)
Not 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.