Git ls-files is Faster Than Fd and Find • Hacker News Board

Re: Git ls-files is Faster Than Fd and Find

#31

Post by cb321 » Sun, Nov 21, 2021, 8:41 PM UTC

masklinn wrote: post #27

cb321 wrote: post #13

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.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 u…

> 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.

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.

Re: Git ls-files is Faster Than Fd and Find

#32

Post by spicybright » Sun, Nov 21, 2021, 8:43 PM UTC

quicklime wrote: post #26

bee_rider wrote: post #15

Of course scanning an index is faster than traversing the filesystem. Is locate/mlocate some obscure command? It works pretty well for this sort of thing (and has the advantage that you wouldn't need to put git repos everywhere, or something silly like that). I often forget what I've named a pdf that I've downloaded, but usually I'll put something related to the topic of a paper in the file name, so a command like: l…

The problem with locate is that it requires the index db to be updated periodically (I think this happens daily by default?). For some use cases, especially those where I'm searching for files in a tree that I'm actively working in, this forces me to fall back to find (or maybe git ls-files now). I feel like it should be the job of the filesystem to maintain an index and incrementally update it whenever files are cre…

It really is strange we don't have that yet.

We already pretend files are on the physical disk and sync it in the background. Adding smarter indexing to that shouldn't be a huge deal.

Re: Git ls-files is Faster Than Fd and Find

#33

Post by c_joly » Sun, Nov 21, 2021, 8:44 PM UTC

filmor wrote: post #4

Well, first doing `find > .my-index` and then measuring `cat .my-index` would give you even better results... I don't find it noteworthy that reading from an index is faster than actually recursively walking the filesystem.

> I don't find it noteworthy that reading from an index is faster than actually recursively walking the filesystem

I agree, what I found noteworthy though is that git ls-files uses this index you already have for.

(author here, “proof”: https://cj.rs/contact/ & https://keybase.io/leowzukw)

Re: Git ls-files is Faster Than Fd and Find

#34

Post by spicybright » Sun, Nov 21, 2021, 8:47 PM UTC

thanatos519 wrote: post #28

gorgoiler wrote: post #12

Earlier quoted context omitted.

My desktop has ~2MB of basenames on it. Memory isn’t free, and there’s more to an inode than a filename, but it seems odd that this data that’s the size of a cat photo doesn’t get special treatment over other vm cache data.

That's tunable, and apparently the default is reasonable: https://sysctl-explorer.net/vm/vfs_cache_pressure/ My workstation has 64GB of RAM and only ~7M directory entries so I have 'vm.vfs_cache_pressure = 1' in /etc/sysctl.conf and cache everything with a full directory traversal via find. The first time it takes 52s; subsequent times take 5s. It has never given me memory problems.

I'm assuming the cache isn't kept on disk tho, right?

As in 52s the first time since boot, 5+ for subsequent runs (incorporating time for changed files/directories)

Re: Git ls-files is Faster Than Fd and Find

#35

Post by topspin » Sun, Nov 21, 2021, 8:49 PM UTC

gorgoiler wrote: post #5

One thing I’ve never understood about Linux filesystems: given how small and bounded the sets of directories and directory entries are, why is filesystem traversal not instantaneous?

> why is filesystem traversal not instantaneous

Because a mounted file system isn't a simple indexed list of paths. File systems are shared, mutable state.

The mechanism you're asking about is called the dentry cache[1] and a decent narrative of its operation is found here[2]. It has the fabulously complex job of atomically brokering the state of an arbitrary number of local and remote file systems between an arbitrary number of processes using arbitrary access patterns without consuming all available RAM. Expecting the dentry cache to yield 'instantaneous' results is unreasonable. Comparing its performance to that of an VCS index is naïve.

[1] https://www.kernel.org/doc/Documentation/filesystems/vfs.txt [2] https://www.halolinux.us/kernel-reference/the-dentry-cache.h... (no endorsement of these people, but the dentry cache description is both concise and sufficient.)

Re: Git ls-files is Faster Than Fd and Find

#36

Post by spicybright » Sun, Nov 21, 2021, 8:56 PM UTC

toxik wrote: post #9

spicybright wrote: post #7

Earlier quoted context omitted.

Lack of caches I'd assume. Not because it's not easy, but because no one has taken the time to implement it.

They say there are two hard problems in computer science: cache invalidation, naming, and off-by-one errors.

Hehe. You're right, I forgot one of the golden rules. There's probably a better reason why no one has implemented it.

Re: Git ls-files is Faster Than Fd and Find

#37

Post by ww520 » Sun, Nov 21, 2021, 8:59 PM UTC

rakoo wrote: post #30

filmor wrote: post #4

Well, first doing `find > .my-index` and then measuring `cat .my-index` would give you even better results... I don't find it noteworthy that reading from an index is faster than actually recursively walking the filesystem.

No, it's not surprising, so why do we still not use indexes for this ? NTFS maintains a journal of all files modification ( https://en.wikipedia.org/wiki/USN_Journal ). This is used by Everything ( https://www.voidtools.com/support/everything/ ) to quickly and efficiently index _all_ files and folders. Thanks to that, searching for a file is instantaneous because it's "just an index read". The feature is common: list…

Updating an index adds additional time, adding a random seek to the index file location. Also requires some transaction to group the update to the file metadata and the index. It just adds more complexity with little benefit.

Re: Git ls-files is Faster Than Fd and Find

#38

Post by R0b0t1 » Sun, Nov 21, 2021, 9:06 PM UTC

cb321 wrote: post #23

R0b0t1 wrote: post #21

Earlier quoted context omitted.

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.

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.

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.

Re: Git ls-files is Faster Than Fd and Find

#39

Post by cb321 » Sun, Nov 21, 2021, 9:17 PM UTC

R0b0t1 wrote: post #38

cb321 wrote: post #23

Earlier quoted context omitted.

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.

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.

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.

Re: Git ls-files is Faster Than Fd and Find

#40

Post by psykotic » Sun, Nov 21, 2021, 9:21 PM UTC

cb321 wrote: post #31

masklinn wrote: post #27

Earlier quoted context omitted.

> 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.

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 work…

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.