Ich möchte lernen, wie man besseren Code schreibt, der den Cache der CPU nutzt. Das Arbeiten mit zusammenhängender Erinnerung scheint die ideale Situation zu sein. Davon abgesehen bin ich neugierig, ob es ähnliche Verbesserungen gibt, die mit nicht zusammenhängendem Speicher gemacht werden können, aber mit einem Array von zu folgenden Zeigern, wie:
%Vor%Dies ist nur ein grober Mock-up-Code, und um dies richtig zu lernen, sagen wir einfach, dass alle Position-Strukturen zufällig auf dem ganzen Haufen erstellt wurden.
Können moderne, intelligente Prozessoren wie Intels i7 vorausschauen und sehen, dass sie in Kürze die Daten von X_ptr benötigen? Würde die folgende Codezeile helfen?
Ich hatte einige Präsentationsfolien gelesen, die darauf hinwiesen, dass ein Code wie dieser den Prozessor dazu veranlassen würde, einige Daten vorab zu lesen. Ist das wahr? Ich bin mir bewusst, dass es nicht standardmäßige, plattformspezifische Möglichkeiten gibt, Prefetching wie __builtin_prefetch aufzurufen, aber es ist wie eine hässliche vorzeitige Optimierung, wenn man es überall hinwirft. Ich suche nach einer Art und Weise, wie ich Cache-effizienten Code unterbewusst schreiben kann.
Ich weiß, dass Sie nicht gefragt haben (und wahrscheinlich brauchen Sie keine Predigt über die richtige Behandlung von Caches, aber ich dachte, ich würde sowieso meine zwei Cents beisteuern. Beachten Sie, dass das alles nur in hot code.Erinnere dich, dass vorzeitige Optimierung die Wurzel allen Übels ist.
Wie in den Kommentaren erwähnt wurde, ist der beste Weg, Container mit tatsächlichen Daten zu haben. Im Allgemeinen sind flache Datenstrukturen den "Zeiger-Spaghetti" vorzuziehen, auch wenn Sie einige Daten duplizieren und / oder einen Preis für die Größenänderung / Verschiebung / Defragmentierung Ihrer Datenstrukturen zahlen müssen.
Und wie Sie wissen, zahlen sich flache Datenstrukturen (z. B. ein Array von Daten) nur aus, wenn Sie die meiste Zeit linear und sequentiell darauf zugreifen.
Aber diese Strategie ist möglicherweise nicht immer verwendbar. Anstelle von tatsächlichen linearen Daten können Sie andere Strategien verwenden, wie Pool-Allokatoren verwenden und über die Pools selbst iterieren, anstatt über den Vektor, der die Zeiger enthält. Das hat natürlich seine eigenen Nachteile und kann etwas komplizierter sein.
Ich bin mir sicher, dass Sie das bereits wissen, aber es muss noch einmal erwähnt werden, dass eine der effektivsten Techniken, um den Cache optimal zu nutzen, kleinere Daten sind! Wenn Sie in obigem Code mit int16_t anstelle von int32_t durchkommen können, sollten Sie dies unbedingt tun. Sie sollten Ihre vielen bool s und Flags und Enums in Bit-Felder packen, Indizes anstelle von Zeigern verwenden (speziell auf 64-Bit-Systemen), feste Hash-Werte in Ihren Datenstrukturen anstelle von Strings usw. verwenden.
Nun zu Ihrer Hauptfrage, ob der Prozessor zufälligen Zeigern folgen und die Daten in den Cache bringen kann, bevor sie benötigt werden. In sehr begrenztem Maße geschieht dies. Wie Sie wahrscheinlich wissen, verwenden moderne CPUs eine Menge Tricks, um ihre Geschwindigkeit zu erhöhen (dh ihre Instruktions-Rentabilität zu erhöhen.) Tricks wie ein Speicherpuffer, Out-of-Order-Ausführung, superskalare Pipelines, mehrere Funktionseinheiten jeder Art, Verzweigung Vorhersage, usw. Die meisten dieser Tricks helfen der CPU, Befehle auszuführen, auch wenn die aktuellen Anweisungen zum Stillstand gekommen sind oder zu lange dauern. Bei Speicherauslastungen (was am langsamsten ist, wenn sich die Daten nicht im Cache befinden) bedeutet dies, dass die CPU so schnell wie möglich zur Anweisung gelangen, die Adresse berechnen und die Daten vom Speichercontroller anfordern soll. Der Speichercontroller kann jedoch nur eine sehr begrenzte Anzahl von ausstehenden Anforderungen haben (normalerweise zwei in diesen Tagen, aber ich bin mir nicht sicher.) Dies bedeutet, dass selbst wenn die CPU sehr ausgeklügelte Dinge in andere Speicherorte (z Elemente Ihres posPointers -Vektors) und leiten daraus ab, dass dies die Adressen neuer Daten sind, die Ihr Code benötigt, er könnte nicht sehr weit voraus sein, da der Speicher-Controller nur so viele Anfragen ausstehen kann.
In jedem Fall, AFAIK, glaube ich nicht, dass CPUs das tatsächlich schon tun. Beachten Sie, dass dies ein schwieriger Fall ist, da die Adressen Ihrer zufällig verteilten Speicherplätze sich selbst im Speicher befinden (im Gegensatz zu einem Register oder berechenbar aus dem Inhalt eines Registers). Und wenn die CPUs es tun würden, würde es nicht haben wegen der Speicherschnittstellenbeschränkungen ohnehin einen großen Effekt.
Die von Ihnen erwähnte Prefetch-Methode scheint für mich gültig zu sein und ich habe sie bereits verwendet, aber sie bringt nur dann einen spürbaren Effekt, wenn Ihre CPU etwas zu tun hat, während sie auf die zukünftigen Daten wartet. Das Inkrementieren von drei Ganzzahlen benötigt viel weniger Zeit als das Laden von 12 Bytes aus dem Speicher (tatsächlich das Laden einer Cache-Zeile) und daher wird dies nicht viel für die Ausführungszeit bedeuten. Aber wenn Sie etwas Wertvolles und Schwergewichtiges hätten, das über die Speichervorabzugriffe gelegt werden könnte (z. B. das Berechnen einer komplexen Funktion, die keine Daten aus dem Speicher benötigt!), Dann könnten Sie sehr schöne Beschleunigungen erhalten. Sie sehen, die Zeit, um durch die obige Schleife zu gehen, ist im Wesentlichen die Summe der Zeit aller Cache-Misses; und Sie erhalten die Koordinateninkremente und die Schleifenbuchhaltung kostenlos. Also hättest du mehr gewonnen, wenn die kostenlosen Sachen wertvoller wären!
Moderne Prozessoren haben Hardware-Prefetch-Mechanismen: Intel Hardware-Prefetcher . Sie leiten Schritt-Zugriffsmuster auf den Speicher ab und holen die Speicherstellen, auf die in naher Zukunft wahrscheinlich zugegriffen wird, vorab.
Im Falle einer völlig zufälligen Zeigerjagd können solche Techniken jedoch nicht helfen. Der Prozessor weiß nicht, dass das Programm, das gerade ausgeführt wird, Zeigerjagd ausführt, daher kann er nicht entsprechend vorabladen. In solchen Fällen sind Hardwaremechanismen für die Leistung schädlich, da sie Werte vorlesen würden, die wahrscheinlich nicht verwendet werden.
Das Beste, was Sie tun können, ist zu versuchen, Ihre Datenstrukturen im Speicher so zu organisieren, dass Zugriffe auf zusammenhängende Teile des Speichers wahrscheinlicher sind.
Tags und Links c++ performance caching pointers cpu-cache