8 ms·

I got run times from the simplest single-threaded directory walk that are only 1.8x slower than git ls-files. (Min time of 10 runs with the git repo housed by

by cb321 5y ago

I got run times from the simplest single-threaded directory walk that are only 1.8x slower than git ls-files. (Min time of 10 runs with the git repo housed by /dev/shm on Linux 5.15.) The "simple" code is in https://github.com/c-blake/cligen/blob/master/cligen/dents.nim https://github.com/c-blake/cligen/blob/master/cligen/dents.n... (just `dents find` does not require the special kernel batch system call module to be fast. That kernel module is more about statx batching but IO uring can also do that these days. For those unfamiliar with Nim, it's a high productivity, high performance systems language.) I believe that GNU find is slow because it is specifically written to allow arbitrary filesystem depth as opposed to "open file descriptor limit-limited depth". (I personally consider this over-/mis-engineered from days of bygone systems with default ulimits of, say, only 64 open fd's. There should at least be a "fast mode" since let's be real - file hierarchies deeper than 256..1024 levels, while possible, are rare and one should optimize for the common case or at least allow manual instruction that this case prevails. AFAIK there is no such "fast mode". Maybe on some BSD?) Meanwhile, I think the Rust fd is slow because of (probably counterproductive) multi-threading (at least it does 11,000 calls to futex).

aaaaaaaaaaab 5y ago
>Meanwhile, I think the Rust fd is slow because of (probably counterproductive) multi-threading (at least it does 11,000 calls to futex). Afaik rustaceans call this “fearless concurrency”.
R0b0t1 5y ago
From experience benchmarking this in the past, Window's poor NTFS implementation sees speedup from multithreading (which I can't make sense of) whereas Linux usually had a penalty for multithreading directory traversals. But, as mentioned below, this is faster because git-ls is using a pregenerated index.
- cb321 5y ago
  No question/disagreement that it's faster from having an index. It just need only be 1.8x faster -- not the much higher ratio reported in the article (on Linux, anyway). I was mostly just adding some performance color that the points of comparison of the article are, in some sense, not very fast.
  - R0b0t1 5y ago
    Hm, yes, I reread the part about the performance of find. GNU find is one of the fastest directory traversals out of the box compared to many other implementations, e.g. the ones that come in stdlibs. I was under the impression the slowness was applying the tests when they were applied.
    - cb321 5y ago
      Running the tests like `-type l` or `-perm` or whatnot surely can be slow, but that is not in play in the article's use case. In my experience, fast vs. slow "reputations" are sadly very unreliable. Here is some system call color. $ find | wc -l 79348 $ strace -c find >/dev/null % time seconds usecs/call calls errors syscall ------ ----------- ----------- --------- --------- ---------------- 29.57 0.039172 1 24453 fcntl 24.51 0.032477 1 19615 close 19.87 0.026329 1 14724 newfstatat 16.78 0.022229 2 9786 getdents64 7.48 0.009909 2 4948 6 openat 0.86 0.001137 1 755 write ... ------ ----------- ----------- --------- --------- ---------------- 100.00 0.132487 1 74336 9 total $ dents find|wc -l 79348 $ strace -c dents f >/dev/null % time seconds usecs/call calls errors syscall ------ ----------- ----------- --------- --------- ---------------- 42.43 0.018491 3 5084 getdents64 28.69 0.012503 2 4896 openat 25.40 0.011071 2 4896 close 3.47 0.001514 2 755 write ... ------ ----------- ----------- --------- --------- ---------------- 100.00 0.043579 2 15697 2 total So, you know, almost 5x the system call count. (EDIT: and yes, yes, not all syscalls are created equally. In this hot cache case there are so many that syscall overhead alone could be a large fraction of costs, though.) But you don't need to trust me. It's probably about 50 lines of C to code up a file tree walk recursion and test it yourself.
      - R0b0t1 5y ago
        > It's probably about 50 lines of C to code up a file tree walk recursion and test it yourself. This is exactly what I was doing, fwiw. I can't match up a lot of the extra calls to close(2) but if you're doing what find does you need to be calling newfstatat(2) to get file information. I'll look again -- there may be a way to get these faster. It was something I was going to propose putting into io_uring.
masklinn 5y ago
> Meanwhile, I think the Rust fd is slow because of (probably counterproductive) multi-threading (at least it does 11,000 calls to futex). There’s probably a switch to run single-threaded so that should be testable.
- cb321 5y ago
  Agreed. Adding -j1 still leaves a very large (and wildly varying actually) number of futex calls shown by strace and slows down execution by another 1.5x. So, a little boost from threads but not much. Someone more interested (than I am) in "fixing" fd should study it more. Often people do not "special case" things like "-j1" to actually be single threaded with (no MT runtime overheads) but instead "launch only 1 worker thread" and such. Might taking hacking on fd to really test what is going on.
  - psykotic 5y ago
    I've only profiled fd on Windows but one thing that stood out was that it performed 2 stat syscalls per file via NtQueryInformationFile (that number should be 0 per file on Windows since stat metadata comes for free with NtQueryDirectoryFile from the directory enumeration). When I mentioned this finding on Twitter, someone confirmed that it's also doubling up the stat syscalls on Linux. But if the OP is actually trying to benchmark raw directory enumeration speed vs git ls-files, they should make sure they're benchmarking against something that's not making per-file stat calls at all.
    - kelnos 5y ago
      > But if the OP is actually trying to benchmark raw directory enumeration speed vs git ls-files, they should make sure they're benchmarking against something that's not making per-file stat calls at all. I think OP is trying to benchmark which tool is fastest/most efficient for his workflow. If one of the tools has bugs (or intentional, but unnecessary behavior) that slow it down unnecessarily, that's great if they're fixed, but doesn't help if they're not. I do think it's going to be pretty hard for a directory walker to do better than a pre-made index listing of the files, though, even with a warm filesystem cache.
bscphil 5y ago
> I believe that GNU find is slow because it is specifically written to allow arbitrary filesystem depth as opposed to "open file descriptor limit-limited depth". I haven't benchmarked find specifically, but I believe the most common Rust library for the purpose, walkdir[1], also allows arbitrary file system recursion depth, and is extremely fast. It was fairly close to some "naive" limited depth code I wrote in C for the same purpose. A lot of go-to C approaches seem to needlessly call stat on every file, so they're even slower. I'd be curious to see benchmarks of whether this actually makes a difference. [1] https://github.com/BurntSushi/walkdir https://github.com/BurntSushi/walkdir
- cb321 5y ago
  I cannot speak to why your "naive" C variant might have been slower than necessary. I might (wildly) guess that you did unnecessary string handling/allocation. You really just need one re-used buffer and a memcpy out of dirents to the tail of said buffer (or even directly to stdio's output buffer). With modern Linux FSes you can use the d_type to decide recursion, not a stat. EDIT: Output perhaps might also be/have been hamstrung by not using fwrite_unlocked on Linux. Really just wild guesses, though. I can also say that https://github.com/google/walk https://github.com/google/walk mentioned in other subthreads is almost as fast as `dents find` and over 2x faster than GNU find on the same linux git tree problem (up to commit 923dcc5eb0c111eccd51cc7ce1658537e3c38b25, btw). It may actually be because most ftw()s call stat (and so are quite slow, at least without some kernel magic like IO uring or sys_batch) that the non-stat calling mode is poorly optimized. In that context, it may seem like a more minor optimization.
Dylan16807 5y ago
You could design the code to keep 25 directories open at a time or something, right? Without needing a 'fast mode' that could break in niche circumstances.
- cb321 5y ago
  Sure..You could probably do X% of whatever setrlimit RLIMIT_NOFILE allows. The best API might be to take as a parameter a number (or fraction) of allowed open fd's and manage the resource sort of like C stdio FILE buffer sizes. OTOH, I think people generally do not realize just how niche >1024 depths are. Even huge hierarchies (like dozens of TB) may be only 12..120 deep. I have trouble getting `dents dstats` to ever report >128 levels deep. Further -- depending upon competition for open fd's -- you can still always fail if you need any new fd's. I.e., the very first opendir could fail. So, it's not like being very file descriptor conservative guarantees success against fd exhaustion. This is also almost surely trickier in a multi-threaded setting where threads share the set of fd's and other threads could open files. Admin authority can also bump RLIMIT_NOFILE (on machines with access to very deep hierarchies or just all the time). One might argue that fd conservative approaches are programmers complicating their life and slowing code to mask (partially!) small (default) limits. One might counter-argue "There is also no quota/limit system provided for 'how deep'!", though. Anyway, I doubt there is a perfect solution here and "out of open files at too deep x/y/z/..." is not so inscrutable an error message. (EDIT: There are admittedly some different design considerations here in a CLI tool which has its own OS process & rlimits vs. a library that might be used in a multi-threaded program.)

by cb321 5y ago

aaaaaaaaaaab 5y ago

>Meanwhile, I think the Rust fd is slow because of (probably counterproductive) multi-threading (at least it does 11,000 calls to futex). Afaik rustaceans call this “fearless concurrency”.

R0b0t1 5y ago

From experience benchmarking this in the past, Window's poor NTFS implementation sees speedup from multithreading (which I can't make sense of) whereas Linux usually had a penalty for multithreading directory traversals. But, as mentioned below, this is faster because git-ls is using a pregenerated index.

cb321 5y ago
No question/disagreement that it's faster from having an index. It just need only be 1.8x faster -- not the much higher ratio reported in the article (on Linux, anyway). I was mostly just adding some performance color that the points of comparison of the article are, in some sense, not very fast.
- R0b0t1 5y ago
  Hm, yes, I reread the part about the performance of find. GNU find is one of the fastest directory traversals out of the box compared to many other implementations, e.g. the ones that come in stdlibs. I was under the impression the slowness was applying the tests when they were applied.
  - cb321 5y ago
    Running the tests like `-type l` or `-perm` or whatnot surely can be slow, but that is not in play in the article's use case. In my experience, fast vs. slow "reputations" are sadly very unreliable. Here is some system call color. $ find | wc -l 79348 $ strace -c find >/dev/null % time seconds usecs/call calls errors syscall ------ ----------- ----------- --------- --------- ---------------- 29.57 0.039172 1 24453 fcntl 24.51 0.032477 1 19615 close 19.87 0.026329 1 14724 newfstatat 16.78 0.022229 2 9786 getdents64 7.48 0.009909 2 4948 6 openat 0.86 0.001137 1 755 write ... ------ ----------- ----------- --------- --------- ---------------- 100.00 0.132487 1 74336 9 total $ dents find|wc -l 79348 $ strace -c dents f >/dev/null % time seconds usecs/call calls errors syscall ------ ----------- ----------- --------- --------- ---------------- 42.43 0.018491 3 5084 getdents64 28.69 0.012503 2 4896 openat 25.40 0.011071 2 4896 close 3.47 0.001514 2 755 write ... ------ ----------- ----------- --------- --------- ---------------- 100.00 0.043579 2 15697 2 total So, you know, almost 5x the system call count. (EDIT: and yes, yes, not all syscalls are created equally. In this hot cache case there are so many that syscall overhead alone could be a large fraction of costs, though.) But you don't need to trust me. It's probably about 50 lines of C to code up a file tree walk recursion and test it yourself.
    - R0b0t1 5y ago
      > It's probably about 50 lines of C to code up a file tree walk recursion and test it yourself. This is exactly what I was doing, fwiw. I can't match up a lot of the extra calls to close(2) but if you're doing what find does you need to be calling newfstatat(2) to get file information. I'll look again -- there may be a way to get these faster. It was something I was going to propose putting into io_uring.

masklinn 5y ago

> Meanwhile, I think the Rust fd is slow because of (probably counterproductive) multi-threading (at least it does 11,000 calls to futex). There’s probably a switch to run single-threaded so that should be testable.

cb321 5y ago
Agreed. Adding -j1 still leaves a very large (and wildly varying actually) number of futex calls shown by strace and slows down execution by another 1.5x. So, a little boost from threads but not much. Someone more interested (than I am) in "fixing" fd should study it more. Often people do not "special case" things like "-j1" to actually be single threaded with (no MT runtime overheads) but instead "launch only 1 worker thread" and such. Might taking hacking on fd to really test what is going on.
- psykotic 5y ago
  I've only profiled fd on Windows but one thing that stood out was that it performed 2 stat syscalls per file via NtQueryInformationFile (that number should be 0 per file on Windows since stat metadata comes for free with NtQueryDirectoryFile from the directory enumeration). When I mentioned this finding on Twitter, someone confirmed that it's also doubling up the stat syscalls on Linux. But if the OP is actually trying to benchmark raw directory enumeration speed vs git ls-files, they should make sure they're benchmarking against something that's not making per-file stat calls at all.
  - kelnos 5y ago
    > But if the OP is actually trying to benchmark raw directory enumeration speed vs git ls-files, they should make sure they're benchmarking against something that's not making per-file stat calls at all. I think OP is trying to benchmark which tool is fastest/most efficient for his workflow. If one of the tools has bugs (or intentional, but unnecessary behavior) that slow it down unnecessarily, that's great if they're fixed, but doesn't help if they're not. I do think it's going to be pretty hard for a directory walker to do better than a pre-made index listing of the files, though, even with a warm filesystem cache.

bscphil 5y ago

> I believe that GNU find is slow because it is specifically written to allow arbitrary filesystem depth as opposed to "open file descriptor limit-limited depth". I haven't benchmarked find specifically, but I believe the most common Rust library for the purpose, walkdir[1], also allows arbitrary file system recursion depth, and is extremely fast. It was fairly close to some "naive" limited depth code I wrote in C for the same purpose. A lot of go-to C approaches seem to needlessly call stat on every file, so they're even slower. I'd be curious to see benchmarks of whether this actually makes a difference. [1] https://github.com/BurntSushi/walkdir https://github.com/BurntSushi/walkdir

cb321 5y ago
I cannot speak to why your "naive" C variant might have been slower than necessary. I might (wildly) guess that you did unnecessary string handling/allocation. You really just need one re-used buffer and a memcpy out of dirents to the tail of said buffer (or even directly to stdio's output buffer). With modern Linux FSes you can use the d_type to decide recursion, not a stat. EDIT: Output perhaps might also be/have been hamstrung by not using fwrite_unlocked on Linux. Really just wild guesses, though. I can also say that https://github.com/google/walk https://github.com/google/walk mentioned in other subthreads is almost as fast as `dents find` and over 2x faster than GNU find on the same linux git tree problem (up to commit 923dcc5eb0c111eccd51cc7ce1658537e3c38b25, btw). It may actually be because most ftw()s call stat (and so are quite slow, at least without some kernel magic like IO uring or sys_batch) that the non-stat calling mode is poorly optimized. In that context, it may seem like a more minor optimization.

Dylan16807 5y ago

You could design the code to keep 25 directories open at a time or something, right? Without needing a 'fast mode' that could break in niche circumstances.

cb321 5y ago
Sure..You could probably do X% of whatever setrlimit RLIMIT_NOFILE allows. The best API might be to take as a parameter a number (or fraction) of allowed open fd's and manage the resource sort of like C stdio FILE buffer sizes. OTOH, I think people generally do not realize just how niche >1024 depths are. Even huge hierarchies (like dozens of TB) may be only 12..120 deep. I have trouble getting `dents dstats` to ever report >128 levels deep. Further -- depending upon competition for open fd's -- you can still always fail if you need any new fd's. I.e., the very first opendir could fail. So, it's not like being very file descriptor conservative guarantees success against fd exhaustion. This is also almost surely trickier in a multi-threaded setting where threads share the set of fd's and other threads could open files. Admin authority can also bump RLIMIT_NOFILE (on machines with access to very deep hierarchies or just all the time). One might argue that fd conservative approaches are programmers complicating their life and slowing code to mask (partially!) small (default) limits. One might counter-argue "There is also no quota/limit system provided for 'how deep'!", though. Anyway, I doubt there is a perfect solution here and "out of open files at too deep x/y/z/..." is not so inscrutable an error message. (EDIT: There are admittedly some different design considerations here in a CLI tool which has its own OS process & rlimits vs. a library that might be used in a multi-threaded program.)