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.
Yes. I once wrote a tool which spends a lot of time traversing the filesystem and to my surprise in one scenario most of its time is spent on-CPU (!) in kernel-mode in the readdir_r(2) syscall implementation. I still haven't dived into what it's doing on the CPU, but it sure is interesting.
Yeah, that's not really the interesting part. It's clever because if you're a developer editing source files, the Git index is relatively up-to-date. So, as the author says, why not take advantage of it?
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"
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.
I suppose eBPF could be used to implement real-time index updates, which could be neat. Maybe I'll investigate doing that as a little side project. Though from a quick look, doing it efficiently may require some modification to mlocate's updatedb program (depending on how -U works exactly...).
As always, it depends. Doing a hefty build can make half a million files on my machine - even minor additional file-creation latency can add up VERY quickly in that scenario. And frankly I do far more builds per day than I do `find`, though the build system likely does a fair number of shallow ones.
In user-visible-oriented folders though, oh heck yes it should all be indexed.
I have to use Windows for work and I never see Everything take any CPU ever, even when I have to compile (maybe not a million files though). It's all asynchronous so builds aren't slowed down, indexing happens in the background but never takes long and when you need it it's all there because as you said you don't need to search for files every second.
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.
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).
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.
>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.
The problem with *notify is that it's a push-based system: the receiver (ie the process that is interested in changes) needs to be running to receive a change. Because there is no ACK, if it's not running, you miss changes and there is no way to get those events. Also, even if you received the change but have some failure to process it, you must find a way to not lose the change.
What the USN Journal does is implement a pull-based system: the sender stores everything, and the receiver queries the sender when it wants/can, on its own rhythm, starting from an offset it manages. In a generic pull-based system the sender can optimistically send a notification for the receiver to be informed as soon as possible.
I have my own personal views, but a push-based system with no acknowledgments only makes sense if missing events is ok, typically because you know you'll receive another event about the same "thing" in a short time; this system is not viable for file changes. A push-based system with acks requires the sender to register each receiver, which is a bit heavy. A pull-based system is just the simplest to implement and solves all problems.
Hey! Are you aware of any non-ntfs filesystems that also maintain a USN style journal? upon which tools like Everything could be created?
I wonder why common linux filesystems like ext2/ext4 don't support this. After having used locate and all its friends (rlocate, plocate, lolcate-rs) - tools like Everything & WizTree on Windows feel like a breath of fresh air!
I'm absolutely not an expert, but I feel like log-structured filesystems (https://en.wikipedia.org/wiki/Log-structured_file_system) are a natural fit for this kind of things: an index "just" has to read the latest written entries.
But if we're talking about the future, we're probably talking about btrfs and zfs, both of which have the internal machinery to give you a feed of "recently changed files" up to the beginning of the filesystem.
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?
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!). It effectively prevents the machine from cleanly shutting down, and you wind up having to wait for the instance to be forcefully terminated.
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.
Because tab completion often has to do i/o, which can put the shell into an uninterruptible sleep state. I personally see this most when I've left home but I still have an NFS mount (to my NAS at home) under my home directory.
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.
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.
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.
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.
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 uring can also do that these days. For those unfamiliar with Nim, it's a high productivity, high performance systems language.)
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 personally consider this over-/mis-engineered from days of bygone systems with default ulimits of, say, only 64 open fd's. There should at least be a "fast mode" since let's be real - file hierarchies deeper than 256..1024 levels, while possible, are rare and one should optimize for the common case or at least allow manual instruction that this case prevails. AFAIK there is no such "fast mode". Maybe on some BSD?)
Meanwhile, I think the Rust fd is slow because of (probably counterproductive) multi-threading (at least it does 11,000 calls to futex).
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.
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.
> 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.
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]
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.
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.
> 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.
I think OP is trying to benchmark which tool is fastest/most efficient for his workflow. If one of the tools has bugs (or intentional, but unnecessary behavior) that slow it down unnecessarily, that's great if they're fixed, but doesn't help if they're not.
I do think it's going to be pretty hard for a directory walker to do better than a pre-made index listing of the files, though, even with a warm filesystem cache.
This is true and an ok point, but the writing of the discussed article even has a subtitle: "Git ls-files is 5 times faster than fd or find, but why?"
My answer is "at least partly because `fd` & `find` are both slow - for different reasons". You are never going to do better than reading a saved answer, but I only get a 1.8x hit for not having an index { which needs maintenance as has been pointed out by almost everyone :-) }. `walk`, linked elsewhere, is less of a strawman comparison but could probably be optimized a bit more.
which suggests that the fd slow down (on Linux, anyway) may be `fd` doing unbuffered writes to stdout (probably to avoid interleave/mixing of multi-threaded output) and not be about the way the file tree recursion is written. The fix is probably for `fd -j1` to do buffered output (and ideally never clone/fork). (The MThread may be unproductive in a different way than my initial futex guess.)
My guess (without looking at the code - honestly Rust kind of hurts my eyeballs) is that this unbuffered mode is not even really guaranteed/sound anyway. If you pipe the output, e.g. `fd -jN|cat>out` with `N>1` somewhere and any deep hierarchy pathname output is bigger than PIPE_BUF you hit trouble. Once those pipe writes lose atomicity, threads can be put to sleep and re-awakened in various orders and wind up interleaving their pipe writes with or without userspace-level buffering.
(filename max)*(open fd default limit)=255*1024 =~ 4*PIPE_BUF. So the "full path print out" may still be capable of being > PIPE_BUF and so still interleave producing non-existent pathnames (which would be so long they would need special care like chdir + chdir... + stat to even verify non-existence). You would very likely have to synthesize a file tree to trigger this failure mode, of course.
I say all the above in terms of a robust tool. In terms of benchmarking walks, it is much easier to just do like `dents dstats` and use the walk to produce a depth histogram instead of mega/gigabytes of path output. If you have some burning need to be multi-threaded it is even easy to histogram in parallel and then merge at the end and the histograms should almost always fit in private L2 CPU caches. Could always be a total count instead of depth histo. AFAIK, GNU find has no `-print`-like `-count` operator to compare, but I'd bet the C internals make such not so hard to add. (Yes, you could use `-exec..+`, but this might be so slow as to make the benchmark questionable.)
Parenthetically, I wonder if any stdlib in any prog.lang does the "chdir loop + stat|other" type of work for users with such pathologically long pathnames for all the file system calls. Seems unlikely, but not impossible, and easy to know when it is needed once a "string knows its length". Food for thought.
> 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.
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.
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.
Sure..You could probably do X% of whatever setrlimit RLIMIT_NOFILE allows. The best API might be to take as a parameter a number (or fraction) of allowed open fd's and manage the resource sort of like C stdio FILE buffer sizes.
OTOH, I think people generally do not realize just how niche >1024 depths are. Even huge hierarchies (like dozens of TB) may be only 12..120 deep. I have trouble getting `dents dstats` to ever report >128 levels deep.
Further -- depending upon competition for open fd's -- you can still always fail if you need any new fd's. I.e., the very first opendir could fail. So, it's not like being very file descriptor conservative guarantees success against fd exhaustion. This is also almost surely trickier in a multi-threaded setting where threads share the set of fd's and other threads could open files.
Admin authority can also bump RLIMIT_NOFILE (on machines with access to very deep hierarchies or just all the time). One might argue that fd conservative approaches are programmers complicating their life and slowing code to mask (partially!) small (default) limits. One might counter-argue "There is also no quota/limit system provided for 'how deep'!", though.
Anyway, I doubt there is a perfect solution here and "out of open files at too deep x/y/z/..." is not so inscrutable an error message. (EDIT: There are admittedly some different design considerations here in a CLI tool which has its own OS process & rlimits vs. a library that might be used in a multi-threaded program.)
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:
locate -i "*svd*.pdf"
will have a decent chance of finding any papers about svd's that I have, and is more or less instantaneous.
Although -- I think I did come across the locate command because I was searching for alternatives to 'find.' I can not for the life of me remember the correct order for the path to start searching, and the filename.
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.
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.
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).
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:
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...
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!
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 this.
A warm buffer cache makes a big difference too, so if you're benchmarking things like find vs other tools, be sure to empty the cache between runs.
For Linux:
echo 3 > /proc/sys/vm/drop_caches
In this case, the author is using hyperfine with --warmup 10, so the numbers are all using a warm buffer cache. A cold cache probably would have been more realistic for comparison, since the benchmark is traversing lots of directories.
Perhaps, but it depends on how it's used in the real world. The author was benchmarking tools for the purpose of finding files in via a text editor. If that's something that's done once, then sure, cold caches make sense. But if it's done frequently, presumably those caches will be warm for all but the first run, so the expected, common performance encountered would be with the warm cache.
79 comments
[ 5.0 ms ] story [ 159 ms ] threadThis seems utterly bizarre statement. What does author imagine SCM dies? Stuff, but listing the files that are the source it is managing is up there.
Like saying FPS is a game its not pushing triangles through GPU.
The larger purpose is facilitated by and requires the lessor purpose.
Thanks for bringing it up, I didn't know about the command. I also might have a use case for it.
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"
In user-visible-oriented folders though, oh heck yes it should all be indexed.
So, in practice, it works.
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.
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).
Most people only have a single user. Sharing a computer with someone is not that common of a thing to do anymore.
What the USN Journal does is implement a pull-based system: the sender stores everything, and the receiver queries the sender when it wants/can, on its own rhythm, starting from an offset it manages. In a generic pull-based system the sender can optimistically send a notification for the receiver to be informed as soon as possible.
I have my own personal views, but a push-based system with no acknowledgments only makes sense if missing events is ok, typically because you know you'll receive another event about the same "thing" in a short time; this system is not viable for file changes. A push-based system with acks requires the sender to register each receiver, which is a bit heavy. A pull-based system is just the simplest to implement and solves all problems.
I wonder why common linux filesystems like ext2/ext4 don't support this. After having used locate and all its friends (rlocate, plocate, lolcate-rs) - tools like Everything & WizTree on Windows feel like a breath of fresh air!
But if we're talking about the future, we're probably talking about btrfs and zfs, both of which have the internal machinery to give you a feed of "recently changed files" up to the beginning of the filesystem.
While writing this answer I stumbled upon https://github.com/rflament/loggedfs which is probably a very nice solution to this problem.
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)
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!). It effectively prevents the machine from cleanly shutting down, and you wind up having to wait for the instance to be forcefully terminated.
[0] https://eklitzke.org/uninterruptible-sleep
e.g., in Go, blocking syscalls get put on their own thread in a thread pool, so that processing can continue while waiting.
I'm sure you can do something similar in a raw event loop, but I don't think the machinery is generally baked in to the io interfaces to do so.
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 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.
As in 52s the first time since boot, 5+ for subsequent runs (incorporating time for changed files/directories)
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.)
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 uring can also do that these days. For those unfamiliar with Nim, it's a high productivity, high performance systems language.)
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 personally consider this over-/mis-engineered from days of bygone systems with default ulimits of, say, only 64 open fd's. There should at least be a "fast mode" since let's be real - file hierarchies deeper than 256..1024 levels, while possible, are rare and one should optimize for the common case or at least allow manual instruction that this case prevails. AFAIK there is no such "fast mode". Maybe on some BSD?)
Meanwhile, I think the Rust fd is slow because of (probably counterproductive) multi-threading (at least it does 11,000 calls to futex).
Afaik rustaceans call this “fearless concurrency”.
But, as mentioned below, this is faster because git-ls is using a pregenerated index.
I was mostly just adding some performance color that the points of comparison of the article are, in some sense, not very fast.
In my experience, fast vs. slow "reputations" are sadly very unreliable.
Here is some system call color.
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.
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.
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_fi...
[2] https://stackoverflow.com/questions/47078417/readdir-returni...
There’s probably a switch to run single-threaded so that should be testable.
I think OP is trying to benchmark which tool is fastest/most efficient for his workflow. If one of the tools has bugs (or intentional, but unnecessary behavior) that slow it down unnecessarily, that's great if they're fixed, but doesn't help if they're not.
I do think it's going to be pretty hard for a directory walker to do better than a pre-made index listing of the files, though, even with a warm filesystem cache.
My answer is "at least partly because `fd` & `find` are both slow - for different reasons". You are never going to do better than reading a saved answer, but I only get a 1.8x hit for not having an index { which needs maintenance as has been pointed out by almost everyone :-) }. `walk`, linked elsewhere, is less of a strawman comparison but could probably be optimized a bit more.
My guess (without looking at the code - honestly Rust kind of hurts my eyeballs) is that this unbuffered mode is not even really guaranteed/sound anyway. If you pipe the output, e.g. `fd -jN|cat>out` with `N>1` somewhere and any deep hierarchy pathname output is bigger than PIPE_BUF you hit trouble. Once those pipe writes lose atomicity, threads can be put to sleep and re-awakened in various orders and wind up interleaving their pipe writes with or without userspace-level buffering.
(filename max)*(open fd default limit)=255*1024 =~ 4*PIPE_BUF. So the "full path print out" may still be capable of being > PIPE_BUF and so still interleave producing non-existent pathnames (which would be so long they would need special care like chdir + chdir... + stat to even verify non-existence). You would very likely have to synthesize a file tree to trigger this failure mode, of course.
I say all the above in terms of a robust tool. In terms of benchmarking walks, it is much easier to just do like `dents dstats` and use the walk to produce a depth histogram instead of mega/gigabytes of path output. If you have some burning need to be multi-threaded it is even easy to histogram in parallel and then merge at the end and the histograms should almost always fit in private L2 CPU caches. Could always be a total count instead of depth histo. AFAIK, GNU find has no `-print`-like `-count` operator to compare, but I'd bet the C internals make such not so hard to add. (Yes, you could use `-exec..+`, but this might be so slow as to make the benchmark questionable.)
Parenthetically, I wonder if any stdlib in any prog.lang does the "chdir loop + stat|other" type of work for users with such pathologically long pathnames for all the file system calls. Seems unlikely, but not impossible, and easy to know when it is needed once a "string knows its length". Food for thought.
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
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.
OTOH, I think people generally do not realize just how niche >1024 depths are. Even huge hierarchies (like dozens of TB) may be only 12..120 deep. I have trouble getting `dents dstats` to ever report >128 levels deep.
Further -- depending upon competition for open fd's -- you can still always fail if you need any new fd's. I.e., the very first opendir could fail. So, it's not like being very file descriptor conservative guarantees success against fd exhaustion. This is also almost surely trickier in a multi-threaded setting where threads share the set of fd's and other threads could open files.
Admin authority can also bump RLIMIT_NOFILE (on machines with access to very deep hierarchies or just all the time). One might argue that fd conservative approaches are programmers complicating their life and slowing code to mask (partially!) small (default) limits. One might counter-argue "There is also no quota/limit system provided for 'how deep'!", though.
Anyway, I doubt there is a perfect solution here and "out of open files at too deep x/y/z/..." is not so inscrutable an error message. (EDIT: There are admittedly some different design considerations here in a CLI tool which has its own OS process & rlimits vs. a library that might be used in a multi-threaded program.)
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:
will have a decent chance of finding any papers about svd's that I have, and is more or less instantaneous.Although -- I think I did come across the locate command because I was searching for alternatives to 'find.' I can not for the life of me remember the correct order for the path to start searching, and the filename.
[1] https://www.linuxuprising.com/2021/09/plocate-is-much-faster...
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.
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.
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:
The mysterious `c` after `"apple"c` is how you specify a case insensitive search...of course.Compare that to fd:
[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...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!
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 this.
For Linux:
In this case, the author is using hyperfine with --warmup 10, so the numbers are all using a warm buffer cache. A cold cache probably would have been more realistic for comparison, since the benchmark is traversing lots of directories.It's a useful command that I consider to be relevant to end users, not just an internal "plumbing" utility