More sixel renderer optimizations.

[ismail-yilmaz]

Hello @jerch,

I don't want to pollute your repos or other active discussion threads with my findings until I can come up with some practical optimization suggestions for your renderer. So I'll put this here.

I've been doing some heavy profiling on my SixelRenderer since last week. Here are some preliminary results:

• I identified both some bottlenecks in my code and the performance sensitive critical parts of sixel rendering in general.
• I achieved some nice progress by some simple tweaks since last week:
  • I have managed to sequeze out a steady 42 MiB/s (2.90 secs) (parsing + rendering) on your sixel-bench animation, which means ~12 MiB/s gain. for me
  • There is a small performance penalty associated with displaying the animation due to the gui event handling (latency) of our GUI toolkit, But my SixelViewer app (a small testing and benchmarking app) can display the full sixel-bench video on average 38.00 Mib (3.10 secs.). As you can guess, this does not translate 1:1 to final terminal performance, because other variables also effect the vte rendering performance. Still it can achieve slightly higher performance than MLTerm now.

The above improvements are all due to some really simple tricks -one of which I borrowed from you- and the examination of the produced assembly code. I am confident that we can raise the throughput bar even higher, because there is still room for optimization.

In the following days this week I'd like to share my findings (code changes/alterations) with you, which you might find interesting and, hopefully, useful for your c/wasm decoder.

[jerch]

@ismail-yilmaz Wow sounds promising - and ofc I am really curious about these improvements on asm level and whether they also apply to wasm to some degree or could be ported back. Its pure stack machine design makes some optimizations behave worse (even pointer arithmetic tends to run slower from my findings).

[jerch]

@ismail-yilmaz Minor note on what I've found worth looking into, but did not get down to it yet:

• The sixel bit deconstruction with branching is actually much more expensive than always writing something somewhere. With more clever index "routing" like writing empty bits to dummy pixels I can gain ~30% speedup in put_single. This somewhat surprised me, would have thought that the memory access to dummy pixels would outweigh the branching + bit testing by far. But seems the branching creates a heavy load here.
• Imho the conditional checks, if the byte at hand is a sixel (eg. in range 63 to 126), can be made much faster with clever bit shifting. Did only profile that one so far, it adds up to quite some runtime, if the sixel data contains only few compression directives.

Both ideas are somewhat branching related, and I think that is promising ground for further optimizations.

Edit: Btw my decoder function kinda invites to use computed gotos, sadly they are not yet natively supported in wasm. If you want to squeeze 10 - 20% more perf, this might be worth a look as well.

[jerch]

@ismail-yilmaz I implemented the "write always something" in put_single by offsetting the canvas pixels and routing empty bits to canvas[0]. Boosted the raw decoding throughput from ~85 MB/s to 95-100 MB/s for my test images (~15% boost). Still not sure, why it shows that much of a speedup, could be a cache side effect - wild theory: I have the data chunk for reading right before that in memory, maybe it gets always loaded into cache due to this "accidental" locality.

[ismail-yilmaz]

@jerch ,

implemented the "write always something"

I apologize for my late reply (Really busy now, and I'll comment on the things you've written, tonight - GMT+3). But I think I finally understand why you get so high results (which is very impressive by the way, congrats!) When I do the same thing, the performance of my decoder falls down to ~25 MiBs (from 42). I now know why (at least, I know what's the main culprit. I'll write the whole thing tonight (GMT + 3) and share some findings, with a suggestion on your decoder's main loop.

Best regards,
İsmail

[jerch]

I apologize for my late reply ...

Well wouldn't call 30 min "late" 😸

Yes I am really interested in your asm findings and whether I can backport some ideas to wasm as well. Wasm itself is pretty reduced in op codes and its stack mechanics, so some things might not work out there.

When I do the same thing, the performance of my decoder falls down to ~25 MiBs (from 42).

Oh, thats weird. Note that those numbers are raw decoder speed, the whole turnover in xterm.js with the sixel-bench test is just at 36 MB/s (gets slowed down by the JS handling pre/posthand). Furthermore my test machine is a i7-2760QM with 2.40GHz and 1333 MHz (0.8 ns) double bank memory. The CPU is kinda old, but I remember seeing big differences in i3/i5 types vs. i7, esp. due their different cache settings. If we want comparable metrics across machines, maybe we should switch to cycles instead.

[ismail-yilmaz]

@jerch

A disclaimer: My experience with, and knowledge of, webassembly is pretty limited at the moment. (Not so with Asm/C/C++ though. )

I will be using the sixel-bench as my main reference here. And the machine I use for testing is old enough Athlon FX 6100 (six core) @3.3 GHz, 8MB, dual channel, @1866 Mhz.

My findings suggest that there are three critical sections that impact the sixel rendering performance. Let's go step by step, shall we?

1. Parameter collection

This was the first interesting part. The fact that higher color palette settings (>= 256) and sixel compression relies on a supplied parameters list makes this section a good candidate for optimization. Throughout my tests and benchmarking I came to the conclusion that for effective cpu cache utilization it would be better to collect the consecutive parameters in a single, separate loop at once (i.e via a dedicated inline function for better instruction and data cache utilization.)
To this end I've created three versions of ReadParams() function, each with a slight modification and run them all 100 times on a 10 MB file that contains random and valid sixel parameters ranging from 0 to 999999.

The code of the said three function can be inspected here. (Note that I use Upp::Stream instead of std::stringstream on the actual code, which is faster and its Peek() and Get() methods are trivially inlineable.)

Here are the results (with -O3 optimization):

// TIMING     - readparams_plain    :  2.97 s  - 29.71 ms ( 2.97 s  / 100 ), min: 29.00 ms, max: 32.00 ms, nesting: 0 - 100
// TIMING     - readparams_faster   :  1.94 s  - 19.37 ms ( 1.94 s  / 100 ), min: 19.00 ms, max: 27.00 ms, nesting: 0 - 100
// TIMING     - readparams_unrolled :  1.72 s  - 17.25 ms ( 1.73 s  / 100 ), min: 17.00 ms, max: 18.00 ms, nesting: 0 - 100

// THROUGHPUT - readparams_plain    :  3.40 MiB/s
// THROUGHPUT - readparams_faster   :  5.20 MiB/s
// THROUGHPUT - readparams_unrolled :  5.80 MiB/s

While the difference between faster and unrolled version can be considered negligible, it is still there. And it also shows that conditional branching may not always be the worst path to take. Which brings me to the question: Does this also apply to wasm? Did you already consider this approach for your decoder.cpp? Because you seem to be handling the parameters on the main loop level.

A side note: A code line from decoder.cpp written in two different ways (CLANG-webassembly, -O3)

else if (code > 62 && code != 127) // original version.
        local.get       3
        i32.const       63
        i32.lt_u
        br_if           0
# %bb.32:               
        local.get       3
        i32.const       127
        i32.eq  
        br_if           0


else if (unsigned(code - 63) < 64) // My altered version
        local.get       3
        i32.const       -63
        i32.add 
        local.tee       2
        i32.const       63
        i32.gt_u
        br_if           0

Now, I don't know which one would be faster as I don't have in-depth knowledge of wasm, so please feel free to correct me at every level, but the fact is this code used for put_pixel is on a very perf-sensitive path, and the altered version seems at least shorter and involves less branching (I don't know how many cycles each instruction takes on wasm) so it may have an impact on the performance - albeit small.

To be continued...

[jerch]

@ismail-yilmaz Thx a bunch, I'll check these things out.

About critical sections - I kinda have a hard time to profile it in wasm, I simply dont know any tools, that can achieve it within wasm. So I went the faulty route of deactivating code paths and comparing the runtimes, which ofc carries the risk of creating bigger dead code branches, that get eliminated by the compiler. Still my findings are these in wasm:

• only inner state handling (deactivated sixel, cursor, params and color processing): 150 - 200 MB/s
• all minus sixel processing (bit decomposition + pixel safe): 95 - 180 MB/s
• all minus params and color processing: 140 - 190 MB/s
• all: 93 - 165 MB/s

Note that the big spread in the runtimes is a result of one test image with 4096 colors and random pixels. This image has almost no compression, thus very high throughput numbers. Normal images are grouped around the lower number with only small variations (< +20 MB/s).

Interpretation of the numbers:

• Sixel processing and pixel save accounts for ~40% of the runtime. This is actually lower than I expected.
• Params and color processing accounts for ~7 % of the runtime. No surprise here, it is within my expectations with slightly worse runtime ratio compared to data ratio, thus slower in processing than the sixel path. This could be further optimized, but the gains are unlikely to surpass 5% overall runtime.
• Most runtime is spent for the inner state handling with ~50% runtime. WTH, the inner state handling only switches branches based on ps.state. Have to admit, that the branches are quite scattered/nested with that weird jump helper, still my expectations were in the 15 - 30% range, not 50%.

So I gonna try to find a simpler state model, as it promises great savings. My original JS implementation uses a DFA switching on every input byte. While this is fairly equal in JS, it actually performs worse in wasm. The current wasm state model is a direct transfer of the DFA states into switch and if-else conditions with less switching per byte but deeper nested side paths (the jump helper results from preserving the DFA states, but might not be needed everywhere).
A first dig into the branching direction shows, that the switch statements might be problematic. They get compiled to br_table instructions in wasm, which dont seem to get the jump table optimization in the final machine code created by the wasm runtime (needs more investigation, did only a quick test with different amount of cases, which revealed a O(n) dependency, bummer).

Edit: Fixed the mixed numbers above.

[ismail-yilmaz]

@jerch ,

I will hopefully write the second and third parts this weekend, and try to clear up some points with the numbers and profiling.
But let me say that I found the culprit in my decoder and changing a single thing skyrockets my decoders throughput to 61 Mib/s (on `sixel-bench) But it is costly, and not really ideal for my decoder's use cases.

I gonna try to find a simpler state model, as it promises great savings.

This is my main loop, by the way:

			for(;;) {
				int c = stream.Get();
				switch(c) {
				case 0x21:
					GetRepeatCount();
					break;
				case 0x22:
					GetRasterInfo();
					break;
				case 0x23:
					SetPalette();
					break;
				case 0x24:
					Return();
					break;
				case 0x2D:
					LineFeed();
					break;
				case -1: // eof or err
					goto Finalize;
				default:
					if(check_range(c, 0x3F, 0x7E))
						PaintSixel(buffer, c - 0x3F);
					break;
				}
			}

Each function is inlined and the only other two inner loops are in ReadParams() (inlined inside SetPalette, GetRepeatCount, GetRasterInfo) and PaintSixel() Also on sixel bench, ReadParams gets called 17575647 times (total), while the PaintSixel is called 69508135 times (total, and called for both compressed and single sixels), And these numbers do not even account for inner loops of these functions! That's why I think they are very sensitive.

[jerch]

@ismail-yilmaz 61 Mib/s for the full deal with sequence parsing, sixel decoding and painting in the terminal? Wow, thats far beyond what I can achieve (xterm.js input processing alone is slower lol).

May I ask you to run the benchmarks of my lib? I have the feeling, that our machines are quite different in the throughput numbers, sadly I have no clue, how to measure wasm execution in terms of CPU cycles, which would be a better number for comparison.

If you are up to test my wasm decoder I can give you the compiled version, thus you wont need to install the emscripten SDK.

[ismail-yilmaz]

@jerch

61 Mib/s for the full deal with sequence parsing, sixel decoding and painting in the terminal? Wow, thats far beyond what I can achieve (xterm.js input processing alone is slower lol).

Unfortunately no. It is sequence parsing + sixel decoding.

• If I display the full animation in the sixel viewer, I get -56 Mib/s. (gui-processing penalty)
• If I display the full animation in the terminal via pty -> ~31 Mib/s (where mlterm gets 23 Mib/s)
• If I dispaly the full animation in the terminal, by direclty feeding to it, -> ~40 Mib/s.

The drop has several reasons. But the most important reason is I have to stick with the gui calls and rules provided by our framework to ensure backend compatibility, as our vte is a widget, not an app. But the raw throughput (when only displaying the image is disabled) for sixel-bench in our vte is around 44 Mib/s. So it is pretty much optimized for its environment.

But this "extremely fast" rendering is not feasible for me because I need to use a static buffer with fixed length to get this. You can see where I'm getting at.. :))

It appears that 42-44 Mib/s range I've recently achieved is the limit for my decoder unless a fundamental change in my assumptions and decoder design.

If you are up to test my wasm decoder I can give you the compiled version, thus you wont need to install the emscripten SDK.

Ah, I totally forgot to mention that I already compiled it just two days ago, but did not have time to test it, sorry. However, if you have an additional script to test sixel-bench with yout wasm, that would be very nice. :)

I will run the existing tests and compare the results with mine. (I'll share the results within next week)

I am really interested in optimizing sixel rendering now, and I really like to see xterm.js with top-notch sixel support. Besides, your decoder.cpp already gets a lot of things right. In fact I was planning to build an experimental renderer around it to see how well it fares against mine in the same environment, but I am very busy, so this will take some time...

[jerch]

Ah, I totally forgot to mention that I already compiled it just two days ago, but did not have time to test it, sorry. However, if you have an additional script to test sixel-bench with yout wasm, that would be very nice. :)

I can prepare a script for the sixel-bench test, sure thing.

If you pulled the whole node-sixel repo, you can run its benchmarks with:

cd node-sixel
git checkout faster_decode
# edit wasm/build.sh to point EMSCRIPTEN_PATH to your emsdk_env.sh
# then run
npm install  # will abort, just ignore it
npm run build-wasm
npm install
# benchmark
node_modules/.bin/xterm-benchmark ./lib/index.benchmark.js

Have not tested that yet on a clean checkout, so bear with me if its not working out of the box. Also my newer optimizations are not yet checked in, thus you will see slightly lower numbers.

Edit: Fixed the checkout/build commands.

[ismail-yilmaz]

I can prepare a script for the sixel-bench test, sure thing.

I'd be grateful, thanks!

I will benchmark it on this sunday.