Fast Directory Listing on Linux
github.com
Fast Directory Listing on Linux
1–10 of 75 posts
Re: Fast Directory Listing on Linux
#2You 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.
Re: Fast Directory Listing on Linux
#3You 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.
Thanks, that's good to know.
The final version of ListDir calls memcmp only when there are files in the same directory that have identical first 8 characters. Apparently, this is rare enough that memcmp doesn't show on the CPU profile. But if it ever does, I'll look into replacing it with something else.
Re: Fast Directory Listing on Linux
#4But why? Why create a tool that does `git status` 10x faster?
Re: Fast Directory Listing on Linux
#5But 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 makes prompt responsive when otherwise it would be sluggish.
Re: Fast Directory Listing on Linux
#6I wonder how this compares to filesystem traversal APIs like fts/ftw?
Re: Fast Directory Listing on Linux
#7But why? Why create a tool that does `git status` 10x faster?
Because `git status` takes a really long time if the repository is large. And no, the linux kernel is not considered a large repository, there are far larger ones around, mostly private at companies, such as Microsoft and others.
Re: Fast Directory Listing on Linux
#8I wonder how this compares to filesystem traversal APIs like fts/ftw?
fts and ftw are glibc wrappers over glibc wrappers that I had to bypass for better performance. They are made for convenience, not for speed.
Re: Fast Directory Listing on Linux
#9You 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.
Thanks, that's good to know. The final version of ListDir calls memcmp only when there are files in the same directory that have identical first 8 characters. Apparently, this is rare enough that memcmp doesn't show on the CPU profile. But if it ever does, I'll look into replacing it with something else.
You should try with the pathological but relatively common case of thousands of files named 'logname.YYYYMMDD.log.gz'
Re: Fast Directory Listing on Linux
#10Earlier quoted context omitted.
Thanks, that's good to know. The final version of ListDir calls memcmp only when there are files in the same directory that have identical first 8 characters. Apparently, this is rare enough that memcmp doesn't show on the CPU profile. But if it ever does, I'll look into replacing it with something else.
You should try with the pathological but relatively common case of thousands of files named 'logname.YYYYMMDD.log.gz'
The final implementation of ListDir has two worse-case scenarios. One is when all files have identical 8 first character but then differ almost immediately. This is bad because I'm telling memcmp that I have 256 bytes of data, which causes it to use the vectorized loop only to exit it on the first iteration. Another is when all files are 255 characters long and differ at the very end. This is bad because string comparisons become very expensive. Even though I'm not showing these benchmarks in the article, this implementation performs very well even in these cases.