[RFC] New 2x faster escape code parser using vector CPU instructions

[kovidgoyal]

Hi all,

I've spent the last few months working on and off on a new escape code parser for kitty, that uses vector CPU instructions (AVX2 or SSE 4.2 or their ARM equivalents, whatever is available) to greatly speed up parsing of the input byte stream. This has led to speedups with throughput for parsing different kind of input data of between 50% to 400%.

There is a new benchmarking kitten that can be used to benchmark terminal performance as well. The benchmark results from running kitten __benchmark__ on my system with kitty master branch and vt branch (the latter has the new code):

master branch:

Results:
  Only ASCII chars         : 4.55s      @ 43.9    MB/s
  Unicode chars            : 2.73s      @ 64.9    MB/s
  CSI codes with few chars : 3.56s      @ 28.1    MB/s
  Long escape codes        : 8.12s      @ 96.5    MB/s
  Images                   : 10.06s     @ 53.0    MB/s

vt branch with SIMD acceleration:

Results:
  Only ASCII chars         : 1.73s      @ 115.7   MB/s
  Unicode chars            : 1.78s      @ 99.5    MB/s
  CSI codes with few chars : 1.76s      @ 56.7    MB/s
  Long escape codes        : 2.39s      @ 327.9   MB/s
  Images                   : 1.97s      @ 270.8   MB/s

A table comparing the results from the vt branch with other terminal emulators I have on my system is at https://github.com/kovidgoyal/kitty/blob/vt/docs/performance.rst#throughput showing kitty is much faster than the rest with the new code.

There are of course some downsides, most importantly, the new code required fairly invasive changes to various parts of kitty so its likely some edge cases are broken. In particular kitty no longer supports input data in non utf-8 encodings and also does not support C1 control codes. The latter are supported only by VTE based terminals and WezTerm out of the box, so they are not widely used.

I'd appreciate if some of you could build kitty from source and help
test things for regressions. Building kitty from source is very easy you
need only C and Go compilers and to run a single command, instructions are at: https://sw.kovidgoyal.net/kitty/build/

Please report any issues you find here.

Thanks, and enjoy!

P.S. For the curious, the things that have been sped up are:

1. Searching for the start and end of escape codes in the input byte stream
2. UTF-8 decoding via SIMD instructions
3. base64 decoding via SIMD instructions (base64 is used for various
   escape codes such as images, copy/paste, etc.)
4. SIMD XOR used for securely storing image frame data in a disk cache

Currently I have restricted the SIMD implementations to AVX2 at max, not
AVX512 as that tends to have a major energy/warm up penalty and prevents
running on "economy cores". Something to revisit in the future.

[EgZvor]

In what cases is this change perceivable?

[kovidgoyal]

On Tue, Jan 16, 2024 at 11:56:58PM -0800, Egor Zvorykin wrote: In what cases is this change perceivable?

Depends on what you do in your terminal. Anything that requires processing lots of data fast, will be faster.

[EgZvor]

Will this improve Vim redrawing speed?

[kovidgoyal]

It will, indeed my original motivation for making kitty was the horrible performance of vim in the terminals at the time. However, whether you notice this particular change or not as a human, depends on your vim config, terminal window size, how sensitive you are to noticing such things, etc.

[neurocyte]

Impressive numbers! I have tried a few basic tests and it is definitely faster. Up to 30% with the craziest pixel pushing test case I tried and around 10% when just scrolling large amounts of text. Nice!

In regular use kitty is really never the bottle neck in anything I do, but it should be a nice little bit of battery/CPU saving though.

I have been using a build from the vt branch all afternoon and have not seen any kind of regression so far. 👍

[mikesmithgh]

This is awesome. Should this build on MacOS?

ProductName: macOS
ProductVersion:	14.2.1 
BuildVersion: 23C71

I am receiving the following error:

./dev.sh build
[1/1] Compiling kitty/simd-string.c ... done
Compiling kitty/simd-string.c ...
clang -MMD -DNDEBUG -DPRIMARY_VERSION=4000 -DSECONDARY_VERSION=31 -DXT_VERSION="0.31.0" -DGL_SILENCE_DEPRECATION -I/Users/mike/go/src/github.com/kovidgoyal/kitty/dependencies/darwin-arm64/include -Wextra -Wfloat-conversion -Wno-missing-field-initializers -Wall -Wstrict-prototypes -std=c11 -pedantic-
errors -Werror -O3 -fwrapv -fstack-protector-strong -pipe -fvisibility=hidden -D_FORTIFY_SOURCE=2 -mbranch-protection=standard -fno-plt -flto -pthread -I/Users/mike/go/src/github.com/kovidgoyal/kitty/dependencies/darwin-arm64/include/libpng16 -I/Users/mike/go/src/github.com/kovidgoyal/kitty/dependen
cies/darwin-arm64/include -I/Users/mike/go/src/github.com/kovidgoyal/kitty/dependencies/darwin-arm64/include -I/var/folders/wj/cqy1nsyn4wn94d96btkldt0r0000gn/T/t/openssl,x86_64,-5kbzhdrp/include -I/Users/mike/go/src/github.com/kovidgoyal/kitty/dependencies/darwin-arm64/include/harfbuzz -I/Users/mike
/go/src/github.com/kovidgoyal/kitty/dependencies/darwin-arm64/python/Python.framework/Versions/3.9/include/python3.9 -c kitty/simd-string.c -o build/fast_data_types-kitty-simd-string.c.o
In file included from kitty/simd-string.c:13:
kitty/simd-string-impl.h:18:10: fatal error: 'simde/x86/avx2.h' file not found
#include <simde/x86/avx2.h>
         ^~~~~~~~~~~~~~~~~~
1 error generated.
The following build command failed: /Users/mike/go/src/github.com/kovidgoyal/kitty/dependencies/darwin-arm64/python/Python.framework/Versions/Current/bin/python3 setup.py develop
exit status 1

[kovidgoyal]

It will work on macOS, you just need to update your copy of the dependencies, with ./dev.sh deps

[mikesmithgh]

It will work on macOS, you just need to update your copy of the dependencies, with ./dev.sh deps

thanks, that worked

[ad-chaos]

I'm getting broken rendering when running the vt branch on my M1 mac.

with the following zshrc

PS1="%% "

export KEYTIMEOUT=1
bindkey -v

autoload -Uz compinit
compinit
zmodload zsh/complist

zstyle ':completion:*' menu select
bindkey -M menuselect '^[' send-break

and the following kitty.conf

font_family      Inconsolata Medium
bold_font        Inconsolata SemiBold
italic_font      Inconsolata Light
bold_italic_font Inconsolata SemiBold
font_size 20

create a window with 50x20 cells , cd into the kitty repository and ls to somewhat fill the entire screen, then cd <Tab> and navigate to any menu item and press escape to see some items from the ls output disappear.

random-clears.mov

And sometimes all output is immediately cleared on my terminal, though I was unable to make a reproducer for it.

Screen.Recording.2024-01-19.at.9.40.32.PM.mov

[kovidgoyal]

@ad-chaos Can you please run kitty with --dump-bytes and do minimal steps to reproduce the problem and post the dump alongwith the window size in cells you reproduced at. Your steps arent reproducing on my M2 mac.

[ad-chaos]

dumped-bytes.log

The window size was 50x20 cells

[kovidgoyal]

@ad-chaos: Thanks, with that I can see a difference between master and
vt, will investigate more when I have a moment.

[kovidgoyal]

@ad-chaos Fixed by 12b684e

[ad-chaos]

I can confirm the problem no longer exists on the latest vt branch.