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 function since it's just expected to be there in those versions.
Fast Directory Listing on Linux
31–40 of 75 posts
Re: Fast Directory Listing on Linux
#32I 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 API at gitstatusd level is simple.
The ListDir API is also relatively simple. The only complication is to pass in an arena which is not a very high bar.
Re: Fast Directory Listing on Linux
#33But why? Why create a tool that does `git status` 10x faster?
The job of gitstatusd is to put Git status in your shell prompt. See screenshot at the top of https://github.com/romkatv/gitstatus . This is an amazingly convenient tool. When you are working on chromium, on every command you type gitstatusd needs to list the contents of 25,000 directories. Low level optimizations like the ones described here are what makes gitstatusd 10 times faster than `git status`, which in turn…
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.
Re: Fast Directory Listing on Linux
#34But why? Why create a tool that does `git status` 10x faster?
The job of gitstatusd is to put Git status in your shell prompt. See screenshot at the top of https://github.com/romkatv/gitstatus . This is an amazingly convenient tool. When you are working on chromium, on every command you type gitstatusd needs to list the contents of 25,000 directories. Low level optimizations like the ones described here are what makes gitstatusd 10 times faster than `git status`, which in turn…
Your documentation indicates that you've tried with core.untrackedCache, but have you tried core.fsmonitor with the watchman hook?
Obviously your "gitstatus" is still generally useful, but if your main itch you're trying to scratch is to have a faster "status" in a particular repo then you should be able to get that down to a few milliseconds with "git status", if you're willing to have watchman sit in the background and monitor it.
Re: Fast Directory Listing on Linux
#35I 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 directory listing and sorting are bundled in a single function. The insight of v5 in the article is that this bundling allows us to achieve higher performance than what we can get if we have a separate API for listing which we can compose with sorting.
So it's a far cry from the cleanest API you can imagine. Levels of abstractions often have to give way when maximum performance is the goal.
Re: Fast Directory Listing on Linux
#36Earlier quoted context omitted.
The job of gitstatusd is to put Git status in your shell prompt. See screenshot at the top of https://github.com/romkatv/gitstatus . This is an amazingly convenient tool. When you are working on chromium, on every command you type gitstatusd needs to list the contents of 25,000 directories. Low level optimizations like the ones described here are what makes gitstatusd 10 times faster than `git status`, which in turn…
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.
This directory-listing code only executes on a "cold" run of gitstatusd, which happens when you `cd` into a repo for the first time. Users obviously can tolerate higher prompt latency in this case but faster is still better.
Re: Fast Directory Listing on Linux
#37A 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
Re: Fast Directory Listing on Linux
#38Earlier quoted context omitted.
The job of gitstatusd is to put Git status in your shell prompt. See screenshot at the top of https://github.com/romkatv/gitstatus . This is an amazingly convenient tool. When you are working on chromium, on every command you type gitstatusd needs to list the contents of 25,000 directories. Low level optimizations like the ones described here are what makes gitstatusd 10 times faster than `git status`, which in turn…
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.
Re: Fast Directory Listing on Linux
#39Earlier quoted context omitted.
The job of gitstatusd is to put Git status in your shell prompt. See screenshot at the top of https://github.com/romkatv/gitstatus . This is an amazingly convenient tool. When you are working on chromium, on every command you type gitstatusd needs to list the contents of 25,000 directories. Low level optimizations like the ones described here are what makes gitstatusd 10 times faster than `git status`, which in turn…
Your documentation indicates that you've tried with core.untrackedCache, but have you tried core.fsmonitor with the watchman hook? Obviously your "gitstatus" is still generally useful, but if your main itch you're trying to scratch is to have a faster "status" in a particular repo then you should be able to get that down to a few milliseconds with "git status", if you're willing to have watchman sit in the background…
> [...] have you tried core.fsmonitor with the watchman hook?
I read the docs but it seems like it's not something I can enable on users' machines. Or maybe there is a way to take advantage of it even if it's not enabled? I really haven't looked much into it.
To clarify, my main motivation isn't to make my own prompt latency low (I don't even work on large git projects) but to make Powerlevel10k as good a product as possible. Git latency is a pain point for the existing users, so I work on optimizing it.
I also cannot rely on users to enable untracked cache even if their filesystem allows it. So gitstatusd performs tests similar to `git update-index --test-untracked-cache` in the background and builds its own untracked cache if tests pass. This makes for a good user experience with no setup or configuration fiddling.
Re: Fast Directory Listing on Linux
#40You 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