Exemplos de Extreme Performance Optimizations

Chamo isso de Extreme porque não acho que seja algo que você queira confiar muito. Pode ser que em alguma arquitetura esses códigos não funcionem (é pouco provável, explico porquê mais adiante).

A primeira vez que vi algo assim foi no código-fonte do Quake. Eles resolveram um problema com cálculos do recíproco da raiz quadrada de um float usando esse tipo de codificação extrema. Eis um exemplo (antes de eu mostrar os do Quake). Suponha que vocẽ queira comparar um float com zero. Normalmente faria assim:

int CompareFloatF(float x)
{
  return (x == 0.0f);
}

Este código gera algo assim:

CompareFloatF:
  fld     DWORD PTR [esp+4]
  xor     edx, edx
  fldz
  mov     eax, 0
  fucomip st, st(1)
  fstp    st(0)
  setnp   dl
  cmove   eax, edx
  ret

Saiba que as instruções de ponto-flutuante fld, fucomip e fstp são LENTAAAAASSSS, como demonstrarei mais adiante. Uma maneira de fazer essa comparação com velocidade é usando do conhecimento da estrutura de um float, que é definida pelo padrão IEEE-754. Um float possui 32 bits de tamanho e sempre que você usa o valor 0.0f em seu código ele é equivalente a 0x00000000 (ou seja, todos os bits zerados). Assim, você pode escrever uma rotina assim:

int CompareFloatI(float x)
{
  return ( *(uint32_t *)&x == 0 );
}

Observe que tomamos o endereço do parâmetro x e convertemos o ponteiro para outro ponteiro do tipo uint32_t. Pegamos então o valor apontado por esse ponteiro e o comparamos com um inteiro sem sinal (zero). O código gerado é esse:

CompareFloatI:
  xor  eax, eax
  mov  edx, DWORD PTR [esp+4]
  test edx, edx
  sete al
  ret

Que é muitas vezes mais performático (e não usa ponto-flutuante!).

Eis uma comparação de performance usando o nosso rdtsc():

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

/* Funções definidas acima! */
extern int CompareFloatI(float);
extern int CompareFloatF(float);

int main(void)
{
  uint64_t t;
  int cmp;
  float x = 1.0f;

  BEGIN_RDTSC(t);
  cmp = CompareFloatI(x);
  END_RDTSC(t);
  printf("CompareFloatI returns %s\n", cmp?"true":"false");
  printf_rdtsc_results("CompareFloatI", t);

  BEGIN_RDTSC(t);
  cmp = CompareFloatF(x);
  END_RDTSC(t);
  printf("CompareFloatF returns %s\n", cmp?"true":"false");
  printf_rdtsc_results("CompareFloatF", t);

  return 0;
}

Executando e comparando o resultado:

$ gcc -mtune=native -O0 -fomit-frame-pointer \
  test.c rdtsc.c -o test
$ ./test
CompareFloatI() returns false
CompareFloatI: 42 cycles
CompareFloatF() returns false
CompareFloatF: 1939 cycles

Ou seja, a rotina CompareFloatF é cerca de 46 vezes mais lenta que a equivalente usando uint32_t.

Como eu disse, vi isso pela primeira vez no código-fonte do Quake. Olhem só:

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5f;

  x2 = number * 0.5f;
  y  = number;
  i  = * ( long * ) &y;           // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 );   // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration

#ifndef Q3_VM
#ifdef __linux__
  assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
  return y;
}

float Q_fabs( float f ) {
  int tmp = * ( int * ) &f;
  tmp &= 0x7FFFFFFF;
  return * ( float * ) &tmp;
}

Hardcore, eh?! Dê uma olhada nos comentários! Hehehe…

A primeira função, Q_rsqrt(), serve para calcular 1/√x. A segunda, Q_abs(), é óbvia, zerando o bit superior obtemos o valor absoluto do float! Ambas poderiam ser facilmente implementadas usando funções contidas no header math.h. Só que seriam muito lentas para as necessidades da ID Software:

float Q_rsqrt(float x)
{
  return ( 1.0f / sqrtf(x) );
}

float Q_abs(float x)
{
  return fabs(x);
}

O motivo pelo qual esse tipo de hack funciona na maioria das arquiteturas é justamente o padrão IEEE-754. Todo mundo segue isso!

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