SEMPRE meça a performance de seus códigos!

Esite é o melhor conselho que posso te dar. De tempos em tempos eu mesmo caio na arapuca de confiar que meus códigos são mais performáticos que códigos mais “modestos” porque eu “pensei em tudo”. Acabo de dando mal!

Um exemplo é uma simples rotina de multiplicação de matrizes que estou usando no código de meu projeto VirtualWorlds… A rotina multiplica duas matrizes 4×4, onde as matrizes são codificadas como column major (para satisfazer a especificação de OpenGL). Criei a rotina cuidadosamente, analizando o código em asm gerado pelo compilador em cada implementação. A rotina final é essa:

void Multiply4x4Matrices_SSE(float *out, const float *a, const float *b)
{
  int i, j;
  __m128 a_column, b_column, r_column;

  for (i = 0; i < 16; i += 4)
  {
    b_column = _mm_set1_ps(b[i]);
    a_column = _mm_load_ps(a);
    r_column = _mm_mul_ps(a_column, b_column);

    for (j = 1; j < 4; j++)
    {
      b_column = _mm_set1_ps(b[i+j]);
      a_column = _mm_load_ps(&a[j*4]);
      r_column = _mm_add_ps(_mm_mul_ps(a_column, b_column), r_column);
    }

    _mm_store_ps(&out[i], r_column);
  }
}

A rotina faz exatamente o que deve, ou seja, está correta. Note que apenas uma multiplicação e uma adição é feita no loop interno. Faço isso para aproveitar a característica SIMD (Single Instruction Multiple Data) do SSE, fazendo 4 multiplicações e 4 adições em apenas duas tacadas. Isso deveria acelerar a rotina em, pelo menos, uns 200% em relação à rotina original, abaixo:

void Multiply4x4Matrices(float *out, const float *a, const float *b)
{
  int i, j, k;

  for (i = 0; i < 4; i++)
  {
    for (j = 0; j < 4; j++)
    {
      out[i*4+j] = 0.0f;

      for (k = 0; k < 4; k++)
        out[i*4+j] += a[k*4+j] * b[i*4+k];
    }
  }
}

Essa ai contém 3 loops, fazendo um total de 64 iterações, contra as 16 iterações e operações “paralelas” da rotina anterior. Ela contém também uma inicialização desnecessária (zerando a posição de ‘out’). Claramente essa rotina é mais lenta, certo? ERRADO!

Vamos medir com o programinha abaixo:

int main(void)
{
  long long t1, t2;

  float a[] = {
     1.0f,  2.0f,  3.0f,  4.0f,   /* coluna 1 */
     2.0f,  3.0f,  4.0f,  1.0f,   /* coluna 2 */
     3.0f,  4.0f,  1.0f,  2.0f,   /* coluna 3 */
     4.0f,  1.0f,  2.0f,  3.0f    /* coluna 4 */
  };

  float b[] = {
     5.0f,  6.0f,  7.0f,  8.0f,   /* coluna 1 */
     6.0f,  7.0f,  8.0f,  5.0f,   /* coluna 2 */
     7.0f,  8.0f,  5.0f,  6.0f,   /* coluna 3 */
     8.0f,  5.0f,  6.0f,  7.0f    /* coluna 4 */
  };

  float out[16];

  START_CYCLE_COUNT(t1);
  Multiply4x4Matrices(out, a, b);
  STOP_CYCLE_COUNT(t1);

  printMatrix4x4(out);

  START_CYCLE_COUNT(t2);
  Multiply4x4Matrices_SSE(out, a, b);
  STOP_CYCLE_COUNT(t2);

  printf("\n\n");
  printMatrix4x4(out);

  printf("\n\nMultiply4x4Matrix: %lld cycles\n"
             "Multiply4x4Matrix_SSE: %lld cycles\n", t1, t2);

  return 0;
}

Onde printMatrix4x4() apenas imprime a matriz; START_CYCLE_COUNT e STOP_CYCLE_COUNT são macros definidas em cycle_counting.h, do meu sandbox (baixe aqui). O resultado é este:

$ gcc -O3 -msse -mtune=native mat4.c -o mat4
$ ./mat4
 70.0  64.0  62.0  64.0 
 64.0  70.0  64.0  62.0 
 62.0  64.0  70.0  64.0 
 64.0  62.0  64.0  70.0 


 70.0  64.0  62.0  64.0 
 64.0  70.0  64.0  62.0 
 62.0  64.0  70.0  64.0 
 64.0  62.0  64.0  70.0 


Multiply4x4Matrix: 468 cycles
Multiply4x4Matrix_SSE: 2006 cycles

Multiply4x4Matrices() gasta quase 1600 ciclos a menos que Multiply4x4Matrices_SSE()!!! Ou seja, minha rotina com SSE é pouco mais que 3 vezes mais lenta que a rotina original!

Então, ai vai, de novo: SEMPRE meça a performance de seus códigos!

ERRATA!!!

Fiquei inconformado com a diferença de performance e dei outra olhada na medição… Acabou que o código inicial, com SSE é mesmo mais rápido que o outro. O problema de medir ciclos usando minhas macros é que deve-se levar em conta os efeitos dos caches (especialmente o cache L1). Com uma única medida, após a limpeza dos caches devido à chamada cpuid(), o código com SSE tende a gastar um tanto a mais de ciclos que o código “normal”, mas uma vez no cache, o código é cerca de 40 ciclos mais rápido que o código “normal”. Basta medir assim:

START_CYCLE_COUNT(t1);
Multiply4x4Matrices(out, a, b);
Multiply4x4Matrices(out, a, b);
Multiply4x4Matrices(out, a, b);
Multiply4x4Matrices(out, a, b);
Multiply4x4Matrices(out, a, b);
Multiply4x4Matrices(out, a, b);
Multiply4x4Matrices(out, a, b);
Multiply4x4Matrices(out, a, b);
Multiply4x4Matrices(out, a, b);
Multiply4x4Matrices(out, a, b);
STOP_CYCLE_COUNT(t1);

printMatrix4x4(out);

START_CYCLE_COUNT(t2);
Multiply4x4Matrices_SSE(out, a, b);
Multiply4x4Matrices_SSE(out, a, b);
Multiply4x4Matrices_SSE(out, a, b);
Multiply4x4Matrices_SSE(out, a, b);
Multiply4x4Matrices_SSE(out, a, b);
Multiply4x4Matrices_SSE(out, a, b);
Multiply4x4Matrices_SSE(out, a, b);
Multiply4x4Matrices_SSE(out, a, b);
Multiply4x4Matrices_SSE(out, a, b);
Multiply4x4Matrices_SSE(out, a, b);
STOP_CYCLE_COUNT(t2);

printf("\n\n");
printMatrix4x4(out);

printf("\n\nMultiply4x4Matrices: %lld cycles\n"
           "Multiply4x4Matrices_SSE: %lld cycles\n", t1 / 10LL, t2 / 10LL);

Na média Multiply4x4Matrices() gasta cerca de 300 ciclos, enquanto Multiply4x4Matrices_SSE() gasta 260. Aumento de performance de cerca de 13% apenas, mas é, de fato, mais performático!

Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. 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 )

Foto do Google+

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

Conectando a %s