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

41–50 of 80 posts

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

#41

Post by ziml77 »

ww520 wrote: post #37
rakoo wrote: post #30

Earlier quoted context omitted.

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.

As someone who uses Everything many times per day, I can say that there is a significant amount of benefit. I don't think I'd be able to function at work without being able to instantly search all my files. The lack of a similar solution on Linux is one of the big barriers to me using it. The best options I've seen there all refresh the index on a schedule.

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

#42

Post by wvh »

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?

Probably having to check if the actual disk entries changed is what slows it down. I wonder if it would be possible with nowadays' memory sizes to keep all metadata in memory as a write-through cache. Not sure if it'd be worth it though, my system has close to half a million files, but I'm only interested in about a hundred or so. I don't think file systems are slow in practice for typical human-scale operations though, with the exception of non-indexed "search all my files" type of operations.

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

#43

Post by ziml77 »

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…

As mentioned elsewhere in these comments, NTFS actually does do that. There are a couple tools out there that take advantage of it like Everything Search and WizTree. I don't know why no open source filesystem has done the same thing.

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

#44

Post by Karellen »

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…

Sarcasm?

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

#45

Post by roywiggins »

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…

WizTree also uses NTFS metadata to perform shockingly fast reports on space usage. Just much, much faster than anything else I've seen, and I'm not sure there's any equivalents for other filesystems.

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

#46

Post by ryantriangles »

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…

Everything's approach has important tradeoffs: the indexing service must be run as administrator/root, and by reading the USN journal it gives users a listing of _all_ files and mtimes on the filesystem regardless of directory permissions. That means that any user who can run a file search can also see every other users' files, which includes their partial web history (since most browsers, including Firefox and Chrome, cache data in files named for the website they're from, and the mtime will often be the last visit time). If you want to avoid this, you can only switch to Everything's traditional directory-traversal-based index, which has the same performance as updatedb/mlocate, Baloo, or fsearch.

I think these tradeoffs are why there hasn't been as much interest in replicating it, combined with the fact that mlocate/fd/find/fsearch are already a lot faster in most circumstances than the default Windows search and good enough for the most common use cases (although there are certainly usecases where they're not).

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

#48

Post by bee_rider »

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…

I suppose this is sort of a problem depending on how you use it. I find that I don't really need to locate things that I've recently used, because I already know where they are as a result of having recently used them. But, other people have different workflows of course (I can imagine, for example, if somebody's workflow involved creating lots of files, only some of which are immediately useful, they might want the ability to scan through them for particular outputs).

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

#49

Post by bscphil »

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…

> 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

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

#50

Post by rakoo »

roywiggins wrote: post #45
rakoo wrote: post #30

Earlier quoted context omitted.

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…

WizTree also uses NTFS metadata to perform shockingly fast reports on space usage. Just much, much faster than anything else I've seen, and I'm not sure there's any equivalents for other filesystems.

WizTree is so fast it makes me yearn for the day we have the same funcitonality on Linux.

Especially not because I'm particularly interested in visualizing free disk space on the regular, but because I want to backup changed files as soon as possible and the only reliable way to do it is to have some kind of journal.

Post reply on HN