Replies: 2 comments 10 replies
|
I think you answered this yourself with your fzf-async, and also Affe uses the same model. |
|
Yeah, Thanks @minad ! I mostly studied the async implementations in consult for it. |
You can already do that with fzf (and I assumed you could with affe too), the initial query is customizable before we start filtering. I've just defaulted to a catch-all "" but you could write a command that is the 'first pass' you filter on after (https://github.com/jojojames/fzf-async/blob/09378bbf01e9290b62ea29266deda32a676f6210/fzf-async.el#L1423). There might be UX to add where the user can type more to re-trigger a new shell-command vs filtering but that's really a UX question, not really a downside of the current approach.
Agree to disagree. Maybe if it was 21M to 20M, sure, but more than double (really probably triple/quadruple if we're trying to line up when performance degrades 1:1), while being more performant/responsive and also offering a more flexible(e.g. single abc vs multi component matching) matching algorithm is a world's apart [IMO]. We could use another angle and focus on completing-read (https://github.com/jojojames/fussy#benchmarking), IMO, .05-.1 is very different from .3-.5 is very different from .8-1+ seconds and so on. (Maybe not in isolation, but additive with the rest of emacs' slow performance.) IMO, it's the same reason line numbers were moved to C, the new flex completion was moved to C (and so on), those little sub second jitters all count. |
|
Okay, if you do prefiltering then it won't be that different from the current Consult approach, except that the second stage filtering is off-loaded to your native filter, and the data won't reach the Elisp level. One could potentially improve Emacs in that regard by parallelizing Regarding the 20M vs 50M and why I don't find the a factor of 2 that huge - I haven't really looked at your implementation, but iiuc you're using worker threads and then I would expect more impressive numbers, or better scaling with the number of threads. Affe uses a single (!) Elisp process, which hands of the candidates to But anyway, I didn't want to actually discuss these numbers, but rather I wanted to point out that you could be a bit more balanced with your statements. I find statements that there is a "huge huge" speedup and everything is "way faster" unbalanced, since one has to take other factors into account too - for instance that the When I wrote Affe as an experiment I had considered to continue more development in that direction, with off-loading more work to external processes, but after I polished the two stage filtering in |
This is the same thought I had, the main bottleneck right now is the single threaded all-completions. This currently applies to completing-read, so I found it faster to pass nil to completion-regexp-list (iirc that's the name) and hand the entire collection to fzf-native to filter. Even without that, (not sure how feasible), it'd be great to process the list in a multithreaded fashion even on empty input (e.g return everything). Or being able to spin up pure-function lisp threads that can compute a value quickly without morphing global lisp state would be appreciated. As a tangent, IMO, the worst thing about emacsvvim right now is the relatively slow completion-in-region system that vim's ycmd seemingly solved 10+ years ago, though that's a different discussion altogether.
I hope you do so as I'm more confident you can push it through if you try.
A few points here, 20M vs 50M was a struggling affe vs a relaxed fzf-async, maybe the real numbers are 20 to 80? No idea really, the comparison is shoddy in the first place because there are too many variables to account for, it was just a quick eye test indexing on speed/latency/# of candidates handled. For example, around a few million candidates, affe regularly blanks out completely in completions for 5-10+ seconds at a time, whereas fzf-async at 50-60million maybe takes a few seconds (not amazing honestly but elisp is just too slow...) to ever get through filtering (again shoddy eye test comparison so this is just to make a point). The second is fzf is doing more per candidate than affe in the first place, multi component out of order matching alone is going to add a lot of wall to wall time (I'd imagine using fzf strictly for filtering would conjure an even bigger gain than 50M), not to mention the scoring/sorting. A lot of the gains going from elisp->C and single thread->multithread are used to accomplish those goals. I'd imagine (wild guess) the speed up is between 5-8x (wild guess) going from elisp->/single->multi using benchmarks from hotfuzz/fzf-native vs orderless (.1 to .8 for flex matching) (https://github.com/jojojames/fussy#benchmarking shows 7-8x caveat: i didn't write the benchmark).
The C side actually processes things extremely fast. The bottleneck is the lisp thread and funneling data back to the lisp runtime. We have to do this on the main emacs thread. There might be ways to optimize this too at the emacs-core layer but I don't have the skill to grok the emacs codebase or push through that type of optimization on the mailing list. e.g. funneling c strings back to elisp strings, setting text properties at all, calling emacs runtime functions in the c core, etc etc are all extremely slow in the context of any milliseconds will add noticeable delay. Again this is where updates to emacs core might solve these issues, there's just no reason why a pure function like converting a simple c string to an emacs string needs to be on the main thread but I don't know all the relevant constraints to the topic so it's a moot point here. The other possible explanation is my C implementation is still inefficient and there are still gains to be had somewhere. I'd welcome that if it meant the implementation can go even faster.
But these are essentially the same thing, we're sending some query to rg and then processing that query. The difference is consult/affe does something like rg-filter-string#emacs-filter-string to separate the initial shell-side filtering with emacs filtering or emacs-filter-string as an input to both rg&emacs. The latter doesn't make sense in a fuzzy matching scenario if rg doesn't handle fuzzy inputs and the former is the same thing as fzf barring UX differences.
Noted, I still hold the same opinion regarding speed/latency but I agree these statements could be better informed on other constraints (e.g. like you mentioned memory). And thank you for the advice.
I think that's it. I came from vim over 10 years ago at this point where fuzzy matchers like ctrlp/cmd-T and then fzf were defacto standard (and then the new stuff like skim/fzy/fff/nucleo that I don't have much context on). I don't think emacs has ever reached that level of UX/filtering/speed (imo fzf-async closes that gap) (just my opinion though).
I agree, the current flex implementations in elisp are too slow which is why I don't use them either and use fzf-native/fussy to get flex+scoring from C instead. The C flex implementation in emacs 31 is much faster than the elisp one from short testing and works for most cases but it's still too slow to me (due to single thread?) and is single component matching from what I understand, so it's not an improvement over what fussy already has. BTW, fzf isn't strictly fuzzy matching, you can just do simple prefix matching or (https://github.com/nvim-telescope/telescope-fzf-native.nvim#telescope-fzf-nativenvim) which makes it just as flexible as orderless imo (though I'm not as familiar with orderless as I am with fzf so that might be incorrect). A pattern I've started using recently when finding files is M-x fzf-async-fd Prompt> 'somedirectory fzzzyfilename ' to get exact substring match on the directory and then fuzzy match after IMO, that's pretty similar to 2 pass filtering except the underlying implementation conceptually differs along with their various tradeoffs. |
Either I misunderstand your statement, or what you say is simply false. It is false if you claim that it is essentially the same if one approach consumes almost no memory and the other consumes gigabytes of memory. For the user on the UI side it may not make a difference. But this is only true until some other processes suffer, swapping sets in or the OOM killer takes out the process. But anyway, I think you got my point, about taking other factors into account.
I understand your point. I never had this experience, I never missed fuzzy filtering and I almost never have performance issues with Emacs. Of course I have to keep an eye on performance bottlenecks here and there, since Emacs has a low ceiling. But overall our preferences differ. I don't have this hyper focus on fast fuzzy filtering, since I don't like its trade-offs. Many Emacs users don't even like the immediately updating UIs and rather proceed step by step in completion. I am not one of these users, but the way Emacs completion works without fuzzy filtering is good and fast enough for me. I use Orderless and it is among the fastest completion styles, while still going through the usual regexp machinery. But then, I don't want Emacs to filter 10 millions of candidates, I cut down the number of candidates earlier in contrast to the Fzf-approach. |
It only consumes more memory if it's doing more. Otherwise the mechanism is the exact same. e.g. Pass some filter to some shell -> process the output of that shell command with fzf / emacs orderless etc fzf-async is just passing "", whereas consult&friends passes in some letters to filter down what the shell returns. The "", in this example will of course do more (e.g. return 60million candidates) than some "abc" query which filters down what the shell returns but there's nothing stopping someone from writing an fzf-async command where the starting shell command is "find . -name "*.el"" or something that pares it down even more. Of if you want to add UX to the mechanism, you can use fzf-async-shell-command to write a custom shell command for the first pass, thereby getting your reduced/filtered set automatically. Or if you want to do it the consult way UX-wise in an incremental fashion, e.g. PROMPT>#filter-to-pass-to-rg/-find#queryr-to-pass-to-emacs, you can do something like this (jojojames/fzfa@deefb08) which accomplishes the same thing. But that doesn't change that all 3 "approaches" are exactly the same. (pass query to shell > process query from shell) The approach I took with fzf-async is what I learned from counsel/consult/affe anyways, the main "innovations" are just using C&multithreading (copying hotfuzz) for speed and using fzf for its matching algorithm. Conceptually it's the same as the elisp approach except we're defaulting to "" pre-matching, made possible by the above speed gains.
Maybe in theory, but practically this isn't an issue. A single web browser tab probably takes more memory than an entire Emacs instance and a 50-60K candidate search session using fzf is probably 30-40MB in total. Sure, limit testing 60 million candidates will consume more memory but that's better than being unable to do so at all. I guess I don't see a real tradeoffs comparison when one side is 'uses a lot of memory when doing X task' and the other is 'unable to do X task'.
That's reasonable and I can see the perspective but there is a world where you're "missing out" right? I kind of see it similar to using the defaults in emacs or using vertico. Or someone using basic completion when orderless exists. (or maybe I'm the one missing out)
orderless is a fantastic package (just like vertico/consult/affe) but I don't think it's fair to call it one of the fastest completion styles when it seemingly takes .3 seconds to complete 90K candidates and .8 seconds to do flex matching (which makes it unusable with company/corfu imo). (Again, I didnt write the benchmark so maybe it's wrong and I'm surprised a package that only filters could possibly be slower than another package that filters+scores+sorts). Anyways, I digress, I'm not sure if there are even real "tradeoffs" to discuss in the first place, IMO the way consult does things isn't a different approach with a different set of tradeoffs to fzf, it's instead just a restricted version of what fzf-async already does. e.g. because of how consult constrains the rules of engagements around filtering, it can't do what the current fzf approach can do (rg "" | fzf) but the reverse isn't true, fzf-async can do "rg "somestr" | fzf" and accomplish what consult is doing. (Or, consult CAN do it, but it's too slow to be viable in most cases.) The purpose of this discussion in the first place was my trying to figure out how to do a "" pass in consult so I can filter/score with fussy and get accurate results when fuzzy matching. We both know consult can be modified to make that flow work, but it doesn't currently; and that was my main gripe with it. And IMO, it still might be good to accomplish that somehow, as there are a ton of polished consult commands/integrations that I don't have the skill to rewrite and maintain. Reworded, if consult was given the optionality to skip filtering (e.g. pass "" to rg/find/fd and pass completion-regexp-list=nil to all-completions) when shelling out to another command and/or result set, functionally it'd be the same as fzf-async. If consult had the ability to replace its current completion-styles filtering with a dynamic module, it'd be similarly as performant as fzf-async. Otherwise, design wise, it's the same. |
Uh oh!
There was an error while loading. Please reload this page.
Hi @minad , followup to #587 and a few related questions
I've written this to do try to skip the regexp filtering and have fussy do both filtering+scoring+sorting in its native c backend which is multithreaded and scores/filters using fzf-native. Question is if this is the right approach (e.g. an override advice for each of these functions I want to use with fussy)? I mainly want to avoid the regexp filtering so I can filter on my own and get the performance improvements.
to `consult--buffer-query'." but it wasn't clear to me how to use it in the way I described above.
Similarly, I also want to use fd/find without prior filtering on them (e.g. "$ find ." or "$ fd" in a directory).
Some questions on this.
I added a print statement to my final sorting function here:
So it definitely sorts the list but it's hard to tell if it's running exactly for the final batch. Could you point me to the right spot to debug this?
Similar to above^, is this the right approach? I don't mind overriding a bunch of consult internal functions to accomplish the goal of filtering+scoring with fussy but it'll be tedious in the future if implementation details change.
I'm assuming because of how consult filters right now (e.g. each new input queries the underlying find/fd fresh), results aren't cached at all. A thought I had was we could just run find or fd once (e.g. with empty query ""), accumulate the candidates in a short lived cache while completion is running and we should be able to fuzzily filter/score over this short lived cache instead of calling the command over and over again. This should get us performance similar to what fzf is doing in the terminal (- the speed of emacs just printing out the strings). e.g. collect candidates once -> filter/search after. Even without the cache, the current speed is adequate (e.g. fd on an m4 mac can speed through 150K files in <1 second on an empty query).
All reactions