Der Mythos von RAM und O (1)

Originalautor: Emil Ernerfeldt
  • Übersetzung


Stockholmer Stadtbibliothek. Foto Minotauria .


In diesem Artikel möchte ich darüber sprechen, dass es eine sehr schlechte Idee ist, die Speicherzugriffszeit mit O (1) zu bewerten. Stattdessen sollten wir O (√N) verwenden. Zuerst werden wir die praktische Seite des Themas betrachten, dann die mathematische, die auf der theoretischen Physik basiert, und dann werden wir die Konsequenzen und Schlussfolgerungen betrachten.


Einleitung


Wenn Sie Informatik und Analyse der algorithmischen Komplexität studiert haben, wissen Sie, dass die Passage durch die verknüpfte Liste O (N), die binäre Suche O (log (N)) und die Suche nach einem Element in der Hash-Tabelle O (1) ist. Was ist, wenn ich dir sage, dass das alles nicht stimmt? Was ist, wenn der Durchgang durch die verknüpfte Liste tatsächlich O (N√N) ist und die Suche in der Hash-Tabelle O (√N) ist?


Glaubst du nicht? Ich werde dich jetzt überzeugen. Ich werde zeigen, dass der Zugriff auf den Speicher nicht O (1) ist, sondern O (√N). Dieses Ergebnis ist sowohl in der Theorie als auch in der Praxis gültig. Beginnen wir mit der Praxis.


Messen


Lassen Sie uns zuerst die Definitionen bestimmen. Die "O" -Notation eignet sich hervorragend für viele Dinge, von der Speichernutzung bis zur Ausführung von Anweisungen. Im Rahmen dieses Artikels bedeutet O (f (N)), dass f (N) die Obergrenze (der schlimmste Fall) der Zeit ist, die erforderlich ist, um auf N Speicherbytes (oder dementsprechend N Elemente derselben Größe) zuzugreifen ) Ich verwende Big O, um die Zeit zu analysieren, aber keine Operationen , und das ist wichtig. Wir werden sehen, dass der Zentralprozessor lange auf langsamen Speicher wartet. Persönlich ist es mir egal, was der Prozessor tut, während er wartet. Ich kümmere mich nur um die Zeit, wie lange diese oder jene Aufgabe dauert, also beschränke ich mich auf die obige Definition.


Ein weiterer Hinweis: RAM im Header bedeutet im Allgemeinen Direktzugriff (Direktzugriff auf den Speicher) und keine bestimmte Art von Speicher. Ich betrachte die Zugriffszeit für Informationen im Speicher, sei es ein Cache, DRAM oder Swap.


Hier ist ein einfaches Programm , das eine verknüpfte Liste der Größe N durchläuft. Größen - von 64 Artikeln bis zu 420 Millionen Artikeln. Jeder Knoten der Liste enthält einen 64-Bit-Zeiger und 64 Datenbits. Knoten sind im Speicher gemischt, so dass jeder Speicherzugriff willkürlich ist. Ich messe den Durchgang durch die Liste mehrmals und markiere dann in der Grafik die Zeit, die erforderlich war, um auf das Element zuzugreifen. Wir sollten ein flaches Diagramm der Form O (1) erhalten. Folgendes passiert in der Realität:



Probleme beim Zugriff auf ein Element in einer verknüpften Liste. Der Zugriff auf ein beliebiges Element in einer 100-Megabyte-Liste ist ungefähr 100-mal langsamer als der Zugriff auf ein Element in einer 10-Kilob-Liste.


Beachten Sie, dass dieses Diagramm eine logarithmische Skala auf beiden Achsen verwendet, sodass der Unterschied tatsächlich sehr groß ist. Ab einer Nanosekunde pro Element haben wir eine ganze Mikrosekunde erreicht! Aber warum? Die Antwort ist natürlich der Cache. Der Systemspeicher (RAM) ist eigentlich recht langsam. Um dies zu kompensieren, fügen clevere Computerentwickler eine Hierarchie von schnelleren, engeren und teureren Caches hinzu, um den Betrieb zu beschleunigen. Mein Computer verfügt über drei Cache-Ebenen: L1, L2, L3, 32 KB, 256 KB bzw. 4 MB. Ich habe 8 Gigabyte RAM, aber als ich dieses Experiment durchführte, hatte ich nur 6 freie Gigabyte, so dass das letzte, das gestartet wurde, auf Festplatte (SSD) auslagerte. Hier ist das gleiche Diagramm, aber mit Cache-Größen.



Die vertikalen Linien geben L1 = 32 KB, L2 = 256 KB, L3 = 4 MB und 6 GB freien Speicher an.


Diese Grafik zeigt die Bedeutung von Caches. Jede Cache-Schicht ist um ein Vielfaches schneller als die vorherige. Dies ist die Realität moderner CPU-Architektur, sei es ein Smartphone, ein Laptop oder ein Mainframe. Aber wo ist hier das allgemeine Muster? Kann eine einfache Gleichung in dieses Diagramm eingefügt werden? Es stellt sich heraus, dass wir es können!


Schauen wir uns das genauer an und stellen fest, dass es zwischen 1 MB und 100 MB eine 10-fache Verlangsamung gibt. Und das gleiche zwischen 100 Megabyte und 10 Gigabyte. Es scheint, dass jede 100-fache Zunahme des verwendeten Speichers eine 10-fache Verlangsamung ergibt. Fügen wir dies dem Diagramm hinzu.



Die blaue Linie ist O (√N).


Die blaue Linie in diesem Diagramm gibt die O (√N) -Kosten für jeden Speicherzugriff an. Hört sich gut an, oder? Natürlich ist dies mein spezielles Auto, und Ihr Bild sieht möglicherweise anders aus. Die Gleichung ist jedoch sehr leicht zu merken, daher sollte sie möglicherweise als grobe Regel verwendet werden.


Sie fragen sich wahrscheinlich, wie es rechts neben dem Zeitplan weitergeht? Geht der Anstieg weiter oder wird der Chart flach? Nun, es wird für eine Weile flach, solange genügend freier Speicherplatz auf der SSD vorhanden ist. Danach muss das Programm auf die Festplatte, dann auf den Festplattenserver, dann auf das entfernte Rechenzentrum usw. umschalten. Jeder Sprung wird eine neue flache Fläche schaffen, aber ich denke, der allgemeine Aufwärtstrend wird sich fortsetzen. Ich habe mein Experiment aufgrund von Zeitmangel und fehlendem Zugang zu einem großen Rechenzentrum nicht fortgesetzt.


„Mit der empirischen Methode können jedoch keine Big-O-Grenzen definiert werden“, sagen Sie. Natürlich! Vielleicht gibt es eine theoretische Grenze für die Verzögerung beim Speicherzugriff?


Runde Bibliothek


Lassen Sie mich ein Gedankenexperiment beschreiben. Angenommen, Sie sind Bibliothekar und arbeiten in einer kreisförmigen Bibliothek. Ihr Tisch ist in der Mitte. Die Zeit, die Sie benötigen, um ein Buch zu erhalten, ist durch die Entfernung begrenzt, die Sie benötigen, um zu reisen. Und im schlimmsten Fall ist dies der Radius, da Sie an den äußersten Rand der Bibliothek gelangen müssen.


Angenommen, Ihre Schwester arbeitet in einer anderen ähnlichen Bibliothek, aber in ihrer (der Bibliothek, nicht ihrer Schwester :), - ca. per.) der Radius ist doppelt so groß. Manchmal muss sie doppelt so viel gehen. Aber ihre Bibliothek hat eine Fläche, die viermal so groß ist wie Ihre, und sie enthält viermal so viele Bücher. Die Anzahl der Bücher ist proportional zum Quadrat des Radius: N∝ r². Und da die Zugriffszeit T für das Buch proportional zum Radius ist, ist N∝ T² oder T∝√N oder T = O (√N).


Dies ist eine grobe Analogie zu einem Zentralprozessor, der Daten aus seiner Bibliothek - dem RAM - abrufen muss. Natürlich ist die Geschwindigkeit des „Bibliothekars“ wichtig, aber hier sind wir durch die Lichtgeschwindigkeit begrenzt. Beispielsweise bewegt sich das Licht in einem Zyklus eines 3-GHz-Prozessors über eine Distanz von 10 cm. Bei einem Roundtrip sollte ein sofort verfügbarer Speicher nicht weiter als 5 Zentimeter vom Prozessor entfernt sein.


Nun, wie viele Informationen können wir innerhalb eines bestimmten Abstands r vom Prozessor platzieren? Wir haben oben über eine runde flache Bibliothek gesprochen, aber was ist, wenn sie kugelförmig ist? Die Größe des Speichers, die in die Kugel passt, ist proportional zum Würfel des Radius - r³. In Wirklichkeit sind Computer ziemlich flach. Dies ist zum Teil eine Frage des Formfaktors und zum Teil eine Frage der Kühlung. Vielleicht werden wir eines Tages lernen, dreidimensionale Speicherblöcke aufzubauen und zu kühlen, aber bisher wird die praktische Begrenzung der Informationsmenge N innerhalb des Radius r N ∝ r² sein. Dies gilt für sehr entfernte Speicher, z. B. Datenzentren (die über die zweidimensionale Oberfläche des Planeten verteilt sind).


Aber ist es theoretisch möglich, das Bild zu verbessern? Dazu müssen Sie etwas über Schwarze Löcher und Quantenphysik lernen!


Theoretische Grenze


Die Informationsmenge, die in einer Kugel mit dem Radius r platziert werden kann, kann unter Verwendung der Beckenstein-Grenze berechnet werden . Dieser Betrag ist direkt proportional zu Radius und Masse: N: r · m. Wie massiv kann eine Kugel sein? Nun, was ist das dichteste im Universum? Schwarzes Loch! Es zeigt sich, dass die Masse des Schwarzen Lochs proportional zum Radius ist: m ∝ r. Das heißt, die Informationsmenge, die in einer Kugel mit dem Radius r platziert werden kann, ist N ∝ r². Wir sind zu dem Schluss gekommen, dass die Informationsmenge durch den Bereich der Kugel und nicht durch das Volumen begrenzt ist!


Kurz gesagt: Wenn Sie versuchen, einen sehr großen L1-Cache im Prozessor abzulegen, wird dieser schließlich in ein Schwarzes Loch zerfallen, wodurch verhindert wird, dass das Berechnungsergebnis an den Benutzer zurückgegeben wird.


Es stellt sich heraus, dass N ∝ r² nicht nur eine praktische, sondern auch eine theoretische Grenze ist! Das heißt, die Gesetze der Physik begrenzen die Geschwindigkeit des Zugriffs auf den Speicher: Um N Datenbits zu erhalten, müssen Sie eine Nachricht in einer Entfernung senden, die proportional zu O (√N) ist. Mit anderen Worten, jede 100-fache Zunahme der Aufgabe führt zu einer 10-fachen Zunahme der Zugriffszeit auf ein Element. Und genau das hat unser Experiment gezeigt!


Ein bisschen Geschichte


In der Vergangenheit waren Prozessoren viel langsamer als der Speicher. Im Durchschnitt war eine Speichersuche schneller als die eigentliche Berechnung. Es war üblich, Tabellen für Sinus und Logarithmus im Speicher abzulegen. Aber die Zeiten haben sich geändert. Die Prozessorleistung stieg viel schneller als die Speichergeschwindigkeit. Die meisten modernen Prozessoren warten nur auf Speicher. Deshalb gibt es so viele Cache-Ebenen. Ich glaube, dass dieser Trend noch lange anhält, daher ist es wichtig, die alten Wahrheiten zu überdenken.


Man kann sagen, dass der springende Punkt von Big-O in der Abstraktion liegt. Architekturdetails wie die Speicherlatenz müssen beseitigt werden. Dies ist wahr, aber ich argumentiere, dass O (1) eine falsche Abstraktion ist . Insbesondere wird Big-O benötigt, um konstante Faktoren zu abstrahieren, aber der Speicherzugriff ist keine konstante Operation. Weder in der Theorie noch in der Praxis.


In der Vergangenheit war jeder Zugriff auf Speicher in Computern ebenso teuer, so O (1). Dies ist jedoch schon seit geraumer Zeit nicht mehr der Fall. Ich glaube, es ist an der Zeit, anders darüber nachzudenken, den Speicherzugriff für O (1) zu vergessen und ihn durch O (√N) zu ersetzen.


Die Konsequenzen


Die Kosten für den Zugriff auf den Speicher hängen von der Größe ab, die angefordert wird - O (√N), wobei N die Größe des Speichers ist, auf den bei jeder Anforderung zugegriffen wird. Wenn also der Aufruf derselben Liste oder Tabelle erfolgt, ist die folgende Aussage wahr:


Das Durchlaufen einer verknüpften Liste ist eine O (NN) -Operation. Die binäre Suche ist O (√N). Von einem assoziativen Array zu erhalten ist O (√N). Tatsächlich ist jede beliebige Suche in einer Datenbank bestenfalls O (√N).


Es ist erwähnenswert, dass die zwischen Operationen ausgeführten Aktionen von Bedeutung sind. Wenn Ihr Programm mit Speicher der Größe N arbeitet, ist jede beliebige Speicheranforderung O (√N). Wenn Sie also eine Liste der Größe K durchgehen, kostet dies O (K√N). Bei wiederholtem Durchlauf (sofort, ohne auf einen anderen Speicher zurückzugreifen) betragen die Kosten O (K√K). Dies ist eine wichtige Schlussfolgerung: Wenn Sie mehrmals auf denselben Speicherort zugreifen müssen, minimieren Sie die Intervalle zwischen den Aufrufen .


Wenn Sie ein Array der Größe K durchlaufen, betragen die Kosten O (√N + K), da nur der erste Anruf willkürlich ist. Der Wiederholungspass ist O (K). Daher eine weitere wichtige Schlussfolgerung: Wenn Sie einen Pass planen, verwenden Sie ein Array .


Es gibt ein großes Problem: Viele Sprachen unterstützen keine echten Arrays. Sprachen wie Java und viele Skriptsprachen speichern alle Objekte im dynamischen Speicher, und das Array enthält tatsächlich ein Array von Zeigern. Wenn Sie ein solches Array durchlaufen, ist die Leistung nicht besser als beim Durchlaufen einer verknüpften Liste. Das Durchlaufen einer Reihe von Objekten in Java kostet O (K√N) . Dies kann durch das Erstellen von Objekten in der richtigen Reihenfolge ausgeglichen werden. Ich hoffe , dass der Speicherzuordner diese Objekte in der richtigen Reihenfolge in den Speicher legt . Wenn Sie jedoch Objekte zu unterschiedlichen Zeiten erstellen oder mischen müssen, funktioniert nichts.


Fazit


Speicherzugriffsmethoden sind sehr wichtig. Sie sollten immer versuchen, auf vorhersehbare Weise auf den Speicher zuzugreifen und beliebige Speicherzugriffe zu minimieren. Natürlich gibt es hier nichts Neues, aber es lohnt sich, es zu wiederholen. Ich hoffe, dass Sie ein neues Tool zum Nachdenken über den Cache übernehmen: Der Zugriff auf den Speicher kostet O (√N). Wenn Sie das nächste Mal die Komplexität bewerten, denken Sie an diese Idee.


Jetzt auch beliebt: