Mesure du temps avec une précision en nanosecondes

Il y a quelques mois, un moment historique est venu pour moi. Les outils standard du système d'exploitation pour mesurer le temps ont cessé de me suffire. Il a fallu du temps pour mesurer avec une précision en nanosecondes et avec des frais généraux en nanosecondes.

J'ai décidé d'écrire une bibliothèque qui résoudrait ce problème. À première vue, il semblait qu'il n'y avait rien de spécial à faire. Mais après un examen plus approfondi, comme toujours, il s'est avéré qu'il y avait de nombreux problèmes intéressants à régler. Dans cet article, je vais parler des problèmes et comment ils ont été résolus.

Étant donné que vous pouvez mesurer différents types de temps sur un ordinateur, je vais immédiatement préciser que nous parlerons ici de «temps par chronomètre». Ou l'heure de l'horloge murale. C’est le temps réel, le temps écoulé, etc. C'est-à-dire un temps "humain" simple, que nous détectons au début de la tâche et arrêtons à la fin.

Microseconde - presque pour toujours

Les développeurs de systèmes haute performance au cours des dernières années se sont habitués à l'échelle de temps en microsecondes. En microsecondes, vous pouvez lire les données d'un lecteur NVMe. En microsecondes, les données peuvent être envoyées sur le réseau. Pas pour tout le monde, bien sûr, mais pour le réseau InifiniBand - facilement.

En même temps, la microseconde avait également une structure. Une pile d'E / S complète se compose de plusieurs composants logiciels et matériels. Les retards introduits par certains d'entre eux se situent au niveau inférieur à la microseconde.

Pour mesurer des retards de cette ampleur, la précision en microsecondes n'est plus suffisante. Cependant, non seulement la précision est importante, mais aussi la surcharge de mesure du temps. L'appel système Linux clock_gettime () renvoie le temps avec une précision en nanosecondes. Sur une machine à portée de main (Intel® Xeon® CPU E5-2630 v2 @ 2,60 GHz), cet appel se termine en environ 120 ns. Très bonne silhouette. De plus, clock_gettime () fonctionne de façon assez prévisible. Cela vous permet de prendre en compte les frais généraux de son appel et de prendre des mesures avec une précision de l'ordre de dizaines de nanosecondes. Cependant, prêtons maintenant attention à cela. Pour mesurer l'intervalle de temps, vous devez effectuer deux appels de ce type: au début et à la fin. C'est-à-dire dépenser 240 ns. Si des intervalles de temps densément espacés de l'ordre de 1 à 10 μs sont mesurés, dans certains cas, le processus de mesure lui-même déformera considérablement le processus observé.

J'ai commencé cette section avec la façon dont la pile d'E / S s'est accélérée ces dernières années. C'est nouveau, mais loin d'être la seule raison de vouloir mesurer le temps rapidement et avec précision. Un tel besoin a toujours été. Par exemple, il y avait toujours un code que je voulais accélérer d'au moins 1 cycle d'horloge du microprocesseur. Ou un autre exemple, tiré de l'article original sur la vulnérabilité sensationnelle Spectre:



Ici, les lignes 72 à 74 mesurent le temps d'exécution d'une seule opération d'accès à la mémoire. Certes, Spectre ne s'intéresse pas aux nanosecondes. Le temps peut être mesuré en «perroquets». Nous reviendrons sur les perroquets et les secondes.

Compteur d'horodatage

La clé d'une mesure rapide et précise du temps est un compteur à microprocesseur spécial. La valeur de ce compteur est généralement stockée dans un registre séparé et est généralement - mais pas toujours - accessible depuis l'espace utilisateur. Sur différentes architectures, le compteur est appelé différemment:

1. compteur d'horodatage x86
2. registre de base de temps sur PowerPC
3. compteur de temps d'intervalle sur Itanium
4. etc.

Ci-dessous, j'utiliserai toujours le nom de "compteur d'horodatage" ou TSC, bien qu'en fait je garde à l'esprit un tel compteur, quelle que soit l'architecture.

La lecture de la valeur TSC habituellement - mais encore une fois pas toujours - est possible avec une seule instruction. Voici un exemple pour x86. À strictement parler, ce n'est pas une instruction d'assembleur pur, mais l'assembleur en ligne GNU:

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

L'instruction rdtsc place deux moitiés de 32 bits du registre TSC dans les registres eax et edx. Parmi ceux-ci, vous pouvez «coller» une seule valeur 64 bits.

Encore une fois, je note: ces instructions (et similaires) dans la plupart des cas peuvent être appelées directement depuis l'espace utilisateur. Aucun appel système. Frais généraux minimaux.

Que faut-il faire maintenant pour mesurer le temps?

1. Exécutez une telle instruction au début de l'intervalle de temps qui nous intéresse. N'oubliez pas la contre-valeur
2. Exécutez une telle instruction à la fin. Nous pensons que la valeur du compteur de la première instruction à la seconde augmentera. Sinon, pourquoi est-il nécessaire? Rappelez-vous la deuxième valeur
3. Nous considérons la différence entre les deux valeurs stockées. C'est notre temps

Cela semble simple, mais ...

Le temps mesuré par la procédure décrite est exprimé en «perroquets». Ce n'est pas en quelques secondes. Mais parfois, les perroquets sont exactement ce dont vous avez besoin. Il y a des situations où les valeurs absolues des intervalles de temps ne sont pas importantes, mais comment les différents intervalles sont liés les uns aux autres. L'exemple Spectre ci-dessus illustre exactement cette situation. La durée de chaque accès à la mémoire individuelle n'a pas d'importance. Il est seulement important que les appels vers certaines adresses soient exécutés beaucoup plus rapidement que vers d'autres (selon que les données sont stockées dans le cache ou dans la mémoire principale).

Mais que faire si ce n'est pas des perroquets, mais des secondes / microsecondes / nanosecondes, etc.? On peut distinguer ici deux cas fondamentalement différents:

1. Des nanosecondes sont nécessaires, mais alors. Autrement dit, il est permis de faire d'abord toutes les mesures nécessaires dans des perroquets et de les stocker quelque part pour un traitement ultérieur (par exemple, en mémoire). Et seulement une fois les mesures terminées, convertir lentement les perroquets collectés en secondes
2. Les nanosecondes sont nécessaires "à la volée". Par exemple, votre processus de mesure a une sorte de «consommateur» que vous ne contrôlez pas et qui attend du temps au format «humain»

Le premier cas est simple, le second - nécessite de l'ingéniosité. La conversion doit être aussi efficace que possible. S'il consomme beaucoup de ressources, il peut fausser considérablement le processus de mesure. Nous parlerons de la conversion efficace ci-dessous. Nous avons jusqu'ici identifié ce problème et passons à un autre.

Les compteurs d'horodatage ne sont pas aussi simples que nous le souhaiterions. Sur certaines architectures:

1. il n'est pas garanti que le TSC soit mis à jour à haute fréquence. Si le TSC est mis à jour, disons, une fois toutes les microsecondes, il ne sera pas possible de corriger les nanosecondes avec lui.
2. la fréquence de mise à jour du TSC peut varier dans le temps
3. sur différents CPU présents dans le système, les TSC peuvent être mis à jour à différentes fréquences
4. il peut y avoir un décalage entre les TSCs sur les différents processeurs

Voici un exemple illustrant le dernier problème. Supposons que nous ayons un système avec deux CPU: CPU1 et CPU2. Supposons que le TSC sur le premier CPU soit derrière le second du nombre de ticks, ce qui équivaut à 5 secondes. Supposons en outre qu'un flux soit lancé dans le système qui mesure le temps des calculs, ce qu'il fait lui-même. Pour ce faire, le flux lit d'abord la valeur TSC, puis fait le calcul, puis lit la deuxième valeur TSC. Si pendant toute sa vie un thread reste sur un seul CPU - sur n'importe quel - alors il n'y a pas de problèmes. Mais que se passe-t-il si le thread a démarré sur CPU1, a mesuré la première valeur TSC là-bas, puis au milieu des calculs a été déplacé par le système d'exploitation vers CPU2, où il a lu la deuxième valeur TSC? Dans ce cas, les calculs sembleront 5 secondes plus longs qu'ils ne le sont réellement.

En raison des problèmes répertoriés ci-dessus, TSC ne peut pas servir de source de temps fiable sur certains systèmes. Cependant, sur d'autres systèmes "souffrant" des mêmes problèmes, le TSC peut toujours être utilisé. Ceci est rendu possible grâce à des caractéristiques architecturales spéciales:

1. l'équipement peut générer une interruption spéciale chaque fois que la fréquence de mise à jour du TSC change. Dans le même temps, l'équipement offre également la possibilité de connaître la fréquence actuelle. Alternativement, le taux de rafraîchissement TSC peut être placé sous le contrôle du système d'exploitation (voir «Power ISA version 2.06 révision B, livre II, chapitre 5»)
2. le matériel ainsi que la valeur TSC peuvent également fournir l'ID du processeur sur lequel cette valeur est lue (voir les instructions Intel RDTSCP, "Intel 64 and IA-32 Architectures Software Developer's Manual", Volume 2)
3. sur certains systèmes, vous pouvez ajuster par programme la valeur TSC pour chaque CPU (voir l'instruction Intel WRMSR et enregistrez IA32_TIME_STAMP_COUNTER, "Intel 64 and IA-32 Architectures Software Developer's Manual", Volume 3)

En général, le thème de la façon dont les compteurs de temps sont mis en œuvre sur différentes architectures est fascinant et étendu. Si vous avez le temps et l'intérêt, je recommande la plongée. Entre autres choses, vous apprendrez, par exemple, que certains systèmes vous permettent de déterminer par programme si TSC peut servir de source fiable de temps.

Il existe donc de nombreuses implémentations architecturales de TSC, chacune avec ses propres caractéristiques. Mais il est intéressant qu'une tendance générale se soit établie dans tout ce zoo. Le matériel et les systèmes d'exploitation modernes s'efforcent de garantir que :

1. TSC ticks à la même fréquence sur chaque CPU du système
2. cette fréquence ne change pas dans le temps
3. il n'y a pas de décalage entre les TSC qui cochent sur différents CPU

Lors de la conception de ma bibliothèque, j'ai décidé de partir de cette prémisse, et non de la vinaigrette des implémentations matérielles.

La bibliothèque

Je n'ai pas commencé à m'étendre sur des puces matérielles d'un tas d'architectures différentes. Au lieu de cela, j'ai décidé que ma bibliothèque serait orientée vers les tendances. Elle a un objectif purement empirique:

1. il vous permet de vérifier expérimentalement la fiabilité de TSC comme source de temps
2. vous permet également de calculer expérimentalement les paramètres nécessaires pour convertir rapidement les ticks en nanosecondes
3. naturellement, la bibliothèque fournit des interfaces pratiques pour lire TSC et convertir les ticks en nanosecondes "à la volée"

Le code de la bibliothèque est disponible ici. Il sera compilé et exécuté uniquement sous Linux.

Dans le code, vous pouvez voir les détails de l'implémentation de toutes les méthodes, qui seront discutées plus tard.

Évaluation de la fiabilité TSC

La bibliothèque fournit une interface qui renvoie deux classements:

1. décalage maximal entre les compteurs appartenant à différents CPU. Seuls les CPU disponibles pour le processus sont pris en compte. Par exemple, si un processus dispose de trois CPU disponibles, et en même temps TSC sur ces CPU est 50, 150, 20, alors le décalage maximum sera 150-20 = 130. Naturellement, la bibliothèque ne sera pas en mesure d'obtenir un véritable décalage maximum expérimentalement, mais elle donnera une estimation dans laquelle s'insérera ce décalage. Que faire ensuite avec l'évaluation? Comment utiliser? Cela résout déjà le code client. Mais la signification est approximativement la suivante. Le décalage maximal est la valeur maximale par laquelle la dimension créée par le code client peut être déformée. Supposons que, dans notre exemple avec trois CPU, le code client commence à mesurer le temps sur CPU3 (où TSC était 20) et se termine sur CPU2 (où TSC était 150). Il s'avère que 130 ticks supplémentaires se glisseront dans l'intervalle mesuré. Et plus jamais. La différence entre CPU1 et CPU2 ne serait que de 100 ticks. Ayant une estimation de 130 ticks (en fait, ce sera beaucoup plus conservateur), le client peut décider si une telle valeur de distorsion lui convient ou non
2. Les valeurs TSC mesurées séquentiellement sur des CPU identiques ou différents augmentent-elles? Voici l'idée. Disons que nous avons plusieurs processeurs. Supposons que leur horloge soit synchronisée et qu'elle coche à la même fréquence. Ensuite, si vous mesurez d'abord le temps sur un processeur, puis le mesurez à nouveau - déjà sur l'un des processeurs disponibles - le deuxième chiffre doit être plus grand que le premier.
   
   J'appellerai cette estimation en dessous de l'estimation de la monotonie TSC
   

Voyons maintenant comment obtenir la première estimation:

1. l'un des processeurs disponibles pour le processus est déclaré «de base»
2. puis tous les autres CPU sont triés, et pour chacun d'eux le décalage est calculé: TSC___CPU – TSC___CPU . Cela se fait comme suit:
   
   • a) trois valeurs mesurées sont prises séquentiellement (l'une après l'autre!): TSC_base_1, TSC_current, TSC_base_2 . Ici, le courant indique que la valeur a été mesurée sur le CPU actuel et la base sur la base
   • b) le décalage TSC___CPU – TSC___CPU doit se situer dans l'intervalle [TSC_current – TSC_base_2, TSC_current – TSC_base_1] . C'est sous l'hypothèse que les TSC cochent à la même fréquence sur les deux CPU.
   • c) les étapes a) -b) sont répétées plusieurs fois. L'intersection de tous les intervalles obtenus à l'étape b) est calculée. L'intervalle résultant est considéré comme l'estimation du décalage TSC___CPU – TSC___CPU
   
   
3. après avoir obtenu une estimation de décalage pour chaque CPU par rapport à la base, il est facile d'obtenir une estimation du décalage maximum entre tous les CPU disponibles:
   
   • a) l'intervalle minimum est calculé, ce qui inclut tous les intervalles résultants obtenus à l'étape 2
   • b) la largeur de cet intervalle est considérée comme l'estimation du décalage maximal entre les TSCs cocher sur différents CPU
   
   

Pour évaluer la monotonie dans la bibliothèque, l'algorithme suivant est implémenté:

1. Disons qu'un processus a N CPU disponible
2. Mesurer TSC sur CPU1
3. Mesurer TSC sur CPU2
4. ...
5. Mesurer TSC sur CPUN
6. Mesurer à nouveau TSC sur CPU1
7. Nous vérifions que les valeurs mesurées augmentent de façon monotone du premier au dernier

Il est important ici que les première et dernière valeurs soient mesurées sur la même CPU. Et voici pourquoi. Disons que nous avons 3 processeurs. Supposons que le TSC sur CPU2 soit décalé de +100 ticks par rapport au TSC sur CPU1. Supposons également que le TSC sur CPU3 soit décalé de +100 ticks par rapport au TSC sur CPU2. Considérez la chaîne d'événements suivante:

• Lisez le TSC sur CPU1. Soit une valeur de 10
• 2 ticks passés
• Lisez TSC sur CPU2. Doit être 112
• 2 ticks passés
• Lisez TSC sur CPU3. Doit être 214

Jusqu'à présent, l'horloge semble synchronisée. Mais mesurons à nouveau le TSC sur CPU1:

• 2 ticks passés
• Lisez le TSC sur CPU1. Doit avoir 16 ans

Oups! La monotonie est rompue. Il s'avère que la mesure des première et dernière valeurs sur le même CPU permet de détecter des décalages plus ou moins importants entre les horloges. La question suivante, bien sûr: "Quelle est l'ampleur des changements?" La quantité de décalage qui peut être détectée dépend du temps qui s'écoule entre les mesures TSC successives. Dans l'exemple donné, ce ne sont que 2 ticks. Les décalages entre les heures dépassant 2 ticks seront détectés. De manière générale, les décalages inférieurs au temps écoulé entre les mesures successives ne seront pas détectés. Ainsi, plus les mesures sont localisées dans le temps, mieux c'est. La précision des deux estimations en dépend. Plus les mesures sont denses:

• plus l'estimation du décalage maximal est faible
• plus la confiance dans l'évaluation de la monotonie

Dans la section suivante, nous verrons comment prendre des mesures précises. J'ajoute ici que lors du calcul des estimations de fiabilité TSC, la bibliothèque effectue de nombreuses vérifications plus simples des "poux", par exemple:

• vérification limitée que les TSC sur différents processeurs fonctionnent à la même vitesse
• vérifier que les compteurs changent vraiment au fil du temps, et pas seulement montrer la même valeur

Deux méthodes de collecte des contre-valeurs

Dans la bibliothèque, j'ai implémenté deux méthodes pour collecter les valeurs TSC:

1. Basculez entre les CPU . Dans cette méthode, toutes les données nécessaires pour évaluer la fiabilité du TSC sont collectées par un seul thread qui «saute» d'un CPU à l'autre. Les deux algorithmes décrits dans la section précédente conviennent à cette méthode et ne conviennent pas à l'autre.
   La «commutation entre les CPU» n'a aucune utilité pratique. La méthode a été mise en œuvre juste pour "jouer". Le problème avec la méthode est que le temps nécessaire pour «faire glisser» un flux d'un CPU à un autre est très important. En conséquence, beaucoup de temps s'écoule entre les mesures TSC successives et la précision des estimations est très faible. Par exemple, une estimation typique du décalage maximum entre TSC est obtenue dans la région de 23 000 ticks.
   
   Cependant, la méthode présente deux avantages:
   
   • c'est absolument déterministe. Si vous avez besoin de mesurer TSC séquentiellement sur CPU1, CPU2, CPU3, alors nous le prenons et le faisons: passer à CPU1, lire TSC, passer à CPU2, lire TSC et enfin, passer à CPU3, lire TSC
   • vraisemblablement, si le nombre de CPU dans le système augmente très rapidement, le temps de commutation entre eux devrait augmenter beaucoup plus lentement. Par conséquent, en théorie, apparemment, un système peut exister - un très grand système! - dans lequel l'utilisation de la méthode sera justifiée. Mais c'est encore peu probable
   
   
2. Mesures commandées en utilisant CAS . Dans cette méthode, les données sont collectées en parallèle par plusieurs threads. Chaque CPU disponible démarre un thread. Les mesures prises par différents threads sont organisées en une seule séquence à l'aide de l'opération «comparer et échanger». Ci-dessous est un morceau de code qui montre comment cela se fait.
   L'idée de la méthode est empruntée à fio , un outil populaire pour générer des charges d'E / S.
   
   Les estimations de fiabilité obtenues avec la puissance de cette méthode semblent déjà plutôt bonnes. Par exemple, une estimation du décalage maximum est déjà obtenue au niveau de plusieurs centaines de ticks. Une vérification de la monotonie vous permet de rattraper l'horloge désynchronisée au sein de centaines de ticks.
   
   Cependant, les algorithmes donnés dans la section précédente ne conviennent pas à cette méthode. Il est important pour eux que les valeurs TSC soient mesurées dans un ordre prédéterminé. La méthode des «mesures ordonnées par CAS» ne le permet pas. Au lieu de cela, une longue séquence de mesures aléatoires est d'abord collectée, puis des algorithmes (déjà différents) tentent de trouver des valeurs lues sur des processeurs «appropriés» dans cette séquence.
   
   Je ne donnerai pas ces algorithmes ici, afin de ne pas abuser de votre attention. Vous pouvez les voir dans le code. Il y a beaucoup de commentaires. En théorie, ces algorithmes sont les mêmes. Un point fondamentalement nouveau est la vérification de la façon dont les séquences TSC de type aléatoire sont statistiquement «qualitatives». Il est également possible de fixer un niveau minimum acceptable de signification statistique pour les estimations de fiabilité du TSC.
   
   Théoriquement, sur de TRÈS grands systèmes, la méthode «ordonnée CAS» peut donner de mauvais résultats. La méthode exige que les processeurs se disputent l'accès à un emplacement de mémoire commun. S'il y a beaucoup de processeurs, la concurrence peut s'avérer très intense. En conséquence, il sera difficile de créer une séquence de mesure avec de bonnes propriétés statistiques. Cependant, pour le moment, cette situation semble peu probable.
   

J'ai promis du code. Voici à quoi cela ressemble de construire des mesures dans une seule chaîne en utilisant CAS.

  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; } 

Ce code est exécuté sur chaque CPU disponible. Tous les threads ont accès à la variable partagée seq_counter . Avant de lire le TSC, le flux lit la valeur de cette variable et la stocke dans la variable seq_num . Lit ensuite TSC. Il essaie ensuite d'augmenter atomiquement seq_counter de un, mais uniquement si la valeur de la variable n'a pas changé depuis sa lecture. Si l'opération réussit, cela signifie que le thread a réussi à « seq_num » le numéro de séquence stocké dans seq_num derrière la valeur TSC mesurée. Le prochain numéro de série, qui pourra être implanté (peut-être déjà dans un autre thread) en sera un de plus. Pour ce nombre est tiré de la variable seq_counter , et chaque appel réussi de __atomic_compare_exchange_n() augmente cette variable d'une __atomic_compare_exchange_n() .


Un autre point à mentionner ici est le soin que tous les flux impliqués dans les mesures démarrent plus ou moins simultanément. Nous sommes intéressés par le fait que les valeurs TSC lues sur différents CPU sont aussi mélangées que possible. Nous ne sommes pas satisfaits de la situation où, par exemple, un thread démarre en premier, termine son travail, puis seulement tous les autres démarrent. La séquence TSC résultante aura des propriétés inutiles. Aucune estimation ne peut en être tirée. Le démarrage simultané de tous les threads est important - et pour cela, des mesures ont été prises dans la bibliothèque.

Convertissez les ticks en nanosecondes à la volée

Après avoir vérifié la fiabilité de TSC, le deuxième objectif majeur de la bibliothèque est de convertir les ticks en nanosecondes à la volée. J'ai emprunté l'idée de cette conversion au fio déjà mentionné. Cependant, j'ai dû apporter des améliorations significatives, car, comme mon analyse l'a montré, en soi, la procédure de conversion ne fonctionne pas assez bien. Là, vous obtenez une faible précision.

Je vais commencer par un exemple.

Idéalement, je voudrais convertir les ticks en nanosecondes comme ceci:
ns_time = tsc_ticks / tsc_per_ns
Nous voulons que le temps consacré à la conversion soit minimal. Par conséquent, nous visons à utiliser exclusivement l'arithmétique entière. Voyons comment cela peut nous menacer.

Si tsc_per_ns = 3 , alors une simple division entière, du point de vue de la précision, fonctionne très bien: ns_time = tsc_ticks / 3 .

Mais que faire si tsc_per_ns = 3.333 ?Si ce nombre est arrondi à 3, la précision de conversion sera très faible. Pour remédier à ce problème comme suit:
ns_time = (tsc_ticks * factor) / (3.333 * factor).

Si le facteur factorest suffisamment grand, la précision sera bonne. Mais quelque chose restera mauvais. A savoir, les frais généraux de conversion. La division entière est une opération très coûteuse. Par exemple, sur x86, il nécessite plus de 10 cycles d'horloge. De plus, les opérations de division entière ne sont pas toujours en pipeline.

Nous réécrivons notre formule sous la forme équivalente
ns_time = (tsc_ticks * factor / 3.333) / factor.

La première division n'est pas un problème. Nous pouvons pré (factor / 3.333)- calculer à l'avance. Mais la deuxième division fait toujours mal. Pour se débarrasser d'elle, choisissonsfactorégal à la puissance de deux. Après cela, la deuxième division peut être remplacée par un décalage de bits - une opération simple et rapide.

Quelle taille pouvez-vous choisir factor? Malheureusement, factoril ne peut pas être arbitrairement important. Elle est limitée par la condition selon laquelle la multiplication dans le numérateur ne doit pas conduire à un débordement de type 64 bits. Oui, nous voulons utiliser uniquement des types «natifs». Encore une fois, pour réduire les frais généraux de conversion au minimum.

Voyons maintenant sa taille factordans notre exemple spécifique. Supposons que nous voulons travailler avec des intervalles de temps allant jusqu'à un an. Au cours de l'année, TSC tiknet les temps suivants: 3.333 * 1000000000 * 60 * 60 * 24 * 365 = 105109488000000000. Diviser une valeur maximale du numéro de type 64 bits est la suivante : 18446744073709551615 / 105109488000000000 ~ 175.5. Donc l'expression(factor / 3.333)ne doit pas dépasser cette valeur. Ensuite , nous avons factor <= 175.5 * 3.333 ~ 584.9. La plus grande puissance de deux qui ne dépasse pas ce nombre est 512. Par conséquent, notre formule de conversion prend la forme:

ns_time = (tsc_ticks * 512 / 3.333) / 512

Ou:

ns_time = tsc_ticks * 153 / 512

Super.Voyons maintenant ce que cette formule a avec précision. Un an contient des 1000000000 * 60 * 60 * 24 * 365 = 31536000000000000nanosecondes. Notre formule donne: 105109488000000000 * 153 / 512 = 31409671218750000. La différence avec la valeur actuelle est de 126328781250000 nanosecondes ou 126328781250000 / 1000000000 / 60 / 60 ~ 35heures.

C'est une grosse erreur. Nous voulons une meilleure précision. Et si nous mesurons des intervalles de temps ne dépassant pas une heure? Je vais omettre les calculs. Ils sont complètement identiques à ceux qui viennent d'être réalisés. La formule finale sera:

ns_time = tsc_ticks * 1258417 / 4194304(1)

L'erreur de conversion ne sera que de 119 305 nanosecondes pendant 1 heure (ce qui est inférieur à 0,2 millisecondes). Très, très bien. Si la valeur convertible maximale est encore inférieure à une heure, la précision sera encore meilleure. Mais comment utilisons-nous cela? Ne limitez pas les mesures de temps à une heure?

Faisons attention au moment suivant:

tsc_ticks = (tsc_ticks_per_1_hour * number_of_hours) + tsc_ticks_remainder

Si nous calculons tsc_ticks_per_1_hour, nous pouvons extraire number_of_hoursde tsc_ticks. Ensuite, nous savons combien de nanosecondes sont contenues en une heure. Il ne nous sera donc pas difficile de traduire en nanosecondes la partie tsc_tickscorrespondant à un nombre entier d'heures. Pour terminer la conversion, nous devrons traduire en nanosecondes tsc_ticks_remainder. Cependant, nous savons que ce nombre de tiques est arrivé en moins d'une heure. Donc, pour le convertir en nanosecondes, nous pouvons utiliser la formule (1).

C'est fait. Un tel mécanisme de conversion nous convient. Résumons-le et optimisons-le maintenant.

Tout d'abord, nous voulons avoir un contrôle flexible sur les erreurs de conversion. Nous ne voulons pas lier les paramètres de conversion à un intervalle de temps de 1 heure. Soit un intervalle de temps arbitraire:

tsc_ticks = modulus * number_of_moduli_periods + tsc_ticks_remainder

Rappelons une fois de plus comment convertir le reste en nanosecondes:

ns_per_remainder = (tsc_ticks_remainder * factor / tsc_per_nsec) / factor

Calculer les paramètres de conversion (on le sait tsc_ticks_remainder < modulus): Par souci d'ennui, il faut noter que la dernière inégalité n'est pas équivalente à la première dans le cadre de l'arithmétique entière. Mais je ne m'y attarderai pas longtemps. Je peux seulement dire que la dernière inégalité est plus grave que la première, et donc sûre à utiliser. Après avoir obtenu de la dernière inégalité , nous calculons: Et puis ces paramètres sont utilisés pour convertir le reste en nanosecondes: Donc, nous avons calculé la conversion du reste. Le prochain problème à résoudre - est l'extraction et de la

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




shift

factor = 2 ^ shift
mult = factor / tsc_per_nsec




ns_per_remainder = (tsc_ticks_remainder * mult) >> shift


tsc_ticks_remaindernumber_of_moduli_periodstsc_ticks. Comme toujours, nous voulons le faire rapidement. Comme toujours, nous ne voulons pas utiliser la division. Par conséquent, nous choisissons simplement moduluségal à la puissance de deux:

modulus = 2 ^ remainder_bit_length

Alors:

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

Super.Nous savons maintenant comment extraire de tsc_ticks number_of_moduli_periodset tsc_ticks_remainder. Et nous savons comment convertir tsc_ticks_remainderen nanosecondes. Il reste à comprendre comment convertir cette partie des ticks, qui est un multiple, en nanosecondes modulus. Mais tout est simple:

ns_per_moduli = ns_per_modulus * number_of_moduli_periods

ns_per_modulusvous pouvez calculer à l'avance. De plus, selon la même formule par laquelle nous convertissons le reste. Cette formule peut être utilisée pour des périodes qui ne dépassent pas modulus. Lui modulus- même , bien sûr, pas plus que modulus.

ns_per_modulus = (modulus * mult) >> shift

C’est tout!Nous avons pu calculer tous les paramètres nécessaires pour convertir les tiques en nanosecondes à la volée. Résumons maintenant brièvement la procédure de conversion:

1. nous avons 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

Dans cette procédure, les paramètres remainder_bit_length, modulus, ns_per_modulus, multet shiftavance de pré - calcul.

Si vous lisez toujours ce post, alors vous êtes super ou super. Il est même possible que vous soyez un analyste des performances ou un développeur de logiciels hautes performances.

Alors voilà.Il s'avère que nous n'avons pas encore fini :)

Rappelez-vous comment nous avons calculé le paramètre mult? C'était comme ça:

mult = factor / tsc_per_nsec

Question: d'où vient-il tsc_per_nsec?
Le nombre de ticks dans une nanoseconde est une très petite valeur. En fait, ma bibliothèque est tsc_per_nsecutilisée à la place (tsc_per_sec / 1000000000). C'est-à-dire:

mult = factor * 1000000000 / tsc_per_sec

Et il y a deux questions intéressantes:

1. Pourquoi tsc_per_secet non tsc_per_msec, par exemple?
2. Où les obtenir tsc_per_sec?

Commençons par le premier. Fio utilise désormais le nombre de ticks par milliseconde. Et cela pose des problèmes. Sur la machine, les paramètres dont je cités ci - dessus tsc_per_msec = 2599998. Alors tsc_per_sec = 2599998971. Si nous amenons ces nombres à une échelle, leur rapport sera très proche de l'unité: 0,999999626. Mais si nous utilisons le premier, et non le second, alors pour chaque seconde, nous aurons une erreur de 374 nanosecondes. Par conséquent - tsc_per_sec.

Plus loin ... Comment compter tsc_per_sec?

Cela se fait sur la base d'une mesure directe: «un certain temps» est un paramètre configurable. Elle peut être plus grande, plus petite ou égale à une seconde. Disons que c'est une demi-seconde. Supposons en outre que la différence réelle entre et s'est avérée être de 0,6 seconde. Alors .

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

La bibliothèque considère plusieurs valeurs de cette manière tsc_per_sec. Et puis, en utilisant des méthodes standard, il les «nettoie» du bruit statistique et reçoit une valeur unique à tsc_per_seclaquelle on peut faire confiance.

Dans le diagramme de mesure du temps ci-dessus, l'ordre des appels clock_gettime()et est important WTMLIB_GET_TSC(). Il est important WTMLIB_GET_TSC()que le même temps s'écoule entre deux appels qu'entre deux appels clock_gettime(). Il sera alors possible de corréler facilement l'heure du système avec les ticks TSC. Et puis la dispersion des valeurs tsc_per_secpeut vraiment être considérée comme aléatoire. Avec ce schéma de mesure, les valeurs tsc_per_secs'écarteront de la valeur moyenne dans les deux sens avec la même probabilité. Et il sera possible de leur appliquer des méthodes de filtrage standard.

Conclusion

C'est peut-être tout.

Mais le sujet de la mesure efficace du temps ne se limite pas à cela. Il existe de nombreuses nuances. Pour les personnes intéressées, je propose de travailler de manière indépendante sur les questions suivantes:

• stocker les paramètres de conversion dans le cache ou - mieux encore - sur les registres
• à quelles limites peut-on réduire modulus(augmentant ainsi la précision de la conversion)?
• comme nous l'avons vu, la précision de la conversion est affectée non seulement modulus, mais aussi par la taille de l'intervalle de temps, qui correspond aux ticks ( tsc_per_msecou tsc_per_sec). Comment équilibrer l'influence des deux facteurs?
• TSC dans la machine virtuelle. Puis-je l'utiliser?
• . , fio timespec. :
  
  tp->tv_sec = nsecs / 1000000000ULL;
  
  , TSC . , ,
  

Les méthodes discutées dans cet article nous permettent de mesurer l'échelle de temps d'une seconde avec une précision de l'ordre de plusieurs dizaines de nanosecondes. C'est la précision que j'observe réellement lors de l'utilisation de ma bibliothèque.

Fait intéressant, le fio, auquel j'ai emprunté certaines méthodes, perd exactement 700 à 900 nanosecondes sur une deuxième échelle (et il y a trois raisons à cela). De plus, il perd en vitesse de conversion en raison du stockage du temps dans un format Linux standard. Cependant, je m'empresse de rassurer les fans de fio. J'ai envoyé aux développeurs une description de tous les problèmes de conversion que j'ai découverts . Les gens travaillent déjà, ils le répareront bientôt.

Je vous souhaite de nombreuses nanosecondes agréables!