One situation I've been having to work with a great deal lately is the problem of not having enough memory for data that is highly, repetitively, and randomly accessed in my applications.
The data is accessed too much to warrant an out-of-core solution, I suppose that I could free up memory from other systems to make room, but instead, I've embarked on a series of containers that are just really fucking cool.
Standard regular grids (such as textures) save a bit of memory because they don't store spatial locality data. Rather, it's implied that through neighborhood association, your location can be derived. Even with idiotically large data sets, you can still access a regular grid pretty randomly, and almost quite immediately. You never need extra traversals besides a single offset value into the memory stream.
But, with idiotically large data, you run into the problem that you either don't have enough memory to hold it all. The problem then, is how do you store your large regular grid data set in memory, while still keeping all the properties to allow random access?
That's where these containers come in. Standard compression algorithms, like JPG2k, vector and wavelets operate on iterative compression systems, such that to get the value of any single data element, we must evaluate a much larger portion of our data.
For clairity, let's define a Random Access Compressed Container (RACC) as having the following properties:
a) The in-memory, working data set is a compressed representation of a larger dataset.
b) Any element of data within the set can be randomly accessed with minimal decompression of non-relevant data. ( this gets a little 'fuzzy' as 'minimal' changes depending on your platform and target performance.)
Optionally, you can modify the RACC to be a Working RACC (WRACC) by adding another property:
c) As data is added to the compressed representation, non-relivant data is re-compressed based upon its corrolation to the input data.
What this basicly means, is that a WRACC is a runtime container that data is added to over time. As the data is added, depending on the compression method, other data may need to be re-compressed to take into account the incoming data. For example, if you and a WRACC that implimented an RLE compression scheme, and you added a piece of data to the set that broke one of the RLE runs internally, then that run would be split into two runs, each strattling the newly inserted data.
Now, each one has their place. I love the ease of use of WRACCs, although you can never get as much compression as you can with a standard RACC.
Some examples:
RACCs
Perfect Spatial Hashing
Hugues Hoppe came up with this one. Basically, he removes sparse data in a set by moving the defined data to a separate data structure which still keeps some implicitly defined regular organization. ( you can read the actual paper for a much better explanation)
The pro's of this are that you can compress your sparse data set in to it's MINIMAL needed representation, and still have random access to it that doesn't requrie any traversals or extra decompression. (note, this works much like the jagged container, in that we must define what data value is considered 'empty' and only move non-empty values into the extra data sets)
The cons are that the data must be static. Which kills us for direct editor usage, but it's still nice to take in some of the philosophies.
WRACCs
Jagged Array
Andrew Foster came up with a great solution for the Halo Wars editor (and where this all started). Basically, we were struggling with exceptionally sparse data sets, but needed the ability for the sparse data set to a) be compressed, and b) still emulate a regular grid to the outside world.
The Jagged array container works by creating pointers to the start of each scanline of your 2D data (IE, one per row). When data is placed into the array, we first determine if that row exists. If it doesn't, then we allocate the entire row, and set the pointer appropriately. When we access the container, we usually pass in a 2D coordinate; If the specified row value exists, then we traverse the row to the column coordinate, and return the proper value. If the row has not been allocated however, then we simply return a pre-specified 'empty' value.
The container works exceptionally well. The row index acts as a pseudo hash key into a table of data (which still maintains regular connectivity). While the x coord is the internal value. We can still keep random access with this process, and we save memory by not allocating 'empty' data.
This does however, degenerate, as we add progressivly more data, the container itself degenerates back to a regular grid. Also, this conainer allocates a great deal more memory than needed most of the time; for instance, if we enter every element in a single column, the JA would allocate every row, and immediatly degenerate into a 2d grid
Random Access RLE (or JaggedRLE)
An extension to this process that I developed is an extra step to help reduce the memory footprint was to RLE any row of data that the jagged array points to. This way, if we have any sort of homogeneous data, we get a mild perf win. This also addresses sparse raster data, such that if there is minimal data elements in a single row, then we do not store the entire row in memory.
Per row, I label RLE compressed blocks with their start and value, and to safe time, I flag unique blocks with the same process. The row index still acts as a hash key, but now the X value requires some searching to occur. To find our X value, I have to find what block the X Value resides in. This requires walking each block in the stripe and adding the traversed pixels to our running count for the line until we find a block that spans X. If the block is compressed, we simply return the repeated value. If it's not compressed, then we return the element that exists where X should be pointing (derived by subtracting the start of the block from X, and adding that to the start of the block as a local index..)
Although it's trickier, you can still submit data into the container @ runtime, and allow it to RLE the row as it changes.
One problem with this however, is that it falls to the standard problems of RLE, in that the more random the data, the less efficient it is to store it as such.
One side observation though, is that it may be wiser to store pointers to blocks, instead of stripes. Usually images are not really raster in nature, and rather block based, such that RLEing a block may yield better results than a scanline.
Well, those are just a few ideas. You can see that these are powerful notions. The ability to edit data that is compressed on the fly, as well as randomly access it with minimal performance hit, all while expressing a minimal memory footprint!
That's good shit.
~Main
0 comments:
Post a Comment