Heim  >  Artikel  >  Backend-Entwicklung  >  Warum ist die Iteration durch „std::vector“ schneller als durch „std::array“?

Warum ist die Iteration durch „std::vector“ schneller als durch „std::array“?

Linda Hamilton
Linda HamiltonOriginal
2024-11-01 17:18:31754Durchsuche

Why is iterating through `std::vector` faster than `std::array`?

Umkehr des Glücks: Iterieren durch std::vector übertrifft std::array

Entgegen der ursprünglichen Annahme hat ein aktueller Benchmark ergeben, dass dies der Fall ist dass das Durchlaufen eines std::vector erheblich schneller ist als das Durchlaufen eines std::array. Dies widerspricht der bisherigen Annahme, dass Arrays eine überlegene Iterationsleistung bieten.

Um die Genauigkeit sicherzustellen, wurden im Benchmark mehrere Verbesserungen vorgenommen:

  • Erzwingung der Ergebnisnutzung: Eine nicht- Eine triviale Schleife wurde verwendet, um zu verhindern, dass die Compiler-Optimierung die Schleife eliminiert.
  • Einsatz der -O3-Optimierung: Der Code wurde mit der höchsten Optimierungsstufe kompiliert, um die Leistung zu maximieren.
  • Isolierende Schleifenmessung: std::chrono wurde nur zur Messung der Iterationszeit verwendet, mit Ausnahme der Variableninitialisierung.

Die gemessenen Zeiten für std::array und std::vector waren wie folgt folgt:

std::array: 99.554109 milliseconds
std::vector: 30.734491 milliseconds

Erforschung der Ursache

Der überraschende Geschwindigkeitsvorteil von std::vector kann auf Speicher-Paging zurückgeführt werden. Das im globalen Bereich gespeicherte Array befindet sich zunächst im .bss-Abschnitt der ausführbaren Datei und wird nicht in den Prozessadressraum ausgelagert. Im Gegensatz dazu wird der std::vector während seiner Erstellung zugewiesen und mit Nullen gefüllt, was dazu führt, dass seine Speicherseiten im Speicher vorhanden sind.

Behebung des Problems

An Um die Wettbewerbsbedingungen zu verbessern, kann man das Array explizit initialisieren oder seine Seiten vor der Iteration in den Speicher übertragen. Hier ist eine Modifikation, die die Array-Iterationszeit mit der des std::vector vergleichbar macht:

<code class="cpp">std::fill_n(v.data(), n, 1);</code>

Alternativ kann die Funktion mlock() verwendet werden, um die Array-Seiten auf Linux-Systemen in den Speicher zu zwingen.

Diese Anpassung zeigt, dass der Leistungsunterschied zwischen std::array und std::vector hauptsächlich auf ihre Speicherverwaltungsstrategien zurückzuführen ist, was die Bedeutung von Speicherzugriffsmustern für die Programmleistung hervorhebt.

Das obige ist der detaillierte Inhalt vonWarum ist die Iteration durch „std::vector“ schneller als durch „std::array“?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn