Benchmark

Quando tentamos melhorar a performance de uma aplicação precisamos, antes de mais nada, medir qual a sua velocidade, tanto inicialmente, quanto no decorrer da otimização. Sem isso não temos como saber se as mudanças feitas melhoraram ou pioraram a eficiência do código.

Portanto, antes de mais nada, precisamos de uma ferramenta, um Benchmark, para medir esta performance e conseguirmos perceber a evolução feita.

A instrução RDTSC

Para medir a performance de um trecho de código precisamos, obviamente, marcar a diferença de tempo entre o início e fim de execução. No entanto precisamos que resolução deste relógio seja boa o suficiente para o que iremos medir. Por exemplo, se precisamos trabalhar a eficiência de uma rotina que é executada várias vezes por segundo, um relógio com precisão de 1 segundo é completamente inútil.

Dentre as alternativas de relógio disponíveis, existe um que se ajusta facilmente este caso, é a instrução RDTSC do processador. Esta instrução retorna o número de clocks do processador desde o momento que o computador foi iniciado. Como a resolução deste relógio é igual à freqüência do processador, qualquer trecho de código vai gerar diferenças entre as leituras.

Entretanto esta instrução também traz alguns problemas. Ela conta clocks do processador e não tempo passado, para calcular este tempo precisamos realizar a equação abaixo.

$tempo = \dfrac{clocks}{frequencia}$

Outra questão é a característica das máquinas atuais de mudança da freqüência do processador conforme o uso. Estes controles são muito legais, pois podem diminuir o consumo de energia da máquina, diminuindo também a conta de luz e, em última análise, diminuindo o impacto sobre o meio-ambiente. Isso tudo é muito bonito, mas é um desastre para uma análise de performance. Desligue todos os controles de velocidade da CPU (Cool'n'Quiet, SpeedStep, etc…) antes de realizar seus testes.

Além disso temos ainda a questão dos ambiente multi-tarefas. Como a instrução RDTSC retorna o número de clocks, ela conta também todas as interferências do sistema operacional (mudanças de contexto, tratamento de interrupções, etc). Não temos como alterar isso, mas podemos minimizar seus efeitos.

  • O Windows muda de contexto a cada 20 mseg, tente fazer benchmarks de funções que caibam neste tempo, ao invés de todo o sistema de uma vez;
  • Rode o benchmark várias vezes, guarde o menor tempo, o maior tempo e faça a média de todos os resultados.

O código

Para facilitar o uso, o ideal é criar uma função com a instrução RDTSC. O código é bem simples, e nem poderia ser diferente, ele retorna o contador atual do processador em uma variável de 64 bits. Neste exemplo o código é compatível somente com o GCC, mas os arquivos para download são compatíveis também com o Microsoft Visual C++ 2005.

inline uint64_t Rdtsc()
{
    union
    {
        uint64_t x64;
        struct
        {
            uint32_t lo;
            uint32_t hi;
        };
    } time;
 
    __asm__ __volatile__ ( "rdtsc\n" : "=a" (time.lo), "=d" (time.hi) );
 
    return time.x64;
}

Na internet encontramos algumas variações deste código. Alguns se aproveitam da característica do Visual C++ de utilizar EDX:EAX como retorno da função, não colocando o retorno em uma variável. Outros colocam uma instrução CPUID antes da execução do RDTSC para limpar o pipeline de execução do processador e impedir que o out-of-order execution atrapalhe a medição do tempo.

Na minha opinião estas técnicas são interessantes para quando precisamos identificar o tempo de execução de um trecho de código muito pequeno ou em caso de sistemas de tempo real, mas para o caso geral de otimização de código elas fazem pouca diferença. Como sempre estamos fazendo um comparativo entre várias execuções, normalmente um valor aproximado é o suficiente para avaliarmos se as modificações surtiram o efeito desejado.

Como utilizar?

Como exemplo, vamos avaliar uma otimização clássica, a técnica de desenrolar o laço. Esta técnica consiste em repetir um código interno ao laço para auxiliar o compilador nas suas otimizações e também para reduzir a relação entre o tempo gasto com a resolução do problema e o tempo gasto com o tratamento de laço.

uint32_t SumBuffer( uint32_t* buffer, uint32_t len )
{
    uint32_t i;
    uint32_t sum = 0;
 
    for( i=0; i<len; i++ )
    {
        sum += buffer[i];
    }
    return sum;
}
 
uint32_t SumBufferUnrolled( uint32_t* buffer, uint32_t len )
{
    uint32_t i;
    uint32_t sum;
    uint32_t chunks = len & ~7;
 
    sum = 0;
 
    for( i=0; i<chunks; i+=8 )
    {
        sum += buffer[i];
        sum += buffer[i+1];
        sum += buffer[i+2];
        sum += buffer[i+3];
        sum += buffer[i+4];
        sum += buffer[i+5];
        sum += buffer[i+6];
        sum += buffer[i+7];
    }
 
    for( ; i<len; i++ )
    {
        sum += buffer[i];
    }
 
    return sum;
}

Em via de regra, medimos sempre o tempo de execução dentro um loop. Precisamos fazer isso pois o tempo de execução varia de acordo com vários aspectos, como estado do cache, time slice do sistema operacional ou carga da máquina. Colocando o código dentro de um loop conseguimos um tempo de execução aproximado que podemos usar. Como padrão eu costumo armazenar a execução mais rápida, a mais lenta e calculo a média de todas as chamadas.

Para analisar a performance destas funções usaremos a função Rdtsc() dentro de um loop chamando a função 10 vezes.

#define BUFFER_LEN (0x000fffff)
#define LOOP_COUNT (10)
 
uint32_t TestSum( uint64_t* min, uint64_t* max, uint64_t* ave )
{
    uint32_t* buffer = new uint32_t[ BUFFER_LEN ];
    uint64_t diff;
    uint32_t dummyRet;
    int i;
 
    *max = 0;
    *min = ~0;
    *ave = 0;
 
    for( i=0; i<LOOP_COUNT; i++ )
    {
        diff = Rdtsc();
        dummyRet = SumBuffer( buffer, BUFFER_LEN );
        diff = Rdtsc() - diff;
 
        if( diff < *min )
        {
            *min = diff;
        }
 
        if( diff > *max )
        {
            *max = diff;
        }
 
        *ave += diff;
    }
 
    *ave /= LOOP_COUNT;
 
    delete[] buffer;
 
    return dummyRet;
}
 
uint32_t TestSumUnrolled( uint64_t* min, uint64_t* max, uint64_t* ave )
{
    uint32_t* buffer = new uint32_t[ BUFFER_LEN ];
    uint64_t diff;
    uint32_t dummyRet;
    int i;
 
    *max = 0;
    *min = ~0;
    *ave = 0;
 
    for( i=0; i<LOOP_COUNT; i++ )
    {
        diff = Rdtsc();
        dummyRet = SumBufferUnrolled( buffer, BUFFER_LEN );
        diff = Rdtsc() - diff;
 
        if( diff < *min )
        {
            *min = diff;
        }
 
        if( diff > *max )
        {
            *max = diff;
        }
 
        *ave += diff;
    }
 
    *ave /= LOOP_COUNT;
 
    delete[] buffer;
 
    return dummyRet;
}
 
int main( void )
{
    uint64_t min, max, ave;
    uint64_t minU, maxU, aveU;
    uint32_t dummySum, dummySumU;
 
    dummySum = TestSum( &min, &max, &ave );
    dummySumU = TestSumUnrolled( &minU, &maxU, &aveU );
 
    printf( "Tempo de execucao           : %8llu, %8llu, %8llu\n", min, max, ave, dummySum );
    printf( "Tempo de execucao (Unrolled): %8llu, %8llu, %8llu\n", minU, maxU, aveU, dummySumU );
 
    return 0;
}

Testei este código no cygwin com o GCC 3.4.4, em uma máquina Pentium 4 HT 3 GHz, e obtive o seguinte resultado:

xxxx@yyyy /cygdrive/c/tmp/poc
$ g++ -O3 -o poc poc.cpp

xxxx@yyyy /cygdrive/c/tmp/poc
$ ./poc.exe
Tempo de execucao           :  3758910, 12396375,  4888809
Tempo de execucao (Unrolled):  3152730, 13149030,  4376331

Os valores podem variar um pouco, mas normalmente a versão “desenrolada” é um pouco mais eficiente do que a versão normal. Curiosamente isto nem sempre é verdade, experimente testar este código com o Microsoft Visual C++ 2005 e tente entender o que acontece.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License