Inverse compression for space-time trade off

Question

A bit of a strange question - but I am developing an application where speed is critical, not memory - I have the ability to blow up to 3 TB on the data storage that this application will use and I am wanting to use a space time trade off to increase processing speed.

My reasoning goes as such - A compression algorithim utilizies a specific function to decrease a file's size, at the cost of the algorithmic run time to uncompress the specific file - I should be able to do the reverse shouldnt I? Increase the files size to reduce the amount of time taken to process the file.

Can you suggest any simple ways to do this? (Inverse probabilistic fragmentalization was what I was thinking but this issue is causing me some major problems at the moment as I do not know the fundamental basis of file compression)

Any help/psudocode/suggestions/answers would be amazing...

Thanks in advance, Martin

Answer 1

There is no magic way to speed up an arbitrary operation by using more memory. Similarly, there is no way to compress arbitrary data. It so happens that a lot of data has exploitable redundancy, but even then, changing the algorithm (e.g. changing a spatial discretization, applying formal model reduction methods, or using an adjoint model) tends to offer much larger gains than generic compression. Furthermore, many operations are limited by the speed of memory rather than the speed of the CPU. Modern file systems such as ZFS and Btrfs offer transparent compression for speed as much as to save disk space. With a fast compression algorithm, it's faster to compress by writing to disk.

From what few details you have given about your application, the most likely way to improve performance at the expense of disk space is to build more/better indexes. Profile carefully and at each point where the algorithm has to do a large read, evaluate the benefits of computing an index so that query could be answered faster. Note that the indexes are not free to compute and that it makes certain changes more expensive (because the indexes have to be updated).

Answer 2

What you are asking is impossible.

First, if you have a data set of that size and are iterating through the whole thing, what's slowing you down is almost certainly the size of your data set. Making your data set bigger is only going to make thing worse, as then you have to spend more time waiting for your disk and RAM to get back to the CPU with some bit of requested memory.

Second, there is usually no "space-time trade off". It's true that some algorithms save time by storing intermediate results, thus using more space (the FFT is an example), but this only works if different parts of your problem have similar subproblems. This isn't a general property of algorithms. There are, occasionally, very specific ways of doing this for very specific problems, but you're case probably isn't one of them.

Answer 3

If you can retrieve all the information you need from only using 8 bits of data, why store it with 256 bits? Expanding a file size means that the processors have to read more bits from the hard disk for the same amount of information, and this will definitely slow down performance.

The main reason why expanded memory results in faster performance is that RAM memory access is generally faster than Hard disk access. In situations where it is absolutely necessary to use 10TB of data to perform a single instruction (not in a loop, but in a single atomic operation). it makes sense that more memory will be better than less.

On the other hand, if you have a dynamic programming problem where there are overlapping subproblems and optimal substructure, then using more memory results in a faster optimal solution. But again, the speedup occurs from using RAM memory, not main memory access.