Time-Memory Tradeoff

In der Informatik ist ein Time-Memory Tradeoff (TMTO, deutsch Zeit-Speicher-Kompromiss oder Zeit-Speicher-Ausgleich) ein Kompromiss, bei dem der Speicherbedarf eines Programmes auf Kosten einer längeren Laufzeit gesenkt wird oder umgekehrt die Laufzeit auf Kosten eines höheren Speicherbedarfs verkürzt wird. Ziel dabei ist es, das Programm unter aktuellen technischen Voraussetzungen möglichst effizient umzusetzen.

Der Begriff wird nicht nur für den entstehenden Kompromiss und für den Vorgang des Abwägens, sondern auch zur Benennung von Problemenklassen, die eine solche Abwägung nahelegen, verwendet. Darüber hinaus werden manche Programme und Algorithmen, die von diesem Vorgehen entscheidend geprägt wurden, mit diesem Wort bezeichnet.

Beispiele für Kompromissformen

• Lookup-Tabelle gegenüber Neuberechnung
  Bei der Verwendung von Lookup-Tabellen kann in der Implementierung die gesamte Tabelle vorberechnet werden, wodurch die Laufzeit verringert, aber der Speicherbedarf erhöht wird.
• Komprimierte Daten gegenüber unkomprimierten Daten
  Ein Ausgleich zwischen Speicher und Laufzeit erfolgt bei der Datenkompression, wobei der Speicherbedarf von Daten verringert wird, aber mehr Zeit zum Dekomprimieren benötigt wird.
• Re-rendering gegenüber gespeicherten Bildern
  Werden auf einem Server LaTeX-Formeln als Quelltext und nicht als Bilddatei gespeichert, so wird der Speicherbedarf gesenkt, aber durch das wiederholte Rendern die Laufzeit erhöht.
• Kleiner Programmcode gegenüber loop unrolling
  Durch Auflösen von Schleifen konnte früher die Laufzeit verkürzt werden, während sich der Programmcode vergrößert. Heutige CPUs benötigen dies nicht mehr und laufen teilweise mit loop unrolling langsamer als ohne.

Beispiele für Algorithmen

• Babystep-Giantstep-Algorithmus, der für die Berechnung des diskreten Logarithmus verwendet wird.
• Dynamische Programmierung zur algorithmischen Lösung von Optimierungsproblemen
• Rainbow-Tabellen in der Kryptographie

Bei den Rainbow-Tabellen hat die konsequente Anwendung dieses Prinzips zu einer kompletten Zweiteilung der Lösung geführt. In einem völlig eigenständigen Vorbereitungsprogramm werden mit ganz erheblichem Rechenaufwand große Tabellen vorbereitet. Andere Programme nutzen die vorbereiteten Tabellen, um damit in relativ geringer Zeit Verschlüsselungen oder Passwörter zu brechen.

Weblinks

• Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off. (PDF; 243 kB)
• Once Upon a Time-Memory Tradeoff. (PDF; 135 kB)