Medición de tiempo con precisión de nanosegundos

Hace un par de meses llegó un momento histórico para mí. Las herramientas estándar del sistema operativo para medir el tiempo han dejado de ser suficientes para mí. Tomó tiempo medir con precisión de nanosegundos y con sobrecarga de nanosegundos.

Decidí escribir una biblioteca que resolviera este problema. A primera vista, parecía que no había nada especial que hacer. Pero después de un examen más detallado, como siempre, resultó que había muchos problemas interesantes que debían ser tratados. En este artículo, hablaré sobre los problemas y cómo se resolvieron.

Como puede medir muchos tipos diferentes de tiempo en una computadora, aclararé de inmediato que aquí hablaremos del "tiempo por cronómetro". O la hora del reloj de pared. Es tiempo real, tiempo transcurrido, etc. Es decir, un tiempo "humano" simple, que detectamos al comienzo de la tarea y lo detenemos al final.

Microsegundo: casi para siempre

Los desarrolladores de sistemas de alto rendimiento en los últimos años se han acostumbrado a la escala de tiempo de microsegundos. En microsegundos, puede leer datos de una unidad NVMe. En microsegundos, los datos se pueden enviar a través de la red. No para todos, por supuesto, sino para InifiniBand-network, fácilmente.

Al mismo tiempo, el microsegundo también tenía una estructura. Una pila de E / S completa consta de varios componentes de software y hardware. Los retrasos introducidos por algunos de ellos se encuentran en el nivel sub-microsegundo.

Para medir retrasos de esta magnitud, la precisión de microsegundos ya no es suficiente. Sin embargo, no solo es importante la precisión, sino también la sobrecarga del tiempo de medición. La llamada al sistema Linux clock_gettime () devuelve el tiempo con precisión de nanosegundos. En una máquina que está al alcance de mi mano (CPU Intel® Xeon® E5-2630 v2 @ 2.60GHz), esta llamada se completa en aproximadamente 120 ns. Muy buena figura. Además, clock_gettime () funciona de manera bastante predecible. Esto le permite tener en cuenta los gastos generales de su llamada y realmente tomar medidas con una precisión del orden de decenas de nanosegundos. Sin embargo, ahora prestemos atención a esto. Para medir el intervalo de tiempo, debe hacer dos llamadas de este tipo: al principio y al final. Es decir gastar 240 ns. Si se miden intervalos de tiempo densamente espaciados del orden de 1-10 μs, entonces, en algunos casos, el proceso de medición en sí mismo distorsionará significativamente el proceso observado.

Comencé esta sección con cómo la pila IO se ha acelerado en los últimos años. Esto es nuevo, pero lejos de ser la única razón para querer medir el tiempo de forma rápida y precisa. Tal necesidad siempre ha sido. Por ejemplo, siempre había un código que quería acelerar por al menos 1 ciclo de reloj del microprocesador. U otro ejemplo, del artículo original sobre la sensacional vulnerabilidad Spectre:



Aquí, las líneas 72-74 miden el tiempo de ejecución de una sola operación de acceso a memoria. Es cierto que Specter no está interesado en nanosegundos. El tiempo se puede medir en "loros". Volveremos a los loros y segundos.

Contador de sello de tiempo

La clave para una medición de tiempo rápida y precisa es un contador de microprocesador especial. El valor de este contador generalmente se almacena en un registro separado y generalmente es accesible, pero no siempre, desde el espacio del usuario. En diferentes arquitecturas, el contador se llama de manera diferente:

1. Contador de sello de tiempo x86
2. registro de base de tiempo en PowerPC
3. contador de tiempo de intervalo en Itanium
4. etc.

A continuación, siempre usaré el nombre "contador de marca de tiempo" o TSC, aunque de hecho tendré en cuenta cualquier contador, independientemente de la arquitectura.

Por lo general, es posible leer el valor de TSC, pero nuevamente no siempre, con una sola instrucción. Aquí hay un ejemplo para x86. Estrictamente hablando, esta no es una instrucción pura de ensamblador, sino el ensamblador en línea de GNU:

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

La instrucción rdtsc coloca dos mitades de 32 bits del registro TSC en los registros eax y edx. De estos, puede "pegar" un solo valor de 64 bits.

Una vez más, noto: esta (y similares) instrucciones en la mayoría de los casos se pueden llamar directamente desde el espacio del usuario. No hay llamadas del sistema. Gastos generales mínimos.

¿Qué debe hacerse ahora para medir el tiempo?

1. Ejecute una de estas instrucciones al comienzo del intervalo de tiempo que nos interese. Recordar el valor del contador
2. Ejecute una de esas instrucciones al final. Creemos que el valor del contador desde la primera instrucción hasta la segunda aumentará. De lo contrario, ¿por qué es necesario? Recuerda el segundo valor
3. Consideramos la diferencia entre los dos valores almacenados. Este es nuestro tiempo

Parece simple, pero ...

El tiempo medido por el procedimiento descrito se expresa en "loros". No es en segundos. Pero a veces los loros son exactamente lo que necesitas. Hay situaciones en las que no son importantes los valores absolutos de los intervalos de tiempo, sino cómo se relacionan entre sí los diferentes intervalos. El ejemplo anterior de Spectre demuestra exactamente esta situación. La duración de cada acceso individual a la memoria no importa. Solo es importante que las llamadas a algunas direcciones se ejecuten mucho más rápido que a otras (dependiendo de si los datos están almacenados en la memoria caché o en la memoria principal).

Pero, ¿qué pasa si no se necesitan loros, sino segundos / microsegundos / nanosegundos, etc.? Aquí se pueden distinguir dos casos fundamentalmente diferentes:

1. Se necesitan nanosegundos, pero entonces. Es decir, está permitido hacer primero todas las mediciones necesarias en loros y almacenarlas en algún lugar para su posterior procesamiento (por ejemplo, en la memoria). Y solo después de que se completen las mediciones, convierta lentamente los loros recolectados en segundos
2. Se necesitan nanosegundos "sobre la marcha". Por ejemplo, su proceso de medición tiene algún tipo de "consumidor" que usted no controla y que espera tiempo en el formato "humano"

El primer caso es simple, el segundo: requiere ingenio. La conversión debe ser lo más efectiva posible. Si consume muchos recursos, puede distorsionar en gran medida el proceso de medición. Hablaremos sobre la conversión efectiva a continuación. Aquí hasta ahora hemos identificado este problema y pasamos a otro.

Los contadores de sello de tiempo no son tan simples como nos gustaría. En algunas arquitecturas:

1. no se garantiza que el TSC se actualice a alta frecuencia. Si el TSC se actualiza, por ejemplo, una vez cada microsegundo, entonces no será posible arreglar nanosegundos con él.
2. la frecuencia con la que se actualiza el TSC puede variar con el tiempo
3. en diferentes CPU presentes en el sistema, los TSC se pueden actualizar a diferentes frecuencias
4. puede haber un cambio entre TSC marcando en diferentes CPU

Aquí hay un ejemplo que ilustra el último problema. Supongamos que tenemos un sistema con dos CPU: CPU1 y CPU2. Suponga que el TSC en la primera CPU está detrás de la segunda por el número de tics, que es equivalente a 5 segundos. Supongamos además que se inicia una secuencia en el sistema que mide el tiempo de los cálculos, lo que él mismo hace. Para hacer esto, la secuencia primero lee el valor de TSC, luego realiza el cálculo y luego lee el segundo valor de TSC. Si durante toda su vida un hilo permanece en una sola CPU, en cualquiera, entonces no hay problemas. Pero, ¿qué pasa si el subproceso comenzó en la CPU1, midió el primer valor de TSC allí y luego, en el medio de los cálculos, el sistema operativo lo movió a la CPU2, donde leyó el segundo valor de TSC? En este caso, los cálculos parecerán 5 segundos más largos de lo que realmente son.

Debido a los problemas enumerados anteriormente, TSC no puede servir como una fuente confiable de tiempo en algunos sistemas. Sin embargo, en otros sistemas que "padecen" los mismos problemas, aún se puede usar TSC. Esto es posible gracias a características arquitectónicas especiales:

1. el equipo puede generar una interrupción especial cada vez que cambia la frecuencia con la que se actualiza el TSC. Al mismo tiempo, el equipo también brinda la oportunidad de averiguar la frecuencia actual. Alternativamente, la frecuencia de actualización del TSC se puede colocar bajo el control del sistema operativo (consulte “Revisión ISA Power 2.0 versión B, Libro II, Capítulo 5”)
2. el hardware, junto con el valor TSC, también puede proporcionar la ID de la CPU en la que se lee este valor (consulte las instrucciones Intel RDTSCP, "Manual del desarrollador de software de las arquitecturas Intel 64 e IA-32", Volumen 2)
3. en algunos sistemas, puede ajustar mediante programación el valor de TSC para cada CPU (consulte las instrucciones de Intel WRMSR y registre IA32_TIME_STAMP_COUNTER, “Manual del desarrollador de software de las arquitecturas Intel 64 e IA-32”, Volumen 3)

En general, el tema de cómo se implementan los medidores de tiempo en diferentes arquitecturas es fascinante y extenso. Si tienes tiempo e interés, te recomiendo bucear. Entre otras cosas, aprenderá, por ejemplo, que algunos sistemas le permiten determinar mediante programación si TSC puede servir como una fuente confiable de tiempo.

Por lo tanto, hay muchas implementaciones arquitectónicas de TSC, cada una con sus propias características. Pero es interesante que se haya establecido una tendencia general en todo este zoológico. El hardware y los sistemas operativos modernos se esfuerzan por garantizar que :

1. El TSC funciona a la misma frecuencia en cada CPU del sistema
2. esta frecuencia no cambia en el tiempo
3. no hay cambio entre TSC marcando en diferentes CPU

Al diseñar mi biblioteca, decidí proceder desde esta premisa, y no desde la vinagreta de las implementaciones de hardware.

La biblioteca

No comencé a instalar chips de hardware de diferentes arquitecturas. En cambio, decidí que mi biblioteca estaría orientada a las tendencias. Ella tiene un enfoque puramente empírico:

1. le permite verificar experimentalmente la confiabilidad de TSC como fuente de tiempo
2. También le permite calcular experimentalmente los parámetros necesarios para convertir rápidamente las garrapatas a nanosegundos
3. naturalmente, la biblioteca proporciona interfaces convenientes para leer TSC y convertir ticks a nanosegundos "sobre la marcha"

El código de la biblioteca está disponible aquí. Se compilará y ejecutará solo en Linux.

En el código, puede ver los detalles de la implementación de todos los métodos, que se discutirán más adelante.

Evaluación de confiabilidad de TSC

La biblioteca proporciona una interfaz que devuelve dos clasificaciones:

1. desplazamiento máximo entre contadores pertenecientes a diferentes CPU. Solo se consideran las CPU disponibles para el proceso. Por ejemplo, si un proceso tiene tres CPU disponibles, y al mismo tiempo el TSC en estas CPU es 50, 150, 20, entonces el cambio máximo será 150-20 = 130. Naturalmente, la biblioteca no podrá obtener un cambio real máximo experimentalmente, pero dará una estimación en la que se ajustará este cambio. ¿Qué hacer a continuación con la evaluación? ¿Cómo usarlo? Esto ya resuelve el código del cliente. Pero el significado es aproximadamente el siguiente. El desplazamiento máximo es el valor máximo por el cual la dimensión que crea el código del cliente puede distorsionarse. Supongamos que, en nuestro ejemplo con tres CPU, el código del cliente comenzó a medir el tiempo en la CPU3 (donde TSC tenía 20) y terminó en la CPU2 (donde TSC tenía 150). Resulta que 130 garrapatas adicionales se arrastrarán en el intervalo medido. Y nunca más. La diferencia entre CPU1 y CPU2 sería de solo 100 ticks. Teniendo una estimación de 130 ticks (de hecho, será mucho más conservador), el cliente puede decidir si tal valor de distorsión le conviene o no
2. ¿Aumentan los valores de TSC medidos secuencialmente en la misma CPU o en diferentes CPU? Aquí está la idea. Digamos que tenemos varias CPU. Supongamos que su reloj está sincronizado y marcando la misma frecuencia. Luego, si primero mide el tiempo en una CPU y luego lo mide nuevamente, ya en cualquiera de las CPU disponibles, entonces el segundo dígito debe ser mayor que el primero.
   
   Llamaré a esta estimación por debajo de la estimación de monotonicidad TSC
   

Ahora veamos cómo podemos obtener la primera estimación:

1. uno de los procesadores disponibles para el proceso se declara "básico"
2. entonces se ordenan todas las otras CPU, y para cada una de ellas se calcula el cambio: TSC___CPU – TSC___CPU . Esto se hace de la siguiente manera:
   
   • a) se toman tres valores medidos secuencialmente (¡uno tras otro!): TSC_base_1, TSC_current, TSC_base_2 . Aquí, actual indica que el valor se midió en la CPU actual y se basa en la base
   • b) el cambio TSC___CPU – TSC___CPU debe estar en el intervalo [TSC_current – TSC_base_2, TSC_current – TSC_base_1] . Esto se da por supuesto que los TSC están funcionando a la misma frecuencia en ambas CPU.
   • c) los pasos a) -b) se repiten varias veces. Se calcula la intersección de todos los intervalos obtenidos en el paso b). El intervalo resultante se toma como la estimación del cambio TSC___CPU – TSC___CPU
   
   
3. Después de obtener una estimación de cambio para cada CPU en relación con la base, es fácil obtener una estimación del cambio máximo entre todas las CPU disponibles:
   
   • a) se calcula el intervalo mínimo, que incluye todos los intervalos resultantes obtenidos en el paso 2
   • b) el ancho de este intervalo se toma como la estimación del cambio máximo entre TSC marcando en diferentes CPU
   
   

Para evaluar la monotonía en la biblioteca, se implementa el siguiente algoritmo:

1. Digamos que un proceso tiene N CPU disponible
2. Medición de TSC en CPU1
3. Medición de TSC en CPU2
4. ...
5. Medición de TSC en CPUN
6. Mida TSC nuevamente en CPU1
7. Verificamos que los valores medidos aumentan monotónicamente del primero al último

Aquí es importante que el primer y el último valor se midan en la misma CPU. Y aquí está el por qué. Digamos que tenemos 3 CPU. Suponga que el TSC en la CPU2 se desplaza por +100 ticks en relación con el TSC en la CPU1. Supongamos también que el TSC en la CPU3 se desplaza por +100 ticks en relación con el TSC en la CPU2. Considere la siguiente cadena de eventos:

• Lea el TSC en CPU1. Deje que se obtenga un valor de 10
• Pasaron 2 garrapatas
• Lea el TSC en la CPU2. Debe ser 112
• Pasaron 2 garrapatas
• Leer TSC en CPU3. Debe ser 214

Hasta ahora, el reloj parece sincronizado. Pero volvamos a medir TSC en CPU1:

• Pasaron 2 garrapatas
• Lea el TSC en CPU1. Debe ser 16

¡Uy! La monotonía está rota. Resulta que medir los valores primero y último en la misma CPU le permite detectar cambios más o menos grandes entre los relojes. La siguiente pregunta, por supuesto: "¿Qué tan grandes son los turnos?" La cantidad de cambio que se puede detectar depende del tiempo que transcurra entre sucesivas mediciones de TSC. En el ejemplo dado, estos son solo 2 ticks. Se detectarán turnos entre horas que excedan las 2 garrapatas. En términos generales, no se detectarán los cambios que sean inferiores al tiempo transcurrido entre mediciones sucesivas. Entonces, cuanto más densas estén las mediciones en el tiempo, mejor. La precisión de ambas estimaciones depende de esto. Cuanto más densas se hacen las mediciones:

• cuanto menor sea la estimación de turno máximo
• mayor confianza en la evaluación de la monotonía

En la siguiente sección, hablaremos sobre cómo tomar medidas ajustadas. Agregaré aquí que mientras calcula las estimaciones de confiabilidad del TSC, la biblioteca realiza muchas más verificaciones simples de "piojos", por ejemplo:

• verificación limitada de que los TSC en diferentes CPU están funcionando a la misma velocidad
• comprobar que los contadores realmente cambian con el tiempo y no solo muestran el mismo valor

Dos métodos para recopilar valores de contador

En la biblioteca, implementé dos métodos para recopilar valores de TSC:

1. Cambiar entre CPU . En este método, todos los datos necesarios para evaluar la confiabilidad del TSC se recopilan mediante un solo subproceso que "salta" de una CPU a otra. Ambos algoritmos descritos en la sección anterior son adecuados para este método y no lo son para el otro.
   "Cambiar entre la CPU" no tiene un uso práctico. El método se implementó por el simple hecho de "jugar". El problema con el método es que el tiempo requerido para "arrastrar" un flujo de una CPU a otra es muy grande. En consecuencia, pasa mucho tiempo entre sucesivas mediciones de TSC y la precisión de las estimaciones es muy baja. Por ejemplo, se obtiene una estimación típica para el cambio máximo entre TSC en la región de 23,000 ticks.
   
   Sin embargo, el método tiene un par de ventajas:
   
   • Es absolutamente determinista. Si necesita medir TSC secuencialmente en CPU1, CPU2, CPU3, simplemente lo tomamos y lo hacemos: cambie a CPU1, lea TSC, cambie a CPU2, lea TSC y, finalmente, cambie a CPU3, lea TSC
   • presumiblemente, si el número de CPU en el sistema crece muy rápido, entonces el tiempo de cambio entre ellas debería crecer mucho más lentamente. Por lo tanto, en teoría, aparentemente, puede existir un sistema, ¡un sistema muy grande! - en el que se justificará el uso del método. Pero aun así, esto es poco probable
   
   
2. Mediciones ordenadas usando CAS . En este método, los datos se recopilan en paralelo mediante múltiples subprocesos. Cada CPU disponible inicia un hilo. Las medidas tomadas por diferentes subprocesos se organizan en una sola secuencia utilizando la operación "comparar e intercambiar". A continuación se muestra un código que muestra cómo se hace esto.
   La idea del método está tomada de fio , una herramienta popular para generar cargas de E / S.
   
   Las estimaciones de confiabilidad obtenidas con el poder de este método ya se ven bastante bien. Por ejemplo, ya se obtiene una estimación del cambio máximo en el nivel de varios cientos de ticks. Una comprobación de la monotonía le permite sincronizar el reloj en cientos de tics.
   
   Sin embargo, los algoritmos dados en la sección anterior no son adecuados para este método. Para ellos es importante que los valores de TSC se midan en un orden predeterminado. El método de "mediciones ordenadas por CAS" no lo permite. En cambio, primero se recopila una secuencia larga de mediciones aleatorias, y luego los algoritmos (ya diferentes) intentan encontrar valores leídos en CPU "adecuadas" en esta secuencia.
   
   No daré estos algoritmos aquí, para no abusar de su atención. Puedes verlos en el código. Hay muchos comentarios En teoría, estos algoritmos son iguales. Un punto fundamentalmente nuevo es la verificación de cómo las secuencias TSC escritas al azar son estadísticamente "cualitativas". También es posible establecer un nivel mínimo aceptable de significancia estadística para las estimaciones de confiabilidad del TSC.
   
   Teóricamente, en sistemas MUY grandes, el método "ordenado por CAS" puede dar malos resultados. El método requiere que los procesadores compitan por el acceso a una ubicación de memoria común. Si hay muchos procesadores, la competencia puede llegar a ser muy intensa. Como resultado, será difícil crear una secuencia de medición con buenas propiedades estadísticas. Sin embargo, por el momento, esta situación parece poco probable.
   

Prometí un código. Esto es lo que parece construir mediciones en una sola cadena usando 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; } 

Este código se ejecuta en cada CPU disponible. Todos los hilos tienen acceso a la variable compartida seq_counter . Antes de leer el TSC, la secuencia lee el valor de esta variable y la almacena en la variable seq_num . Luego lee TSC. Luego intenta aumentar atómicamente seq_counter en uno, pero solo si el valor de la variable no ha cambiado desde que se leyó. Si la operación es exitosa, esto significa que el hilo logró "replantear" el número de secuencia almacenado en seq_num detrás del valor medido del TSC. El próximo número de serie, que podrá apostar (posiblemente ya en otro hilo) será uno más. Para este número se toma de la variable seq_counter , y cada llamada exitosa de __atomic_compare_exchange_n() aumenta esta variable en uno.


Otro punto que vale la pena mencionar aquí es el cuidado de que todos los flujos involucrados en las mediciones comiencen más o menos simultáneamente. Estamos interesados ​​en el hecho de que los valores de TSC leídos en diferentes CPU están tan mezclados como sea posible. No estamos satisfechos con la situación cuando, por ejemplo, un subproceso comienza primero, termina su trabajo y solo entonces comienzan todos los demás. La secuencia TSC resultante tendrá propiedades inútiles. No se pueden extraer estimaciones de ella. El inicio simultáneo de todos los hilos es importante, y para ello, se han tomado medidas en la biblioteca.

Convierte ticks a nanosegundos sobre la marcha

Después de verificar la confiabilidad de TSC, el segundo propósito principal de la biblioteca es convertir las garrapatas a nanosegundos sobre la marcha. Tomé prestada la idea de esta conversión del ya mencionado fio. Sin embargo, tuve que hacer algunas mejoras significativas porque, como lo mostró mi análisis, en sí mismo el procedimiento de conversión no funciona lo suficientemente bien. Ahí tienes baja precisión.

Comenzaré con un ejemplo.

Idealmente, me gustaría convertir los ticks a nanosegundos como este:
ns_time = tsc_ticks / tsc_per_ns
Queremos que el tiempo dedicado a la conversión sea mínimo. Por lo tanto, nuestro objetivo es utilizar exclusivamente aritmética de enteros. Veamos cómo esto puede amenazarnos.

Si tsc_per_ns = 3 , entonces una división entera simple, desde el punto de vista de la precisión, funciona bien: ns_time = tsc_ticks / 3 .

Pero, ¿y si tsc_per_ns = 3.333 ? Si este número se redondea a 3, la precisión de conversión será muy baja.Para superar este problema de la siguiente manera:
ns_time = (tsc_ticks * factor) / (3.333 * factor).

Si el factor factores lo suficientemente grande, entonces la precisión será buena. Pero algo seguirá siendo malo. A saber, gastos generales de conversión. La división de enteros es una operación muy costosa. Por ejemplo, en x86 requiere más de 10 ciclos de reloj. Además, las operaciones de división de enteros no siempre se canalizan.

Volvemos a escribir nuestra fórmula en forma equivalente
ns_time = (tsc_ticks * factor / 3.333) / factor.

La primera división no es un problema. Podemos precalcular (factor / 3.333)por adelantado. Pero la segunda división sigue siendo dolorosa. Para deshacernos de él, elija factorigual a la potencia de dos. Después de eso, la segunda división puede ser reemplazada por un cambio de bit, una operación simple y rápida.

¿Qué tan grande puedes elegir?factor? Desafortunadamente, factorno puede ser arbitrariamente grande. Está limitado por la condición de que la multiplicación en el numerador no debe conducir a un desbordamiento del tipo de 64 bits. Sí, queremos usar solo tipos "nativos". Nuevamente, para mantener los gastos generales de conversión al mínimo.

Ahora veamos qué tan grande puede ser factoren nuestro ejemplo específico. Supongamos que queremos trabajar con intervalos de tiempo de hasta un año. Durante el año, TSC tiknet los siguientes tiempos: 3.333 * 1000000000 * 60 * 60 * 24 * 365 = 105109488000000000. Divide un valor máximo de número de tipo de 64 bits es: 18446744073709551615 / 105109488000000000 ~ 175.5. Por lo tanto, la expresión (factor / 3.333)no debe ser mayor que este valor. Entonces tenemos:factor <= 175.5 * 3.333 ~ 584.9. La potencia más grande de dos que no excede este número es 512. Por lo tanto, nuestra fórmula de conversión toma la forma:

ns_time = (tsc_ticks * 512 / 3.333) / 512

O

ns_time = tsc_ticks * 153 / 512

bien. Veamos ahora qué tiene esta fórmula con precisión. Un año contiene 1000000000 * 60 * 60 * 24 * 365 = 31536000000000000nanosegundos. Nuestra fórmula da: 105109488000000000 * 153 / 512 = 31409671218750000. La diferencia con el valor actual es 126328781250000 nanosegundos u 126328781250000 / 1000000000 / 60 / 60 ~ 35horas.

Este es un gran error. Queremos una mejor precisión. ¿Qué pasa si medimos intervalos de tiempo de no más de una hora? Omitiré los cálculos. Son completamente idénticos a los que acabamos de hacer. La fórmula final será:

ns_time = tsc_ticks * 1258417 / 4194304(1)

El error de conversión será de solo 119,305 nanosegundos por 1 hora (que es menos de 0.2 milisegundos). Muy muy bien. Si el valor convertible máximo es incluso menos de una hora, entonces la precisión será aún mejor. ¿Pero cómo usamos esto? ¿No limite las mediciones de tiempo a una hora?

Prestemos atención al siguiente momento:

tsc_ticks = (tsc_ticks_per_1_hour * number_of_hours) + tsc_ticks_remainder

si calculamos tsc_ticks_per_1_hour, podemos extraer number_of_hoursde tsc_ticks. A continuación, sabemos cuántos nanosegundos hay en una hora. Por lo tanto, no será difícil para nosotros traducir en nanosegundos esa parte tsc_ticksque corresponde a un número entero de horas. Para completar la conversión, necesitaremos traducir en nanosegundostsc_ticks_remainder. Sin embargo, sabemos que este número de garrapatas llegó en menos de una hora. Entonces, para convertirlo a nanosegundos, podemos usar la fórmula (1).

ListoTal mecanismo de conversión nos conviene. Resumamos y optimicemos ahora.

En primer lugar, queremos tener un control flexible sobre los errores de conversión. No queremos vincular los parámetros de conversión a un intervalo de tiempo de 1 hora. Sea un intervalo de tiempo arbitrario: una

tsc_ticks = modulus * number_of_moduli_periods + tsc_ticks_remainder

vez más, recuerde cómo convertir el resto a nanosegundos:

ns_per_remainder = (tsc_ticks_remainder * factor / tsc_per_nsec) / factor

calcule los parámetros de conversión (lo sabemos tsc_ticks_remainder < modulus): en aras de la tedio, debe tenerse en cuenta que la última desigualdad no es equivalente a la primera en el marco de la aritmética de enteros. Pero no me detendré en esto por mucho tiempo. Solo puedo decir que la última desigualdad es más severa que la primera y, por lo tanto, segura de usar. Una vez obtenido de la última desigualdad , calculamos:

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


Y luego estos parámetros se utilizan para convertir el resto a nanosegundos: Entonces, descubrimos la conversión del resto. El siguiente problema que hay que resolver - es la eliminación de y de . Como siempre, queremos hacerlo rápido. Como siempre, no queremos usar la división. Por lo tanto, simplemente elegimos igual a la potencia de dos: Entonces:

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)

GenialAhora sabemos cómo extraer de tsc_ticks number_of_moduli_periodsy tsc_ticks_remainder. Y sabemos cómo convertir tsc_ticks_remaindera nanosegundos. Queda por comprender cómo convertir esa parte de las garrapatas, que es un múltiplo, en nanosegundos modulus. Pero todo es simple:

ns_per_moduli = ns_per_modulus * number_of_moduli_periods

ns_per_moduluspuede calcular por adelantado. Además, de acuerdo con la misma fórmula por la cual convertimos el resto. Esta fórmula se puede usar por períodos de tiempo que no son más largos modulus. Él mismo modulus, por supuesto, no más que modulus.

ns_per_modulus = (modulus * mult) >> shift

Eso es todo!Pudimos calcular todos los parámetros necesarios para convertir las garrapatas a nanosegundos sobre la marcha. Ahora resuma brevemente el procedimiento de conversión:

1. tenemos 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

En este procedimiento, los parámetros remainder_bit_length, modulus, ns_per_modulus, multy el shiftavance cálculo previo.

Si todavía estás leyendo esta publicación, entonces eres genial o genial. Incluso es posible que sea analista de rendimiento o desarrollador de software de alto rendimiento.

Entonces aquí.Resulta que todavía no hemos terminado :)

¿Recuerdas cómo calculamos el parámetro mult? Fue así:

mult = factor / tsc_per_nsec

Pregunta: ¿de dónde viene tsc_per_nsec?
El número de tics en un nanosegundo es un valor muy pequeño. De hecho, mi biblioteca se tsc_per_nsecusa en su lugar (tsc_per_sec / 1000000000). Es decir:

mult = factor * 1000000000 / tsc_per_sec

Y hay dos preguntas interesantes:

1. ¿Por qué tsc_per_secy no tsc_per_msec, por ejemplo?
2. ¿Dónde conseguir estos tsc_per_sec?

Comencemos con el primero. Fio ahora usa la cantidad de tics por milisegundo. Y hay problemas con eso. En la máquina, los parámetros de los cuales me nombraron anteriormente tsc_per_msec = 2599998. Mientras tsc_per_sec = 2599998971. Si llevamos estos números a una escala, su relación será muy cercana a la unidad: 0.999999626. Pero si usamos el primero, y no el segundo, entonces por cada segundo tendremos un error de 374 nanosegundos. Por lo tanto - tsc_per_sec.

Además ... ¿Cómo contar tsc_per_sec?

Esto se realiza sobre la base de la medición directa: "algún tiempo" es un parámetro configurable. Puede ser más grande, más pequeño o igual a un segundo. Digamos que es medio segundo. Supongamos además que la diferencia real entre y resultó ser 0.6 segundos. Entonces .

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 biblioteca considera varios valores de esta manera tsc_per_sec. Y luego, utilizando métodos estándar, los "limpia" del ruido estadístico y recibe un valor único en el tsc_per_secque se puede confiar.

En el diagrama de medición de tiempo anterior, el orden de las llamadas clock_gettime()y es importante WTMLIB_GET_TSC(). Es importante WTMLIB_GET_TSC()que transcurra el mismo tiempo entre dos llamadas que entre dos llamadas clock_gettime(). Entonces será posible correlacionar fácilmente el tiempo del sistema con tics TSC. Y luego, la dispersión de valores tsc_per_secpuede considerarse realmente aleatoria. Con este esquema de medición, los valores tsc_per_secse desviarán del valor promedio en cualquier dirección con la misma probabilidad. Y será posible aplicarles métodos de filtrado estándar.

Conclusión

Quizás eso es todo.

Pero el tema de la medición efectiva del tiempo no se limita a esto. Hay muchos matices. Para aquellos interesados, propongo trabajar de forma independiente en los siguientes temas:

• almacenar parámetros de conversión en caché o, mejor aún, en registros
• ¿A qué límites se puede reducir modulus(aumentando así la precisión de la conversión)?
• Como hemos visto, la precisión de la conversión se ve afectada no solo modulus, sino también por el tamaño del intervalo de tiempo, que se correlaciona con los ticks ( tsc_per_mseco tsc_per_sec). ¿Cómo equilibrar la influencia de ambos factores?
• TSC en la máquina virtual. ¿Puedo usarlo?
• . , fio timespec. :
  
  tp->tv_sec = nsecs / 1000000000ULL;
  
  , TSC . , ,
  

Los métodos discutidos en este artículo nos permiten medir la escala de tiempo de un segundo con una precisión del orden de varias decenas de nanosegundos. Esta es la precisión que realmente observo cuando uso mi biblioteca.

Curiosamente, el fio, del cual tomé prestados algunos métodos, pierde exactamente 700-900 nanosegundos en una segunda escala (y hay tres razones para esto). Además, pierde velocidad de conversión debido al almacenamiento de tiempo en un formato estándar de Linux. Sin embargo, me apresuro a tranquilizar a los fanáticos del fio. Envié a los desarrolladores una descripción de todos los problemas de conversión que descubrí . La gente ya está trabajando, lo arreglarán pronto.

¡Te deseo muchos nanosegundos agradables!