Tempo de processamento – Funções muito rápidas


Medir o tempo que uma função gasta para ser executada parece ser bem simples, olhando superficialmente.

Teoricamente, só seria necessário gravar o tempo de início e subtrair do tempo do fim.

O problema nesse tipo de medição é que, nos PCs só temos acesso à milisegundos (10⁻³ s) no relógio e uma instrução que seja processada em poucos ciclos de clock dura alguns nanosegundos (10⁻⁹ s).

O que fazer para medir esses nanosegundos?

A primeira solução é usar probabilidade:

pulso

Olhando a imagem, podemos perceber que a medição de tempo pode ser tanto zero ou um, dependendo se a função começou a ser executada próximo do início da borda de subida do pulso de clock.

Assim, mandamos a função ser executada centenas ou milhares de vezes e teremos como encontrar sua duração, com um erro que diminui com o aumento do número de execuções.

Note que o processador conta ciclos de clock, que na função clock() duram 1 milisegundo cada. Por isso, em alguns lugares teremos divisões por 1000.

Exemplo:

#define N 1000000
tempo_inicial = clock() / 1000;
for (i =0; i < N; i++) {
    funcao();
}
tempo_final = clock() / 1000;
duracao = (tempo_final - tempo_inicial)/N;

Essa solução funciona muito bem, mas na medida que você vai aumentando a complexidade ou os dados de entrada vai ser preciso ficar ajustando o número de execuções, para que não demore tempo demais para dar precisão de nanosegundos à uma função que demore microsegundos ou até alguns milisegundos.

Assim, é aconselhado usar um medidor de tempo máximo para executar instruções. Ou seja, antes de executar a função novamente, deve-se conferir se o tempo de execução de esgotou ou não, garantindo um número mais alto de execuções para funções mais rápidas e um número menor (com erro maior) para funções mais demoradas.

Exemplo:

#define tTotal 1000
numExecs = 0;
t1 = clock();
limite = t1 + tTotal;
while ( clock() < limite ) {
    funcao();
    numExecs++;
}
t2 = clock();
duracao = (t2-t1) / (numExecs*1000);

Como o Sistema Operacional está quase sempre realizando operações leves, podemos ter erros de medidas caso a função fosse rodada apenas uma vez, como inicialmente proposto. Com o uso de probabilidade, podemos diluir esse gasto entre todas as medidas, tornando-o desprezível.

Alguns erros de medida podem ser gerados por causa do “warm-up” de cache, entre outras coisas, sendo aconselhado repetir o teste algumas vezes. O valor medido será quase constante após algumas medidas.

Uma Observação:

Caso a função a ser medida seja muito rápida, esse segundo método pode criar um overhead, fazendo com que o tempo total para entradas com poucos dados seja confundido com o gasto de processamento do código do nosso cronômetro.

Para amenizar isso, é possível repetir o bloco sem chamar a função e depois subtrair o tempo gasto do tempo total anterior.

Note que isso só será necessário em funções que durem menos de microsegundos.

Anúncios
  1. Em assembly tem o opcode RDTSC que conta o número de clocks do processador desde que foi ligado. Com ele, dá pra medir com precisão intervalos de nanosegundos. Em compensação influências externas (tipo cache) ficam mais evidentes.

    • Vianna
    • 4 de novembro de 2009

    Sim, sim. Já tinha lido esse link aqui: http://smallcode.weblogs.us/2007/12/07/performance-measurements-with-rdtsc/

    Eu quis fazer algo mais acessível, mas ainda sim funcional. Não sou nenhum gênio da computação como você. 🙂

    Abraços

  2. Faltou o nome do autor da publicação. abraço descobrir uma coisa nova.

  3. Olá, seu artigo ficou muito bom. Legítimo
    essas informações. Felicidades.

  1. No trackbacks yet.

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

w

Conectando a %s

Anúncios
%d blogueiros gostam disto: