romka2

You can use powerlevel10k with the default system font. It works fine with urxvt without any twiddling.

The minor modification would be from `$opts` to `$=opts`.

I'd been using ZSH for a year as if it was Bash with better history and much better completions. The difference mentioned above was the only one I knew about. I kept writing my scripts in Bash and was quite happy with the UX.

Pro tip: s/powerlevel9k/powerlevel10k/. Same config, same theme, but much faster.

I remember reading this article back when I was still using Bash. I've finally got the history I like only after switching to ZSH.

You can get decent history in ZSH just by setting the right options. If you want great history, you'll need to write a bit of code. Right now my history works as follows.

History is written to disk after every command. Up and Down keys go through the local history (from the same session). Ctrl+Up and Ctrl+Down go through the shared history (from all sessions). Ctrl+R also uses shared history (it's easy to add another binding for local history but I don't have it). Pressing Up/Ctrl+Up after typing something will go over history entries that have the matching prefix. For example, `git<Up>` will show the last command from the current session that starts with `git`. Here's my config: https://old.reddit.com/r/zsh/comments/bsa224/how_to_setup_a_....

In addition, my history is stored in Git. History from the local machine comes first, and from other machines second. This is fairly easy to do it Bash, too.

This format looks somewhat underpowered. If one record is corrupted, there is no way to read anything after it. For the same reason there is no lookup/sharding support, such as finding the first record that starts in the second half of the file. If a writer crashes, a new instance of writer cannot append to an existing file without reading its whole content and truncating on the last readable record.

RecordIO supports a form of random access lookup, although it's rarely used. Riegeli supports random access lookups as a first-class operation.

That appears to be exactly RecordIO.

I suppose you mean "exactly" in a figurative way. Riegeli is definitely inspired by RecordIO and is meant as a successor to it but it's not RecordIO.

Is there a reason that doesn't meet your requirements?

I need to store timeseries with fast lookup by timestamp. Riegeli doesn't support this out of the box. If I had discovered it before I built ChunkIO, I probably would've pulled the low-level code out of it and added timeseries support on top. Or maybe not. Reliability is very important to me and it's risky to use work-in-progress software that may or may not have any production footprint (I'm no longer with Google so I don't know if they use it internally.)

There is no listed equivalent of RecordIO. What do people use for high-reliability journals?

When I needed something like RecordIO to store market data, I couldn't find anything. So I implemented https://github.com/romkatv/ChunkIO. I later learned of https://github.com/google/riegeli (work in progress), which could've saved me a lot of time if only I found it earlier. I think my ChunkIO is a better though.

What part of the code do you expect to get faster with `-march=sandybridge -mtune=sandybridge`?

excessive ASM is a mistake these days

There is no ASM in the article.

I would agree with this sentence if "optimizing" were replaced with "making marketing claims". Optimization is the process of finding the fastest implementation. In the case of ListDir each successive version is faster than the last on a benchmark with warm IO caches, therefore it'll be faster on the same benchmark with cold IO caches (this is not a general claim; I'm talking specifically about ListDir). Benchmarking with warm IO caches is easier (invalidating caches is generally very difficult) and yields more reliable and more actionable results, hence it's better to benchmark with hot caches. It has nothing to do with the average vs worst case.

No, I did the opposite. I made sure the disk caches are warm before each benchmark. Since all versions of ListDir are identical in terms of IO demands, warming up caches is an effective way to reduce benchmark variability and to make performance differences of different code versions easier to detect without changing their order on the performance ladder.

I've posted some details explaining why gitstatusd doesn't use inotify in https://github.com/romkatv/gitstatus/commit/050aaaa04b652e15.... The short version is that the default max_user_watches limit is much too low to be useful for gitstatusd and I cannot ask or expect users to change their system settings.

nftw is a wrapper over opendir/readdir, not the other way around.

Yep, this is mentioned in the doc.

[...] every element in entries has d_type at offset -1. This can be useful to the callers that need to distinguish between regular files and directories (gitstatusd, in fact, needs this). Note how ListDir() implements this feature at zero cost, as a lucky accident of dirent64_t memory layout.

Yep, every string is potentially an allocation (unless it's short and std::string implements Small String Optimization) plus O(log N) allocations by the vector itself.

C++11 didn't make returning the vector in this function faster because it's written in a way to take advantage of RVO. It did make growing the vector faster though -- individual strings now get moved instead of copied.

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.

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.

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

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.

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.

You are quoting a self-deprecating joke. I care deeply about my code being readable, which can be quite challenging when writing high-performance code close to the metal. I'm self-consciously aware of every tricky bit I put in my code. I have to be confident it's worth it (usually because it makes things faster in the real world) and offset the added complexity by writing documentation.

"." and ".." are filtered out before sorting. Sorting is O(N^2) in the common case (when there are fewer than 65 files in a directory), so it pays off to reduce the number of entries by 2 before we get there.

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.

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.

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.

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.

Take a look at the example: https://github.com/romkatv/gitstatus#gitstatusd. Even though this example uses ZSH, it's just for exposition. It launches gitstatusd, writes a request to its stdin, reads the request from stdout and prints it. You can discern from it the format it uses for requests and responses.

There is also a formal description of request/response format in `gitstatusd --help`, or in https://github.com/romkatv/gitstatus/blob/master/src/options....

Indeed, gitstatus is one of the reasons Powerlevel10k is faster than all other ZSH themes. It also uses a patched version of libgit2 that is 4 times faster than the original. There is some info here: https://www.reddit.com/r/linux/comments/b0suyu/powerlevel10k....

Powerlevel10k also uses advanced ZSH. Explained in https://www.reddit.com/r/zsh/comments/b1xxuj/abusing_zsh_par....

There is also information on https://github.com/romkatv/powerlevel10k/ that probably didn't exist when you've discovered Powerlevel10k.

Note that the hashtable micro-benchmarks open-sourced by Google cannot be used to figure out which of the two hashtable implementations is faster. See https://groups.google.com/forum/#!topic/hashtable-benchmarks... for the details. If someone ran a high-quality production load test with two implementations (Google definitely can do that), it would give us useful information.

Disclaimer: I wrote the micro-benchmarks referenced above and parts of Swiss Table. I'm no longer with Google.