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

Fast Directory Listing on Linux

github.com

Post reply on HN
Print view View original

41–50 of 75 posts

Re: Fast Directory Listing on Linux

#41

Post by romka2 »

ridiculous_fish wrote: post #29

A lovely way to sort strings, especially strings that may have long shared prefixes, is a 3-way partition quicksort. This allows you to avoid walking the same prefix over and over the way that memcmp does. Pick your pivot element and partition the strings into based on the first character only. Note this differs from classic quicksort in that we're maintaining three regions, not two. Now recurse for all three regions…

That's a cool algorithm.

The improvements in the article look pretty small between different versions because CPU time is dominated by system calls that are out of my control. If you look at userspace CPU only, the speedup between v1 and v5 is 15x. In other words, the final version uses 15 times less CPU time in userspace. It also uses less CPU in the kernel, but the improvement there isn’t as dramatic (just the openat vs open optimization).

If some clever sorting optimization could yield infinite speedup and would optimize away all loop counters and pointer arithmetics, the overall performance of ListDir v5 would only increase by 3%. v5 is basically all kernel code, there is almost nothing left to optimize algorithm-wise.

Re: Fast Directory Listing on Linux

#42

Post by tele_ski »

romka2 wrote: post #35
tele_ski wrote: post #31

I think this is an awesome article and a really cool idea on how the author incremetally improved their code for performance. But is the API as easy to use for a programmer? I find a complex API into a function makes it much harder to understand even if its your own code months later. I also feel like the parent_fd parameter is sort of glossed over and is an exercise on how to pass that into the final versions of the…

The real implementation of ListDir accepts the descriptor of the directory it needs to list (not parent_fd plus dirname like it's done in the article) and doesn't close it. This is fairly straightforward. You still have to pass Arena as an extra parameter though, which adds inconvenience, and d_type is still at -1 offset -- a rather unusual thing for an API. The biggest downside from the API perspective is that direc…

Since this is C++, what about using a thread_local Arena for the storage? Then you could simplify the API a bit and not re-allocate too!

I also agree, the parent_fd is trivial but it isn't as easy to use as no parameter.

Re: Fast Directory Listing on Linux

#43

Post by Robin_Message »

ridiculous_fish wrote: post #29

A lovely way to sort strings, especially strings that may have long shared prefixes, is a 3-way partition quicksort. This allows you to avoid walking the same prefix over and over the way that memcmp does. Pick your pivot element and partition the strings into based on the first character only. Note this differs from classic quicksort in that we're maintaining three regions, not two. Now recurse for all three regions…

That's interesting, it's effectively doing a radix sort but in a more scalable way.

Re: Fast Directory Listing on Linux

#44

Post by saagarjha »

agumonkey wrote: post #37
ridiculous_fish wrote: post #29

A lovely way to sort strings, especially strings that may have long shared prefixes, is a 3-way partition quicksort. This allows you to avoid walking the same prefix over and over the way that memcmp does. Pick your pivot element and partition the strings into based on the first character only. Note this differs from classic quicksort in that we're maintaining three regions, not two. Now recurse for all three regions…

what about symbol trees ? /a/b/c/d/e => {a,b,c,d,e} symbol table + [a,b,c,d,e] and you accumulate into a tree/trie

Tries/trees have pointers which can be slow, so I’d measure before using something like this.

Re: Fast Directory Listing on Linux

#45

Post by the8472 »

If you're not hitting the caches then there's a lot more to gain by optimizing IO patterns, either by traversing multiple directories in parallel (to fill SSD command queues) or by performing readaheads on the directories (to be friendly to HDD elevators). Sadly the latter is somewhere between difficult and impossible .

Re: Fast Directory Listing on Linux

#46

Post by romka2 »

the8472 wrote: post #45

If you're not hitting the caches then there's a lot more to gain by optimizing IO patterns, either by traversing multiple directories in parallel (to fill SSD command queues) or by performing readaheads on the directories (to be friendly to HDD elevators). Sadly the latter is somewhere between difficult and impossible .

gitstatusd calls ListDir in parallel from multiple threads. At least with a fast SSD it's CPU bound. I don't have an HDD to test on.

Re: Fast Directory Listing on Linux

#47

Post by saagarjha »

mistrial9 wrote: post #40
CoolGuySteve wrote: post #2

You can get faster than memcmp by rolling your own SSE/AVX compare. memcmp typically has a few branches and instruction cachelines of just trying to verify that it's running on aligned memory and checking how aligned (ie 8byte stride vs 64 byte stride). All that can be skipped with a for-loop of intrinsics if you the programmer know alignment characteristics the compiler cannot infer.

dont you want the compiler to do this for you, with ARCH flags? a bit of foresight and a little checking seems like enough.. excessive ASM is a mistake these days CXXFLAGS -march=sandybridge -mtune=sandybridge

The point is that the compiler does not have enough information to do this automatically.

Re: Fast Directory Listing on Linux

#48

Post by avar »

majewsky wrote: post #38
Lorkki wrote: post #33

Earlier quoted context omitted.

Isn't inotify meant for exactly this kind of thing, though? You are already introducing a hard dependency on Linux syscalls in "v4" of the optimisations, so it would seem advantageous to make use of that to avoid the full directory traversal for most of the time.

inotify requires you to hold open fds for all the dirs and files you're watching iirc, so in repos that large, you'll be crushed by the file-descriptor-per-process limit.

It doesn't, you might need to tweak its limits via /proc/sys/fs/inotify/max_* on such repositories, but those limits are not the same as the much lower open FD limits (as in ulimit -n ...).

Re: Fast Directory Listing on Linux

#50

Post by aasasd »

In my experience, another important component of fast directory listings is a cron job that does “ls -R” every half hour. Because you can't control the eagerness of fs metadata caches even if your fileserver has plenty of free mem.
Post reply on HN