Estoy experimentando con un lexer, y encontré que cambiar de un while-loop a un if-statement y un do-while-loop en una parte del programa me llevó a un código ~ 20% más rápido, lo que me pareció una locura. Aislé la diferencia en el código generado por el compilador a estos fragmentos de ensamblaje. ¿Alguien sabe por qué el código rápido es más rápido?¿Por qué este código de ensamblaje es más rápido?
En el conjunto, 'edi' es la posición actual del texto, 'ebx' es el final del texto, y 'isAlpha' es una tabla de búsqueda que tiene 1 si el carácter es alfabético y 0 en caso contrario.
El código lenta:
slow_loop:
00401897 cmp edi,ebx
00401899 je slow_done (4018AAh)
0040189B movzx eax,byte ptr [edi]
0040189E cmp byte ptr isAlpha (4533E0h)[eax],0
004018A5 je slow_done (4018AAh)
004018A7 inc edi
004018A8 jmp slow_loop (401897h)
slow_done:
El código rápido:
fast_loop:
0040193D inc edi
0040193E cmp edi,ebx
00401940 je fast_done (40194Eh)
00401942 movzx eax,byte ptr [edi]
00401945 cmp byte ptr isAlpha (4533E0h)[eax],0
0040194C jne fast_loop (40193Dh)
fast_done:
Si me quedo sólo estos fragmentos de montaje contra un megabyte de texto que consiste solamente en la letra 'a', el código rápido es un 30% más rápido. Mi suposición es que el código lento es lento debido a errores de predicción de las ramas, pero pensé en un ciclo que sería un costo de una sola vez.
Aquí está el programa que he utilizado para probar los dos fragmentos:
#include <Windows.h>
#include <string>
#include <iostream>
int main(int argc, char* argv[])
{
static char isAlpha[256];
for (int i = 0; i < sizeof(isAlpha); ++i)
isAlpha[i] = isalpha(i) ? 1 : 0;
std::string test(1024*1024, 'a');
const char* start = test.c_str();
const char* limit = test.c_str() + test.size();
DWORD slowStart = GetTickCount();
for (int i = 0; i < 10000; ++i)
{
__asm
{
mov edi, start
mov ebx, limit
inc edi
slow_loop:
cmp edi,ebx
je slow_done
movzx eax,byte ptr [edi]
cmp byte ptr isAlpha [eax],0
je slow_done
inc edi
jmp slow_loop
slow_done:
}
}
DWORD slowEnd = GetTickCount();
std::cout << "slow in " << (slowEnd - slowStart) << " ticks" << std::endl;
DWORD fastStart = GetTickCount();
for (int i = 0; i < 10000; ++i)
{
__asm
{
mov edi, start
mov ebx, limit
fast_loop:
inc edi
cmp edi,ebx
je fast_done
movzx eax,byte ptr [edi]
cmp byte ptr isAlpha [eax],0
jne fast_loop
fast_done:
}
}
DWORD fastEnd = GetTickCount();
std::cout << "fast in " << (fastEnd - fastStart) << " ticks" << std::endl;
return 0;
}
La salida del programa de prueba es
slow in 8455 ticks
fast in 5694 ticks
Eso * es * una locura: es una optimización muy común que los compiladores pueden hacer solos. En cuanto a por qué es más rápido, hay un salto menos por iteración en el código rápido, y los saltos solo tienen un rendimiento limitado. – harold
un perfilador de registro basado en el rendimiento probablemente arroje la mejor respuesta, pero aparte del obvio salto, supongo que el segundo bit de código es más rápido porque se adapta mejor a la caché de código (también hay pocos bytes para buscar y decodificar, pero esa sobrecarga no tiene sentido aquí). la alineación del objetivo de salto también puede ser otro factor, pero eso es difícil de decir aquí sin direcciones – Necrolis
Brian, ¿cuál es tu CPU? Eche un vistazo a http://www.agner.org/optimize/ Y harold, los jmps estáticos se predicen como siempre en las CPU modernas (no Atom) x86, por lo que no deberían costar nada. – osgx