Tuesday, December 23, 2008

Compressed Vectors - Part 2

My last post introduced an STL vector that uses RLE to save space and an index for reasonably fast random access.

But that's not the whole story.  We're trying to compress the "snapshot structure".  Those familiar with the lowest level of X-Plane multiplayer networking know that X-Plane uses a packed structure to describe one "frame" of the sim - that is, plane location, control surface deflections, needles, etc.  It is very heavily packed (both with and without loss, depending on the parameter).

The flight replay is essentially a giant vector of these structures.  So...how to utilize our compressed vector (which only compresses identical data)?

The answer is the plane_old_data compressed vector.  Basically this vector relies on the fact that its items are plain old data (POD) and stores each struct across many vectors (each usually containing 4-byte int or 8-byte long longs for items).  Call each of these vectors that covers a sequence of cross sections of our struct "track".  (Those who have used ProTools will understand why I say this.)

Now we can use our compressed vector for each track.  The result is that consecutive values over time at the same offset in our struct get compressed.  If the struct is filled with parameters (some of which vary, some of which don't), we get to compress the ones that do.

Once we get this structure integrated, we'll see what kind of packing efficiency we get.

No comments:

Post a Comment