libretro/RetroArch — pull request #566 by Alcaro (2014-02-21 21:04:18+00:00)
Title: New state_manager implementation

(Skip to ----- HERE ----- if you're not interested in how savestate compression can be implemented and you just want to see what accepting this pull request will lead to.)

While writing a program of my own, I chose to write my own implementation of RetroArch's savestate manager, using another internal data structure. (Actually, I wrote three different implementations, to see which data structure is best.) None matches RetroArch's model, so that's a fourth; and ZSNES uses a fifth. (I don't know what Braid does. Could be something that's dependent on knowing the exact nature of the inserted data.)

ZSNES' method is simple: It just stores the savestates uncompressed. Nothing else can defeat that in speed and ease-of-implementation, and since the default is storing only 8 savestates, the memory use is no big deal. (The same model remains in ZMZ, despite fitting far worse there; Braid-style plus Snes9X savestates being bigger equals 123MB RAM.) This is called "raw" in the comparison chart.

RetroArch stores 8 bytes for each changed uint32; the offset, and the XOR between the input and output. This has the nice property that 0 is an impossible value for these eight bytes, so it's used to separate each slot. This allows discarding of old savestates to just be "scan forwards from where we'll write the next state, until we find a 0". (Some speed benefit may be had by just storing a "is this valid" flag and doing this scan only if a savestate is pulled, but it's unlikely that this takes enough time to matter.) Overflowing the buffer is handled by ANDing the offset; uneven amounts of RAM is rounded up. Tell it to use 33MB and it allocates 64MB. This is called "retroarch" in the comparison chart.

My first implementation split each savestate up in chunks of some arbitrarily chosen size (I don't remember the exact formula), stored a boolean for each chunk telling if it's changed, and stored the chunk of the previous savestate if it is changed. Since all values are valid in this data structure, each state was preceded by a pointer to the next compressed state (as well as followed by a pointer to itself), and a state was discarded if compressing this one could potentially clobber the next; it also returned to the beginning if it could potentially hit the wraparound point. This was fast, but didn't compress very well compared to the alternatives. This is called "alcaro-blocks" in the comparison chart.

My second implementation was more patching-based. It stores an uint16 telling how many bytes are unchanged, then an uint16 for how many bytes were changed, and finally stores the changed data. Wraparound and discarding old data was handled as previously. This gave a tremendous boost in compression quality, but was a bit slower; however, I was able to optimize it a bit, and it is now faster than the block implementation. This is "alcaro-patch", and is the one I'm offering. (The others give worse space-time tradeoffs.)

My third implementation was almost like the second, but with a granularity of eight bytes, and some things simplified. This gave slightly better speed than alcaro-patch, but considerably worse compression ratio. This is called "alcaro-8byte".

----- HERE -----

I inserted 16384 savestates(*) from Gambatte, Zelda Oracle of Seasons title screen, and compressed that. Then I repeated that 320 times, and repeated that for each of the five savestate compressors.

The results:

| Name | Compression ratio (lower is better) | Time taken, compression (lower is better) | Time taken, decompression (lower is better) |
| ---- | ------------- | --------- | ------- |
| raw | 100% | 15753ms (this has already been subtracted from all other numbers, to make them easier to compare - it's the time spent generating the data to compress) | (uncomparable - not all of the 16384 states could fit) |
| alcaro-patch | 0.589846% | 21003ms | 929ms |
| alcaro-8byte | 1.191570% | 19183ms (91% of alcaro-patch) | 12812ms (1379% of alcaro-patch) |
| alcaro-block | 4.175155% | 20787ms (99% of alcaro-patch) | (uncomparable - not all of the 16384 states could fit) |
| retroarch | 0.909935% | 68758ms (327% of alcaro-patch) | 957ms (101% of alcaro-patch - however, this fluctuates wildly, I've seen everything from 75% to 300%) |
All tests were run on Linux, 64bit. However, despite me adding 'sudo nice -n-20 time ./test', the times fluctuate quite a lot; I'd trust the compression times only to one significant digit, and less than that for decompression. (The compression ratios are the same between runs.)

But even then, 300% can't be explained by fluctuations, and it's not a typo either; this one does take a third of the time to compress the same amount of savestates, compared to the current implementation. (I expect the gains to be lower, but still measurable, for 32bit.)
Of course, most of the time is still spent in the libretro core, but if you're near 60fps, everything counts.

About 50% more savestates will also fit in the same amount of memory; while mine leaves a bit of its buffer untouched (rarch's compressor doesn't do this), the improvement in raw compression ratio more than makes up for this. It will also use the exact amount of RAM you tell it to (plus twice the size of a savestate; the current state manager does that too, though one of them is allocated by retroarch.c), instead of potentially rounding up quite a bit.
I don't know if there's any speed change for decompression, but since decompression is already two hundred times faster than compression, it's not important.

The terrible speed for decompressing alcaro-8byte is probably because it makes a copy of the savestate for each rewind. This would be a 30-40 line patch (it was for alcaro-patch), but since it's already proven to use twice as much memory as alcaro-patch, we don't want it, and it's a waste of time to work on a component we know we won't want.
(The same copy operation is present in alcaro-block, but due to its even worse compression ratio, it couldn't fit all 16384 states in its buffer; we'd end up comparing decompressing 4300 savestates to decompressing 16384, which doesn't give any meaningful results.)

(*) Actually, it's faked data based on these Gambatte states; I recorded whether each byte had changed, and play that back. The compressors don't care about how the data is different, just that it is, and it's far faster to generate. The eight-minute runs to generate the above table would probably take an hour if I used a real Gambatte, and the jittering would be far more severe as well.

I think I identified and matched most parts of RetroArch's code style, but it wouldn't surprise me if I missed something.