How fast can decompression algorithims work?
Why?
Because, is it possible to keep data in RAM compressed, effectively increasing your memory pool by requesting the information / data and decompressing it to use it then (if the data changed) recompressing it back into the memory pool?
Is there any decompression / compression technique fast enough and compresses enough to make such a thing worth it?
Might be a stupid idea. If it is... oh well.
But if it isn't.. hopefully some people can use it.
Kelemit
I don't have references on-hand, but I'll try to think through some reasons why this is hard to use in a general case.
First, it will have to be lossless compression, otherwise your machine will wreck everything in short order.
Let's say we use a simple dictionary-based compression scheme.
From a computational standpoint, it is about linear, I think.
See a symbol in the compressed data, look it up in the dictionary.
It's linearly scaling, but the scaling factor is at least 2, since you need to read two pieces of data to get at what you are reading.
Things get more complicated if the dictionary file is too big to cache well, and if the architecture of the machine is too narrow in the memory pipeline or lean on execution resources to handle what is at least a doubling of the computational load per data access.
It doesn't necessarily mean that everything will take twice as long, but unlike reading compressed files from a hard disk, there's a lot less idle time when reading from RAM.
For compression, a dictionary method will have to scan through the data set at least once.
This is a problem, just because a single write is almost always much smaller than the data file you are writing to. This means that frequently written data cannot be compressed. Only rarely used and read-only data files can be compressed.
In doing a scan, the compressor will accumulate a set of patterns it will make up the dictionary. This is happening in memory, and depending on the data being compressed, the number of candidates can be large. It will likely be more than just 1, so the amount of work per write is increased by at least the number of candidates, in addition to the scan that occurred before.
For compression to work, the candidates must be sorted by the number of times they are encountered in the data set. Sorting takes about NlogN steps, probably.
The best case is if there's only one candidate. A write then will only double the work involved, if taken in isolation to all the other work already done. Otherwise, things get worse and more than just a simple multiple of the size of the data.
After doing this sorting, the data file must be reread and then recompared to the final dictionary and then rewritten. This is based on the data set's size, but if this were the only work involved, it would still multiply the amount of work inolved by at least double.
There's tons of overhead involved in all of this, and there is no guarantee that the combined size of the dictionary and the compressed data will be less than the size of the original+the size of the compression program.
In addition, the scratch space needed for all the intermediate work will probably be too much to justify the space savings for anything but very large data sets.
In certain special cases where the data is highly compressible and the format and type is known beforehand, it is possible to do a few space-saving tricks or use specialized hardware. General on-demand compression is way out of bounds, though.
