Zeitmessung mit Nanosekundengenauigkeit

Vor ein paar Monaten kam ein historischer Moment für mich. Standard-Betriebssystem-Tools zum Messen der Zeit reichen für mich nicht mehr aus. Es dauerte einige Zeit, um mit Nanosekundengenauigkeit und mit Nanosekunden-Overhead zu messen.

Ich beschloss, eine Bibliothek zu schreiben, die dieses Problem lösen würde. Auf den ersten Blick schien es nichts Besonderes zu geben. Bei näherer Betrachtung stellte sich jedoch wie immer heraus, dass es viele interessante Probleme gab, die gelöst werden mussten. In diesem Artikel werde ich über die Probleme sprechen und wie sie gelöst wurden.

Da Sie viele verschiedene Arten von Zeit auf einem Computer messen können, werde ich sofort klarstellen, dass wir hier über "Zeit mit Stoppuhr" sprechen werden. Oder Wanduhrzeit. Es ist Echtzeit, verstrichene Zeit usw. Das heißt, eine einfache "menschliche" Zeit, die wir zu Beginn der Aufgabe erkennen und am Ende anhalten.

Mikrosekunde - fast für immer

Entwickler von Hochleistungssystemen haben sich in den letzten Jahren an die Mikrosekunden-Zeitskala gewöhnt. In Mikrosekunden können Sie Daten von einem NVMe-Laufwerk lesen. In Mikrosekunden können Daten über das Netzwerk gesendet werden. Natürlich nicht für jedermann, aber für InifiniBand-Netzwerk - ganz einfach.

Gleichzeitig hatte die Mikrosekunde auch eine Struktur. Ein vollständiger E / A-Stapel besteht aus mehreren Software- und Hardwarekomponenten. Die von einigen von ihnen eingeführten Verzögerungen liegen im Submikrosekundenbereich.

Um Verzögerungen dieser Größenordnung zu messen, reicht die Mikrosekundengenauigkeit nicht mehr aus. Es ist jedoch nicht nur die Genauigkeit wichtig, sondern auch der Aufwand für die Messzeit. Der Linux-Systemaufruf clock_gettime () gibt die Zeit mit einer Genauigkeit von Nanosekunden zurück. Auf einem Computer, der mir direkt zur Verfügung steht (Intel® Xeon® CPU E5-2630 v2 bei 2,60 GHz), wird dieser Anruf in ca. 120 ns abgeschlossen. Sehr gute Figur. Außerdem funktioniert clock_gettime () ziemlich vorhersehbar. Auf diese Weise können Sie den Overhead seines Anrufs berücksichtigen und tatsächlich Messungen mit einer Genauigkeit in der Größenordnung von zehn Nanosekunden durchführen. Lassen Sie uns jetzt jedoch darauf achten. Um das Zeitintervall zu messen, müssen Sie zwei solche Anrufe tätigen: am Anfang und am Ende. Das heißt, 240 ns ausgeben. Wenn dicht beabstandete Zeitintervalle in der Größenordnung von 1-10 μs gemessen werden, verzerrt in einigen solchen Fällen der Messprozess selbst den beobachteten Prozess erheblich.

Ich habe diesen Abschnitt damit begonnen, wie sich der E / A-Stapel in den letzten Jahren beschleunigt hat. Dies ist neu, aber bei weitem nicht der einzige Grund, die Zeit schnell und genau messen zu wollen. Ein solches Bedürfnis war schon immer. Zum Beispiel gab es immer einen Code, den ich um mindestens 1 Taktzyklus des Mikroprozessors beschleunigen wollte. Oder ein anderes Beispiel aus dem Originalartikel über die sensationelle Spectre-Sicherheitslücke:



Hier messen die Zeilen 72 bis 74 die Ausführungszeit einer einzelnen Speicherzugriffsoperation. Specter interessiert sich zwar nicht für Nanosekunden. Die Zeit kann in "Papageien" gemessen werden. Wir werden zu den Papageien und Sekunden zurückkehren.

Zeitstempelzähler

Der Schlüssel zur schnellen und genauen Zeitmessung ist ein spezieller Mikroprozessorzähler. Der Wert dieses Zählers wird normalerweise in einem separaten Register gespeichert und ist normalerweise - aber nicht immer - vom Benutzerbereich aus zugänglich. Auf verschiedenen Architekturen wird der Zähler unterschiedlich genannt:

1. x86 Zeitstempelzähler
2. Zeitbasisregister auf PowerPC
3. Intervallzeitzähler auf Itanium
4. usw.

Im Folgenden werde ich immer den Namen "Zeitstempelzähler" oder TSC verwenden, obwohl ich in Wirklichkeit jeden solchen Zähler unabhängig von der Architektur im Auge behalten werde.

Das Lesen des TSC-Werts ist normalerweise - aber auch nicht immer - mit einer einzigen Anweisung möglich. Hier ist ein Beispiel für x86. Genau genommen ist dies keine reine Assembler-Anweisung, sondern der GNU-Inline-Assembler:

uint32_t eax, edx; __asm__ __volatile__( "rdtsc" : "=a" (eax), "=d" (edx)); 

Der Befehl rdtsc platziert zwei 32-Bit-Hälften des TSC-Registers in den Registern eax und edx. Von diesen können Sie einen einzelnen 64-Bit-Wert "kleben".

Ich stelle noch einmal fest: Diese (und ähnliche) Anweisungen können in den meisten Fällen direkt aus dem Benutzerbereich aufgerufen werden. Keine Systemaufrufe. Minimaler Overhead.

Was muss jetzt getan werden, um die Zeit zu messen?

1. Führen Sie eine solche Anweisung zu Beginn des für uns interessanten Zeitintervalls aus. Zählerwert merken
2. Führen Sie am Ende eine solche Anweisung aus. Wir glauben, dass der Wert des Zählers von der ersten Anweisung zur zweiten steigen wird. Warum wird es sonst benötigt? Denken Sie an den zweiten Wert
3. Wir betrachten den Unterschied zwischen den beiden gespeicherten Werten. Dies ist unsere Zeit

Es sieht einfach aus, aber ...

Die nach dem beschriebenen Verfahren gemessene Zeit wird in „Papageien“ ausgedrückt. Es ist nicht in Sekunden. Aber manchmal sind Papageien genau das, was Sie brauchen. Es gibt Situationen, in denen nicht die absoluten Werte der Zeitintervalle wichtig sind, sondern die Beziehung zwischen den verschiedenen Intervallen. Das obige Spectre-Beispiel zeigt genau diese Situation. Die Dauer jedes einzelnen Speicherzugriffs spielt keine Rolle. Es ist nur wichtig, dass Aufrufe an einige Adressen viel schneller ausgeführt werden als an andere (abhängig davon, ob die Daten im Cache oder im Hauptspeicher gespeichert sind).

Aber was ist, wenn keine Papageien benötigt werden, sondern Sekunden / Mikrosekunden / Nanosekunden usw.? Hier lassen sich zwei grundsätzlich unterschiedliche Fälle unterscheiden:

1. Aber dann werden Nanosekunden benötigt. Das heißt, es ist zulässig, zuerst alle erforderlichen Messungen in Papageien durchzuführen und sie zur weiteren Verarbeitung irgendwo zu speichern (z. B. im Speicher). Und erst nach Abschluss der Messungen werden die gesammelten Papageien langsam in Sekunden umgewandelt
2. Nanosekunden werden "on the fly" benötigt. Zum Beispiel hat Ihr Messprozess eine Art „Verbraucher“, den Sie nicht kontrollieren und der Zeit im „menschlichen“ Format erwartet

Der erste Fall ist einfach, der zweite - erfordert Einfallsreichtum. Die Konvertierung sollte so effektiv wie möglich sein. Wenn es viele Ressourcen verbraucht, kann es den Messprozess stark verzerren. Wir werden im Folgenden über eine effektive Konvertierung sprechen. Hier haben wir dieses Problem bisher identifiziert und gehen zu einem anderen über.

Zeitstempelzähler sind nicht so einfach, wie wir es gerne hätten. Auf einigen Architekturen:

1. Es kann nicht garantiert werden, dass die TSC mit hoher Frequenz aktualisiert wird. Wenn die TSC beispielsweise einmal pro Mikrosekunde aktualisiert wird, ist es nicht möglich, Nanosekunden damit zu reparieren.
2. Die Häufigkeit, mit der die TSC aktualisiert wird, kann im Laufe der Zeit variieren
3. Auf verschiedenen im System vorhandenen CPUs können TSCs mit unterschiedlichen Frequenzen aktualisiert werden
4. Es kann zu einer Verschiebung zwischen TSCs kommen, die auf verschiedenen CPUs ticken

Hier ist ein Beispiel, das das letzte Problem veranschaulicht. Angenommen, wir haben ein System mit zwei CPUs: CPU1 und CPU2. Angenommen, die TSC auf der ersten CPU liegt um die Anzahl der Ticks hinter der zweiten, was 5 Sekunden entspricht. Angenommen, im System wird ein Stream gestartet, der die Zeit der Berechnungen misst, was er selbst tut. Dazu liest der Stream zuerst den TSC-Wert, führt dann die Berechnung durch und liest dann den zweiten TSC-Wert. Wenn ein Thread während seiner gesamten Lebensdauer nur auf einer CPU verbleibt - auf einer beliebigen -, gibt es keine Probleme. Was aber, wenn der Thread auf CPU1 gestartet, dort den ersten TSC-Wert gemessen und dann in der Mitte der Berechnungen vom Betriebssystem auf CPU2 verschoben wurde, wo er den zweiten TSC-Wert las? In diesem Fall erscheinen die Berechnungen 5 Sekunden länger als sie tatsächlich sind.

Aufgrund der oben aufgeführten Probleme kann TSC auf einigen Systemen nicht als zuverlässige Zeitquelle dienen. Auf anderen Systemen, die unter denselben Problemen "leiden", kann TSC jedoch weiterhin verwendet werden. Möglich wird dies durch besondere architektonische Merkmale:

1. Das Gerät kann jedes Mal einen speziellen Interrupt erzeugen, wenn sich die Häufigkeit ändert, mit der die TSC aktualisiert wird. Gleichzeitig bietet das Gerät die Möglichkeit, die aktuelle Frequenz herauszufinden. Alternativ kann die TSC-Aktualisierungsrate unter die Kontrolle des Betriebssystems gestellt werden (siehe „Power ISA Version 2.06 Revision B, Buch II, Kapitel 5“).
2. Zusammen mit dem TSC-Wert kann das Gerät auch die ID der CPU bereitstellen, auf der dieser Wert gelesen wird (siehe Intel RDTSCP-Anweisung, „Entwicklerhandbuch für Intel 64- und IA-32-Architekturen-Software“, Band 2).
3. Auf einigen Systemen können Sie den TSC-Wert für jede CPU programmgesteuert anpassen (siehe Intel WRMSR-Anweisung und Register IA32_TIME_STAMP_COUNTER, „Entwicklerhandbuch für Intel 64- und IA-32-Architekturen-Software“, Band 3).

Im Allgemeinen ist das Thema, wie Zeitmesser auf verschiedenen Architekturen implementiert werden, faszinierend und umfangreich. Wenn Sie Zeit und Interesse haben, empfehle ich Tauchen. Unter anderem erfahren Sie beispielsweise, dass Sie mit einigen Systemen programmgesteuert bestimmen können, ob TSC als zuverlässige Zeitquelle dienen kann.

Es gibt also viele architektonische Implementierungen von TSC, von denen jede ihre eigenen Eigenschaften hat. Es ist jedoch interessant, dass sich in diesem ganzen Zoo ein allgemeiner Trend etabliert hat. Moderne Hardware und Betriebssysteme bemühen sich darum, dass :

1. TSC tickt auf jeder CPU im System mit der gleichen Frequenz
2. Diese Frequenz ändert sich zeitlich nicht
3. Es gibt keine Verschiebung zwischen TSCs, die auf verschiedenen CPUs ticken

Beim Entwerfen meiner Bibliothek habe ich mich entschieden, von dieser Prämisse auszugehen und nicht von der Vinaigrette der Hardware-Implementierungen.

Die Bibliothek

Ich habe nicht angefangen, auf Hardware-Chips einer Reihe verschiedener Architekturen zu legen. Stattdessen entschied ich mich für eine trendorientierte Bibliothek. Sie hat einen rein empirischen Fokus:

1. Damit können Sie die Zuverlässigkeit von TSC als Zeitquelle experimentell überprüfen
2. Außerdem können Sie die Parameter experimentell berechnen, die für die schnelle Umwandlung von Zecken in Nanosekunden erforderlich sind
3. Natürlich bietet die Bibliothek praktische Schnittstellen zum Lesen von TSC und zum Konvertieren von Zecken in Nanosekunden "on the fly".

Den Bibliothekscode finden Sie hier. Es wird nur unter Linux kompiliert und ausgeführt.

Im Code sehen Sie die Details der Implementierung aller Methoden, die später erläutert werden.

TSC-Zuverlässigkeitsbewertung

Die Bibliothek bietet eine Schnittstelle, die zwei Bewertungen zurückgibt:

1. maximale Verschiebung zwischen Zählern, die zu verschiedenen CPUs gehören. Es werden nur CPUs berücksichtigt, die dem Prozess zur Verfügung stehen. Wenn für einen Prozess beispielsweise drei CPUs verfügbar sind und die TSC auf diesen CPUs gleichzeitig 50, 150, 20 beträgt, beträgt die maximale Verschiebung 150-20 = 130. Natürlich wird die Bibliothek nicht in der Lage sein, experimentell eine echte maximale Verschiebung zu erhalten, aber sie wird eine Schätzung geben, in die diese Verschiebung passt. Was tun als nächstes mit der Bewertung? Wie benutzt man? Dies löst bereits den Client-Code. Die Bedeutung ist jedoch ungefähr die folgende. Die maximale Verschiebung ist der maximale Wert, um den die Dimension, die der Clientcode erstellt, verzerrt werden kann. Angenommen, in unserem Beispiel mit drei CPUs begann der Client-Code, die Zeit auf CPU3 (wo TSC 20 war) zu messen, und endete auf CPU2 (wo TSC 150 war). Es stellt sich heraus, dass sich zusätzliche 130 Ticks in das gemessene Intervall einschleichen. Und nie wieder. Der Unterschied zwischen CPU1 und CPU2 würde nur 100 Ticks betragen. Mit einer Schätzung von 130 Ticks (in der Tat wird es viel konservativer sein) kann der Kunde entscheiden, ob ein solcher Verzerrungswert zu ihm passt oder nicht
2. Erhöhen sich die TSC-Werte, die nacheinander auf derselben oder verschiedenen CPUs gemessen werden? Hier ist die Idee. Nehmen wir an, wir haben mehrere CPUs. Angenommen, ihre Uhr ist synchronisiert und tickt mit derselben Frequenz. Wenn Sie dann zuerst die Zeit auf einer CPU messen und dann erneut messen - bereits auf einer der verfügbaren CPUs -, sollte die zweite Ziffer größer sein als die erste.
   
   Ich werde diese Schätzung unterhalb der TSC-Monotonie-Schätzung nennen
   

Nun wollen wir sehen, wie wir die erste Schätzung erhalten können:

1. Einer der für den Prozess verfügbaren Prozessoren wird als "grundlegend" deklariert.
2. dann werden alle anderen CPUs sortiert und für jede von ihnen wird die Verschiebung berechnet: TSC___CPU – TSC___CPU . Dies geschieht wie folgt:
   
   • a) Drei Messwerte werden nacheinander (nacheinander!) TSC_base_1, TSC_current, TSC_base_2 : TSC_base_1, TSC_current, TSC_base_2 . Hier zeigt der Strom an, dass der Wert auf der aktuellen CPU und die Basis auf der Basis gemessen wurde
   • b) Die Verschiebung TSC___CPU – TSC___CPU muss im Intervall [TSC_current – TSC_base_2, TSC_current – TSC_base_1] . Dies setzt voraus, dass TSCs auf beiden CPUs mit der gleichen Frequenz ticken.
   • c) Die Schritte a) -b) werden mehrmals wiederholt. Der Schnittpunkt aller in Schritt b) erhaltenen Intervalle wird berechnet. Das resultierende Intervall wird als Schätzung der Verschiebung TSC___CPU – TSC___CPU
   
   
3. Nachdem für jede CPU eine Verschiebungsschätzung relativ zur Basis erhalten wurde, ist es einfach, eine Schätzung der maximalen Verschiebung zwischen allen verfügbaren CPUs zu erhalten:
   
   • a) Das Mindestintervall wird berechnet, das alle in Schritt 2 erhaltenen resultierenden Intervalle enthält
   • b) Die Breite dieses Intervalls wird als Schätzung der maximalen Verschiebung zwischen TSCs verwendet, die auf verschiedenen CPUs ticken
   
   

Um die Monotonie in der Bibliothek zu bewerten, wird der folgende Algorithmus implementiert:

1. Angenommen, ein Prozess verfügt über N CPU
2. TSC auf CPU1 messen
3. TSC auf CPU2 messen
4. ...
5. TSC auf CPUN messen
6. TSC erneut an CPU1 messen
7. Wir überprüfen, ob die gemessenen Werte vom ersten bis zum letzten monoton ansteigen

Hierbei ist es wichtig, dass der erste und der letzte Wert auf derselben CPU gemessen werden. Und hier ist warum. Nehmen wir an, wir haben 3 CPUs. Angenommen, die TSC auf CPU2 ist gegenüber der TSC auf CPU1 um +100 Ticks verschoben. Angenommen, die TSC auf CPU3 ist gegenüber der TSC auf CPU2 um +100 Ticks verschoben. Betrachten Sie die folgende Ereigniskette:

• Lesen Sie die TSC auf CPU1. Es sei ein Wert von 10 erhalten
• 2 Zecken bestanden
• Lesen Sie TSC auf CPU2. Muss 112 sein
• 2 Zecken bestanden
• Lesen Sie TSC auf CPU3. Muss 214 sein

Bisher sieht die Uhr synchronisiert aus. Aber lassen Sie uns noch einmal TSC auf CPU1 messen:

• 2 Zecken bestanden
• Lesen Sie die TSC auf CPU1. Muss 16 sein

Ups! Monotonie ist gebrochen. Es stellt sich heraus, dass Sie durch Messen des ersten und letzten Werts auf derselben CPU mehr oder weniger große Verschiebungen zwischen den Uhren erkennen können. Die nächste Frage natürlich: "Wie groß sind die Schichten?" Das Ausmaß der Verschiebung, das erkannt werden kann, hängt von der Zeit ab, die zwischen aufeinanderfolgenden TSC-Messungen vergeht. Im angegebenen Beispiel sind dies nur 2 Ticks. Verschiebungen zwischen Stunden, die 2 Ticks überschreiten, werden erkannt. Im Allgemeinen werden Verschiebungen, die kürzer als die zwischen aufeinanderfolgenden Messungen verstrichene Zeit sind, nicht erkannt. Je dichter die Messungen in der Zeit sind, desto besser. Die Genauigkeit beider Schätzungen hängt davon ab. Je dichter die Messungen sind:

• Je niedriger die maximale Schichtschätzung
• desto mehr Vertrauen in die Beurteilung der Monotonie

Im nächsten Abschnitt werden wir darüber sprechen, wie man enge Messungen vornimmt. Ich möchte hier hinzufügen, dass die Bibliothek bei der Berechnung der TSC-Zuverlässigkeitsschätzungen viel mehr einfache "Läuse" -Prüfungen durchführt, zum Beispiel:

• eingeschränkte Überprüfung, ob TSCs auf verschiedenen CPUs mit derselben Geschwindigkeit ticken
• Überprüfen Sie, ob sich die Zähler im Laufe der Zeit wirklich ändern und nicht nur den gleichen Wert anzeigen

Zwei Methoden zum Sammeln von Zählerwerten

In der Bibliothek habe ich zwei Methoden zum Sammeln von TSC-Werten implementiert:

1. Zwischen CPU wechseln . Bei dieser Methode werden alle Daten, die zur Bewertung der Zuverlässigkeit der TSC erforderlich sind, von einem einzelnen Thread erfasst, der von einer CPU zur anderen springt. Beide im vorherigen Abschnitt beschriebenen Algorithmen sind für diese Methode geeignet und für die andere nicht.
   "Umschalten zwischen der CPU" hat keinen praktischen Nutzen. Die Methode wurde nur implementiert, um "herumzuspielen". Das Problem bei der Methode ist, dass die Zeit, die erforderlich ist, um einen Stream von einer CPU auf eine andere zu ziehen, sehr groß ist. Dementsprechend vergeht zwischen aufeinanderfolgenden TSC-Messungen viel Zeit, und die Genauigkeit der Schätzungen ist sehr gering. Beispielsweise wird eine typische Schätzung für die maximale Verschiebung zwischen TSC im Bereich von 23.000 Zecken erhalten.
   
   Das Verfahren hat jedoch einige Vorteile:
   
   • es ist absolut deterministisch. Wenn Sie TSC nacheinander an CPU1, CPU2, CPU3 messen müssen, nehmen wir es einfach und tun es: Wechseln Sie zu CPU1, lesen Sie TSC, wechseln Sie zu CPU2, lesen Sie TSC und wechseln Sie schließlich zu CPU3, lesen Sie TSC
   • Wenn die Anzahl der CPUs im System sehr schnell zunimmt, sollte die Umschaltzeit zwischen ihnen vermutlich viel langsamer ansteigen. Daher kann theoretisch anscheinend ein System existieren - ein sehr großes System! - in denen die Anwendung der Methode gerechtfertigt ist. Dies ist jedoch unwahrscheinlich
   
   
2. Messungen mit CAS bestellt . Bei dieser Methode werden Daten parallel von mehreren Threads erfasst. Jede verfügbare CPU startet einen Thread. Messungen, die von verschiedenen Threads durchgeführt werden, werden in einer einzigen Sequenz unter Verwendung der Operation "Vergleichen und Tauschen" angeordnet. Unten finden Sie einen Code, der zeigt, wie dies gemacht wird.
   Die Idee der Methode stammt von fio , einem beliebten Tool zur Erzeugung von E / A-Lasten.
   
   Die Zuverlässigkeitsschätzungen, die mit der Leistung dieser Methode erhalten wurden, sehen bereits ziemlich gut aus. Beispielsweise wird bereits eine Schätzung der maximalen Verschiebung auf der Ebene von mehreren hundert Ticks erhalten. Eine Überprüfung der Monotonie ermöglicht es Ihnen, die Uhr innerhalb von Hunderten von Ticks nicht synchron zu erfassen.
   
   Die im vorherigen Abschnitt angegebenen Algorithmen sind jedoch für diese Methode nicht geeignet. Für sie ist es wichtig, dass die TSC-Werte in einer vorgegebenen Reihenfolge gemessen werden. Die Methode der von CAS bestellten Messungen erlaubt dies nicht. Stattdessen wird zuerst eine lange Folge von Zufallsmessungen gesammelt, und dann versuchen (bereits unterschiedliche) Algorithmen, Werte zu finden, die auf „geeigneten“ CPUs in dieser Folge gelesen werden.
   
   Ich werde diese Algorithmen hier nicht angeben, um Ihre Aufmerksamkeit nicht zu missbrauchen. Sie können sie im Code sehen. Es gibt viele Kommentare. Theoretisch sind diese Algorithmen gleich. Ein grundlegend neuer Punkt ist die Überprüfung, wie zufällig typisierte TSC-Sequenzen statistisch „qualitativ“ sind. Es ist auch möglich, ein akzeptables Mindestmaß an statistischer Signifikanz für TSC-Zuverlässigkeitsschätzungen festzulegen.
   
   Theoretisch kann bei SEHR großen Systemen die Methode „CAS-geordnet“ zu schlechten Ergebnissen führen. Das Verfahren erfordert, dass Prozessoren um den Zugriff auf einen gemeinsamen Speicherort konkurrieren. Wenn es viele Prozessoren gibt, kann sich der Wettbewerb als sehr intensiv herausstellen. Infolgedessen wird es schwierig sein, eine Messsequenz mit guten statistischen Eigenschaften zu erstellen. Im Moment scheint diese Situation jedoch unwahrscheinlich.
   

Ich habe Code versprochen. So sieht es aus, wenn Sie mit CAS Messungen in einer einzigen Kette erstellen.

  for ( uint64_t i = 0; i < arg->probes_count; i++ ) { uint64_t seq_num = 0; uint64_t tsc_val = 0; do { __atomic_load( seq_counter, &seq_num, __ATOMIC_ACQUIRE); __sync_synchronize(); tsc_val = WTMLIB_GET_TSC(); } while ( !__atomic_compare_exchange_n( seq_counter, &seq_num, seq_num + 1, false, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)); arg->tsc_probes[i].seq_num = seq_num; arg->tsc_probes[i].tsc_val = tsc_val; } 

Dieser Code wird auf jeder verfügbaren CPU ausgeführt. Alle Threads haben Zugriff auf die gemeinsam genutzte Variable seq_counter . Vor dem Lesen der TSC liest der Stream den Wert dieser Variablen und speichert ihn in der Variablen seq_num . Dann liest TSC. Dann wird versucht, seq_counter atomar um eins zu erhöhen, jedoch nur, wenn sich der Wert der Variablen seit dem Lesen nicht geändert hat. Wenn die Operation erfolgreich ist, bedeutet dies, dass es dem Thread gelungen ist, die in seq_num hinter dem gemessenen TSC-Wert gespeicherte seq_num . Die nächste Seriennummer, die (möglicherweise bereits in einem anderen Thread) eingesetzt werden kann, ist eine weitere. Diese Nummer wird der Variablen seq_counter entnommen, und jeder erfolgreiche Aufruf von __atomic_compare_exchange_n() erhöht diese Variable um eins.


Ein weiterer erwähnenswerter Punkt ist die Sorgfalt, dass alle an Messungen beteiligten Flüsse mehr oder weniger gleichzeitig beginnen. Wir sind daran interessiert, dass die auf verschiedenen CPUs gelesenen TSC-Werte so gemischt wie möglich sind. Wir sind nicht zufrieden mit der Situation, in der beispielsweise ein Thread zuerst startet, seine Arbeit beendet und erst dann alle anderen beginnen. Die resultierende TSC-Sequenz hat nutzlose Eigenschaften. Daraus können keine Schätzungen gezogen werden. Der gleichzeitige Start aller Threads ist wichtig - und dafür wurden Maßnahmen in der Bibliothek ergriffen.

Konvertieren Sie Zecken im laufenden Betrieb in Nanosekunden

Nach Überprüfung der Zuverlässigkeit von TSC besteht der zweite Hauptzweck der Bibliothek darin, Zecken im laufenden Betrieb in Nanosekunden umzuwandeln. Die Idee dieser Umstellung habe ich dem bereits erwähnten Fio entlehnt. Ich musste jedoch einige signifikante Verbesserungen vornehmen, da das Konvertierungsverfahren, wie meine Analyse gezeigt hat, in fio selbst nicht gut genug funktioniert. Dort erhalten Sie eine geringe Genauigkeit.

Ich beginne mit einem Beispiel.

Idealerweise möchte ich Zecken wie folgt in Nanosekunden umwandeln:
ns_time = tsc_ticks / tsc_per_ns
Wir möchten, dass der Zeitaufwand für die Konvertierung minimal ist. Daher möchten wir ausschließlich ganzzahlige Arithmetik verwenden. Mal sehen, wie uns das bedrohen kann.

Wenn tsc_per_ns = 3 , tsc_per_ns = 3 eine einfache Ganzzahldivision unter dem Gesichtspunkt der Genauigkeit ns_time = tsc_ticks / 3 : ns_time = tsc_ticks / 3 .

Aber was ist, wenn tsc_per_ns = 3.333 ?Wenn diese Zahl auf 3 gerundet wird, ist die Konvertierungsgenauigkeit sehr gering. Zur Lösung dieses Problems wie folgt:
ns_time = (tsc_ticks * factor) / (3.333 * factor).

Wenn der Faktor factorgroß genug ist, ist die Genauigkeit gut. Aber etwas wird schlecht bleiben. Konvertierungsaufwand. Die Ganzzahldivision ist eine sehr teure Operation. Auf x86 sind beispielsweise mehr als 10 Taktzyklen erforderlich. Außerdem werden Operationen zur Ganzzahldivision nicht immer per Pipeline ausgeführt.

Wir schreiben unsere Formel in der entsprechenden Form
ns_time = (tsc_ticks * factor / 3.333) / factor.

Die erste Division ist kein Problem. Wir können (factor / 3.333)im Voraus vorberechnen . Aber die zweite Liga ist immer noch Schmerz. Um sie loszuwerden, wählen wirfactorgleich der Potenz von zwei. Danach kann die zweite Abteilung durch eine Bitverschiebung ersetzt werden - eine einfache und schnelle Operation.

Wie groß kannst du wählen factor? Leider kann factores nicht beliebig groß sein. Es ist durch die Bedingung begrenzt, dass die Multiplikation im Zähler nicht zu einem Überlauf des 64-Bit-Typs führen darf. Ja, wir möchten nur "native" Typen verwenden. Auch hier, um den Conversion-Overhead auf ein Minimum zu beschränken.

Nun wollen wir sehen, wie groß es factorin unserem speziellen Beispiel sein kann. Angenommen, wir möchten mit Zeitintervallen von bis zu einem Jahr arbeiten. Im Laufe des Jahres tiknet TSC mal folgenden: 3.333 * 1000000000 * 60 * 60 * 24 * 365 = 105109488000000000. Unterteile ein Maximalwert von 64-Bit - Typennummer ist: 18446744073709551615 / 105109488000000000 ~ 175.5. Also der Ausdruck(factor / 3.333)sollte nicht größer als dieser Wert sein. Dann haben wir factor <= 175.5 * 3.333 ~ 584.9. Die größte Zweierpotenz, die diese Zahl nicht überschreitet, ist 512. Daher hat unsere Umrechnungsformel die Form:

ns_time = (tsc_ticks * 512 / 3.333) / 512

Oder:

ns_time = tsc_ticks * 153 / 512

Fein. Lassen Sie uns nun mit Genauigkeit sehen, was diese Formel hat. Ein Jahr enthält 1000000000 * 60 * 60 * 24 * 365 = 31536000000000000Nanosekunden. Unsere Formel ergibt: 105109488000000000 * 153 / 512 = 31409671218750000. Die Differenz zum Barwert beträgt 126328781250000 Nanosekunden oder 126328781250000 / 1000000000 / 60 / 60 ~ 35Stunden.

Das ist ein großer Fehler. Wir wollen eine bessere Genauigkeit. Was ist, wenn wir Zeitintervalle von nicht mehr als einer Stunde messen? Ich werde die Berechnungen weglassen. Sie sind völlig identisch mit denen, die gerade gemacht wurden. Die endgültige Formel lautet:

ns_time = tsc_ticks * 1258417 / 4194304(1)

Der Konvertierungsfehler beträgt nur 119.305 Nanosekunden pro 1 Stunde (was weniger als 0,2 Millisekunden entspricht). Sehr sehr gut. Wenn der maximale konvertierbare Wert noch weniger als eine Stunde beträgt, ist die Genauigkeit sogar noch besser. Aber wie nutzen wir das? Zeitmessungen nicht auf eine Stunde beschränken?

Achten Sie auf den folgenden Punkt:

tsc_ticks = (tsc_ticks_per_1_hour * number_of_hours) + tsc_ticks_remainder

Wenn wir Vorkalkulation tsc_ticks_per_1_hour, können wir extrahieren number_of_hoursaus tsc_ticks. Als nächstes wissen wir, wie viele Nanosekunden in einer Stunde enthalten sind. Daher wird es für uns nicht schwierig sein, den Teil tsc_ticks, der einer ganzen Anzahl von Stunden entspricht, in Nanosekunden zu übersetzen . Um die Konvertierung abzuschließen, müssen wir in Nanosekunden übersetzentsc_ticks_remainder. Wir wissen jedoch, dass diese Anzahl von Zecken in weniger als einer Stunde auftrat. Um es in Nanosekunden umzuwandeln, können wir die Formel (1) verwenden.

Fertig. Ein solcher Umwandlungsmechanismus passt zu uns. Lassen Sie es uns jetzt zusammenfassen und optimieren.

Zunächst möchten wir eine flexible Kontrolle über Konvertierungsfehler haben. Wir möchten die Konvertierungsparameter nicht an ein Zeitintervall von 1 Stunde binden. Es sei ein beliebiges Zeitintervall: Denken Sie noch

tsc_ticks = modulus * number_of_moduli_periods + tsc_ticks_remainder

einmal daran, wie der Rest in Nanosekunden konvertiert wird:

ns_per_remainder = (tsc_ticks_remainder * factor / tsc_per_nsec) / factor

Wir berechnen die Konvertierungsparameter (das wissen wir tsc_ticks_remainder < modulus):

modulus * (factor / tsc_per_nsec) <= UINT64_MAX
factor <= (UINT64_MAX / modulus) * tsc_per_nsec
2 ^ shift <= (UINT64_MAX / modulus) * tsc_per_nsec


Aus Gründen der Langeweile ist anzumerken, dass die letzte Ungleichung im Rahmen der Ganzzahlarithmetik nicht der ersten entspricht. Aber ich werde nicht lange darauf eingehen. Ich kann nur sagen, dass die letzte Ungleichung schwerwiegender ist als die erste und daher sicher zu verwenden ist.

Nachdem wir aus der letzten Ungleichung erhalten haben shift, berechnen wir: Und dann werden diese Parameter verwendet, um den Rest in Nanosekunden umzuwandeln: Also haben wir die Restumrechnung herausgefunden. Das nächste zu lösende Problem - ist die Entfernung und aus . Wie immer wollen wir es schnell machen. Wie immer wollen wir keine Division verwenden. Deshalb wählen wir einfach gleich der Zweierpotenz: Dann:

factor = 2 ^ shift
mult = factor / tsc_per_nsec




ns_per_remainder = (tsc_ticks_remainder * mult) >> shift


tsc_ticks_remaindernumber_of_moduli_periodstsc_ticksmodulus

modulus = 2 ^ remainder_bit_length



number_of_moduli_periods = tsc_ticks >> remainder_bit_length
tsc_ticks_remainder = tsc_ticks & (modulus - 1)

Großartig.Wir wissen jetzt, wie man aus tsc_ticks number_of_moduli_periodsund extrahiert tsc_ticks_remainder. Und wir wissen, wie man tsc_ticks_remainderin Nanosekunden umwandelt . Es bleibt zu verstehen, wie dieser Teil der Zecken, der ein Vielfaches ist, in Nanosekunden umgewandelt wird modulus. Aber alles ist einfach:

ns_per_moduli = ns_per_modulus * number_of_moduli_periods

ns_per_modulusSie können im Voraus rechnen. Darüber hinaus nach der gleichen Formel, nach der wir den Rest umrechnen. Diese Formel kann für Zeiträume verwendet werden, die nicht länger als sind modulus. Er selbst modulusnatürlich nicht länger als modulus.

ns_per_modulus = (modulus * mult) >> shift

Das ist alles! Wir konnten alle Parameter berechnen, die erforderlich sind, um Zecken im laufenden Betrieb in Nanosekunden umzuwandeln. Fassen Sie nun das Konvertierungsverfahren kurz zusammen:

1. wir haben tsc_ticks
2. number_of_moduli_periods = tsc_ticks >> remainder_bit_length
3. tsc_ticks_remainder = tsc_ticks & (modulus - 1)
4. ns = ns_per_modulus * number_of_moduli_periods + (tsc_ticks_remainder * mult) >> shift

Bei diesem Verfahren werden Parameter remainder_bit_length, modulus, ns_per_modulus, multund shiftVorkalkulation voraus.

Wenn Sie diesen Beitrag noch lesen, sind Sie großartig oder großartig. Es ist sogar möglich, dass Sie ein Performance-Analyst oder Entwickler von Hochleistungssoftware sind.

Also.Es stellt sich heraus, dass wir noch nicht fertig sind :)

Erinnerst du dich, wie wir den Parameter berechnet haben mult? Es war so:

mult = factor / tsc_per_nsec

Frage: Woher kommt es tsc_per_nsec?
Die Anzahl der Zecken in einer Nanosekunde ist ein sehr kleiner Wert. Tatsächlich tsc_per_nsecwird stattdessen meine Bibliothek verwendet (tsc_per_sec / 1000000000). Das heißt:

mult = factor * 1000000000 / tsc_per_sec

Und es gibt zwei interessante Fragen:

1. Warum tsc_per_secund nicht tsc_per_mseczum Beispiel?
2. Woher bekommen diese tsc_per_sec?

Beginnen wir mit dem ersten. Fio verwendet jetzt tatsächlich die Anzahl der Ticks pro Millisekunde. Und damit gibt es Probleme. Auf der Maschine, die Parameter , von denen ich oben genannt tsc_per_msec = 2599998. Während tsc_per_sec = 2599998971. Wenn wir diese Zahlen auf eine Skala bringen, liegt ihr Verhältnis sehr nahe bei Eins: 0,999999626. Wenn wir jedoch die erste und nicht die zweite verwenden, haben wir für jede Sekunde einen Fehler von 374 Nanosekunden. Deshalb - tsc_per_sec.

Weiter ... Wie zählt man tsc_per_sec?

Dies erfolgt auf der Grundlage einer direkten Messung: „einige Zeit“ ist ein konfigurierbarer Parameter. Sie kann größer, kleiner oder gleich einer Sekunde sein. Nehmen wir an, es ist eine halbe Sekunde. Nehmen wir weiter an, dass der tatsächliche Unterschied zwischen und 0,6 Sekunden betrug. Dann .

start_sytem_time = clock_gettime()
start_tsc = WTMLIB_GET_TSC()
-
end_system_time = clock_gettime()
end_tsc = WTMLIB_GET_TSC()


end_system_timestart_system_timetsc_per_sec = (end_tsc – start_tsc) / 0,6

Die Bibliothek berücksichtigt auf diese Weise mehrere Werte tsc_per_sec. Mit Standardmethoden werden sie dann von statistischem Rauschen „gereinigt“ und erhalten einen einzigen tsc_per_secvertrauenswürdigen Wert .

Im obigen Zeitmessdiagramm ist die Reihenfolge der Anrufe clock_gettime()und wichtig WTMLIB_GET_TSC(). Es ist wichtig, WTMLIB_GET_TSC()dass zwischen zwei Anrufen dieselbe Zeit vergeht wie zwischen zwei Anrufen clock_gettime(). Dann ist es möglich, die Systemzeit leicht mit TSC-Ticks zu korrelieren. Und dann kann die Streuung der Werte tsc_per_secwirklich als zufällig angesehen werden. Bei diesem Messschema tsc_per_secweichen die Werte mit der gleichen Wahrscheinlichkeit in beide Richtungen vom Durchschnittswert ab. Und es wird möglich sein, Standardfiltermethoden auf sie anzuwenden.

Fazit

Vielleicht ist das alles.

Das Thema der effektiven Zeitmessung ist jedoch nicht darauf beschränkt. Es gibt viele Nuancen. Für Interessierte schlage ich vor, unabhängig an folgenden Themen zu arbeiten:

• Speichern von Konvertierungsparametern im Cache oder - noch besser - in Registern
• bis zu welchen Grenzen kann reduziert werden modulus(wodurch die Genauigkeit der Konvertierung erhöht wird)?
• Wie wir gesehen haben, wird die Konvertierungsgenauigkeit nicht nur beeinflusst modulus, sondern auch durch die Größe des Zeitintervalls, das mit Ticks ( tsc_per_msecoder tsc_per_sec) korreliert . Wie kann der Einfluss beider Faktoren ausgeglichen werden?
• TSC in der virtuellen Maschine. Kann ich es benutzen?
• . , fio timespec. :
  
  tp->tv_sec = nsecs / 1000000000ULL;
  
  , TSC . , ,
  

Mit den in diesem Artikel beschriebenen Methoden können wir die Zeitskala einer Sekunde mit einer Genauigkeit in der Größenordnung von mehreren zehn Nanosekunden messen. Dies ist die Genauigkeit, die ich bei der Verwendung meiner Bibliothek tatsächlich beobachte.

Interessanterweise verliert das Fio, von dem ich einige Methoden ausgeliehen habe, auf einer zweiten Skala genau 700-900 Nanosekunden (und dafür gibt es drei Gründe). Außerdem verliert die Konvertierungsgeschwindigkeit aufgrund der Speicherung von Zeit in einem Standard-Linux-Format. Ich beeile mich jedoch, Fio-Fans zu beruhigen. Ich habe Entwicklern eine Beschreibung aller Konvertierungsprobleme gesendet , die ich entdeckt habe . Die Leute arbeiten bereits, sie werden es bald beheben.

Ich wünsche Ihnen viele angenehme Nanosekunden!