Medição de tempo com precisão de nanossegundos

Alguns meses atrás, um momento histórico veio para mim. As ferramentas padrão do sistema operacional para medir o tempo deixaram de ser suficientes para mim. Demorou um tempo para medir com precisão de nanossegundos e sobrecarga de nanossegundos.

Decidi escrever uma biblioteca que resolveria esse problema. À primeira vista, parecia que não havia nada de especial para fazer. Mas, após uma análise mais detalhada, como sempre, verificou-se que havia muitos problemas interessantes a serem resolvidos. Neste artigo, falarei sobre os problemas e como eles foram resolvidos.

Como você pode medir muitos tipos diferentes de tempo em um computador, vou esclarecer imediatamente que aqui falaremos sobre "tempo por cronômetro". Ou hora do relógio de parede. É tempo real, tempo decorrido etc. Ou seja, um tempo "humano" simples, que detectamos no início da tarefa e paramos no final.

Microssegundo - quase para sempre

Os desenvolvedores de sistemas de alto desempenho nos últimos anos se acostumaram à escala de tempo de microssegundos. Em microssegundos, você pode ler dados de uma unidade NVMe. Em microssegundos, os dados podem ser enviados pela rede. Não para todos, é claro, mas para a rede InifiniBand - facilmente.

Ao mesmo tempo, o microssegundo também tinha uma estrutura. Uma pilha de E / S completa consiste em vários componentes de software e hardware. Os atrasos introduzidos por alguns deles estão no nível de microssegundos.

Para medir atrasos dessa magnitude, a precisão do microssegundo não é mais suficiente. No entanto, não apenas a precisão é importante, mas também a sobrecarga do tempo de medição. A chamada do sistema clock_gettime () do Linux retorna a hora com precisão de nanossegundos. Em uma máquina que está ao meu alcance (CPU Intel® Xeon® E5-2630 v2 a 2.60GHz), essa chamada é concluída em cerca de 120 ns. Muito boa figura. Além disso, clock_gettime () funciona de maneira bastante previsível. Isso permite que você leve em consideração a sobrecarga da chamada e efetue medições com precisão da ordem de dezenas de nanossegundos. No entanto, vamos agora prestar atenção a isso. Para medir o intervalo de tempo, você precisa fazer duas chamadas: no início e no final. I.e. gaste 240 ns. Se forem medidos intervalos de tempo densamente espaçados da ordem de 1 a 10 μs, em alguns casos, o próprio processo de medição distorcerá significativamente o processo observado.

Comecei esta seção com a aceleração da pilha de E / S nos últimos anos. Isso é novo, mas está longe de ser o único motivo para querer medir o tempo com rapidez e precisão. Essa necessidade sempre foi. Por exemplo, sempre havia um código que eu queria acelerar pelo menos 1 ciclo de clock do microprocessador. Ou outro exemplo, do artigo original sobre a sensacional vulnerabilidade Spectre:



Aqui, as linhas 72-74 medem o tempo de execução de uma única operação de acesso à memória. É verdade que o Spectre não está interessado em nanossegundos. O tempo pode ser medido em "papagaios". Voltaremos aos papagaios e segundos.

Contador de carimbo de data / hora

A chave para a medição rápida e precisa do tempo é um contador especial de microprocessador. O valor desse contador geralmente é armazenado em um registro separado e geralmente é - mas nem sempre - acessível no espaço do usuário. Em arquiteturas diferentes, o contador é chamado de maneira diferente:

1. contador de carimbo de hora x86
2. registro de base de tempo no PowerPC
3. contador de tempo de intervalo no Itanium
4. etc.

Abaixo, sempre usarei o nome "contador de carimbo de data / hora" ou TSC, embora na verdade eu tenha em mente esse contador, independentemente da arquitetura.

A leitura do valor TSC normalmente - mas nem sempre - é possível com uma única instrução. Aqui está um exemplo para x86. Estritamente falando, esta não é uma instrução pura do assembler, mas o assembler GNU inline:

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

A instrução rdtsc coloca duas metades de 32 bits do registrador TSC nos registradores eax e edx. Destas, você pode "colar" um único valor de 64 bits.

Mais uma vez, observo: essas instruções (e similares) na maioria dos casos podem ser chamadas diretamente do espaço do usuário. Nenhuma chamada do sistema. Sobrecarga mínima.

O que agora precisa ser feito para medir o tempo?

1. Execute uma dessas instruções no início do intervalo de tempo de seu interesse. Lembre-se do valor do contador
2. Execute uma dessas instruções no final. Acreditamos que o valor do contador da primeira instrução para a segunda aumentará. Caso contrário, por que é necessário? Lembre-se do segundo valor
3. Consideramos a diferença entre os dois valores armazenados. Este é o nosso tempo

Parece simples, mas ...

O tempo medido pelo procedimento descrito é expresso em "papagaios". Não é em segundos. Mas às vezes os papagaios são exatamente o que você precisa. Há situações em que os valores absolutos dos intervalos de tempo não são importantes, mas como os diferentes intervalos se relacionam. O exemplo Spectre acima demonstra exatamente essa situação. A duração de cada acesso individual à memória não importa. É importante que chamadas para alguns endereços sejam executadas muito mais rapidamente do que para outras (dependendo se os dados estão armazenados no cache ou na memória principal).

Mas e se não forem necessários papagaios, mas segundos / microssegundos / nanossegundos, etc.? Dois casos fundamentalmente diferentes podem ser distinguidos aqui:

1. Nanossegundos são necessários, mas então. Ou seja, é permitido primeiro fazer todas as medidas necessárias em papagaios e armazená-las em algum lugar para processamento adicional (por exemplo, na memória). E somente após as medições serem concluídas, convertendo lentamente os papagaios coletados em segundos
2. Nanossegundos são necessários "on the fly". Por exemplo, seu processo de medição possui algum tipo de "consumidor" que você não controla e que espera tempo no formato "humano"

O primeiro caso é simples, o segundo - requer desenvoltura. A conversão deve ser o mais eficaz possível. Se consumir muitos recursos, pode distorcer bastante o processo de medição. Falaremos sobre a conversão efetiva abaixo. Até aqui, identificamos esse problema e passamos para outro.

Os contadores de data e hora não são tão simples quanto gostaríamos. Em algumas arquiteturas:

1. não é garantido que o TSC seja atualizado em alta frequência. Se o TSC for atualizado, digamos, uma vez a cada microssegundo, não será possível corrigir nanossegundos com ele.
2. a frequência com a qual o TSC é atualizado pode variar ao longo do tempo
3. em diferentes CPUs presentes no sistema, os TSCs podem ser atualizados em diferentes frequências
4. pode haver uma mudança entre os TSCs em diferentes CPUs

Aqui está um exemplo que ilustra o último problema. Suponha que tenhamos um sistema com duas CPUs: CPU1 e CPU2. Suponha que o TSC na primeira CPU esteja atrás da segunda pelo número de ticks, o que equivale a 5 segundos. Suponha ainda que um fluxo seja lançado no sistema que mede o tempo dos cálculos, o que ele próprio faz. Para fazer isso, o fluxo primeiro lê o valor TSC, depois faz o cálculo e, em seguida, lê o segundo valor TSC. Se durante toda a sua vida útil um thread permanecer em apenas uma CPU - em qualquer -, não haverá problemas. Mas e se o encadeamento iniciado na CPU1, medisse o primeiro valor TSC lá e, no meio dos cálculos, fosse movido pelo sistema operacional para a CPU2, onde leria o segundo valor TSC? Nesse caso, os cálculos parecerão 5 segundos mais longos do que realmente são.

Devido aos problemas listados acima, o TSC não pode servir como uma fonte confiável de tempo em alguns sistemas. No entanto, em outros sistemas "sofrendo" dos mesmos problemas, o TSC ainda pode ser usado. Isso é possível graças a recursos arquitetônicos especiais:

1. o equipamento pode gerar uma interrupção especial sempre que a frequência com a qual o TSC é atualizado for alterada. Ao mesmo tempo, o equipamento também oferece a oportunidade de descobrir a frequência atual. Como alternativa, a taxa de atualização do TSC pode ser colocada sob o controle do sistema operacional (consulte “Power ISA Versão 2.06 Revisão B, Livro II, Capítulo 5”)
2. juntamente com o valor TSC, o equipamento também pode fornecer o ID da CPU na qual esse valor é lido (consulte as instruções Intel RDTSCP, “Manual do desenvolvedor de software das arquiteturas Intel 64 e IA-32”, volume 2)
3. em alguns sistemas, você pode ajustar programaticamente o valor TSC para cada CPU (consulte a instrução Intel WRMSR e registre IA32_TIME_STAMP_COUNTER, “Manual do desenvolvedor de software das arquiteturas Intel 64 e IA-32”, volume 3)

Em geral, o tema de como os medidores de tempo são implementados em diferentes arquiteturas é fascinante e extenso. Se você tiver tempo e interesse, recomendo mergulhar. Entre outras coisas, você aprenderá, por exemplo, que alguns sistemas permitem determinar programaticamente se o TSC pode servir como uma fonte confiável de tempo.

Portanto, existem muitas implementações arquitetônicas do TSC, cada uma com suas próprias características. Mas é interessante que uma tendência geral tenha sido estabelecida em todo esse zoológico. Os sistemas operacionais e hardware modernos se esforçam para garantir que :

1. O TSC marca na mesma frequência em cada CPU do sistema
2. essa frequência não muda no tempo
3. não há mudança entre TSCs marcando em diferentes CPUs

Ao projetar minha biblioteca, decidi seguir essa premissa, e não o vinagrete das implementações de hardware.

A biblioteca

Não comecei a colocar chips de hardware de várias arquiteturas diferentes. Em vez disso, decidi que minha biblioteca seria orientada a tendências. Ela tem um foco puramente empírico:

1. permite verificar experimentalmente a confiabilidade do TSC como fonte de tempo
2. também permite calcular experimentalmente os parâmetros necessários para converter rapidamente ticks em nanossegundos
3. naturalmente, a biblioteca fornece interfaces convenientes para ler TSC e converter ticks em nanossegundos "on the fly"

O código da biblioteca está disponível aqui. Será compilado e executado apenas no Linux.

No código, você pode ver os detalhes da implementação de todos os métodos, que serão discutidos posteriormente.

Avaliação de Confiabilidade TSC

A biblioteca fornece uma interface que retorna duas classificações:

1. deslocamento máximo entre contadores pertencentes a diferentes CPUs. Somente CPUs disponíveis para o processo são consideradas. Por exemplo, se um processo tiver três CPUs disponíveis e, ao mesmo tempo, o TSC nessas CPUs for 50, 150, 20, o deslocamento máximo será 150-20 = 130. Naturalmente, a biblioteca não poderá obter um turno máximo real experimentalmente, mas fornecerá uma estimativa na qual esse turno se ajustará. O que fazer em seguida com a avaliação? Como usar? Isso já resolve o código do cliente. Mas o significado é aproximadamente o seguinte. O deslocamento máximo é o valor máximo pelo qual a dimensão que o código do cliente faz pode ser distorcida. Suponha que, em nosso exemplo com três CPUs, o código do cliente comece a medir o tempo na CPU3 (onde TSC tinha 20 anos) e termine na CPU2 (onde TSC tenha 150). Acontece que 130 carrapatos extras entrarão no intervalo medido. E nunca mais. A diferença entre CPU1 e CPU2 seria de apenas 100 ticks. Tendo uma estimativa de 130 ticks (na verdade, será muito mais conservador), o cliente pode decidir se esse valor de distorção combina com ele ou não
2. Os valores TSC medidos sequencialmente na mesma ou em diferentes CPUs aumentam. Aqui está a ideia. Digamos que temos várias CPUs. Suponha que o relógio esteja sincronizado e marcando na mesma frequência. Então, se você medir primeiro o tempo em uma CPU e depois medir novamente - já em qualquer uma das CPUs disponíveis -, o segundo dígito deverá ser maior que o primeiro.
   
   Vou chamar essa estimativa abaixo da estimativa de monotonicidade do TSC
   

Agora vamos ver como podemos obter a primeira estimativa:

1. um dos processadores disponíveis para o processo é declarado "básico"
2. todas as outras CPUs são classificadas e para cada uma delas o deslocamento é calculado: TSC___CPU – TSC___CPU . Isso é feito da seguinte maneira:
   
   • a) três valores medidos são obtidos seqüencialmente (um após o outro!): TSC_base_1, TSC_current, TSC_base_2 . Aqui, current indica que o valor foi medido na CPU atual e base na base
   • b) o turno TSC___CPU – TSC___CPU deve estar no intervalo [TSC_current – TSC_base_2, TSC_current – TSC_base_1] . Isso está sob a suposição de que os TSCs estão marcando na mesma frequência em ambas as CPUs.
   • c) os passos a) -b) são repetidos várias vezes. A interseção de todos os intervalos obtidos na etapa b) é calculada. O intervalo resultante é obtido como a estimativa do turno TSC___CPU – TSC___CPU
   
   
3. depois que uma estimativa de turno é obtida para cada CPU em relação à base, é fácil obter uma estimativa do turno máximo entre todas as CPUs disponíveis:
   
   • a) o intervalo mínimo é calculado, incluindo todos os intervalos resultantes obtidos na etapa 2
   • b) a largura desse intervalo é tomada como estimativa do deslocamento máximo entre os TSCs em diferentes CPUs
   
   

Para avaliar a monotonia na biblioteca, o seguinte algoritmo é implementado:

1. Digamos que um processo tenha N CPU disponível
2. Medindo TSC na CPU1
3. Medindo TSC na CPU2
4. ...
5. Medindo TSC no CPUN
6. Meça o TSC novamente na CPU1
7. Verificamos que os valores medidos aumentam monotonicamente do primeiro ao último

É importante aqui que o primeiro e o último valor sejam medidos na mesma CPU. E aqui está o porquê. Digamos que temos 3 CPUs. Suponha que o TSC na CPU2 seja deslocado em +100 ticks em relação ao TSC na CPU1. Suponha também que o TSC na CPU3 seja deslocado em +100 ticks em relação ao TSC na CPU2. Considere a seguinte cadeia de eventos:

• Leia o TSC na CPU1. Seja obtido um valor de 10
• 2 carrapatos passaram
• Leia TSC na CPU2. Deve ser 112
• 2 carrapatos passaram
• Leia TSC na CPU3. Deve ser 214

Até agora, o relógio parece sincronizado. Mas vamos medir o TSC na CPU1 novamente:

• 2 carrapatos passaram
• Leia o TSC na CPU1. Deve ter 16 anos

Opa! A monotonia está quebrada. Acontece que medir o primeiro e o último valor na mesma CPU permite detectar mudanças mais ou menos grandes entre os relógios. A próxima pergunta, é claro: "Qual o tamanho das mudanças?" A quantidade de turno que pode ser detectada depende do tempo decorrido entre as sucessivas medições de TSC. No exemplo dado, estes são apenas 2 ticks. Serão detectados turnos entre as horas que excederem 2 ticks. De um modo geral, mudanças que são menores que o tempo decorrido entre medições sucessivas não serão detectadas. Portanto, quanto mais densas as medições estiverem localizadas no tempo, melhor. A precisão de ambas as estimativas depende disso. Quanto mais densas forem as medidas:

• quanto menor a estimativa de turno máximo
• quanto mais confiança na avaliação da monotonia

Na próxima seção, falaremos sobre como fazer medições rigorosas. Acrescentarei aqui que, ao calcular as estimativas de confiabilidade do TSC, a biblioteca faz muito mais verificações simples de "piolhos", por exemplo:

• verificação limitada de que TSCs em diferentes CPUs estão correndo na mesma velocidade
• verificando se os contadores realmente mudam com o tempo e não apenas mostram o mesmo valor

Dois métodos para coletar valores de contador

Na biblioteca, implementei dois métodos para coletar valores de TSC:

1. Alterne entre CPU . Nesse método, todos os dados necessários para avaliar a confiabilidade do TSC são coletados por um único encadeamento que “salta” de uma CPU para outra. Ambos os algoritmos descritos na seção anterior são adequados para este método e não são adequados para o outro.
   "Alternar entre a CPU" não tem uso prático. O método foi implementado apenas para "brincar". O problema com o método é que o tempo necessário para "arrastar" um fluxo de uma CPU para outra é muito grande. Consequentemente, passa muito tempo entre medições sucessivas de TSC e a precisão das estimativas é muito baixa. Por exemplo, uma estimativa típica para o deslocamento máximo entre o TSC é obtida na região de 23.000 carrapatos.
   
   No entanto, o método tem algumas vantagens:
   
   • é absolutamente determinístico. Se você precisar medir o TSC sequencialmente na CPU1, CPU2, CPU3, basta fazê-lo: alterne para CPU1, leia TSC, alterne para CPU2, leia TSC e, finalmente, alterne para CPU3, leia TSC
   • presumivelmente, se o número de CPUs no sistema crescer muito rápido, o tempo de alternância entre elas deverá aumentar muito mais lentamente. Portanto, em teoria, aparentemente, um sistema pode existir - um sistema muito grande! - em que o uso do método será justificado. Mas ainda assim isso é improvável
   
   
2. Medições solicitadas usando o CAS . Nesse método, os dados são coletados em paralelo por vários threads. Cada CPU disponível inicia um thread. As medições realizadas por diferentes threads são organizadas em uma única sequência usando a operação "comparar e trocar". Abaixo está um pedaço de código que mostra como isso é feito.
   A idéia do método é emprestada do fio , uma ferramenta popular para gerar cargas de E / S.
   
   As estimativas de confiabilidade obtidas com o poder desse método já parecem muito boas. Por exemplo, uma estimativa do turno máximo já é obtida no nível de várias centenas de ticks. Uma verificação de monotonia permite que você pegue o relógio fora de sincronia dentro de centenas de ticks.
   
   No entanto, os algoritmos dados na seção anterior não são adequados para esse método. É importante para eles que os valores de TSC sejam medidos em uma ordem predeterminada. O método de "medições ordenadas pelo CAS" não permite isso. Em vez disso, primeiro uma longa sequência de medições aleatórias é coletada e, em seguida, algoritmos (já diferentes) tentam encontrar valores lidos em CPUs "adequadas" nessa sequência.
   
   Não darei esses algoritmos aqui, para não abusar de sua atenção. Você pode vê-los no código. Existem muitos comentários. Em teoria, esses algoritmos são os mesmos. Um ponto fundamentalmente novo é a verificação de como as seqüências TSC de tipo aleatório são estatisticamente "qualitativas". Também é possível definir um nível mínimo aceitável de significância estatística para as estimativas de confiabilidade do TSC.
   
   Teoricamente, em sistemas MUITO grandes, o método "ordenado por CAS" pode fornecer resultados ruins. O método requer que os processadores concorram pelo acesso a um local de memória comum. Se houver muitos processadores, a concorrência poderá se tornar muito intensa. Como resultado, será difícil criar uma sequência de medidas com boas propriedades estatísticas. No entanto, no momento, essa situação parece improvável.
   

Eu prometi algum código. Veja como é criar medições em uma única cadeia usando o 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 é executado em todas as CPUs disponíveis. Todos os encadeamentos têm acesso à variável compartilhada seq_counter . Antes de ler o TSC, o fluxo lê o valor dessa variável e o armazena na variável seq_num . Então lê TSC. Em seguida, ele tenta aumentar atomicamente seq_counter em um, mas apenas se o valor da variável não tiver sido alterado desde que foi lido. Se a operação for bem-sucedida, isso significa que o encadeamento conseguiu "piquetar" o número de sequência armazenado em seq_num atrás do valor TSC medido. O próximo número de série, que poderá apostar (possivelmente já em outro encadeamento) será mais um. Esse número é obtido da variável seq_counter e cada chamada bem-sucedida de __atomic_compare_exchange_n() aumenta essa variável em um.


Outro ponto que vale a pena mencionar aqui é o cuidado de que todos os fluxos envolvidos nas medições iniciem mais ou menos simultaneamente. Estamos interessados ​​no fato de que os valores TSC lidos em diferentes CPUs são tão mistos quanto possível. Não estamos satisfeitos com a situação em que, por exemplo, um thread inicia primeiro, termina seu trabalho e somente então todos os outros começam. A sequência TSC resultante terá propriedades inúteis. Nenhuma estimativa pode ser extraída dele. O início simultâneo de todos os threads é importante - e, para isso, foram tomadas medidas na biblioteca.

Converta carrapatos em nanossegundos em tempo real

Após verificar a confiabilidade do TSC, o segundo objetivo principal da biblioteca é converter ticks em nanossegundos em tempo real. Peguei emprestada a ideia dessa conversão do fio já mencionado. No entanto, eu tive que fazer algumas melhorias significativas, porque, como mostrou minha análise, o processo de conversão não funciona bem o suficiente. Lá você obtém baixa precisão.

Vou começar com um exemplo.

Idealmente, gostaria de converter ticks em nanossegundos como este:
ns_time = tsc_ticks / tsc_per_ns
Queremos que o tempo gasto na conversão seja mínimo. Portanto, pretendemos usar aritmética exclusivamente inteira. Vamos ver como isso pode nos ameaçar.

Se tsc_per_ns = 3 , uma divisão inteira simples, do ponto de vista da precisão, funciona bem: ns_time = tsc_ticks / 3 .

Mas e se tsc_per_ns = 3.333 ?Se esse número for arredondado para 3, a precisão da conversão será muito baixa. Para ultrapassar este problema da seguinte forma:
ns_time = (tsc_ticks * factor) / (3.333 * factor).

Se o fator factorfor grande o suficiente, a precisão será boa. Mas algo continuará ruim. Ou seja, sobrecarga de conversão. A divisão inteira é uma operação muito cara. Por exemplo, no x86, são necessários mais de 10 ciclos de clock. Além disso, as operações de divisão inteira nem sempre são canalizadas.

Nós reescrever nossa fórmula na forma equivalente
ns_time = (tsc_ticks * factor / 3.333) / factor.

A primeira divisão não é um problema. Podemos pré (factor / 3.333)- calcular antecipadamente. Mas a segunda divisão ainda é dor. Para se livrar dela, vamos escolherfactorigual ao poder de dois. Depois disso, a segunda divisão pode ser substituída por uma mudança de bits - uma operação simples e rápida.

Quão grande você pode escolher factor? Infelizmente, factornão pode ser arbitrariamente grande. É limitado pela condição de que a multiplicação no numerador não deve levar ao estouro do tipo de 64 bits. Sim, queremos usar apenas tipos "nativos". Novamente, para manter as despesas gerais de conversão no mínimo.

Agora vamos ver o quão grande pode ser factorem nosso exemplo específico. Suponha que desejemos trabalhar com intervalos de tempo de até um ano. Durante o ano, TSC tiknet nos seguintes horários: 3.333 * 1000000000 * 60 * 60 * 24 * 365 = 105109488000000000. Dividir um valor máximo do número do tipo de 64 bits é: 18446744073709551615 / 105109488000000000 ~ 175.5. Então a expressão(factor / 3.333)não deve exceder esse valor. Então nós temos factor <= 175.5 * 3.333 ~ 584.9. A maior potência de duas que não excede esse número é 512. Portanto, nossa fórmula de conversão assume a forma:

ns_time = (tsc_ticks * 512 / 3.333) / 512

Ou:

ns_time = tsc_ticks * 153 / 512

Ótimo. Vamos agora ver o que essa fórmula tem com precisão. Um ano contém 1000000000 * 60 * 60 * 24 * 365 = 31536000000000000nanossegundos. Nossa fórmula dá: 105109488000000000 * 153 / 512 = 31409671218750000. A diferença com o valor presente é 126328781250000 nanossegundos ou 126328781250000 / 1000000000 / 60 / 60 ~ 35horas.

Este é um grande erro. Queremos uma melhor precisão. E se medirmos intervalos de tempo não superiores a uma hora? Eu vou omitir os cálculos. Eles são completamente idênticos aos que acabamos de fazer. A fórmula final será:

ns_time = tsc_ticks * 1258417 / 4194304(1)

O erro de conversão será de apenas 119.305 nanossegundos por 1 hora (menos de 0,2 milissegundos). Muito, muito bom Se o valor máximo conversível for menor que uma hora, a precisão será ainda melhor. Mas como usamos isso? Não limite as medições de tempo a uma hora?

Preste atenção para o seguinte ponto:

tsc_ticks = (tsc_ticks_per_1_hour * number_of_hours) + tsc_ticks_remainder

Se precalculation tsc_ticks_per_1_hour, podemos extrair number_of_hoursa partir tsc_ticks. Em seguida, sabemos quantos nanossegundos estão contidos em uma hora. Portanto, não será difícil traduzir em nanossegundos a parte tsc_ticksque corresponde a um número inteiro de horas. Para concluir a conversão, precisaremos traduzir em nanossegundostsc_ticks_remainder. No entanto, sabemos que esse número de ticks ocorreu em menos de uma hora. Portanto, para convertê-lo em nanossegundos, podemos usar a fórmula (1).

Feito. Esse mecanismo de conversão nos convém. Vamos resumir e otimizar agora.

Antes de tudo, queremos ter um controle flexível sobre os erros de conversão. Não queremos vincular os parâmetros de conversão a um intervalo de tempo de 1 hora. Que seja um intervalo de tempo arbitrário:

tsc_ticks = modulus * number_of_moduli_periods + tsc_ticks_remainder

Mais uma vez, lembre-se de como converter o restante em nanossegundos:

ns_per_remainder = (tsc_ticks_remainder * factor / tsc_per_nsec) / factor

Calculamos os parâmetros de conversão (sabemos disso 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


Por uma questão de tédio, deve-se notar que a última desigualdade não é equivalente à primeira na estrutura da aritmética inteira. Mas não vou insistir nisso por muito tempo. Só posso dizer que a última desigualdade é mais grave que a primeira e, portanto, segura de usar.

Depois de obtermos a última desigualdade shift, calculamos: E então esses parâmetros são usados ​​para converter o restante em nanossegundos: Então, calculamos a conversão restante. O próximo problema a ser resolvido - é a remoção de e partir . Como sempre, queremos fazer isso rápido. Como sempre, não queremos usar a divisão. Portanto, simplesmente escolhemos igual ao poder de dois: Então: Excelente. Agora sabemos como extrair de

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)

tsc_ticks number_of_moduli_periodse tsc_ticks_remainder. E sabemos como converter tsc_ticks_remainderem nanossegundos. Resta entender como converter essa parte dos ticks, que é um múltiplo, em nanossegundos modulus. Mas tudo é simples:

ns_per_moduli = ns_per_modulus * number_of_moduli_periods

ns_per_modulusvocê pode calcular antecipadamente. Além disso, de acordo com a mesma fórmula pela qual convertemos o restante. Essa fórmula pode ser usada por períodos que não excedam modulus. Ele mesmo modulus, é claro, não mais do que isso modulus.

ns_per_modulus = (modulus * mult) >> shift

Isso é tudo! Conseguimos calcular todos os parâmetros necessários para converter ticks em nanossegundos em tempo real. Agora, resuma brevemente o procedimento de conversão:

1. nós temos 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

Neste procedimento, parâmetros remainder_bit_length, modulus, ns_per_modulus, multe shiftavanço precalculation.

Se você ainda está lendo este post, você é ótimo ou ótimo. É até possível que você seja um analista de desempenho ou desenvolvedor de software de alto desempenho.

Então aqui.Acontece que ainda não terminamos :)

Lembra como calculamos o parâmetro mult? Foi assim:

mult = factor / tsc_per_nsec

Pergunta: de onde vem tsc_per_nsec?
O número de ticks em um nanossegundo é um valor muito pequeno. De fato, minha biblioteca é tsc_per_nsecusada em seu lugar (tsc_per_sec / 1000000000). Ou seja:

mult = factor * 1000000000 / tsc_per_sec

E há duas perguntas interessantes:

1. Por que tsc_per_sec, e não tsc_per_msec, por exemplo?
2. Onde conseguir isso tsc_per_sec?

Vamos começar com o primeiro. O Fio atualmente usa o número de ticks por milissegundo. E há problemas com isso. Na máquina, os parâmetros dos quais eu nomeei acima tsc_per_msec = 2599998. Enquanto tsc_per_sec = 2599998971. Se colocarmos esses números em uma escala, a proporção deles estará muito próxima da unidade: 0,999999626. Mas se usarmos o primeiro, e não o segundo, a cada segundo, teremos um erro de 374 nanossegundos. Portanto - tsc_per_sec.

Além disso ... Como contar tsc_per_sec?

Isso é feito com base na medição direta: “algum tempo” é um parâmetro configurável. Pode ser maior, menor ou igual a um segundo. Digamos que seja meio segundo. Suponha ainda que a diferença real entre e resultou em 0,6 segundos. Então .

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

A biblioteca considera vários valores dessa maneira tsc_per_sec. E então, usando métodos padrão, "os limpa" de ruído estatístico e recebe um valor único tsc_per_secque pode ser confiável.

No diagrama de medição de tempo acima, a ordem das chamadas clock_gettime()e é importante WTMLIB_GET_TSC(). É importante WTMLIB_GET_TSC()que o mesmo tempo transcorra entre duas chamadas e entre duas chamadas clock_gettime(). Então será possível correlacionar facilmente a hora do sistema com os ticks do TSC. E então a dispersão de valores tsc_per_secpode realmente ser considerada aleatória. Com esse esquema de medição, os valores tsc_per_secse desviarão do valor médio em qualquer direção com a mesma probabilidade. E será possível aplicar métodos de filtragem padrão a eles.

Conclusão

Talvez seja só isso.

Mas o tópico da medição efetiva do tempo não se limita a isso. Existem muitas nuances. Para os interessados, proponho trabalhar de forma independente nos seguintes assuntos:

• armazenamento de parâmetros de conversão em cache ou - melhor ainda - em registros
• até que limites podem ser reduzidos modulus(aumentando assim a precisão da conversão)?
• como vimos, a precisão da conversão é afetada não apenas modulus, mas também pelo tamanho do intervalo de tempo, que se correlaciona com os ticks ( tsc_per_msecou tsc_per_sec). Como equilibrar a influência de ambos os fatores?
• TSC na máquina virtual. Posso usar?
• . , fio timespec. :
  
  tp->tv_sec = nsecs / 1000000000ULL;
  
  , TSC . , ,
  

Os métodos discutidos neste artigo permitem medir a escala de tempo de um segundo com uma precisão da ordem de várias dezenas de nanossegundos. Essa é a precisão que eu realmente observo ao usar minha biblioteca.

Curiosamente, o fio, do qual emprestei alguns métodos, perde exatamente 700-900 nanossegundos em uma segunda escala (e há três razões para isso). Além disso, perde na velocidade de conversão devido ao armazenamento de tempo em um formato Linux padrão. No entanto, apresso-me a tranquilizar os fãs do fio. Enviei aos desenvolvedores uma descrição de todos os problemas de conversão que descobri . As pessoas já estão trabalhando, elas irão corrigi-lo em breve.

Desejo-lhe muitos agradáveis ​​nanossegundos!