Systematic Gaming

September 24, 2008

Data Compression Evaluation

Filed under: file management — Tags: , — systematicgaming @ 1:38 pm

When discussing load times I mentioned that compression is an important way of reducing load times.  I also said that memory usage can be reduced by compressing data into smaller fixed sized blocks – instead of compressing a file as a single block.  There is also a variety of compression algorithms available, with different performance characteristics and strengths.

So how do you choose the proper compressor?  There is no single best algorithm, many have different strengths and weaknesses and are useful in different situations.  We’ll investigate a few different compression algorithms and more importantly evaluate what to look for when deciding on how to compress your data.

I’ve done some simple benchmarking using a couple of freely available libraries: zlib (which I demonstrated in my load time article), 7-zip (A.K.A LZMA), LZO and BCL.  I chose these due to their variety, free availability and ease of use. BCL has a number of compression algorithms, I’ve only shown results from Huffman encoding, since Huffman compression is such a textbook compression algorithm it’s worth comparing against.

To start let’s look at the compression ratios of our algorithm using two sample test files – a large text file and a large RLE-encoded targa image file.  The graphs show compression percentage vs block size, with the largest block size begin the entire file.  The reason I’m looking at block sizes is to reduce the memory overhead required to decompress a file, since we can then decompress data in nice fixed-sized blocks reducing high watermarks. A lower value represents better compression.

Compression Ratio (Text File)

Compression Ratio (Text File)

Not surprisingly text compresses pretty well, even the basic Huffman algorithm doing quite well.  LZMA does very well, at 1/3 the original size.  We can see that the larger the block size is the better the compression ratio is.  Most algorithms tend to flatten at larger block sizes, however LZMA does seem to not flatten nearly as much as the others and clearly has the best compression ratio.

Compression of TGA File

Compression of TGA File

This TGA file already uses a primitive run-length-encoded compression scheme, so unlike the raw text file some redundant data has already been removed.  The trend of better compression with larger block sizes continues.  However we can see that Huffman doesn’t do very well with binary data, and even does worse as the block size increases.  Also, the compression ration of the TGA is not as good as the text file, but LZMA still reduces it by over 50% at larger block sizes.  So we can see that the compression algorithm has a large impact on the compression ratio. With LZMA achieving the best compression in all cases.

As important as the compression ratio is – since smaller files directly lead to less time reading files – it’s not the only factor we should examine when selecting a compression algorithm.  How long it takes to decompress data is also very important.  If it takes longer to decompress a file than the time it takes to read it uncompressed, we haven’t gained anything.  So lets look at the how long it took to decompress.

Decompression Time

Decompression Time

We can see that LZMA is much slower than the other algorithms, over 5 times insome cases.  We can also see a clear trend where LZMA clearly has a high per-block cost, with Zlib and LZO being fairly constant.  So we can now see that the increased compression of LZMA comes at a cost in decompression time.

The time to decompress is interesting, what we really want to know is how much faster will a given compression format make our data reads.  To figure out this, we need to look at the total time it takes to read and decompress the compressed data.  This is a better comparison since it shows the advantage of using slower, high-compression algorithms because they read less data.

The next chart compares our compressed data versus a 10MB/s read device.  We compute

(time to read compressed data + time to decompress data)
         / (time to read uncompressed data)

Which give us the next chart

Compression Time vs. No Compression

Compression Time vs. No Compression

Now we can actually see what load time improvement we’d get with different compression algorithms.  Any algorithm with a ratio greater than 1.0 will be slower than uncompressed data.  So we can now see that LZMA, which compresses data really well, would slow down our load times for a single file.  ZLib we can see is over twice as fast as an uncompressed read.

The previous test really only shows single threaded, single file load time improvements.  If our game is heavily threaded, on a platform with enough processors, we may be able to mostly ignore decompression time by simply using enough multiprocessing.  In this case we may simply want the algorithm with the best compression ratio.

However some platforms, like the PS3, have somewhat limited processors.  While SPUs are fast processors, they have only 256kB of memory.  This means for the PS3, if you want to decompress data on the SPU you’ll need to use smaller blocks so they fit in RAM.  Or customize your decompressor to understand the memory limitations of the SPU and stream data properly.

This also brings up the question of how much memory do you need to decompress data?  Some algorithms can require very large look up tables or other working memory which can make them unsuitable or impractical for console games.

You can’t simply choose a compression algorithm based on the load time savings.  The algorithm needs to fit within the confines of a console game.  So when considering how to compress your data, take these key points into consideration:

  • Total load time reduction provided by the algorithm.  As discussed above, this is the total reduction of load time by reducing data read and time taken by decompression.  Of course depending on platform and CPU resources you many not care about decompression time unless it is extremely slow.
  • How much memory is used by decompression.  Some algorithms need substantial working memory, some need almost none.  You need to take this into account, especially if the working memory is too large for your target platform (e.g. PS3’s SPU)
  • Can you decompress in-place? Does the algorithm work in fixed sized blocks?  Can it decompress a stream of data efficiently?  These are important questions to ask.  LZO for example can be decompressed in place – meaning you can decompress data into the same buffer as the compressed data, without needing temporary memory, which is really nice for low-memory conditions and memory fragmentation.  The trade off is LZO doesn’t have a great compression ratio.
  • How long does it take to compress the data?  Generally not a large problem, but some algorithms, especially ones not well optimized can be very slow.  This is a concern when you try to compress gigabytes of data.
  • Last but certainly not least, what license does the software use?  This is a question you must ask of any external source or library, you need to make sure the distribution license works for you.  You can’t rely on a GPL library for a professional console game, but if you’re making a freeware game, releasing the source may not be an issue.

I’m not endorsing any of the particular algorithms or libraries we looked at, they were chosen because their contrasts made for good talking points.  Also, often console platforms will provide their own compression API too, which are usually worth evaluating, since they are optimized for the target platform and can be quite fast.

I hope this article give you some insight into compression of game data, and while we haven’t chosen a best algorithm, we now know how to compare various compressors and know how to make informed decisions.

Advertisements

2 Comments »

  1. You can decompress asynchronously at the same time the data is loaded from read device. Then compression is free – unless it takes more time than reading. You are either decompression time-limited or read speed-limited.

    Comment by xzvc — August 31, 2010 @ 1:50 pm

    • I totally agree that you should be reading data and decompressing in parallel. That’s still not the same as free, unless you’re not doing anything other than loading files. For an open world game that isn’t true, and you will need to make sure decompression doens’t impact frame rates. It also requries that you have multiple data sources to read (which you often do) or a block/chunk based compression scheme where you can decompress the file in parts.

      Also it does matter what your target platform and medium are – Blueray? Pick the fastest. Downloadable content? Hightest compression maybe better (or necessary) regardless of loadtime.

      Comment by systematicgaming — August 31, 2010 @ 11:27 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: