C++, Möglichkeiten zur Verbesserung der Cache-Lokalität?

Question

Ich habe eine Implementierung einer Klasse X, die zwei Zeiger auf zwei Informationen hat. Ich habe eine neue Implementierung geschrieben, Klasse Y, die nur einen Zeiger auf eine Struktur hat, die die zwei Teile der Information zusammen als benachbarte Elemente enthält. Die Methoden von X und Y müssen normalerweise nur eine der Informationen bearbeiten, stellen aber eine get() -Methode bereit, die einen Zeiger auf das zweite Stück zurückgibt (in diesem Fall gibt die Klasse X ihren Zeiger auf dieses Stück zurück und die Klasse Y gibt die Adresse zurück) des zweiten Mitglieds der Struktur). Bei normaler Verwendung werden Aufrufe an die Methoden von X und Y durch Aufrufe von get() unterbrochen und an dem zurückgegebenen zweiten Teil ausgeführt.

Ich erwarte, dass in realen Situationen sollte eine Leistungsverbesserung sein, jetzt, da die beiden Teile der Informationen in der Klasse Y-Implementierung nebeneinander sind (weil sie benachbarte Mitglieder einer Struktur sind), aber ich Ich sehe keinen Unterschied in den Benchmarks, die ich geschrieben habe (dazwischenliegende Aufrufe an die Methoden von X und Y mit der Arbeit an ihren zweiten Stücken in großen Schleifen). Ich vermute, das liegt daran, dass bei beiden Tests alles in den Cache passt. Ich möchte das noch nicht in meiner echten App ausprobieren, da sich die Semantik von X und Y auf andere subtile Arten unterscheidet, die nicht mit dieser Optimierung in Verbindung stehen, und die Verwendung der Anwendung zu portieren ist etwas Arbeit, und diese Benchmarks sollen dazu beitragen, dies zu rechtfertigen Arbeit an erster Stelle.

Was ist der beste Weg, den Unterschied in der Leistung aufgrund der besseren Cache-Lokalität zu beobachten? Wenn ich eine Menge Dummy-Arbeit an einem Array mache, das der Größe des Caches zwischen den Aufrufen entspricht, ist das ausreichend? Oder möchte ich an einem Array arbeiten, das etwas kleiner ist als die Cachegröße, so dass die Arbeit an meinen Instanzen meiner Klasse dazu führt, dass Dinge in den Cache hinein und aus ihm herausfallen? Ich bin mir nicht sicher, wie man etwas programmiert, das gegen Compiler-Optimierungen und verschiedene Cache-Größen robust ist.

Answer 1

Wenn ich Ihre Situation richtig verstehe (und bitte korrigieren Sie mich wenn nicht), dann ist es sechs von eins, oder ein halbes Dutzend der anderen.

In Klasse X benötigen Sie einen Zeiger-Lookup für beide Informationen. In der Klasse Y benötigen Sie eine Suche nach der ersten und zwei (die erste und dann die Verschiebung) für die zweite. Das opfert "Lokalität" für einen anderen Speicherzugriff. Compiler sind leider immer noch sehr gut darin, Bus-Zeit damit zu verschwenden, Wörter im RAM nachzuschlagen.

Wenn es möglich ist, erhalten Sie die besten Ergebnisse, indem Sie die beiden Zielinformationsinformationen direkt in der betreffenden Klasse halten (d. H. Jedes eigene Klassenmitglied), anstatt diese Zeiger für unnötige Indirektion zu verwenden. Da ich keinen Code sehe, kann ich fast nichts sagen.

Auf jeden Fall erhalten Sie eine höhere Leistung aus dem Studium der algorithmischen Komplexität Ihrer Anwendung als je zuvor mit Mikro-Optimierung von zwei Variablen in einer Klassendefinition. Eine gute Idee ist es auch, ein Profiling-Tool zu verwenden, um (objektiv) zu sehen, wo Ihre Engpässe liegen (gprof ist auf * nix-Systemen üblich). Gibt es einen eindeutigen Grund, warum Sie das Caching von Standorten speziell erhöhen möchten?

Answer 2

Wenn Sie Linux verwenden, bietet die Verwendung von Cachegrind in Verbindung mit KCacheGrind möglicherweise mehr Informationen darüber, wie sich Ihr Cache verhält.

Answer 3

Sie könnten einen Benchmark speziell für den Cache erstellen. Ordnen Sie beispielsweise die Datenblöcke, auf die hingewiesen wird, so zu, dass sie garantiert auf verschiedenen Cache-Zeilen liegen (z. B. durch Verwendung eines benutzerdefinierten Speicherzuordners, der Zuweisungen auf mindestens einige hundert Bytes verteilt). Dann iterieren Sie wiederholt über eine Anzahl von Objekten, die zu groß sind, um sogar in den L2-Cache zu passen (sehr plattformabhängig, da es von der Anzahl der Zeilen im Cache abhängt, aber 1 Million würde die meisten Architekturen abdecken und nur ein paar hundert Megabyte RAM benötigen) gesamt).

Dies gibt Ihnen eine obere Grenze für den Leistungszuwachs, der durch den Wechsel von X zu Y erzielt wird. Aber es führt dazu, dass die Leistung von X auf eine wahrscheinliche reale Nutzung reduziert wird. Und um Ihren Fall zu beweisen, benötigen Sie eine Untergrenze, keine Obergrenze. Ich bin mir also nicht sicher, ob Sie viel erreichen würden, es sei denn, Sie stellen fest, dass selbst dieser schlimmste Fall immer noch keinen wesentlichen Unterschied macht und Sie sich nicht mit der Optimierung beschäftigen müssen.

Auch wenn Sie nicht die theoretische Worst-Case-Leistung von X anstreben, wird jeder Benchmark, der den Cache übersteigt, nur einen willkürlichen Punkt schlechter Leistung von X auswählen und nachsehen, ob Y besser ist. Es ist nicht weit, den Benchmark zu manipulieren, damit Y gut aussieht. Es ist wirklich egal, wie Ihr Code in zwielichtigen Benchmarks funktioniert, außer vielleicht für die Zwecke der Vermarktung Lügen Literatur.

Die beste Möglichkeit, den Leistungsunterschied in der realen Welt zu beobachten, besteht darin, einen realen Client Ihrer Klasse zu messen. Sie sagen, dass "die Semantik von X und Y sich auf andere subtile Weise unterscheidet, die nicht mit dieser Optimierung zusammenhängen". In diesem Fall kann ich nur empfehlen, eine Klasse Z zu schreiben, die sich von X nur hinsichtlich dieser Optimierung unterscheidet das in Ihrer Anwendung als Vergleich.

Sobald Ihre Tests versuchen, die schlechteste realistische Verwendung darzustellen, können Sie, wenn Sie keinen Leistungsunterschied feststellen, wahrscheinlich keine Leistungssteigerung erzielen.

All das gesagt, wenn es logisch Sinn macht (das heißt, es macht den Code nicht mehr erstaunlich), dann würde ich empfehlen, die Anzahl der Heap-Zuweisungen in C++ einfach als Faustregel zu minimieren. Es neigt nicht dazu, die Geschwindigkeit oder den Gesamtspeicherverbrauch zu verschlechtern, und es vereinfacht tendenziell die Handhabung Ihrer Ressourcen. Eine Faustregel rechtfertigt natürlich kein Umschreiben des Arbeitscodes.