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

61–70 of 80 posts

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

#61

Post by ReidZB »

ziml77 wrote: post #41
ww520 wrote: post #37

Earlier quoted context omitted.

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

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

#62

Post by chrsig »

amelius wrote: post #56
chrsig wrote: post #14

Earlier quoted context omitted.

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.

indeed. this is one of the benefits of a concurrent sequential processing model with a scheduler.

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.

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

#63

Post by pabs3 »

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…

In Linux there is fanotify for monitoring for filesystem-wide events.

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

#64

Post by nerdponx »

varenc wrote: post #58
nerdponx wrote: post #57

Earlier quoted context omitted.

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!

That would be interesting, and I'd probably use it!

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

#66

Post by Groxx »

ziml77 wrote: post #41
ww520 wrote: post #37

Earlier quoted context omitted.

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.

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.

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

#67

Post by cb321 »

Dylan16807 wrote: post #59
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.

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

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

#68

Post by kelnos »

psykotic wrote: post #40
cb321 wrote: post #31

Earlier quoted context omitted.

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

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

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

#69

Post by kelnos »

tyingq wrote: post #19

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

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.

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

#70

Post by kelnos »

amelius wrote: post #8
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?

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

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.
Post reply on HN