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

51–60 of 80 posts

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

#51

Post by rakoo »

ryantriangles wrote: post #46
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…

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

That's an extremely important tradeoff but it's not an issue in the process: it is possible to split indexing and searching in a root process and querying in a user process that asks the first one, and the first one filters with the different rights. Nothing we've never heard of.

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

#52

Post by sillysaurusx »

ryantriangles wrote: post #46
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…

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

It feels like the index update should be a part of the filesystem layer itself. Not a separate process like you're saying.

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

#54

Post by varenc »

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…

Not a direct part of the filesystem, but macOS does a good job of keeping a constantly up to date filesystem index. It powers Spotlight but is also used for other less user facing things. Running `mdfind` will locate whatever file I want near instantly and the index usually gets updated in a couple seconds.

The background indexing does get bogged down when there’s a massive number of file changes, so I exclude things like “node_modules” folders. It also indexes the actual content of text files and not just filenames.

Sadly the CLI interface for `mdfind` is incredibly obtuse and verbose, and very under documented [0]. When querying anything besides just a filename I still have to lookup the correct incantation. For example, here's how to do a case insensitive search for any folder containing "apple" modified in the last year:

  mdfind 'kMDItemDisplayName = "*apple*"c && kMDItemFSContentChangeDate
The mysterious `c` after `"apple"c` is how you specify a case insensitive search...of course.

Compare that to fd:

  fd --changed-within=1y -t d -i apple
[0] Nothing in the macOS man pages actually explains the `mdfind` query language, nor is there even a link or suggestion of where to learn more. This developer documentation sort of covers it, but it's not quite the same: https://developer.apple.com/documentation/corespotlight/csse...

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

#55

Post by cb321 »

bscphil wrote: post #49
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 fo…

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

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

#56

Post by amelius »

chrsig wrote: post #14
amelius wrote: post #8

Earlier quoted context omitted.

Also, why can tab-completion in Bash hang my shell?

This is actually an incredibly frustrating thing -- when doing disk i/o, the process goes into an uninterruptible sleep state[0]. So if your shell is doing some tab completion that goes into an uninterruptible sleep, there's no escape sequence you can send it to cancel that operation. Where I've seen this be the most vexing is in AWS if an EBS volume dies (surprisingly more frequent of an occurrence than you'd think!…

This is indeed nasty. Imagine you have a server built using asyncio style multitasking, and one of the tasks tries to do disk i/o ... This basically throws the entire asyncio style programming out of the window.

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

#57

Post by nerdponx »

varenc wrote: post #54
quicklime wrote: post #26

Earlier quoted context omitted.

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…

Not a direct part of the filesystem, but macOS does a good job of keeping a constantly up to date filesystem index. It powers Spotlight but is also used for other less user facing things. Running `mdfind` will locate whatever file I want near instantly and the index usually gets updated in a couple seconds. The background indexing does get bogged down when there’s a massive number of file changes, so I exclude things…

Is there an API for mdfind? If so, maybe it'd be worthwhile to try writing an alternative CLI frontend for it, if anyone is looking for a project.

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

#58

Post by varenc »

nerdponx wrote: post #57
varenc wrote: post #54

Earlier quoted context omitted.

Not a direct part of the filesystem, but macOS does a good job of keeping a constantly up to date filesystem index. It powers Spotlight but is also used for other less user facing things. Running `mdfind` will locate whatever file I want near instantly and the index usually gets updated in a couple seconds. The background indexing does get bogged down when there’s a massive number of file changes, so I exclude things…

Is there an API for mdfind? If so, maybe it'd be worthwhile to try writing an alternative CLI frontend for it, if anyone is looking for a project.

There is! Found a simple example: https://gist.github.com/dagronf/3d03094a7ee79c1f91607f4c365f...

I've thought about just making a simpler shell script that turns a valid `fd` query into the obscure `mdfind` incantation. And you can use `-onlyin ...` to limit the search to a particular dir just like fd/find. Might get around to it!

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

#59

Post by Dylan16807 »

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…

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.

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

#60

Post by charcircuit »

ryantriangles wrote: post #46
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…

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

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

Most people only have a single user. Sharing a computer with someone is not that common of a thing to do anymore.

Post reply on HN