Caching to speed up prompt generation

[romkatv]

tl;dr: I patched P9K to reduce my zsh prompt drawing latency by over 10x. Is this something you would be interested in adopting?

I recently started using Windows Subsystem for Linux and discovered that my standard Linux zsh environment was so slow, it was barely usable. It was taking over a second to draw a prompt after each command. Granted, it was never snappy even on Linux but it was at least manageable.

I've spent some time profiling and optimizing the code and the results look promising. On each prompt P9K performs a lot of computation and over 90% of it is the same as in the last prompt. I implemented simple caching to avoid recomputing things and now my prompts get rendered in less than 100ms on WSL -- over 10x reduction in latency. They are now also blazingly fast on Linux.

I'm not an expert in zsh, so I didn't want to open a PR right away. I also didn't write any tests. If there is interest in this type of improvements, the code is here: https://github.com/romkatv/powerlevel9k/tree/caching. The code adds a general caching mechanism for anything that prompt generators might want to cache between calls, and then applies it to left_prompt_segment and right_prompt_segment for nice latency reduction across the board. It also contains optimizations for all prompt generators that I personally use and that were showing up on my profile as being slow. Let me know what you want me to do. Open a PR, sign something so that you can pull the code, go away, something else?

P.S.

My .zshrc is here: https://github.com/romkatv/dotfiles-public/blob/master/.zshrc.

[onaforeignshore]

This is a very interesting approach, but are you aware that the whole codebase is being rewritten for 0.7.0? Your functions are based on the master (current) branch, but we are in the process of migrating to the next (0.7.0) branch.

[romkatv]

... are you aware that the whole codebase is being rewritten for 0.7.0?

Nope. Didn't know that. I'm open to suggestions for how to proceed. Doing nothing is fine with me, too.

[romkatv]

In case anyone is also bothered by how slow the vcs/git prompt is, I've managed to speed it up by a large margin. On Linux my whole prompt (which includes vcs as well as all the prompts I listed in the previous comment) renders in 50ms when I'm in a git repo with 1k files. In a large repo such as Linux kernel, it renders in 300ms -- too slow for my taste. I added an option to disable scanning dirty files for repos above certain size and set it at 4k files in my .zshrc. With this option my prompt renders in 150ms when in Linux repo. The prompt also uses color-coding to signal that it didn't scan for dirty files. Finally vcs prompt is fast enough to be usable for me!

The trick was to write a custom C binary that prints everything we need to know about a git repo. It's much faster than calling git multiple times, which spawns a dozen processes with accompanying pipes and repeats many actions unnecessarily -- such as scanning parent folders in search of .git. And also caching, of course, to make rendering itself fast. The C code is in https://github.com/romkatv/gitstatus. The ZSH code is in the same branch as caching: https://github.com/romkatv/powerlevel9k/tree/caching.

If anyone wants to give it a try with their own master-based setup (especially if it's sluggish), here's a non-committal way to do it.

# Enable caching of parts of the prompt to make rendering much faster.
POWERLEVEL9K_USE_CACHE=true
# Enable alternative implementation for the vcs prompt. It's much faster but it only supports git.
# Tell it to not scan for dirty files in repos with over 4k files.
POWERLEVEL9K_VCS_STATUS_COMMAND="/tmp/gitstatus --dirty-max-index-size=4096"
wget https://github.com/romkatv/gitstatus/releases/latest/download/gitstatus -P /tmp
chmod +x /tmp/gitstatus
# Adjust this path depending on where you normally source powerlevel9k.zsh-theme from.
POWERLEVEL9K_INSTALLATION_DIR=~/.oh-my-zsh/custom/themes/powerlevel9k
source <(curl -f https://raw.githubusercontent.com/romkatv/powerlevel9k/caching/powerlevel9k.zsh-theme)

Then see if your current shell feels more responsive. No permanent changes are done to your setup, so once you exit zsh you are back to business as usual.

I can vouch for the following prompts being fast in the patched version:

• root_indicator
• dir_writable
• dir
• status
• command_execution_time
• background_jobs
• time
• vcs

[dritter]

Hi @romkatv !
This is very interesting and super impressive results you got. It is true that we depend crucially on IO performance. This is especially a pain on WSL or inside VMs.
TBH I am a bit ambiguous about the caching, because there are a lot of external influences that could/should lead to cache invalidation that we cannot control. In case of the dir segment, which is good cachable at the first glimpse (chpwd hook), there are truncation strategies that depend on a unique path. So, if another folder was created that starts with the same characters, without changing the folder, the cache would be stale..
This is a pretty weak example, but my point is the more the command depends on externals, the less cachable is the result.
But you found an awesome "workaround" (holy moly, you've written a whole C++ lib) for the vcs (well, at least for the git part) segment. Have you considered upstreaming this either to git directly (I always wondered why there is no circuit breaker for git status when the first untracked file was found) or to zsh (as a replacement for VCS_INFO)?

@bhilburn Would we add a binary to P9K to replace VCS_INFO? And that needs to work on all major OSes..

Edit: By upstreaming to git I meant the concept obviously. Having a single command that outputs machine-readable information as fast as possible. Of course there is git status --porcelain, but we need a lot more information that that.

[romkatv]

TBH I am a bit ambiguous about the caching, because there are a lot of external influences that could/should lead to cache invalidation that we cannot control.

This is implemented in a safe way. The data we pull from the cache is never stale. Every entry in the cache is immutable and it never becomes invalid. Here's how it works. Every time we need to draw a vcs prompt, we call gitstatus. It might print something like this (10 values, each on its line):

"master"
"master"
"git@github.com:romkatv/gitstatus.git"
""
1
1
0
3
0
2

(The meaning of each line is documented at powerlevel9k.zsh-theme).

From this we can assemble the vcs prompt. It doesn't depend on any other data such as $PWD, time of the day or anything else (if it did depend on any of the above, we would add them to the cache key). Once we assemble the prompt, we can save it for the future. The key in the cache is the ten lines that gitstatus gave us. The next time we call gitstatus, it's likely to give us the same 10 lines of data because the state of a repository rarely changes (at least the part of the state that affects the prompt). We find the fully formatted prompt that corresponds to this data in the cache -- with all icons and colors already resolved -- and display it instantly.

So we have two things: fast way to get the git state, and then a fast way to format that data as a prompt. The first is fast because C, the second is fast because caching.

I use the same technique for printing other prompts, such as dir. The input data for dir is the directory path, so the cache contains things like "/home/romka" => <formatted dir segment, with icons colors and all>. Whenever I'm in "/home/romka", the segment can be looked up and printed in no time. It's always valid for this directory.

Likewise for status segment. Its key is the error code of the command. For error code 0 the segment always looks the same (green checkbox on grey background for me), so we can cache it. Likewise for error code 1, 2 and so on.

Have you considered upstreaming this either to git directly (I always wondered why there is no circuit breaker for git status when the first untracked file was found) or to zsh (as a replacement for VCS_INFO)?

Not really. This is a larger commitment than I can afford.

FWIW, I did try to make it more-or-less generic in p9k. It's possible to ditch vcs_info in p9k in favor of much simpler model. You can see in the code that I added POWERLEVEL9K_VCS_STATUS_COMMAND. This parameter specifies the command that is supposed to print the ten lines. prompt_vcs can then render the prompt with very little effort, thanks to the data being in exactly the format it needs.

By default, POWERLEVEL9K_VCS_STATUS_COMMAND could point to a function that generates the ten lines by calling git: git rev-parse --abbrev-ref HEAD to print the current branch, git rev-list --walk-reflogs --count refs/stash to get the number of stashes, git diff-index --cached --quiet --ignore-submodules=dirty HEAD to check for staged files, and so on.

Users could override POWERLEVEL9K_VCS_STATUS_COMMAND for better performance (e.g., by using my binary, or even writing something faster). However, I think even without it the prompt will be much faster than with vcs_info, simply because there would be so much less zsh involved in massaging the data.

It's also possible to use vcs_info to produce the 10 lines in the required format. This gives us a fallback for vcs backends other than git. I didn't implement this because I don't work with non-git repos.

[docwhat]

I'm concerned that your gitstatus tool isn't cross platform. Some platforms that should be covered include macOS, ppc64le Linux, the various arms, the bsds, etc.

I have thought of doing something similar using golang (which is great for cross compiling) but my git-internals-fu isn't that strong.

Caching the work that ZSH is doing to build the actual prompt (symbols, colors, etc.) shouldn't be taking so long that caching it speeds it up my 10x. If it is, then we should fix the ZSH code.

[Syphdias]

Just my two cents, I think it's a great idea and it would synergize really well with making the prompt asynchronous (insert fitting issue here). Show the old prompt from the cache and update to the current values if ready. With a synchronous prompt it has its drawback, I agree.

[romkatv]

I'm concerned that your gitstatus tool isn't cross platform.

That's a valid concern. In theory it can be as cross-platform as libgit2, which officially supports all major platforms. Getting there isn't difficult but it's work nonetheless. Ideally, I'd love to see p9k having a configurable provider of vcs status information so that users who care about the responsiveness of their shell (like myself) could plug in their (potentially platform-specific) implementation without having to rewrite prompt formatting code in p9k. Users who don't care could use the most portable default implementation (like vcs_info). This is roughly what I've attempted to sketch in my patch.

Caching the work that ZSH is doing to build the actual prompt (symbols, colors, etc.) shouldn't be taking so long that caching it speeds it up my 10x. If it is, then we should fix the ZSH code.

Indeed. I was surprised when my improvised profiler had pointed to the formatting code as the primary CPU hog in p9k. Having replaced a large chunk of p9k with more efficient code, and having added caching, I've confirmed that indeed formatting is a major cause of prompt latency.

Consider the following trivial prompt function:

prompt_greet() {
  if [[ -n $POWERLEVEL9K_GREETING ]]; then
    $1_prompt_segment $0 $2 green black $POWERLEVEL9K_GREETING LINUX_ICON
  fi
}

If POWERLEVEL9K_GREETING is not empty, this prompt segment will display it with a Linux icon next to it. It's as simple as it gets. No user overrides to change colors or icons or anything fancy like that.

When I add this prompt to POWERLEVEL9K_RIGHT_PROMPT_ELEMENTS and type POWERLEVEL9K_GREETING=hi, prompt_greet generates the following string:

 %f%F{002}<%f%K{002}%F{000} hi%F{000} @

(I've replaced the Linux icon with @ to make it readable.)

We can see the "hi" message surrounded by some fluff. In order to produce this string, p9k executed 120 lines of code. That's a lot of code for such a simple segment. The same 120 lines will execute on every prompt.

If we run the same experiment with the patched version of p9k from https://github.com/romkatv/powerlevel9k/tree/caching, we get 58 lines on the first drawing of the prompt--half of the original--and just 11 lines on subsequent prompts. If you look carefully at the last trace, you'll notice that it says "bye" rather than "hi". And yet, it has hit the cache. This is because p9k has cached the formatting fluff but the dynamic content isn't in the cache. Function prompt_greet will generate its output with 11 lines of code for every prompt after the first one even if we keep changing POWERLEVEL9K_GREETING.

Here are the 11 lines, annotated:

# Should we join this segment with the previous?  This is a function call.
_p9k_should_join_right 4
    [[ 2 -ge 4 ]]
local join=false

# The cache key incorporates everything that affects the formatting of the segment.
# Note the lack of "hi" or "bye" in it.
local cache_key='right_prompt_segment prompt_greet green black LINUX_ICON 008 false'

# Check if we have the formatting fluff in the cache. This is a function call.
_p9k_cache_get 'right_prompt_segment prompt_greet green black LINUX_ICON 008 false'
    _P9K_RETVAL=\''%F{002}<%K{002} %F{000}'\'' '\''002'\'' '\''%F{000}@ '\' 
    [[ \''%F{002}<%K{002} %F{000}'\'' '\''002'\'' '\''%F{000}@ '\' != __p9k_empty__ ]]

# Cache hit! We've retrieved the formatting fluff from the cache.
local tuple=( '%F{002}<%K{002} %F{000}' 002 '%F{000}@ ' )

# Splice the dynamic content into the formatting string and print the prompt.
echo -n '%F{002}<%K{002} %F{000}bye %F{000}@ '

# Update the environment so that the next segment knows how to print itself.
CURRENT_BG=002
LAST_SEGMENT_INDEX=4

The difference in performance is immediately apparently when you try it. Even if your prompt latency feels OK now, you'll still notice the improvement.

I'm happy to keep using my own patched version with a custom C binary. Anyone else is welcome to try it. If you want to use any ideas or code in p9k, go ahead and copy them.

[romkatv]

I think it's a great idea and it would synergize really well with making the prompt asynchronous (insert fitting issue here). Show the old prompt from the cache and update to the current values if ready.

Thanks, Syphdias.

I just want to clarify that the cache I implemented never gives you wrong results. It's a pure optimization that never affects what actually gets printed. The only impact it has is that printing happens much faster, and memory usage is a bit higher. [1]

Even though the git prompt I now have is an order of magnitude faster than the stock one, it produces the same results. [2]

[1] This isn't exactly true. With the official p9k you can set POWERLEVEL9K_TIME_FOREGROUND=red in an interactive shell and the next prompt will have time prompt segment printed in red. My version doesn't pick up live configuration changes (FWIW, the official p9k doesn't pick up all live config changes either; my version just picks up even fewer). But it always, 100%, picks up dynamic environment changes. It never displays wrong or stale data in the prompt.

[2] This is also not exactly true. My gitstatus doesn't support a few features that the official vcs_info-based prompt supports. For example, it never prints tags. This is easily fixable. If anything, the approach with a C binary is much more flexible. You have more freedom w.r.t. what information you extract from git repos and you get to use a decent API instead of solving command-line flag puzzles.

[docwhat]

120 lines of code

A quick look at the code doesn't show much that should be slow. It is all tests ([[ ]]) and string manipulation.

Another question: Are you using ZSH compiling?

Basically, those lines of code should be very fast and if they aren't we should delve into what's being slow and fix it before we start optimizing via caching.

The async stuff is fixing specific known problems and will speed up the VCS segment.

[romkatv]

A quick look at the code doesn't show much that should be slow. It is all tests ([[ ]]) and string manipulation.

No, I'm not. Didn't know such a thing existed. Sounds exciting! What's the right way to enable ZSH compilation for p9k? I'm using oh-my-zsh if that's relevant.

Basically, those lines of code should be very fast and if they aren't we should delve into what's being slow and fix it before we start optimizing via caching.

FWIW, here's trace comparison for prompt_vcs in a git repo: https://gist.github.com/romkatv/5ab160354e69f201a23a33665e674f78. 738 lines vs 19. I believe the original code has called git 15 times and made 20+ file reads directly from .git.

[docwhat]

The magic words to search for are zcompinit and zcompile.

[docwhat]

Basically, those lines of code should be very fast and if they aren't we should delve into what's being slow and fix it before we start optimizing via caching.

FWIW, here's trace comparison for prompt_vcs in a git repo: https://gist.github.com/romkatv/5ab160354e69f201a23a33665e674f78. 738 lines vs 19. I believe the original code has called git 15 times and made 20+ file reads directly from .git.

Oh, I'm not arguing that vcs_info is fast... it is correct but it isn't fast. The async branch (which will in effect have caching since it will only change when it needs to) will address that particular issue.