Performance: two_percent is faster and more efficient than fzf
#561
Comments
|
Just curious. Is there a reason why you can't/won't merge these changes back into skim? |
As I stated in my post:
My experience has been that this project is not actively maintained. I think I still have PRs outstanding: https://github.com/lotabout/skim/pulls/kimono-koans. If anyone wants to assist, and contribute here, I'd help. If no one else is so inclined, right now, I'll just keep developing in my own fork/branch. |
|
Just curious, what's the reason for the name "two_percent"? It's kinda hard to remeber (as in, what it does) and also to recommend to folks... |
|
In the US, at least, we sell milk with different percentages of milk fat. If you install |
|
Have you also implemented fzf-like color option parsing? I am very used to having some elements of the ui in Edit: I tried |
No, I haven't done any work re this, but I already see bold colors in my view? See: https://asciinema.org/a/637475 |
|
Hi @kimono-koans we'd be happy to work with you to merge your improvements back into Skim ! Please tell us if you are interested |
Maybe the white looks a little bit whiter, but that isn't bold as in bold. |
Once you start merging new things, I'll perhaps work on some commits for upstream. |
|
With this release, we should have some "quiet time" to start progressively merging your branch if you'd like |
|
I don't see much point in measuring the performance of v1 algorithm, because it is rarely used in practice. fzf does switch to it if an item is very long, but only for that item, and the rest of the items in the list are processed using the default algorithm. This switching happens when M * N > 102400, where M is the length of the query, and N is the length of an item. So for the query Also, please consider benchmarking against the latest version of fzf because the performance of fzf has improved a lot. |
|
Pretty cool that we got @junegunn to comment, huh?
This is very true as you'll see below. To @LoricAndre and As you can see below, the last, Note, I am using my own rudimentary fuzzy find algorithm as well, but you can see the more general performance improvements in the I'd be pleased to begin merging my code back into One issue I see is that my methods are/were pretty hacky, compared to the right way to reduce memory usage, here, which is by using a string interner, but that would probably require an API break. If you're looking at doing something like that, I'll continue no further. Next, my priorities may be different than yours/the project's. One goal is reduce long term memory usage, and allow for multiple invocations of So, philosophically, I don't know, but I hope we are on the same page. If not, I'd be pleased to allow others to merge my code as they see fit, and/or assist by directing them to where the bodies are. |
|
@kimono-koans Thanks for following up. Out of curiosity, I cloned your repository, built it ( unset FZF_DEFAULT_OPTS
QUERY=hopscotchbubblehopscotchbubble
for input in github8 github32; do
du -sh $input
wc -l $input
hyperfine -i -m 20 -w 3 "./sk --query=$QUERY --exit-0 < $input" "fzf --query=$QUERY --exit-0 < $input"
done
The result was quite different from yours. Maybe it depends on the characteristics of the input and the query? Or am I doing something wrong? I noticed skim was a bit unstable that it would sometimes hang, I had to restart |
@junegunn: I didn't want to call you, sir! I think all of us respect what you've done with But... so long as we're just having fun, my branch is called My test corpus is: https://github.com/benhoyt/countwords/blob/master/kjvbible.txt You'll need to concatenate it together 10x: No, I don't think the above is a reasonable test of what a fuzzy finder should do, but the Rust version must go faster, so I've tried to make it do so. While I have you here, could you give a brief summary of your v2 algo function and what makes it so good? I'm very interested in how it is so fast and so good. Thank you. |
|
I'd love to discuss your changes and how we can make skim faster. I'm not sure I want hacky changes to be merged here, but skim is still in v0 and we can allow ourselves some minor API changes (as was the case for the first few PRs when I took over). |
When I say "hacky", I mean adding a string interner is the "correct" solution to our problem, but I can't imagine implementing without blowing up much of
Some of my prior PRs addressed this. See specifically: #505 That's another thing -- re: my prior PRs, although most are performance focused, I did add a few features, and I'll need the This shouldn't be too much of a problem because this is a feature At the end of this, I need |
|
About the disabled option, the PR was missing both tests and documentation, would you be able to reopen it with these elements against the current version of skim ? Your changes in |
Seems I had a deadlock caused by one thread trying to read an atomic bool, while I updated it from another thread. Had no idea this was even possible in Rust! I've created a new version: https://github.com/kimono-koans/two_percent/releases/tag/0.12.10 This is against the default Thanks! |
Pleased to resubmit the disabled feature with tests and docs. |
Thank you.
I can confirm that it no longer hangs.
Thanks for clarification. But even with that, I'm getting vastly different numbers. ~/github/two_percent/target/release/sk --version
fzf --version
unset FZF_DEFAULT_OPTS
QUERY=hopscotchbubblehopscotchbubble
for input in kjvbible_x10.txt github16 github32; do
echo ----------
wc $input
echo ----------
hyperfine -i -m 20 -w 3 \
"~/github/two_percent/target/release/sk --query=$QUERY --exit-0 < $input" \
"fzf --query=$QUERY --exit-0 < $input"
done
I'm not convinced a Rust implementation "must be faster" than a highly optimized Go implementation, when the latter was carefully crafted to minimize GC overhead, avoid memory copies, and leverage SIMD operations, etc. PGO can also make some difference. fzf implements a modified version of Smith-Waterman algorithm. It's an O(nm) DP algorithm as I mentioned above, but in fzf, it's O(n) when the pattern doesn't match the item. But anyway, I think we're at the point where the performance arms race doesn't matter much. Because they're all good enough for most everyday use cases. These days, I've mostly focused on the usability and extensibility aspects of fzf, not so much on performance. |
You have to use a different algorithm for search, or set via an env var:
Agreed. My statement was meant, again, mostly as a joke. Although I do think it's important that any Rust fuzzy finder must make an effort to go faster than
Agreed. |
If the reason you're not using
skimis raw performance, my branch,two_percent, is faster, more efficient and uses less memory thanfzffor largish inputs (40MB):If anyone else is interested in performance improvements, and refactoring to reduce long term memory usage, I've been building on
skimactively and I am eager to work with others who are similarly inclined.Re: @lotabout 's wonderful comment re: performance:
For ordinary text inputs, I'm using
Arc<Box<str>>which I think is 32B? If there is some way to useArc<str>, that would be even better but I can't seem to make it work re: traits. Re: my 10x duplicated KJV Bible 43M-ish corpus, the memory usage is about 90M on my Mac.On ingest, I have a method for deduplicating lines. This is a significant performance win for inputs with lots of empty or the same lines.
Algorithm switching is broken in the latest version. This is fixed in mine. I have a
simplealgorithm which is much closer to thefzfv1 algo used for large inputs. See above. You too can now write your own super, simple algo or improve mine!I've made a few changes which may help.
My experience has been that ingest was not reading in enough bytes at once, and other threads were spinning wait on the lock.
The text was updated successfully, but these errors were encountered: