8.1.0 find the targets very slow in a large directory when using fzf. 8.0.0 works well.

[rockyzhang24]

Hi,

I am using fd as the default command of fzf. After updating to the latest version, I find it is very slow to find the target in a large directory (like home).

For FZF, I set export FZF_DEFAULT_COMMAND="fd --hidden --follow --exclude .git". Then I run fzf under my home directory. Next, I type a directory name which is right under home directory say .config, and it will take very very long to find ~/.config. It shows many files under ~/Library which I do not care about. I attached a screenshot below. You can see that ~/.config won't show up even though it has scanned 1080073 entries.

Before updating fd and I cannot remember which version it was, it works very well. When I type .config, it will show up almost immediately. The results could be adjusted automatically based on which query I typed so that my target will show up right away. For example, when I typed .config, it would not show me all those Library/..../config which I did not care about, and instead it would show ~/.config. Very smart.

What version of fd are you using?

fd 8.1.0

Which operating system / distribution are you on?

macOS 10.15.4 (the latest)

Thank you very much!!

Update1:

To be clearer, I put two GIF below (this time I ran fzf under home and tried to search a directory, ~/gitrepos):

1). I didn't set fzf default command, which means let fzf use the default find. When I started to type gitrepos, the targets appeared immediately.

2). I set fzf default command to fd --type f. This time when I started to type gitrepos, the targets wouldn't appear until all entries were scanned.

Update2:

I just now deleted the latest version of fd and re-installed version 8.0.0 (with brew install https://raw.githubusercontent.com/Homebrew/homebrew-core/d874b06712ec20efd86f2fbf20e97aa2f24e9f5b/Formula/fd.rb). The original performance is back. So I am sure the latest version has a bug. Thank you!

[sharkdp]

Thank you for reporting this.

For FZF, I set export FZF_DEFAULT_COMMAND="fd --hidden --follow --exclude .git". Then I run fzf under my home directory.

Note that this might scan much more than your home directory due to --follow. It could even leave your main partition an scan other devices. Are you sure you want to use --follow for this use case?

Next, I type a directory name which is right under home directory say .config, and it will take very very long to find ~/.config

As far as I understand this correctly, there could be two reasons for that: (1) The whole fd search takes longer or (2) the ~/.config folder appears later in the search results.

As for (2), note that the output order of fd is NOT deterministic. You would thus need to remove your benchmarks many times to make sure that this is not just a random occurrence.

It shows many files under ~/Library which I do not care about.

Maybe you want to use --exclude to skip them completely? That would make everything faster as well.

I attached a screenshot below. You can see that ~/.config won't show up even though it has scanned 1080073 entries.

Again. The output order is not deterministic.

Before updating fd and I cannot remember which version it was, it works very well. When I type .config, it will show up almost immediately.

Are you sure that nothing else changed? Could you please run fd in isolation to make sure that this is a problem with fd? You could use hyperfine to compare the two versions:

Save 'fd version 8.x.0' as fd-v8.x.0 binaries, then run the following from your home directory:

hyperfine \
  --warmup 5
  'fd-v8.0.0 --hidden --follow --exclude .git' \
  'fd-v8.1.0 --hidden --follow --exclude .git'

I personally cannot see any performance differences between the two versions.

[rockyzhang24]

Thank you for your help. Do you see my two update statements along with two GIFs at the end of my last post? I guarantee that I didn't change anything but the different versions.

I will demonstrate what I did below: (my OS is macOS 10.15.4)

1. Without doing anything (not set anything variable of fzf), just run the vanilla fzf by typing fzf in home directory. Next, in fzf prompt, type .config to get the ~/.config folder. fzf by default uses find as its searching command. And you can see that .config folder appears immediately while you're typing .config.
2. Test fd v8.1.0
   1. Set `EXPORT FZF_DEFAULT_COMMAND="fd --type f --hidden --follow"
   2. Install fd by running brew install fd, which will install version 8.1.0.
      Then at the home directory, run fzf by fzf. In fzf prompt, just type .config. Then you can see that the .config folder won't appear and it will take a very very long time to get this folder.
3. Test fd version 8.0.0:
   1. Uninstall fd by running brew uninstall fd
   2. Run brew log fd and find the commit id where v8.0.0 is. It is d874b06712ec20efd86f2fbf20e97aa2f24e9f5b.
   3. Run brew install https://raw.githubusercontent.com/Homebrew/homebrew-core/d874b06712ec20efd86f2fbf20e97aa2f24e9f5b/Formula/fd.rb to install v8.0.0
   4. Then do the same thing. Under home directory, run fzf by fzf. In fzf prompt, just type .config. This time, you will see that .config folder appears immediately while you're typing the folder name. It performs the same as find but it uses much less time to finish scanning the whole home folder.

The procedure I described above is complete.

Thank you.

[sharkdp]

I certainly believe you that this is all it takes to reproduce the error. The problem is that (1) I don't have your home folder (2) I don't have MacOS and (3) I don't really want to debug things in fd by running fzf. I'd rather debug fd directly, should there be any problem.

This is why I proposed a direct benchmark of fd 8.0 vs 8.1. You could get those two binaries by installing the respective version via Homebrew and then copying it somewhere:

# brew install fd v8.x.0
cp $(which fd) /tmp/fd-v8.x.0

[rockyzhang24]

Thank you.

Below the output of hyperfine:

v8.1.0 takes a very long time compared to v8.0.0.

[sharkdp]

Ok, there seems to be a drastic regression. But you are running the command from /tmp. Could you run it from your home folder?

[rockyzhang24]

Sure. Still running under my home folder. Just a moment please. :)
v8.0.0 has finished. Now, v8.1.0 is running and it is much slower. I will post the screenshot once it finishes.

[rockyzhang24]

Hi,
Here is the result.

8.0.0 is faster (not sure whether it is accurate because I was watching YouTube while hyperfine was running :P). And actually based on my observation when running fzf, both of the scanning speed for 8.0.0 and 8.1.0 are very fast. When we run fzf, we can see a number that shows how many entries have been scanned. The number increases very fast for both versions. My concern is that 8.1.0 can get the target immediately but 8.0.0 not.

Also, I ran this test under some different directories. 8.1.0 is slower. Screenshots attached below.

1). ~/gitrepos which has the repos I cloned from github

2). ~/Dropbox

[sharkdp]

It looks like not much difference (not sure whether it is accurate because I was watching YouTube while hyperfine was running :P). And actually based on my observation when running fzf, both of the scanning speed for 8.0.0 and 8.1.0 are very fast. When we run fzf, we can see the number which shows how many entries has been scanned. The number increases very fast for both versions. My concern is that 8.1.0 can get the target immediately but 8.0.0 not.

If the overall speed of both searches is roughly the same, I guess it's mostly a matter of luck because the order of the results is non-deterministic, as I have mentioned. Note that the search within fzf has nothing to do with fd. There is no feedback from fzf to fd.

However, I have no idea why 8.1 would consistently show the .config folder later than 8.0. That seems weird.

Unrelated to this ticket, but: if the search really takes 160 seconds, you might consider dropping either --hidden or --follow. Or --exclude some folders. The whole fun of fzfing through your home folder goes away if it takes 160 seconds. My home folder has 1.2 million entries and it only takes a second to print all results (it takes longer with colors enabled, i.e. in the interactive fzf view).

Also, I ran this test under some different directories. 8.1.0 is slower. Screenshots attached below.

1). ~/gitrepos which has the repos I cloned from github

Oh, wow. That definitely seems like a significant drop in performance. It would be great if you could help me figure out what is going on, because I can definitely not reproduce this locally:

❯ hyperfine --warmup 5 'fd-v8.0.0 --hidden --follow --exclude .git' 'fd-v8.1.0 --hidden --follow --exclude .git'
Benchmark #1: fd-v8.0.0 --hidden --follow --exclude .git
  Time (mean ± σ):     196.8 ms ±   4.4 ms    [User: 878.9 ms, System: 587.3 ms]
  Range (min … max):   192.6 ms … 206.4 ms    15 runs
 
Benchmark #2: fd-v8.1.0 --hidden --follow --exclude .git
  Time (mean ± σ):     195.5 ms ±   3.9 ms    [User: 879.6 ms, System: 582.9 ms]
  Range (min … max):   190.5 ms … 205.7 ms    14 runs
 
Summary
  'fd-v8.1.0 --hidden --follow --exclude .git' ran
    1.01 ± 0.03 times faster than 'fd-v8.0.0 --hidden --follow --exclude .git'

The first thing we should check: do both commands actually return the same results? Could you please do the following:

fd-v8.0.0 --hidden --follow --exclude .git | sort > /tmp/output_8.0
fd-v8.1.0 --hidden --follow --exclude .git | sort > /tmp/output_8.1
diff /tmp/output_8.0 /tmp/output_8.1

If this does not show any differences, we would need to find the commit that caused the regression. Because I can not really see any obvious things in the CHANGELOG that could have caused this. The most dramatic change is the disabling of jemalloc in fd 8.1, which could definitely lead to a performance regression like this. But if I'm not mistaking, Homebrew had already disabled jemalloc via the patch in https://raw.githubusercontent.com/Homebrew/homebrew-core/d874b06712ec20efd86f2fbf20e97aa2f24e9f5b/Formula/fd.rb

[rockyzhang24]

Thank you!!!

If the overall speed of both searches is roughly the same

v8.0.0 is still 1x faster than v8.1.0.

I guess it's mostly a matter of luck because the order of the results is non-deterministic, as I have mentioned

I have run fzf many many times (at least 50 times and above) with v8.1.0 and v8.0.0 under my quite large home directory. And without any exception, fzf with v8.0.0 fd will show the targets immediately. Every time. And fzf with v8.1.0 will show the targets almost till the end of the scanning. Here is the most important: the targets will show up almost till the end of the scanning, not somewhere in the middle of the scanning. With 8.0.0, the targets will show up right away no matter how large the directory is, and each time, not any exceptions.

It would be great if you could help me figure out what is going on

Definitely. It's my pleasure. Because running under my home directory takes lots of time, I will first test this diff stuff under ~/.config folder. Screenshot showing the result (not show any difference) attached below:

[rockyzhang24]

Run brew log fd, I got:

I installed fd v8.1.0 via https://raw.githubusercontent.com/Homebrew/homebrew-core/5f06a6b8a6f752e02cf548f77d3885334c2b7a0b/Formula/fd.rb. Then the issue still exists.
Installed fd v8.0.0 via brew install https://raw.githubusercontent.com/Homebrew/homebrew-core/d874b06712ec20efd86f2fbf20e97aa2f24e9f5b/Formula/fd.rb. The issue is gone.

[sharkdp]

I think I might have found the reason why this happens. I actually upgraded the fd dependencies without noticing that there was a new version of the ignore crate available. It comes with this pretty significant change: BurntSushi/ripgrep#1554 (!)

This would explain perfectly well why you previously saw low-depth results first (as the search was breadth first) while it takes almost until the end of the search now (with depth first traversal). The overall search time might also be influenced by this, as the scheduling of different threads might be affected by this (?).

v8.0.0 is still 1x faster than v8.1.0.

1.03 x faster means: 3% faster. Not very conclusive. But the runs in the other two directories show a much larger gap.

[rockyzhang24]

Wow, so it is! Thank you. Is it possible for fd to provide an option to choose depth-first traversal or breadth-first traversal? For fzf, breadth-first traversal is much more efficient, and in the large directory (if some directory is very deep) depth-first traversal is terrible.

But the runs in the other two directories show a much larger gap.

Yes. Especially in a small directory, the gap is large.

[sharkdp]

Wow, so it is! Thank you. Is it possible for fd to provide an option to choose depth-first traversal or breadth-first traversal? For fzf, breadth-first traversal is much more efficient, and in the large directory (if some directory is very deep) depth-first traversal is terrible.

I first need to understand all the implications of this change. This comes as a surprise to me as well. I certainly agree that breadth-first sounds more useful for the typical fd use case. I will keep you updated.

[rockyzhang24]

Roger that! Thanks. :P

[tavianator]

Breadth-first is almost always better for finding files: https://twitter.com/tavianator/status/1144718120852103168

I am curious to try the test case that motivated the ignore change. So far I haven't run into any situations where the higher memory consumption of breadth-first search actually matters.

[sharkdp]

@tavianator Thank you for the feedback

I have performed a few benchmarks on my machine and haven't found any case where the new version of ignore in 8.1 leads to a worse performance (so far). I suppose it would have to be a benchmark that uses -1/--max-results=1, because the full traversal seems to be slightly faster now.

Also, note that fd does not really perform a clean breadth/depth-first traversal due to the parallel nature of the directory walker.

If someone can come up with a reproducible test case where the new version is definitely slower, I'm happy to revisit this ticket.

[tavianator]

Yeah it mainly matters for interactive use, where you care about time to first result.

[hauntsaninja]

In terms of a reproducible benchmark, maybe:

~/dev λ git clone --depth 100 https://github.com/torvalds/linux.git
~/dev λ cd linux
~/dev/linux master λ mv virt virt_fdfd 
~/dev/linux master λ hyperfine -w 10 -m 100 '~/tmp/fd-v8.0.0 --hidden -1 virt_fdfd' '~/tmp/fd-v8.1.1 --hidden -1 virt_fdfd'
Benchmark #1: ~/tmp/fd-v8.0.0 --hidden -1 virt_fdfd
  Time (mean ± σ):      73.1 ms ±   0.8 ms    [User: 598.3 ms, System: 464.4 ms]
  Range (min … max):    70.9 ms …  76.2 ms    100 runs
 
Benchmark #2: ~/tmp/fd-v8.1.1 --hidden -1 virt_fdfd
  Time (mean ± σ):     147.3 ms ±   4.2 ms    [User: 652.4 ms, System: 1355.0 ms]
  Range (min … max):   140.4 ms … 158.4 ms    100 runs
 
Summary
  '~/tmp/fd-v8.0.0 --hidden -1 virt_fdfd' ran
    2.02 ± 0.06 times faster than '~/tmp/fd-v8.1.1 --hidden -1 virt_fdfd'

But weirdly, v8.1.1 just seems to be slower overall:

~/dev/linux master λ hyperfine -w 10 -m 100 '~/tmp/fd-v8.0.0' '~/tmp/fd-v8.1.1'
Benchmark #1: ~/tmp/fd-v8.0.0
  Time (mean ± σ):     111.9 ms ±   1.4 ms    [User: 696.8 ms, System: 490.8 ms]
  Range (min … max):   109.6 ms … 117.8 ms    100 runs
 
Benchmark #2: ~/tmp/fd-v8.1.1
  Time (mean ± σ):     156.8 ms ±   5.4 ms    [User: 840.6 ms, System: 1391.3 ms]
  Range (min … max):   141.7 ms … 166.7 ms    100 runs
 
Summary
  '~/tmp/fd-v8.0.0' ran
    1.40 ± 0.05 times faster than '~/tmp/fd-v8.1.1'

On a Mac, I got these fds from brew.

I'm not familiar with fd/rg/ignore internals and how the parallelisation works, but is iterative deepening DFS (perhaps with exponential deepening) a search option that could be made to work?

[tavianator]

Iterative deepening is particularly bad on most directory trees in my experience (bfs implements it under -S ids if you want to try). The reason is that it only amortizes nicely on trees with fairly consistent fanout. But real directory trees tend to have very few files at the deepest levels, forcing you to explore almost the whole tree repeatedly just to find a small number of deep files.

Exponential deepening should be better, I'll try it out.

[tavianator]

I implemented exponential deepening in this commit. It's about 85% slower than simple breadth-first search on the Linux kernel source tree. That's much better than the standard iterative deepening, which is about 5x slower.

[hauntsaninja]

Thanks for investigating / implementing! Looks like the maximum depth for the Linux source is 9, which is unlucky in that it's just past another deepening threshold. But if we limit to depth 7, it's pretty competitive with DFS. Obviously this depends on directory tree, but I guess if fd-find is looking to implement something like this, maybe deepening to 1, 2, 4, ∞, could resolve this issue without too much of a completion time compromise.

~/dev/linux master λ hyperfine -w 3 "~/dev/bfs/bfs -S dfs -maxdepth 7"
Benchmark #1: ~/dev/bfs/bfs -S dfs -maxdepth 7
  Time (mean ± σ):     246.1 ms ±   7.4 ms    [User: 46.4 ms, System: 177.4 ms]
  Range (min … max):   238.4 ms … 260.6 ms    11 runs
 
~/dev/linux master λ hyperfine -w 3 "~/dev/bfs/bfs -S eds -maxdepth 7"
Benchmark #1: ~/dev/bfs/bfs -S eds -maxdepth 7
  Time (mean ± σ):     262.0 ms ±   2.7 ms    [User: 38.0 ms, System: 202.1 ms]
  Range (min … max):   258.8 ms … 266.5 ms    11 runs

[rockyzhang24]

Hi @sharkdp

I think I might have found the reason why this happens. I actually upgraded the fd dependencies without noticing that there was a new version of the ignore crate available. It comes with this pretty significant change: BurntSushi/ripgrep#1554 (!)

I first need to understand all the implications of this change. This comes as a surprise to me as well. I certainly agree that breadth-first sounds more useful for the typical fd use case. I will keep you updated.

Any updates? Thank you very much.

[rockyzhang24]

As my further investigated, fzf with fd v8.1.1 still bring this performance issue. I put my test procedure below for the users who encounter the same thing as a reference. My OS is macOS 10.15.5.

See the GIF below. I run fzf on my home directory which is a very large directory, and tried to search ~/.config/zsh/.zshrc file. After launching fzf, I typed a query like .config zsh zshrc. You can see that as I was tying, ~/.config/zsh/.zshrc file didn't show up, and instead, a zshrc file in my Trash bin appeared whose path is ~/.Trash/dotfiles-tmp/.config/zsh/.zshrc

Then next, I uninstalled fd v8.1.1 and installed fd v8.0.0 instead. And I performed the same test. This time you can see that as I was typing the query, ~/.config/zsh/.zshrc file appeared immediately on the first place.

[tmccombs]

that would be consistent with doing a depth-first traversal, since it probably searches .Trash before .config.

[rockyzhang24]

@tmccombs Exactly. This is what sharkdp mentioned in his previous comment (#599 (comment)). ripgrep switched to DFS. Even though this switching will reduce the peak memory usage and won't affect the time of the full search, it may take a very long time for the shallow target to be searched out. And fzf needs the shallow result to be shown quickly. Any change will have pros and cons. The author of ripgrip said switching to DPS can make some cases perform better. However, it brings this side-effect to fzf.