Re:Lyra: Fast, in-memory, typo-tolerant, full-text search en...
by nine_k on Monday August 01, 2022 @07:48AM
(#32304670)
Modern computers are ridiculously fast. V8 JIT compiler can produce pretty fast native code for hot paths.
Thus all together allows JS perform surprisingly well in the vanilla case, even using simple algorithms. I wonder how much faster could one make the lookup by e.g. using a typed array to represent the trie and the index; that would be cache-friendly.
Re:Lyra: Fast, in-memory, typo-tolerant, full-text search en...
by tomsmeding on Monday August 01, 2022 @08:11AM
(#32304870)
I'm less surprised about the fact that JS can be fast, and more that a vanilla trie can be fast and (hopefully) resource-efficient; I had the impression that any scalable index would need to compact the trie in some manner (i.e. combining multiple characters in one node) or do other algorithmic improvements that I don't know about. (That's why I looked at the code, to find those -- but I didn't really find any)
Re:Lyra: Fast, in-memory, typo-tolerant, full-text search en...
by micheleriva on Monday August 01, 2022 @08:58AM
(#32305298)
The current release of Lyra is treating the trie structure as a tree (of course), but we're planning to start approaching it as a graph for the exact reason you're mentioning. We don't have performance comparisons yet, but we'll document everything
The readme says that the trie has some tricks to make it fast; the only such trick that I could find is "fast properties", which seems to be a JS-specific thing to make object property access faster (something with promoting an ad-hoc object to a prototype, which presumably enjoys more optimisation in JS engines).
Hence I'm sort-of surprised that this performs well! If a simple trie is sufficient for that, I might go forward with implementing search for some of my other stuff just like that.