Estatística, Cache e a confiabilidade do RDTSC

Já acabei com o minha auto-flagelação (é assim que se escreve?!) e resolvi fazer umas medidas com relação ao uso da função rdtsc(). Como só faz sentido fazer testes com uma função destinada a testes do ponto de vista estatístico, então aqui vamos nós usar médias, modas e desvios-padrão. Aliás, por este último, entenda como sendo a média dos desvios da média (huh! ou seja: a maioria das amostras desviam-se de uma certa quantidade da média simples das mesmas amostras, ok?).

O desvio padrão nos dará uma idéia da precisão das medidas via rdtsc(). Vou usar o coeficiente de variação para expressar isso. Esse coeficiente é o a relação entre a o desvio-padrão (expressado pela letra grega σ) e a média (expresada pela letrea grega μ). A relação é dada em porcentagem. A interpretação é que a maioria das amostras desviam-se x porcento da média…

Antes de começarmos quero que você tenha em mente algumas informações sobre o seu hardware:

• Sua memória é particionada em blocos de 4 kB chamados páginas. Essas páginas podem ou não existir fisicamente. No caso de elas ainda não existirem o sistema operacional vai criá-la e, para isso, pode simplesmente alocar o bloco de memória e colocá-lo num diretório de páginas ou, se este diretório estiver cheio ou prestes a encher, pode decidir guardar uma ou mais das páginas pré-existentes em disco e atribuí-las ao seu processo (ou seja, fazer swap). Esses processos são demorados e implicam numa parada total do seu processo (tempo dedicado 100% para o kernel);
• Todos os processadores modernos possuem caches. Hoje é muito comum termos 2 caches. Um deles é o chamado cache L1 e localiza-se no interior do processador. Também hoje é comum termos caches L1 com 64 kB de tamanho. O outro cache é o L2 e também é muito comum que este cache esteja dentro do processador também. Em bons processadores o cache L2 pode ter 4 MB de tamanho. Caches aumentam a velocidade do acesso à memória porque, com eles, a quantidade de acessos à memória é diminuída. O problema é quando uma linha (64 bytes), correspondente a um bloco da memória do sistema, não se encontra no cache L1. Neste caso o processador pára tudo e tenta ler a linha do cache L2. Se a linha também não está no cache L2 então este tentará ler um bloco de linhas da memória do sistema e depois repassa a linha lida para o cache L1;
• Existem muitas coisas feitas pelo kernel do seu sistema operacional que o seu processo não tem controle. A maioria deles interrompe a execução de seu processo.

Esses três fatores afetam muito a medição dos ciclos de máquina de um fragmento do seu processo. E estes são os motivos que causam imprecisão no uso da função rdtsc().

O processo que usei para colher dados estatísticos do uso de rdtsc() compreende a leitura de n diferenças de tempo entre chamadas à rdtsc() e o armazenamento dessas diferenças em um buffer com n “quad words” (ou seja, cada entrada é do tipo “uint64_t”). Este tamanho n vai ser de 8 elementos (64 bytes), 32 elementos (256 bytes), 256 elementos (4 kB) e 1024 elementos (8 kB). Em essência, o fragmento de código que armazena as diferenças é assim:

int i;
uint64_t buffer[BUFFER_SIZE], *p;

for (p = buffer, i = 0; i < BUFFER_SIZE; i++, p++)
{
  *p = rdtsc();
  *p = rdtsc() - *p;
}

Eis as estatísticas para 8 e 32 elementos:

$ ./test8
Tamanho do buffer: 64 bytes.
Média: 314.12
Desvio padrão: 9.49
Coeficiente de variação: 3.02%
Valor mínimo: 308
Valor máximo: 336

$ ./test32
Tamanho do buffer: 256 bytes.
Média: 308.22
Desvio padrão: 1.24
Coeficiente de variação: 0.40%
Valor mínimo: 308
Valor máximo: 315

Dentro do Cache e da Página não há muitos problemas!

Uma vez que o buffer está dentro do cache L1, a variação na medição de tempo não é lá grandes coisas. Chega a ser menor o igual a 5%. O problema é quando cruzamos a fronteira de uma página:

$ # Ainda não cruzamos a fronteira de 4096 bytes aqui!
$ ./test256
Tamanho do buffer: 2048 bytes.
Média: 309.94
Desvio padrão: 3.49
Coeficiente de variação: 1.13%
Valor mínimo: 308
Valor máximo: 336

$ # Agora sim, cruzamos a fronteira!
$ ./test1024
Tamanho do buffer: 8192 bytes.
Média: 322.03
Desvio padrão: 290.35
Coeficiente de variação: 90.16%
Valor mínimo: 308
Valor máximo: 7434

Continuamos dentro de uma página!

Os picos provavelmente são devidos à paginação e aos efeitos do cache.

É interessante observar que, no último gráfico, os picos ocorrem aproximadamente aos 4 kB e aos 8 kB, justamente a fronteira de uma página!

Observem que, no geral, mesmo com os efeitos da paginação e do cache, RDTSC não foge muito de seu valor esperado, exceto em alguns pontos. Se fizermos os mesmos testes com um buffer de 1 milhão de elementos, obteríamos um gráfico mais ou menos como o último, com mais picos graças ao número quase 1000 vezes maior de amostras.

Meu veredito? rdtsc() possui problemas de precisão, mas é muito confiável. Mas, acho que eu já havia dito isso aqui, não?