Time-memory tradeoff
In computer science , a time-memory tradeoff (TMTO, German time-memory compromise or time-memory balance ) is a compromise in which the memory requirement of a program is reduced at the expense of a longer runtime or, conversely, the runtime at the expense of a higher memory requirement is shortened. The aim is to implement the program as efficiently as possible under current technical conditions .
The term is used not only for the resulting compromise and for the weighing process, but also to designate problem classes that suggest such weighing. In addition, some programs and algorithms that have been decisively shaped by this procedure are identified with this word.
Examples of compromise forms
-
Lookup table versus recalculation
When using lookup tables, the entire table can be precalculated in the implementation, which reduces the runtime but increases the memory requirement. - Compressed data versus uncompressed data
A balance between memory and running time occurs with data compression , whereby the memory requirement of data is reduced, but more time is required for decompression. -
Re-rendering versus saved images
If LaTeX formulas are saved on a server as source text and not as an image file, the memory requirement is reduced, but the runtime is increased through repeated rendering. - Small program code compared to loop unrolling In the past,
by breaking up loops , the runtime could be shortened while the program code increased. Today's CPUs no longer need this and sometimes run slower with loop unrolling than without.
Examples of algorithms
- Babystep-Giantstep algorithm used to calculate the discrete logarithm .
- Dynamic programming for the algorithmic solution of optimization problems
- Rainbow tables in cryptography
With the rainbow tables, the consistent application of this principle has resulted in a complete split of the solution. In a completely independent preparation program, large tables are prepared with a considerable amount of computing effort. Other programs use the prepared tables to break encryptions or passwords in a relatively short time.
Web links
- Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off. (PDF; 243 kB)
- Once Upon a Time-Memory Tradeoff. (PDF; 135 kB)