3
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ What application are you developing? What problem are you trying to solve? $\endgroup$ – Geoff Oxberry Mar 17 '12 at 17:57
  • $\begingroup$ Hey Geoff, thanks for helping out again. I am working on a Turing capable algorithm at the moment and the data requirements for about 40 years of continuous reading (of books pulled of project gutenberg) works out at around about 4GB, where as the time it takes to process this information to recieve a response from the system is about 10 minutes. I am assuming that I should be able to for example reduce the operation time by a factor of 100 if I increase the data set by the same factor.. Cheers :) $\endgroup$ – marscom Mar 17 '12 at 18:19
  • $\begingroup$ Also if this can be resolved (and I am working on it right now) then I will likely be able to remove about 400 lines of code which is utilized for the engines analysis (I can't explain the algorithms operation for obvious reasons) so I'm quite excited about that :) - Cheers - Martin $\endgroup$ – marscom Mar 17 '12 at 18:25
  • $\begingroup$ Hey all, thanks for providing so many answers, I find them depressing though, as I cannot understand why standard file compression would implement a space time trade off that will decrease space while increasing time, are you sure I cannot simply do the opposite? I dont see why I couldnt. Cheers, Martin $\endgroup$ – marscom Mar 18 '12 at 17:24
  • $\begingroup$ The only way I can think this would be possible would be to do a large amount of preprocessing. This, however, would be highly algorithm dependent, and the preprocessing you do would have to be so expensive that disk reads are faster rather than simply redoing the calculation. $\endgroup$ – Godric Seer Mar 26 '14 at 19:15
5
$\begingroup$

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).

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.