Lyra: Fast, in-memory, typo-tolerant, full-text search engine in TypeScript
github.com
github.com
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.
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.
Damerau-Levenshtein is a significant upgrade from the default Levenshtein algorithm used as it also picks up the very common transposition error much more efficiently for not a lot of extra code.
https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_di...
Typed arrays would also probable speed thing up quite a bit.
Tokenizing may not be faster. Set the first row of weights to ZERO. When you're done, look for the lowest value in the final array. This also saves the trouble of trying to tokenize properly for every language as it's only concerned with the bytes themselves.
https://stackoverflow.com/questions/8139958/algorithm-to-fin...
Performance of that algorithm also suffers a LOT with very long strings. For those, we went with one more like the fuzzy search used in Sublime text. Basically, you iterate the string one time and look for the search characters to appear in order. To go more advanced add a weight to each match type. Stuff like consecutive characters that match, cases match, or immediately transposed characters next to each other give higher weights to the resulting string.
https://www.forrestthewoods.com/blog/reverse_engineering_sub... (this looks like a decent overview of sublime fuzzy search).
https://www.lloydatkinson.net/posts/2022/writing-a-fuzzy-sea...
I might make a branch to try out Lyra and compare results.
1. System APIs (including fetch, etc) are entirely different from Node. Probably not relevant for this library though
2a. CommonJS-style imports/exports aren't supported; you have to use proper ES imports/exports
2b. Import paths must include the file extension, which non-Deno JS/TS often doesn't do
3. You don't use a package manager to install Deno dependencies; you import the source directly from the local file system or from a remote URL. The good news is this includes GitHub URLs! But the bad news is that eg. any transitive dependencies listed in a package.json won't be found
So... it's usually easy to port a project to Deno, but few NPM projects are compatible out of the box
One workaround that can often be used for points 2 and 3 is to load the package through something like Skypack (https://www.skypack.dev/), which will theoretically turn the whole thing into an ES module. But sometimes, depending on the library, there may still be weird issues
The sooner we can ship all libraries as ES modules by default, the better!
It's quite straightforward for simple use cases (small corpus, no typo tolerance, no fuzzing, etc.)
Probably something to do with being designed to run as part of a web browser. :)
It is possible to write very fast js, but it's hard to write very fast idiomatic js
The biggest problem I have with TypeScript is to know WHAT .ts files will be compiled into. I.e., if you're using enums or decorators, there's no plain support for them in JS so you'll end up having some kind of "polyfills", which are not so optimized.
Once you analyze your compiled JS, you can write TS knowing what you're gonna get, which is the trick to make it optimized.
My two cents :)
Decorators, yeah, I can imagine that’d end up interesting.
As a matter of fact, I have a similar module in my applications, e.g. for typo resistant searching through help docs and hierarchical menus.
Minor nitpick: JS/V8 beats Go in most benchmarks that are relevant for search.
JS is the outlier here however, because of the insane amount of optimizations that made it perform so unreasonably well, despite being an interpreted language.
I.e. specifically regex, which is highly relevant in searching through strings: https://github.com/mariomka/regex-benchmark
And the always interesting techempower Project, which leaves the implementation to participants of each round. https://www.techempower.com/benchmarks/#section=data-r21&tes...
Choose whatever category you wish there, js is faster then go in almost all categories there.
Even though I said it before, I'm going to repeat myself as I expect you to ignore my previous message: the language doesn't make any implementation fast or slow. You can have a well performing search engine in go and JS. The performance difference will most likely not be caused by the language with these two choices. And the same will apply with C/Rust. The language won't make the engine performant and creating a maximally performant search engine is hard. But a theoretically perfect implementation would likely be fastest in C/Rust, followed by the usual suspects such as Go/Java/C#/JS and finally ending with all other interpreted languages such as ruby and python
The techempower benchmarks seem geared towards http backend server frameworks. There's only one Javascript framework that scores well, "just-js", but that's a bit low-level for a framework. I don't think it says much about text search performance.
> the language doesn't make any implementation fast or slow
Not ignoring that, but I think it's half true (you can't have a well performing app in native Python, basically, but a bad implementation will also cost a lot of performance). JS is fast enough for most tasks, that's true.
I think some languages are much easier to make things fast in than others. Even if the theoretical limit is the same (or nearly the same) in all languages.
Messing up somewhere in Javascript with async isn’t unlikely.