Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Git ls-files is Faster Than Fd and Find

cj.rs

Post reply on HN
Print view View original

21–30 of 80 posts

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

#21

Post by R0b0t1 »

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…

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.

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

#22

Post by c_joly »

rmetzler wrote: post #3

Small typo occurring two times: git ls-file instead of git ls-file s . Thanks for bringing it up, I didn't know about the command. I also might have a use case for it.

Thanks for pointing this out and for your kind words. A fix for the typos should be live soon.

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

#23

Post by cb321 »

R0b0t1 wrote: post #21
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…

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.

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

#24

Post by xyzzy_plugh »

mikewhy wrote: post #17

FYI to anyone looking to try this out: the `--others` flag, used to include untracked files, will also print out files included in your .gitignore. So if you have eg. a node_modules/ or venv/ folder, all its contents will be listed. This is often unwanted noise. I haven't been able to find if there's some combination of flags that would get the desired behaviour, but it's been a while since I've messed around with th…

What's the desired behaviour you want? --cached --others --exclude-standard will show tracked and untracked but not ignored.

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

#25

Post by cb321 »

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…

plocate [1] is even faster (but of course with either you need to re-scan the whole FSes and rebuild indexes to have an up-to-date view).

[1] https://www.linuxuprising.com/2021/09/plocate-is-much-faster...

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

#26

Post by quicklime »

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 created or removed, but afaict no modern filesystem offers it.

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

#27

Post by masklinn »

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.

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

#28

Post by thanatos519 »

gorgoiler wrote: post #12
m000 wrote: post #10

Earlier quoted context omitted.

What you describe is an over-specialized optimization that very few users would benefit from, but would still introduce significant complexity. Linux already transparently caches filesystem metadata. You already get a good speedup if you attempt the same directory walk twice, and not much have changed in the filesystem.

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.

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

#30

Post by rakoo »

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: listing files. We know that indexes help solve the issue. But we still use `find` because there's no efficient files indexing strategy. Yes, there's updatedb/mlocate, but updating the db requires a full traversal of the filesytem because there's no efficient listing of changes in linux, only filesystems-specific stuff.

So we will still have articles like this until the situation changes, and it will still be relevant to the discussion because it's not "solved"

Post reply on HN