Space–time tradeoff

From Wikipedia, the free encyclopedia
  (Redirected from Space-time tradeoff)
Jump to: navigation, search

In computer science, a space–time or time–memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution (and, conversely, the computation time can be reduced at the cost of increased memory use). As the relative costs of CPU cycles, RAM space, and hard drive space change—hard drive space has for some time been getting cheaper at a much faster rate than other components of computers[citation needed]—the appropriate choices for space–time tradeoffs have changed radically. Often, by exploiting a space–time tradeoff, a program can be made to run much faster.

History[edit]

The basic idea of time–memory tradeoff goes back to the earliest time of evolution, since basically using knowledge instead of brute-force trials, and encoding reflex reactions in the DNA to avoid the organism to have to "calculate", i.e., think how to react, in time-critical situations, are examples of this. More specifically to the use in computers, look-up tables (and in particular, e.g., storing coefficients of power series for transcendental functions) have been implemented since the very earliest operating systems.[citation needed]

In 1980 Martin Hellman first proposed using a time–memory tradeoff for cryptanalysis.[1]

Types of tradeoff[edit]

Lookup tables vs. recalculation[edit]

The most common situation is an algorithm involving a lookup table: an implementation can include the entire table, which reduces computing time, but increases the amount of memory needed, or it can compute table entries as needed, increasing computing time, but reducing memory requirements.

Compressed vs. uncompressed data[edit]

A space–time tradeoff can be applied to the problem of data storage. If data is stored uncompressed, it takes more space but less time than if the data were stored compressed (since compressing the data reduces the amount of space it takes, but it takes time to run the decompression algorithm). Depending on the particular instance of the problem, either way is practical. There are also rare instances where it is possible to directly work with compressed data, such as in the case of compressed bitmap indices, where it is faster to work with compression than without compression.

Re-rendering vs. stored images[edit]

Storing only the LaTeX source and rendering it as an image every time the page is requested would be trading time for space; more time used, but less space. Rendering the image when the page is changed and storing the rendered images would be trading space for time; more space used, but less time. This technique is more generally known as caching.

Smaller code vs. loop unrolling[edit]

Larger code size can be traded for higher program speed when applying loop unrolling. This technique makes the code longer for each iteration of a loop, but saves the computation time required for jumping back to the beginning of the loop at the end of each iteration.

Other examples[edit]

Algorithms that also make use of space–time tradeoffs include:

See also[edit]

External links[edit]

References[edit]

  1. ^ Hellman, Martin (July 1980). "A Cryptanalytic Time-Memory Tradeoff". IEEE Transactions on Information Theory 26 (4): 401–406. doi:10.1109/tit.1980.1056220.