3 ms·

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,

by 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.
    - cb321 5y ago
      You need not newfstatat every dirent unless you need more metadata (times, size, etc.) for something else (as alluded to above by, at least, both me and bscphil elsewhere in this thread). You can simply try to call `opendir()` based upon `d_type`. See [1]. IIRC, this d_type in dirent usage is somewhat new (maybe mid- to late- 1990s) compared to Unix itself. In olden times, one had to stat. It is possible the filesystem you are testing on gives DT_UNKNOWN all the time mandating stats. [2] [1] https://lobste.rs/s/kpzdew/git_ls_files_is_faster_than_fd_find#c_nal5fc https://lobste.rs/s/kpzdew/git_ls_files_is_faster_than_fd_fi... [2] https://stackoverflow.com/questions/47078417/readdir-returning-dirent-with-d-type-dt-unknown-for-directories-and https://stackoverflow.com/questions/47078417/readdir-returni...

by cb321 5y ago

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.
  - cb321 5y ago
    You need not newfstatat every dirent unless you need more metadata (times, size, etc.) for something else (as alluded to above by, at least, both me and bscphil elsewhere in this thread). You can simply try to call `opendir()` based upon `d_type`. See [1]. IIRC, this d_type in dirent usage is somewhat new (maybe mid- to late- 1990s) compared to Unix itself. In olden times, one had to stat. It is possible the filesystem you are testing on gives DT_UNKNOWN all the time mandating stats. [2] [1] https://lobste.rs/s/kpzdew/git_ls_files_is_faster_than_fd_find#c_nal5fc https://lobste.rs/s/kpzdew/git_ls_files_is_faster_than_fd_fi... [2] https://stackoverflow.com/questions/47078417/readdir-returning-dirent-with-d-type-dt-unknown-for-directories-and https://stackoverflow.com/questions/47078417/readdir-returni...