keithw/mosh — pull request #527 by cgull (2014-05-18 04:08:30+00:00)
Title: Performance improvements for Terminal::Framebuffer and Terminal::Display

This is a big sprawly pull request that reworks Mosh's framebuffer and display handling, gaining large speedups. It's also a bit of a kitchen sink, it has some other small things that I didn't think worth extracting to their own fork.

This pull is not yet ready for general consumption. There's a new resize crash. There may still be a very occasional random crash happening, hard to tell. There's a couple of things I want to add, and one I want to pull out. It's very ready for testing though, and I encourage people who have had performance problems, or people working on mobile implementations, to try it.

For the common case of an idle Mosh, or one that you're typing into where only one line on the display is being updated, it takes hugely less CPU. My benchmarks show 10-1000x improvement (I'm not sure I completely believe the high end of that range, I'm not sure that OpenBSD box is reporting accurately). For the worst-case of, say, 'cat src/mosh/configure', it's 3x or more faster on every system I tested except for one, which was about 2.5x. (Alas, that one is the RPi, which seems particularly resistant to optimization). The server's performance is improved more significantly than the client's, especially when idle, so shell server admins will like this. Battery constrained devices should do way better. Memory usage is way down. Binaries are 10% smaller. Compiles are 25% faster.

I specifically looked at #487, #468, #372 for optimization/profiling/benchmarking. These are all greatly improved, maybe even fixed. I didn't look specifically at #297 or another issue on performance I can't find now, but they're probably improved. Well, the RPi is still a bit slow for 300x100 windows, but it's usable.
There's some improvement in terminal optimization for #135.

A number of things go into this patch, but the big changes are confined to Terminal::Display and Terminal::Framebuffer. The big ones are:

* Reduce the memory footprint of Terminal::Cell and associated container for characters. Contained characters are now UTF-8 instead of UTF-32, and the container is std::string instead of std::vector. Attributes are contained in a single byte, instead of 5 or so 32-bit words. On 32-bit Linux systems, a Cell was down to 24 bytes at one point (but that has crept up a bit, see below).

* Refactor/rewrite Terminal::Display::new_frame() and put_cell() to make them much more efficient, and to constify the two Framebuffers passed in. This amounts to a near-complete rewrite of the code that does the cell-by-cell display of changed frames. This took quite a bit of work, there's a lot of odd little bits of state to keep track of. I'd like to say that it's cleaner now, but I can definitely say it's much faster now without any cost to readability or abstraction.

The new rendering of diffs is quite good in practice for Latin/narrow characters. I've not seen any mis-rendering on my screen in a while, but I have seen mosh's "round-trip" verification of display updates fail rarely on text from Chinese spam. I don't do C, J or K, so that's at best lightly tested. I haven't closely examined the quality of the old display rendering, so I don't really know how they compare, but I think old and new are not far apart.

* The constification of new_frame()'s arguments allowed the really big win: making Rows ref-counted and copy-on-write. This is the same idea as copy-on-write for std::string but applied at a higher level. This means that instead of copying the entire frame for any change to the display (which can be 1.5MB of data), on every keystroke, only the changed row is copied. Also the multiple copies of the framebuffer that the state code keeps are now mostly the same data, so that memory requirement is reduced (on average, not at the limit). Additionally we're now able to quickly detect when rows are the same because they're the same object, eliminating most of the cost of scanning for changes. This by my estimation changes the cost of small changes on windows of X * Y size from O(x*y) to O(x+y). My benchmarks don't come out quite that well, but the improvement is still huge. The downside is that when the entire display changes, it still all has to be copied, so the improvement is smaller there. This requires C++11 std::shared_ptr or std::tr1::shared_ptr, so that's a significant new dependency. I've spent a bit of time looking at simple C++03 shared_ptr implementations that are not Boost that we could bring into Mosh, but haven't found the right one yet. There's plenty of them out there. Making Boost an optional dependency to get shared_ptr for older systems is also an option.

* I did the light rework to allow Terminal::Framebuffer to use different containers for Cells and Rows. Benchmarking shows that, pretty much everywhere I've looked, vector is somewhat faster than deque for Rows (partly because they hold pointers instead of Rows now), and string is somewhat-to-much faster then vector for the characters held by Cells.

There's probably two dozen small optimizations for various things, some of which are premature. :) But they generally don't obfuscate; many of them improve the code.

For lots of text being displayed, the proudest nail now seems to be the character-input chain. I've got a few small optimizations already in place but I think much larger improvements can be made there too.

Also discovered: Even though Mosh is C++03 code, compiling it with your compiler set to use C++11 doubles its performance every place I've tried it (OS X 10.9, FreeBSD 10, Linux/gcc4.7+). I'd suggest adding that to autoconf, but there will be issues about what version of C++ developers vs. packagers vs. users are using there.

Enjoy! Tell me what you like! Tell me what you don't!