Divisões nem sempre são maléficas!

Nos processadores mais antigos o uso de divisões era considerado maléfico para a performance. Afinal, divisões consomem bem mais ciclos de máquina do que multiplicações. Deem uma olhada nas rotinas abaixo:

#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include <xmmintrin.h>
#include "rdtsc.h"

typedef union
{
  float v[4] __attribute__((aligned(16)));
  __m128 x;
} vec4;

void VectorNormalize1(vec4 *out, vec4 *v)
{
  float len;

  out->v[0] = v->v[0];
  out->v[1] = v->v[1];
  out->v[2] = v->v[2];

  len = sqrtf((v->v[0] * v->v[0]) +
              (v->v[1] * v->v[1]) +
              (v->v[2] * v->v[2]));

  if (len != 0.0f)
  {
    out->v[0] /= len;
    out->v[1] /= len;
    out->v[2] /= len;
  }
}

void VectorNormalize2(vec4 *out, vec4 *v)
{
  float len;

  out->v[0] = v->v[0];
  out->v[1] = v->v[1];
  out->v[2] = v->v[2];

  len = sqrtf((v->v[0] * v->v[0]) +
              (v->v[1] * v->v[1]) +
              (v->v[2] * v->v[2]));

  if (len != 0.0f)
  {
    len = 1.0f / len;

    out->v[0] *= len;
    out->v[1] *= len;
    out->v[2] *= len;
  }
}

void VectorNormalize3(vec4 *out, vec4 *v)
{
  float len;
  vec4 temp;

  out->x = v->x;

  temp.x = _mm_mul_ps(v->x, v->x);
  len = sqrtf(temp.v[0] + temp.v[1] + temp.v[2]);

  if (len != 0.0f)
  {
    temp.x = _mm_set1_ps(len);

    /* A ordem aqui é importante! */
    out->x = _mm_div_ps(out->x, temp.x);
  }
}

void VectorNormalize4(vec4 *out, vec4 *v)
{
  float len;
  vec4 temp;

  out->x = v->x;

  temp.x = _mm_mul_ps(v->x, v->x);
  len = sqrtf(temp.v[0] + temp.v[1] + temp.v[2]);

  if (len != 0.0f)
  {
    temp.x = _mm_set1_ps(len);
    temp.x = _mm_rcp_ps(temp.x);
    out->x = _mm_mul_ps(temp.x, out->x);
  }
}

int main(void)
{
  vec4 v = { 1.0f, 1.0f, 1.0f, 1.0f };
  vec4 o;
  uint64_t t;

  BEGIN_RDTSC(t);
    VectorNormalize1(&o, &v);
  END_RDTSC(t);
  printf("VectorNormalize1() cycles: %llu\n", t);
  printf("o = { %.2f, %.2f, %.2f }\n", o.v[0], o.v[1], o.v[2]);

  BEGIN_RDTSC(t);
    VectorNormalize2(&o, &v);
  END_RDTSC(t);
  printf("VectorNormalize2() cycles: %llu\n", t);
  printf("o = { %.2f, %.2f, %.2f }\n", o.v[0], o.v[1], o.v[2]);

  BEGIN_RDTSC(t);
    VectorNormalize3(&o, &v);
  END_RDTSC(t);
  printf("VectorNormalize3() cycles: %llu\n", t);
  printf("o = { %.2f, %.2f, %.2f }\n", o.v[0], o.v[1], o.v[2]);

  BEGIN_RDTSC(t);
    VectorNormalize4(&o, &v);
  END_RDTSC(t);
  printf("VectorNormalize4() cycles: %llu\n", t);
  printf("o = { %.2f, %.2f, %.2f }\n", o.v[0], o.v[1], o.v[2]);

  return 0;
}

Você poderia esperar que VectorNormalize2 fosse mais veloz que VectorNormalize1, já que fazemos apenas uma divisão (para calcular o valor recíproco de len) e substituímos as 3 divisões por 3 multiplicações. Mas a medição dos tempos das rotinas demonstra justamente o contrário:

$ gcc -O0 -mtune=native -msse -mfpmath=both \
 -fomit-frame-pointer -o test test.c rdtsc.c -lm
$ ./test
VectorNormalize1() cycles: 2282
o = { 0.58, 0.58, 0.58 }
VectorNormalize2() cycles: 9730
o = { 0.58, 0.58, 0.58 }
VectorNormalize3() cycles: 336
o = { 0.58, 0.58, 0.58 }
VectorNormalize4() cycles: 301
o = { 0.58, 0.58, 0.58 }

De fato, a rotina VectorNormalize2 é quase 5 vezes mais lenta que sua equivalente usando divisões. Você pode argumentar que essas rotinas estão lentas graças a vetorização (SSE), mas se extirparmos VectorNormalize3 e VectorNormalize4 e compilarmos o código com a opção -mfpmath=387, obteremos o mesmo resultado para as duas primeiras rotinas.

É interessante notar que as rotinas equivalentes (VectorNormalize3 e VectorNormalize4), que usam SSE explicitamente, comportam-se de maneira contrária. A rotina VectorNormalize4 é um pouco (só um pouco!) mais rápida que VectorNormalize3. No SSE as divisões parecem ter o mesmo problema dos processadores antigos.

Aliás, coloquei as rotinas usando SSE para demonstrar esse ponto e também para mostrar que a rotina tradicional (que não usa SSE) é cerca de 8 vezes mais lenta do que sua equivalente que usa SSE, às vezes mais.

Como regra geral, meça a performance de seu código. Às vezes o senso comum não serve lá de muita coisa!

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