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

8

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 es in Situationen des wirklichen Lebens eine Leistungsverbesserung geben sollte, jetzt da die zwei Informationen in der Implementierung der Klasse Y im Speicher nebeneinander sind (weil sie benachbarte Mitglieder einer Struktur sind), aber ich ' Ich sehe keinen Unterschied in den Benchmarks, die ich geschrieben habe (die Aufrufe an die Methoden von X und Y werden mit der Arbeit an ihren zweiten Stücken in großen Schleifen vermischt). 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 das Portieren der verwendenden Anwendung wird etwas Arbeit sein, 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, sodass die Arbeit an meinen Instanzen meiner Klasse dazu führt, dass Dinge in den Cache hinein und aus ihm herausfallen? Ich bin nicht sicher, wie man etwas codiert, das gegen Compiler-Optimierungen und verschiedene Cache-Größen robust ist.

    
Joseph Garvin 16.06.2009, 21:13
quelle

3 Antworten

8

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

    
Soo Wei Tan 16.06.2009 22:57
quelle
2

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 Zuordnungen auf mindestens einige hundert Bytes puffert). 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) total).

Dies gibt Ihnen eine obere Grenze für den Leistungszuwachs, der durch den Wechsel von X zu Y erzielt wird. Aber es wird dadurch erreicht, dass die Leistung von X auf eine wahrscheinliche tatsächliche Nutzung herabgesetzt 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 würden feststellen, dass selbst dieser schlimmste Fall immer noch keinen signifikanten Unterschied macht und Sie sich nicht um die Optimierung kümmern müssen.

Auch wenn Sie nicht auf die theoretische Worst-Case-Leistung von X abzielen, wird jeder Benchmark, der den Cache überschreiten soll, nur einen beliebigen 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 spielt wirklich keine Rolle, wie Ihr Code in fragwürdigen Benchmarks funktioniert, außer vielleicht für die Zwecke der Marketing 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, dass Sie eine Klasse Z schreiben, die sich von X nur unterscheidet diese Optimierung, und verwenden Sie das in Ihrer Anwendung als Vergleich.

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

Alles, was gesagt wird, wenn es logisch Sinn macht (das heißt, es macht den Code nicht erstaunlicher), dann würde ich befürworten, die Anzahl der Heap-Zuweisungen in C ++ zu minimieren, einfach als Faustregel. 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.

    
Steve Jessop 17.06.2009 00:49
quelle
0

Wenn ich Ihre Situation richtig verstehe (und bitte korrigieren Sie mich wenn nicht), dann sind 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 einen Suchvorgang für den ersten und zwei (den ersten und dann den Offset) für den zweiten. Das opfert "Lokalität" für einen anderen Speicherzugriff. Compiler sind leider immer noch sehr gut darin, Zeit mit dem Bus zu verschwenden, wenn sie Wörter im RAM nachschlagen.

Wenn es möglich ist, erhalten Sie die besten Ergebnisse, wenn Sie die zwei Zielinformationen direkt in der fraglichen Klasse halten (d. h. jedes eigene Klassenmitglied), anstatt diese Zeiger für unnötige Indirektion zu verwenden. Da ich keinen Code sehe, kann ich nicht viel mehr sagen.

Auf jeden Fall erhalten Sie durch das Studium der algorithmischen Komplexität Ihrer Anwendung mehr Leistung als jemals zuvor, wenn Sie zwei Variablen in einer Klassendefinition mikrooptimieren. Eine gute Idee ist es auch, ein Profiling-Tool zu verwenden, um (objektiv) zu sehen, wo Ihre Engpässe sind (gprof ist auf * nix-Systemen üblich). Gibt es einen eindeutigen Grund, warum Sie das lokale Caching speziell erhöhen möchten?

    
Chris Tonkinson 16.06.2009 22:42
quelle