3 ms·
Modern computers are ridiculously fast. V8 JIT compiler can produce pretty fast native code for hot paths. Thus all together allows JS perform surprisingly wel
by nine_k 4y ago
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.
- tomsmeding 4y agoI'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)
- micheleriva 4y agoThe 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