Sind nicht zusammenhängende Arrays performant?

Wenn ein Benutzer in C # ein erstellt List<byte>und diesem Bytes hinzufügt, ist die Möglichkeit gegeben, dass ihm der Speicherplatz ausgeht und mehr Speicherplatz zugewiesen werden muss. Es weist das Doppelte (oder einen anderen Multiplikator) der Größe des vorherigen Arrays zu, kopiert die Bytes und verwirft den Verweis auf das alte Array. Ich weiß, dass die Liste exponentiell wächst, weil jede Zuordnung teuer ist und sich dies auf O(log n)Zuordnungen beschränkt, bei denen nur das Hinzufügen 10zusätzlicher Elemente jedes Mal zu O(n)Zuordnungen führen würde.

Bei großen Arrays kann jedoch viel Platz verschwendet werden, möglicherweise fast die Hälfte des Arrays. Um den Speicher zu verkleinern, habe ich eine ähnliche Klasse geschrieben, NonContiguousArrayListdie List<byte>als Hintergrundspeicher verwendet, wenn weniger als 4 MB in der Liste vorhanden sind, und dann zusätzliche 4 MB-Byte-Arrays mit NonContiguousArrayListzunehmender Größe zuweist .

Im Gegensatz zu List<byte>diesen Arrays sind sie nicht zusammenhängend, sodass keine Daten kopiert werden müssen, sondern lediglich eine zusätzliche 4M-Zuordnung. Wenn ein Element nachgeschlagen wird, wird der Index durch 4M geteilt, um den Index des Arrays zu erhalten, das das Element enthält, und dann durch Modulo 4M, um den Index innerhalb des Arrays zu erhalten.

Können Sie auf Probleme mit diesem Ansatz hinweisen? Hier ist meine Liste:

• Nicht zusammenhängende Arrays haben keine Cache-Lokalität, was zu einer schlechten Leistung führt. Bei einer Blockgröße von 4 MB scheint es jedoch genügend Orte für eine gute Zwischenspeicherung zu geben.
• Der Zugriff auf ein Objekt ist nicht ganz so einfach, es gibt eine zusätzliche Indirektionsebene. Würde das weg optimiert werden? Würde es Cache-Probleme verursachen?
• Da nach Erreichen des 4-MB-Grenzwerts ein lineares Wachstum zu verzeichnen ist, können Sie weit mehr Zuweisungen vornehmen als normalerweise (z. B. maximal 250 Zuweisungen für 1 GB Arbeitsspeicher). Nach 4M wird kein zusätzlicher Speicher kopiert. Ich bin mir jedoch nicht sicher, ob die zusätzlichen Zuordnungen teurer sind als das Kopieren großer Speicherblöcke.

Bei den von Ihnen erwähnten Maßstäben unterscheiden sich die Bedenken völlig von denen, die Sie erwähnt haben.

Cache-Lokalität

• Es gibt zwei verwandte Konzepte:
  1. Lokalität, die Wiederverwendung von Daten in derselben Cache-Zeile (räumliche Lokalität), die kürzlich besucht wurde (zeitliche Lokalität)
  2. Automatisches Cache-Prefetching (Streaming).
• Bei den von Ihnen erwähnten Maßstäben (Hundert MB bis Gigabyte, in 4-MB-Blöcken) haben die beiden Faktoren mehr mit Ihrem Datenelementzugriffsmuster zu tun als mit dem Speicherlayout.
• Meine (ahnungslose) Vorhersage ist, dass es statistisch gesehen möglicherweise keinen großen Leistungsunterschied gibt als eine riesige zusammenhängende Speicherzuweisung. Kein Gewinn, kein Verlust.

Zugriffsmuster für Datenelemente

• Dieser Artikel veranschaulicht visuell, wie sich Speicherzugriffsmuster auf Leistung auswirken.
• Kurz gesagt, denken Sie daran, dass die einzige Möglichkeit, die Leistung zu verbessern, darin besteht, mit den Daten, die bereits in den Cache geladen wurden, sinnvoller zu arbeiten , wenn Ihr Algorithmus bereits durch die Speicherbandbreite eingeschränkt ist.
• Mit anderen Worten, selbst wenn YourList[k]und YourList[k+1]hat eine hohe Wahrscheinlichkeit in Folge sein (ein in vier Millionen Chance, nicht), wird diese Tatsache nicht die Leistung Hilfe , wenn Sie Zugriff auf Ihre Liste vollständig zufällig, oder in großen Schritten unberechenbar zBwhile { index += random.Next(1024); DoStuff(YourList[index]); }

Interaktion mit dem GC-System

• Hier sollten Sie sich meiner Meinung nach am meisten konzentrieren.
• Verstehen Sie mindestens, wie Ihr Design mit Folgendem interagiert:
  • Generations-Müllabfuhr ,
  • Großer Objekthaufen
• Ich kenne mich in diesen Themen nicht aus und überlasse es anderen, Beiträge zu leisten.

Overhead von Adressversatzberechnungen

• Der typische C # -Code führt bereits viele Adressversatzberechnungen durch, sodass der zusätzliche Aufwand Ihres Schemas nicht schlimmer wäre als der typische C # -Code, der in einem einzelnen Array ausgeführt wird.
  • Denken Sie daran, dass C # -Code auch die Überprüfung des Arraybereichs durchführt. und diese Tatsache hindert C # nicht daran, eine vergleichbare Array-Verarbeitungsleistung mit C ++ - Code zu erreichen.
  • Der Grund dafür ist, dass die Leistung hauptsächlich durch die Speicherbandbreite beeinträchtigt wird.
  • Der Trick zur Maximierung des Nutzens der Speicherbandbreite besteht darin, SIMD-Anweisungen für Lese- / Schreibvorgänge im Speicher zu verwenden. Weder typisches C # noch typisches C ++ tun dies. Sie müssen auf Bibliotheken oder Sprach-Add-Ons zurückgreifen.

Um zu veranschaulichen, warum:

• Adressberechnung durchführen
• (Laden Sie im Fall von OP die Chunk-Basisadresse (die sich bereits im Cache befindet) und führen Sie dann eine weitere Adressberechnung durch.)
• Lesen / Schreiben von der Elementadresse

Der letzte Schritt nimmt immer noch den Löwenanteil der Zeit in Anspruch.

Persönlicher Vorschlag

• Sie können eine CopyRangeFunktion bereitstellen , die sich wie eine Funktion verhält Array.Copy, jedoch zwischen zwei Instanzen von Ihrer NonContiguousByteArrayoder zwischen einer Instanz und einer anderen normalen ausgeführt wird byte[]. Für diese Funktionen kann SIMD-Code (C ++ oder C #) verwendet werden, um die Speicherbandbreitennutzung zu maximieren. Anschließend kann der C # -Code im kopierten Bereich ohne Mehraufwand für die Dereferenzierung oder Adressberechnung ausgeführt werden.

Bedenken hinsichtlich Benutzerfreundlichkeit und Interoperabilität

• Anscheinend können Sie dies nicht NonContiguousByteArraymit C # -, C ++ - oder fremdsprachigen Bibliotheken verwenden, die zusammenhängende Bytearrays oder Bytearrays erwarten , die fixiert werden können.
• Wenn Sie jedoch eine eigene C ++ - Beschleunigungsbibliothek (mit P / Invoke oder C ++ / CLI) schreiben, können Sie eine Liste von Basisadressen mehrerer 4-MB-Blöcke in den zugrunde liegenden Code übergeben.
  • Wenn Sie beispielsweise Zugriff auf Elemente gewähren müssen, die bei beginnen (3 * 1024 * 1024)und enden (5 * 1024 * 1024 - 1), bedeutet dies, dass sich der Zugriff über chunk[0]und erstreckt chunk[1]. Sie können dann ein Array (Größe 2) von Byte-Arrays (Größe 4M) erstellen, diese Blockadressen anheften und sie an den zugrunde liegenden Code übergeben.
• Eine weitere Verwendbarkeit Sorge ist , dass Sie nicht in der Lage sein werden , die implementieren IList<byte>Schnittstelle effizient: Insertund Removedauern einfach zu lange zu verarbeiten , weil sie erfordert O(N)Zeit.
  • In der Tat sieht es so aus, als ob Sie nichts anderes implementieren können, als IEnumerable<byte>dass es sequentiell gescannt werden kann und das wars.

Es ist erwähnenswert, dass C ++ bereits eine äquivalente Struktur von Standard hat std::deque. Gegenwärtig wird dies als Standardeinstellung empfohlen, wenn eine Arbeitssequenz mit wahlfreiem Zugriff benötigt wird.

Die Realität ist, dass zusammenhängender Speicher fast völlig unnötig ist, sobald die Daten eine bestimmte Größe überschritten haben - eine Cache-Zeile hat nur 64 Bytes und eine Seitengröße von nur 4 bis 8 KB (typische Werte derzeit). Sobald Sie anfangen, über ein paar MB zu sprechen, geht das Problem aus dem Fenster. Gleiches gilt für die Allokationskosten. Der Preis für die Verarbeitung all dieser Daten - auch wenn sie nur gelesen werden - stellt den Preis für die Zuteilung sowieso in den Schatten.

Der einzige andere Grund, sich darüber Sorgen zu machen, ist die Anbindung an C-APIs. Sie können jedoch ohnehin keinen Zeiger auf den Puffer einer Liste abrufen, sodass hier keine Bedenken bestehen.

Wenn Speicherabschnitte zu unterschiedlichen Zeitpunkten zugewiesen werden, wie in den Unterfeldern in Ihrer Datenstruktur, können sie im Speicher weit voneinander entfernt sein. Ob dies ein Problem ist oder nicht, hängt von der CPU ab und ist sehr schwer länger vorherzusagen. Du musst es testen.

Dies ist eine ausgezeichnete Idee, die ich in der Vergangenheit verwendet habe. Natürlich sollten Sie für Ihre Sub-Array-Größen und die Bitverschiebung für die Division nur Zweierpotenzen verwenden (dies kann im Rahmen der Optimierung geschehen). Ich fand diese Art von Struktur etwas langsamer, da Compiler eine einzelne Array-Indirektion einfacher optimieren können. Sie müssen testen, da sich diese Optimierungsarten ständig ändern.

Der Hauptvorteil besteht darin, dass Sie näher an die obere Speichergrenze Ihres Systems herangehen können, solange Sie diese Arten von Strukturen konsistent verwenden. Solange Sie Ihre Datenstrukturen vergrößern und keinen Müll produzieren, vermeiden Sie zusätzliche Garbage Collections, die bei einer normalen Liste auftreten würden. Für eine riesige Liste könnte dies einen großen Unterschied bedeuten: den Unterschied zwischen der Fortsetzung der Ausführung und dem Verlust des Speichers.

Die zusätzlichen Zuordnungen sind nur dann ein Problem, wenn Ihre Sub-Array-Blöcke klein sind, da bei jeder Array-Zuordnung ein Speicheroverhead auftritt.

Ich habe ähnliche Strukturen für Wörterbücher (Hash-Tabellen) angelegt. Das vom .net-Framework bereitgestellte Dictionary hat das gleiche Problem wie List. Wörterbücher sind insofern schwieriger, als Sie auch das Aufbereiten vermeiden müssen.

Bei einer Blockgröße von 4 MB ist nicht garantiert, dass ein einzelner Block im physischen Speicher zusammenhängend ist. Es ist größer als eine typische VM-Seitengröße. Lokalität in dieser Größenordnung nicht aussagekräftig.

Sie müssen sich um die Fragmentierung des Heapspeichers kümmern: Wenn die Zuweisungen so erfolgen, dass Ihre Blöcke im Heapspeicher weitgehend nicht zusammenhängend sind, erhalten Sie beim Zurückfordern durch den GC möglicherweise einen Heapspeicher, der zu fragmentiert ist, um auf einen zu passen nachträgliche Zuordnung. Dies ist in der Regel eine schlimmere Situation, da Fehler an nicht zusammenhängenden Stellen auftreten und möglicherweise einen Neustart der Anwendung erzwingen.

Ich drehe einige der zentralsten Teile meiner Codebasis (eine ECS-Engine) um die Art der von Ihnen beschriebenen Datenstruktur, obwohl sie kleinere zusammenhängende Blöcke verwendet (eher 4 Kilobyte anstelle von 4 Megabyte).

Es verwendet eine doppelte freie Liste, um Einfügungen und Entfernungen in konstanter Zeit zu erreichen, mit einer freien Liste für freie Blöcke, die zum Einfügen bereit sind (Blöcke, die nicht voll sind), und einer subfreien Liste innerhalb des Blocks für Indizes in diesem Block bereit, beim Einsetzen zurückgefordert zu werden.

Ich werde die Vor- und Nachteile dieser Struktur behandeln. Beginnen wir mit einigen Nachteilen, denn es gibt eine Reihe von Nachteilen:

Nachteile

1. Das Einfügen von ein paar hundert Millionen Elementen in diese Struktur dauert ungefähr viermal länger als std::vector(eine rein zusammenhängende Struktur). Und ich bin ziemlich vernünftig bei Mikrooptimierungen, aber es gibt nur konzeptionell mehr Arbeit zu tun, da der übliche Fall zuerst den freien Block oben in der Liste der freien Blöcke untersuchen muss, dann auf den Block zugreifen und einen freien Index aus den Blöcken einfügen muss freie Liste, schreibe das Element an die freie Position und überprüfe dann, ob der Block voll ist und lösche den Block aus der Liste der freien Blöcke, wenn dies der Fall ist. Es ist immer noch eine Operation mit konstanter Zeit, aber mit einer viel größeren Konstante, als wenn man zurückschiebt std::vector.
2. Der Zugriff auf Elemente mit einem Direktzugriffsmuster dauert etwa doppelt so lange, da die zusätzliche Indizierungsarithmetik und die zusätzliche Indirektionsebene erforderlich sind.
3. Der sequenzielle Zugriff wird einem Iteratorentwurf nicht effizient zugeordnet, da der Iterator jedes Mal, wenn er inkrementiert wird, eine zusätzliche Verzweigung ausführen muss.
4. Der Speicherbedarf beträgt in der Regel etwa 1 Bit pro Element. 1 Bit pro Element klingt vielleicht nicht nach viel, aber wenn Sie damit eine Million 16-Bit-Ganzzahlen speichern, sind das 6,25% mehr Speicher als bei einem perfekt kompakten Array. In der Praxis wird jedoch in der Regel weniger Speicher verwendet, als std::vectorwenn Sie die komprimieren vector, um die überschüssige Kapazität zu beseitigen, die sie reserviert. Auch verwende ich es im Allgemeinen nicht, um solche jugendlichen Elemente zu speichern.

Vorteile

1. Der sequenzielle Zugriff mit einer for_eachFunktion, die Rückrufverarbeitungsbereiche von Elementen innerhalb eines Blocks verwendet, ist mit der Geschwindigkeit des sequenziellen Zugriffs nahezu konkurrierend std::vector(nur wie ein 10% iger Unterschied). Die meiste Zeit in einer ECS-Engine wird mit sequenziellem Zugriff verbracht.
2. Es ermöglicht zeitlich konstante Entfernungen aus der Mitte, wobei die Struktur die Zuordnung von Blöcken aufhebt, wenn sie vollständig leer sind. Infolgedessen ist es im Allgemeinen recht anständig, sicherzustellen, dass die Datenstruktur niemals wesentlich mehr Speicher als erforderlich belegt.
3. Es macht keine Indizes für Elemente ungültig, die nicht direkt aus dem Container entfernt werden, da nur Löcher zurückbleiben, indem ein Ansatz mit einer freien Liste verwendet wird, um diese Löcher beim anschließenden Einfügen zurückzugewinnen.
4. Selbst wenn diese Struktur eine epische Anzahl von Elementen enthält, müssen Sie sich nicht so viele Gedanken über Speichermangel machen, da nur kleine zusammenhängende Blöcke angefordert werden, die für das Betriebssystem keine Herausforderung darstellen, eine große Anzahl nicht verwendeter zusammenhängender Blöcke zu finden Seiten.
5. Es eignet sich gut für Parallelität und Thread-Sicherheit, ohne die gesamte Struktur zu sperren, da Operationen im Allgemeinen auf einzelne Blöcke beschränkt sind.

Jetzt war einer der größten Vorteile für mich, dass es trivial geworden ist, eine unveränderliche Version dieser Datenstruktur zu erstellen:

Seitdem öffnete sich jede Art von Türen für das Schreiben von mehr Funktionen ohne Nebenwirkungen, was es viel einfacher machte, Ausnahmesicherheit, Thread-Sicherheit usw. zu erreichen. Die Unveränderlichkeit war eine Sache, mit der ich entdeckte, dass ich sie leicht erreichen konnte Diese Datenstruktur ist im Nachhinein und aus Versehen entstanden, aber wahrscheinlich einer der schönsten Vorteile, die sie mit sich gebracht hat, da sie die Pflege der Codebasis erheblich vereinfacht hat.

Nicht zusammenhängende Arrays haben keine Cache-Lokalität, was zu einer schlechten Leistung führt. Bei einer Blockgröße von 4 MB scheint es jedoch genügend Orte für eine gute Zwischenspeicherung zu geben.

Bei Blöcken dieser Größe sollte man sich nicht mit der Lokalität von Referenzen befassen, geschweige denn mit 4-Kilobyte-Blöcken. Eine Cache-Zeile hat normalerweise nur 64 Byte. Wenn Sie Cache-Ausfälle reduzieren möchten, konzentrieren Sie sich nur auf die richtige Ausrichtung dieser Blöcke und bevorzugen nach Möglichkeit sequentiellere Zugriffsmuster.

Eine sehr schnelle Möglichkeit, ein Direktzugriffsspeichermuster in ein sequentielles umzuwandeln, besteht in der Verwendung eines Bitsets. Angenommen, Sie haben eine Schiffsladung Indizes und diese sind in zufälliger Reihenfolge. Sie können sie einfach durchpflügen und Bits im Bitset markieren. Dann können Sie durch Ihren Bitsatz iterieren und prüfen, welche Bytes ungleich Null sind, indem Sie beispielsweise jeweils 64 Bits prüfen. Sobald Sie auf einen Satz von 64-Bit stoßen, von denen mindestens ein Bit gesetzt ist, können Sie mithilfe von FFS- Anweisungen schnell feststellen, welche Bits gesetzt sind. Die Bits geben an, auf welche Indizes Sie zugreifen sollen, es sei denn, Sie erhalten die Indizes nacheinander sortiert.

Dies hat einen gewissen Overhead, kann aber in einigen Fällen einen lohnenden Austausch bedeuten, insbesondere wenn Sie diese Indizes mehrmals durchlaufen werden.

Der Zugriff auf ein Objekt ist nicht ganz so einfach, es gibt eine zusätzliche Indirektionsebene. Würde das weg optimiert werden? Würde es Cache-Probleme verursachen?

Nein, es kann nicht weg optimiert werden. Zumindest der Direktzugriff kostet bei dieser Struktur immer mehr. Es erhöht Ihre Cache-Ausfälle jedoch häufig nicht so stark, da Sie mit dem Array von Zeigern auf Blöcke in der Regel eine hohe zeitliche Lokalität erzielen, insbesondere, wenn Ihre allgemeinen Ausführungspfade sequentielle Zugriffsmuster verwenden.

Da nach Erreichen des 4-MB-Grenzwerts ein lineares Wachstum zu verzeichnen ist, können Sie weit mehr Zuweisungen vornehmen als normalerweise (z. B. maximal 250 Zuweisungen für 1 GB Arbeitsspeicher). Nach 4M wird kein zusätzlicher Speicher kopiert. Ich bin mir jedoch nicht sicher, ob die zusätzlichen Zuordnungen teurer sind als das Kopieren großer Speicherblöcke.

In der Praxis ist das Kopieren oft schneller, weil es selten vorkommt und nur so etwas wie " log(N)/log(2)times total" auftritt, während gleichzeitig der übliche schmutzig-billige Fall vereinfacht wird, in dem Sie ein Element viele Male in das Array schreiben können, bevor es voll wird und erneut zugeteilt werden muss. In der Regel werden Sie mit dieser Art von Struktur keine schnelleren Einfügungen erhalten, da die allgemeine Fallarbeit teurer ist, selbst wenn sie sich nicht mit dem teuren seltenen Fall der Neuzuweisung großer Arrays befassen muss.

Die Hauptattraktivität dieser Struktur liegt für mich trotz aller Nachteile in der Reduzierung des Speicherbedarfs, da ich mir keine Gedanken über OOM machen muss und Indizes und Zeiger speichern kann, die nicht ungültig werden, die Parallelität und die Unveränderlichkeit. Es ist schön, eine Datenstruktur zu haben, in der Sie Dinge in konstanter Zeit einfügen und entfernen können, während sie sich selbst bereinigt und Zeiger und Indizes in der Struktur nicht ungültig macht.