Overhead von Atomic-Operationen

von Hubert Schmid vom 2012-12-23

Welchen Overhead haben Atomic-Operationen gegenüber regulären Speicherzugriffen? Dieser Frage möchte ich nachgehen – zumindest für die weit verbreitete x86-Architektur. Eine allgemeine Betrachtung ist dagegen schwierig. Denn wie sich zeigen wird, ist das Verhalten stark von der eingesetzten Hardware- und Speicher-Architektur abhängig.

Für die Analyse habe ich ein kleines Programm in C++ geschrieben, das mir hinreichend viel Kontrolle über die Speicherzugriffe gibt. Bei jedem Testlauf werden 20 Milliarden Operationen auf den Speicher ausgeführt. Auf die wesentlichen Teile gehe ich später ein. Die Laufzeitmessungen führe ich auf einen Server mit 16 Kernen durch. Dabei verzichte ich auf Hyper-Threading, um die Ergebnisse einfacher interpretieren zu können. Die Tests werden jeweils mit einem einzelnen und 16 parallelen Threads ausgeführt, um sehen zu können, wie sich der Overhead auf atomare und parallele Operationen verteilt.

Lesende Zugriffe

Ich beginne mit regulären Lesezugriffen und einem Thread. Die folgende Funktion wird 20 Milliarden Mal nacheinander ausgeführt. Um dabei unerwünschte Optimierungen zu verhindern, ist die globale Variable mit volatile gekennzeichnet. Das bedeutet in C++ im Wesentlichen, dass die Speicherzugriffe tatsächlich durchgeführt werden.

volatile int _volatile{0}; int read_volatile() { return _volatile; }

Die Laufzeit liegt bei 7,78 Sekunden – was ungefähr 2,6 Milliarden Operationen pro Sekunde entspricht und damit ziemlich genau dem Takt der einzelnen Kerne. Das ist gut. Denn das bedeutet auch, dass die Leseoperationen tatsächlich durchgeführt werden, und dass die Programmsteuerung die Ergebnisse kaum verfälscht.

Den gleichen Test führe ich nun mit einer Atomic-Variablen und der folgenden Funktion durch – mit dem Ergebnis, dass die Laufzeit des Programms wiederum bei 7,78 Sekunden liegt. Die Atomic-Leseoperationen verursachen also keinen Overhead auf der x86-Architektur. Die einfache Erklärung dafür ist, dass bei dieser Prozessor-Architektur alle Leseoperationen atomar sind – zumindest unter gewissen Rahmenbedingungen wie der korrekten Speicherausrichtung.

std::atomic<int> _atomic{0}; int read_atomic() { return _atomic.load(std::memory_order_relaxed); }

In den nächsten beiden Tests werden die Funktionen mit jeweils 16 parallelen Threads ausgeführt. Wenig überraschend sind die Laufzeiten in beiden Fällen identisch: Die 20 Milliarden Operationen benötigen 0,50 Sekunden, was fast 16 Mal schneller als mit einem einzelnen Thread ist. Das Programm skaliert quasi optimal auf alle Kerne.

Wie ist das möglich, wo doch der Speicherbus wesentlich langsamer ist? Die Erklärung ist einfach: Systeme dieser Art haben viele Caches, die sich auf Sockel und Kerne verteilen. Der gleiche Speicherbereich kann sich gleichzeitig in mehreren Caches befinden, so dass mehrere Kerne mit voller Geschwindigkeit auf die Daten zugreifen können. Das gilt allerdings nur für Lese-Operationen. Denn in diesem Fall ist die Zeile in allen betroffenen Caches als Shared gekennzeichnet. Währenddessen sind Schreiboperationen nicht möglich.

Schreibende Zugriffe

Bei reinen Schreibzugriffen wird ein Wert unabhängig vom bisherigen Wert an eine Speicherstelle geschrieben. Die Laufzeit dieser Operationen messe ich nicht – und zwar aus zwei Gründen: Erstens kenne ich kein reales Beispiel, in dem solche Operationen in der Häufigkeit ausgeführt werden, dass sie für die Laufzeit relevant wären. Und zweitens greift in diesem Fall ein besonderer Mechanismus, wodurch die Ergebnisse stark beeinflusst werden und einen irreführenden Eindruck hinterlassen.

Nur in aller Kürze: Reine Schreiboperationen werden unabhängig vom Cache-Zustand durchgeführt. Sie werden in eine Queue eingefügt, deren Einträge asynchron abgearbeitet werden – sobald die Queue exklusiven Zugriff auf die Cache-Zeile bekommt.

Kombinierte Zugriffe

Wichtiger als die reinen Schreibzugriffe sind Operationen, bei denen eine Speicherstelle abhängig vom aktuellen Wert verändert wird. Ein typisches Beispiel einer solchen Operation ist compare_exchange. Für die Messungen verwende hingegen die Inkrement-Operation, da sie in meinen Anwendungen viel häufiger ausgeführt wird.

Im ersten Testlauf wird die folgende Funktion wiederum in einem Thread 20 Milliarden Mal nacheinander ausgeführt. Die Laufzeit liegt mit 46,9 Sekunden zwar deutlich über der Laufzeit für den entsprechenden Test mit reinen Leseoperationen, aufgrund der höheren Komplexität und des doppelten Speicherzugriffs aber noch im erwarteten Rahmen.

volatile int _volatile{0}; int write_volatile() { return _volatile++; }

Den gleichen Test führe ich wiederum mit einer Atomic-Variablen und der folgenden Funktion durch. Im Gegensatz zu den Tests mit Leseoperationen steigt die Laufzeit dabei signifikant von 46,9 Sekunden auf 179 Sekunden – wohlgemerkt mit nur einem Thread. Also obwohl die CPU praktisch die gleiche Arbeit leistet, benötigt sie für atomare Operationen fast die vierfache Zeit.

std::atomic<int> _atomic{0}; int write_atomic() { return _atomic.fetch_add(1, std::memory_order_relaxed); }

Im letzten Testlauf führe die Funktion wieder in 16 parallelen Threads aus, um zu sehen wie gut die atomaren Update-Operationen auf mehrere Kerne skalieren. Bei den Lesezugriffen ist der Durchsatz fast linear mit der Anzahl der Kerne gestiegen. Bei den Updates sieht das allerdings anders aus: Statt 179 Sekunden auf einem Kern benötigt das Programm auf 16 Kernen 698 Sekunden für die insgesamt 20 Milliarden Operationen. Die Laufzeit hat sich also durch die Parallelisierung fast um einen Faktor vier verschlechtert.

Die Erklärung ist relativ einfach: Auf dieser Architektur kann ein Kern nur dann ein atomares Update ausführen, wenn er exklusiven Zugriff auf den entsprechenden Speicherbereich besitzt. Da alle Kerne immer wieder auf die gleiche Speicherstelle zugreifen, wird die Cache-Zeile häufig zwischen den Kernen transferiert. Und diese Operation ist relativ teuer.

Fazit

Die Laufzeitmessungen haben gezeigt, dass atomare Leseoperationen auf der x86-Architektur schnell sind und fast linear mit der Anzahl der Kerne skalieren. Dagegen sind atomare Updates teuer – insbesondere wenn sie von mehreren Kernen zeitgleich durchgeführt werden. Bei 16 Kernen ist der Unterschied schon relativ groß: Leseoperationen sind in diesem Fall fast 1400 Mal schneller als Schreiboperationen.

Doch kein Grund zur Panik: Auch auf 16 Kernen wurden immerhin noch 28,6 Millionen Updates pro Sekunde ausgeführt, was für fast alle Anwendungen schnell genug ist. Ist man dennoch in der Situation, in der atomare Updates die parallele Ausführung signifikant beeinträchtigen, so gibt es zwei Lösungsalternativen: Entweder reduziert man die Anzahl der Update-Operationen – oder man verteilt sie auf unterschiedliche Cache-Zeilen und führt die einzelnen Werte bei Bedarf durch zusätzliche Leseoperationen zusammen.