loop

Enquanto eu escrevia o post anterior, ainda acabei fazendo um mini-teste paralelamente.  Estão vendo o loop abaixo?

sub ecx, 1;
test ecx, ecx;
jnz loop_label;

Pois então, existe uma instrução em assembly que faz exatamente o mesmo que essas 3 instruções. Ela se chama loop.

loop loop_label;

Ela decrementa ecx e repete o loop enquanto ecx não for zero. Experimentei usar essa instrução, e o interessante é que em todos os testes ela foi mais lenta do que usar as 3 instruções separadamente! Isso acontecia nos dois processadores (Pentium 4 e Sempron). Não coletei resultados, mas a instrução loop demorava consistentemente alguns poucos ciclos a mais. Por isso optei pela versão mais rápida, com 3 instruções. Não que isso fosse fazer diferença nos resultados do post anterior, mas é interessante, né?

Anúncios

static_cast<int>(double_var);

Pois então, continuando o assunto do assembly do post anterior…

Segundo lia em vários lugares, truncar um double para um int é uma operação lenta na arquitetura x86, apesar de ser uma operação básica das linguagens C e C++. O interessante é que arredondar um número é mais rápido porque as flags do processador ficam por default no modo de arredondamento (depois de muito pesquisar, parece que esse default é pra obter mais precisão nas operações em geral, pois não é só a conversão pra int que faz uso dessa flag).

Então achei que esse seria um bom motivo pra aprender um pouco mais de assembly, já que o ganho de desempenho parecia ser significativo e alternativas usando construções de alto nível são esparsas: tem o lrint do C99, tem bibliotecas externas com uma função round, como o cvRound da OpenCV que usam assembly, mas nada suficientemente bom (você instalaria uma biblioteca só pra ter uma função round? é melhor copiar a função direto). E faria as medidas com outra instrução assembly, a rdtsc.

As funções que eu usei são as seguintes (se acharem algum erro, me avisem; assembly não é minha especialidade, hehe):

Pra obter o tempo atual:

/* O VC++ 2002 não aceita long long, vai __int64 mesmo... */
__declspec(naked) unsigned __int64 get_rdtsc()
{

__asm
{

push ebx;
xor eax, eax;
cpuid;
rdtsc;
pop ebx;
ret;

}

}

Pra fazer 400 conversões de double pra int em assembly, com fld seguido de fistp:

__declspec(naked)
unsigned __int64 asm_double_to_int(...)
{

__asm
{

/* Preferi fazer toda a manipulação da pilha à mão (por isso o __declspec(naked)) */
push ebp;
mov ebp, esp;
sub esp, 12;

call get_rdtsc;
mov dword ptr [ebp-8], eax;
mov dword ptr [ebp-4], edx;

mov ecx, 100; // Loop counter
loop_label:
fld qword ptr [ebp+8];
fistp dword ptr [ebp-12];

fld qword ptr [ebp+8];
fistp dword ptr [ebp-12];

fld qword ptr [ebp+8];
fistp dword ptr [ebp-12];

fld qword ptr [ebp+8];
fistp dword ptr [ebp-12];

sub ecx, 1;
test ecx, ecx;
jnz loop_label;

call get_rdtsc;

/*
A subtração de valores 64 bits eu tirei daqui:
win32-assembly-cheat-sheet
*/

sub eax, dword ptr [ebp-8];
sbb edx, dword ptr [ebp-4];

mov esp, ebp;
pop ebp;
ret;

}

}

Pra fazer 400 casts de double pra int em C++, com o mesmo tipo de loop feito:

/* Com as variáveis volatile o otimizador não remove código inútil... */
unsigned __int64 cast_double_to_int(volatile double a)
{

int i = 100;
unsigned __int64 t1 = get_rdtsc();
volatile int j;
do{

j = static_cast<int>(a);
j = static_cast<int>(a);
j = static_cast<int>(a);
j = static_cast<int>(a);

}while(--i);
unsigned __int64 t2 = get_rdtsc();
return t2 - t1;

}

O código do main está abaixo. Testo o arredondamento de 2 números (5.5 e 1.125) repetindo cada teste 8 vezes.

int main(int argc, char ** argv)
{

const int reps = 8;
unsigned __int64 tempo;
cout << "Assembly (default rounding):\nTest 1:\n";
for(int i = 0; i < reps; ++i){

tempo =
asm_double_to_int(5.5);
cout << tempo << '\n';

}
cout << "Test 2:\n";
for(int i = 0; i < reps; ++i){

tempo =
asm_double_to_int(1.125);
cout << tempo << '\n';

}
cout << "---------------------------------\nC++ cast (truncating):\nTest 1:\n";
for(int i = 0; i < reps; ++i){

tempo =
cast_double_to_int(5.5);
cout << tempo << '\n';

}
cout << "Test 2:\n";
for(int i = 0; i < reps; ++i){

tempo =
cast_double_to_int(1.125);
cout << tempo << '\n';

}
return 0;

}

Então vamos aos resultados. Fiz os testes no Visual C++ .NET 2002 e no Visual C++ .NET 2005 Express. Não testei com o GCC porque a sintaxe de inline assembly é meio esquisita e eu não aprendi direito. Testei em duas máquinas. Uma é um Intel Pentium 4 Northwood 2.4 GHz e o outro é um AMD Sempron Mobile 3000. Os resultados são em número de ciclos, não em segundos. Quanto mais ciclos, mais lento, mas só se a comparação for feita com outra execução no mesmo processador. A compilação é em modo Release (isto é, com otimizações).

VC++ 2002, Pentium 4 2.4GHz:


Assembly (default rounding):
Test 1:
2440
1540
1424
1424
1460
1424
1424
1460
Test 2:
1460
1460
1424
1424
1460
1424
1424
1424
---------------------------------
C++ cast (truncating):
Test 1:
26440
26236
25904
25904
26440
26440
25472
26440
Test 2:
26440
26452
25904
26440
25472
26808
25580
25904

========================

VC++ 2005, Pentium 4 2.4 GHz:


Assembly (default rounding):
Test 1:
2460
1412
1428
1412
1420
1412
1420
1420
Test 2:
1412
1420
1412
1424
1412
1412
1420
1412
---------------------------------
C++ cast (truncating):
Test 1:
8760
6896
6904
6900
6904
6904
7560
6892
Test 2:
6900
7248
6900
6904
6904
6904
6904
6904

========================
========================

VC++2002, Sempron Mobile 3000:


Assembly (default rounding):
Test 1:
992
877
877
877
877
877
877
877
Test 2:
877
877
877
877
877
877
877
877
---------------------------------
C++ cast (truncating):
Test 1:
8281
7366
7330
7294
7294
7294
7294
7294
Test 2:
7294
7294
7294
7294
7294
7294
7294
7294

========================

VC++2005, Sempron Mobile 3000:


Assembly (default rounding):
Test 1:
773
708
708
689
689
689
689
689
Test 2:
716
689
689
689
689
689
689
689
---------------------------------
C++ cast (truncating):
Test 1:
4902
4678
4678
4647
4922
4922
4922
4922
Test 2:
4695
4922
4922
4922
4922
4922
4922
4922

Conclusões:

1 – Dá pra ver que o Pentium 4 precisa de mais ciclos pra fazer a mesma coisa, por isso os Pentium 4 tinham freqüências maiores, pra compensar isso. (eu disse “tinham” porque a geração do Pentium 4 já passou, hehe)

2 – O VC++2002 executa o truncamento chamando uma função que arredonda e, se necessário faz uma subtração pra transformar o arredondamento em truncamento. O VC++2005 chama uma função que trunca usando uma instrução SSE2 (cvttsd2si) do processador, que é bem mais rápida, como dá pra ver. O programa decide dinamicamente se o SSE2 está disponível e usa a instrução em caso afirmativo. Nos testes, os 2 processadores tinham SSE2.

3 – Não importa qual seja a técnica usada pelo compilador, nem o processador, arredondar em assembly sempre resulta em menos instruções e maior desempenho do que truncar com um cast. Isso é interessante de ser feito quando você precisa de um int a partir de um double e não importa se vai truncar ou arredondar. Por exemplo, quando coordenadas em double precisam ser convertidas pra coordenadas de pixels, a diferença é minúscula, ainda mais se for uma animação. Outro caso é a linguagem Lua, que usa bastante a conversão de double pra int (pois todas as variáveis numéricas em Lua são double) e por isso usa este tipo de truque pra fazer a conversão, já que tanto truncar quanto arredondar servem.

Se você tem um loop interno fazendo muito dessas conversões de double pra int, convém considerar usar uma funçãozinha em assembly com fld e fistp como esta:

inline int double_to_int(double val)
{

int t;
__asm
{

fld val;
fistp t;

}
return t;

}

4 – Naturalmente, o assunto não está esgotado, pois existem muitos outros tipos de processador pra comparar, compiladores (que resultados será que o GCC e o compilador Intel gerariam?) e maneiras de truncar doubles, como por exemplo: fazer como o VC++2002 (com arredondamento e alguns testes); como VC++2005 (com SSE2); setando as flags do processador pra truncar (ruim porque exige esvaziar o pipeline, se os compiladores não geraram isso, deve ser lento, hehe); ou usar a instrução fisttp do SSE3 (sei que o meu Pentium 4 não a suporta; não tenho muita idéia do seu desempenho). Pra arredondar também deve haver mais algumas alternativas… Além de tudo isso poderia fazer experimentos setando as opções do compilador pra usar “fast math” e ver que código o compilador gera, mas daí eu não ia terminar nunca este post!!

Assembly, OCaml e o memory dump

Hoje eu ganhei uns bons pontos no meu nível nerd (isso é bom ou ruim?), porque estava mexendo com umas rotinazinhas em assembly e medindo o desempenho com a instrução rdtsc. Mas me deparei com um comportamento bizarro ao fazer a subtração dos tempos final e inicial que não consegui entender. E só acontecia compilando como Release, e com variáveis volatile (usei volatile pra tentar evitar que o otimizador removesse o código que eu estava tentando medir…). Nos outros casos funcionava tudo como esperado. Eu até ia postar os detalhes aqui, mas era muita coisa, preciso fazer mais uns testes antes. Se alguém quiser mais detalhes do que eu estava tentando fazer, é só deixar um recado! (duvido que alguém queira)

Pra quem estava mexendo com linguagens funcionais, ir pra assembly é um baita pulo. O OCaml é legal, mas faltam alguns detalhes pra ficar massa mesmo. Tem idéias legais como o pattern-matching e currying, e o nível de abstração é super-alto, mesmo compilando pra código nativo. A sintaxe é mais ou menos. A biblioteca padrão tem coisas interessantes, mas tem umas porcarias. Quem é que vai usar uma tabela associativa implementada com listas ligadas? Ainda bem que também tem hashtables. E como é que têm coragem de colocar um operador (@) que pode estourar a pilha com chamadas recursivas se bastaria fazer uma implementação iterativa (ainda bem que dá pra baixar separadamente uma biblioteca pra consertar isso). Tenho que conferir o F# também (da Microsoft) que é baseado em OCaml…

(este post foi completamente desorganizado, é mais ou menos um memory dump do que eu estou pensando agora…)