fd: Benchmark is unfair. find(1) should not be used for grepping.

Hi,

I believe the benchmarks you provide compared to find(1) are unfair. find(1) should not be used for grepping; following the Unix principles, find(1) should just find, and grep(1) should be responsible for filtering the output of find(1).

If we pipe find(1) to grep(1), the performance is significantly faster than just using find(1):

$ time find ~ -iregex '.*[0-9]\.c$' >/dev/null

real	0m1.103s
user	0m0.881s
sys	0m0.220s
$ time find ~ | grep -i '/[^/]*[0-9]\.c$' >/dev/null

real	0m0.346s
user	0m0.103s
sys	0m0.260s

find | grep seems to be faster than fdfind in my own simple test:

$ time fdfind -HI '.*[0-9]\.c$' ~ >/dev/null

real	0m0.383s
user	0m1.920s
sys	0m6.126s

Can you please provide benchmarks against this pipeline in your readme?

What version of fd are you using? [paste the output of fd --version here]

$ dpkg -l | grep fd-find
ii  fd-find                               8.7.0-3+b1                               amd64        Simple, fast and user-friendly alternative to find
$ fdfind --version
fdfind 8.7.0

Just for completeness, here’s my CPU:

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         46 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  24
  On-line CPU(s) list:   0-23
Vendor ID:               GenuineIntel
  Model name:            13th Gen Intel(R) Core(TM) i9-13900T
    CPU family:          6
    Model:               183
    Thread(s) per core:  1
    Core(s) per socket:  24
...
Caches (sum of all):     
  L1d:                   896 KiB (24 instances)
  L1i:                   1.3 MiB (24 instances)
  L2:                    32 MiB (12 instances)
  L3:                    36 MiB (1 instance)

Thanks!

About this issue

  • Original URL
  • State: open
  • Created 3 years ago
  • Comments: 23 (3 by maintainers)

Most upvoted comments

On the other hand, it might be interesting to fork find(1) into a new program f(1), which would get rid of all the crap from find(1). Just find stuff. It looks like a fun project for me.

@jgardona

That’s a small thing, actually. Compare to this:

alx@debian:~$ time find ~ | wc -l
660487

real	0m0.338s
user	0m0.080s
sys	0m0.273s
alx@debian:~$ time find ~ -type f | wc -l
603577

real	0m0.344s
user	0m0.096s
sys	0m0.262s
alx@debian:~$ time find ~ -type d | wc -l
53914

real	0m0.314s
user	0m0.091s
sys	0m0.223s

😃

BTW, maybe you should default to -j1 when writing to a pipe? Usually, the pipe will be slower consuming the path names than find(1) producing them.

There are two important cases where this isn’t true:

  • When I/O is slow, multi threaded I/O can be a huge improvement
  • When filtering, the output may be very small but we want to parallelize the filtering as much as possible

New benchmark below in this message.

Thanks for doing those. Here’s my attempt to replicate them, with hyperfine. The working directory is a checkout of the Chromium source tree (2,119,292 files):

Benchmark 1: find . -iregex '.*[0-9]\.c$' | wc -l
  Time (mean ± σ):      8.736 s ±  0.057 s    [User: 6.468 s, System: 2.222 s]
  Range (min … max):    8.614 s …  8.791 s    10 runs
 
Benchmark 2: find . | grep -i '/[^/]*[0-9]\.c$' | wc -l
  Time (mean ± σ):      2.970 s ±  0.017 s    [User: 1.718 s, System: 2.387 s]
  Range (min … max):    2.946 s …  3.003 s    10 runs
 
Benchmark 3: fd -u '.*[0-9]\.c$' | wc -l
  Time (mean ± σ):     221.8 ms ±   2.1 ms    [User: 4561.5 ms, System: 5194.0 ms]
  Range (min … max):   216.4 ms … 224.5 ms    13 runs
 
Benchmark 4: fd -u | grep -i '/[^/]*[0-9]\.c$' | wc -l
  Time (mean ± σ):     681.0 ms ±  15.2 ms    [User: 4200.0 ms, System: 4313.2 ms]
  Range (min … max):   656.1 ms … 701.3 ms    10 runs
 
Benchmark 5: fd -u -j1 '.*[0-9]\.c$' | wc -l
  Time (mean ± σ):      2.543 s ±  0.021 s    [User: 0.671 s, System: 1.905 s]
  Range (min … max):    2.504 s …  2.562 s    10 runs
 
Benchmark 6: fd -u -j1 | grep -i '/[^/]*[0-9]\.c$' | wc -l
  Time (mean ± σ):      3.732 s ±  0.081 s    [User: 4.850 s, System: 3.626 s]
  Range (min … max):    3.600 s …  3.833 s    10 runs

TL;DR:

find | grep is by far the most efficient command in terms of CPU load, and performance per CPU time. It is also decently fast. However, it doesn’t parallelize as much as fdfind.

True, but for me fd -j1 is even better than find | grep.

fdfind | grep is useless.

That’s not surprising to me. With fd you get multi-threaded filtering, but with fd | grep you get at most one core of grep.

What does surprise me is that fd -j1 | grep is slower than find | grep. Not sure why that is, I’ll look into it.

If you want excellent efficiency with great performance, use find | grep; and if you want absolute performance, and have lots of iddle CPUs and you want to use them all for finding your files, use fdfind.

Don’t forget about fd -j1! But to be fair, there’s no reason a find implementation couldn’t be just as fast.

find alone is not useful. I think everybody agrees on this. Let’s not use it.

find -iregex is pretty slow because grep uses a much faster regex implementation. Theoretically, GNU find could use the same implementation and become more useful. (Though find | grep does allow for more parallelism, assuming single-threaded find.)

fdfind alone is the fastest if you have many iddle cores, and want to use them all at once for finding your files. It is not efficient at all, but it is fast. If you care about latency of fractions of a second, go ahead.

Personally I use fd mainly interactively, and I’m happy to burn CPU cores for lower latency. In other contexts, like for example a background task on a loaded machine, efficiency is more important.

But fd -j1 is pretty efficient too! It has the lowest user+system CPU consumption of anything in the benchmark. The reason fd appears CPU-inefficient is that crossbeam (used to communicate between threads) tends to prefer spinning over blocking. Spinning burns CPU time but has much lower latency than blocking.

find alone is not useful. I think everybody agrees on this. Let’s not use it. @alejandro-colomar

Sounds good.👍 Let’s open a patch to GNU Coreutils to delete that functionality from GNU find. Once that lands we can update these benchmarks.

find(1) should not be used for grepping

Then why does find(1) support grepping?

Because its inventor was told to do it that way, it seems. Here’s the (funny) history of the design of find(1): https://doc.cat-v.org/unix/find-history

@jgardona find completing in 2.9 ms means that’s probably a very small directory tree. I’d imagine that most of the time taken by fd is startup overhead, maybe due to #1203