c++ - operaciones - rotacion de bits en c

¿Posibilidad de optimización para seguir operaciones de bits?

Question

¿Crees que hay espacio para optimizaciones en la función haswon (ver a continuación)?

Reconocí que cambiar el tipo de argumento de __int64 a unsigned __int64 hizo que la función fuera más rápida, por lo tanto, quizás todavía haya una posibilidad de optimización.

En más detalle: estoy escribiendo un juego de conectar cuatro . Recientemente utilicé Profiler Very Sleepy y reconocí que la función ya usó gran parte del tiempo de la CPU. La función utiliza una representación de bitboard de la conexión de cuatro placas para un jugador. La función en sí misma encontré en las fuentes del benchmark fourstones . La representación de bitboard es la siguiente:

. . . . . . . TOP
5 12 19 26 33 40 47
4 11 18 25 32 39 46
3 10 17 24 31 38 45
2 9 16 23 30 37 44
1 8 15 22 29 36 43
0 7 14 21 28 35 42 BOTTOM

La función:

// return whether newboard includes a win
bool haswon(unsigned __int64 newboard)
{
unsigned __int64 y = newboard & (newboard >> 6);
if (y & (y >> 2 * 6)) // check / diagonal
return true;
y = newboard & (newboard >> 7);
if (y & (y >> 2 * 7)) // check horizontal -
return true;
y = newboard & (newboard >> 8);
if (y & (y >> 2 * 8)) // check / diagonal
return true;
y = newboard & (newboard >> 1);
if (y & (y >> 2)) // check vertical |
return true;
return false;
}

¡Gracias!

Edición: CPU es x86, arquitectura de 32 bits, estoy usando el compilador de Visual Studio 2008 Express Edition. Los indicadores de optimización son / O2 / Oi / GL.

Probé la función haswon2 que sugirió Ben Jackson. Los ensamblados del compilador de Microsoft, con los indicadores de optimización predeterminados para las versiones de lanzamiento (/ O2 / Oi / GL), que muestran casi ninguna diferencia de tiempo de ejecución. Parece que el compilador VC en comparación con gcc no puede aprovechar que no debe evaluar cada condición en estricto orden.

Resultados: original de haswon:

haswon2 de Ben Jackson:

Edit2: Asamblea de haswon:

00401A10 mov eax,dword ptr [esp+4]
00401A14 mov ecx,dword ptr [esp+8]
00401A18 push ebx
00401A19 push esi
00401A1A push edi
00401A1B mov edx,eax
00401A1D mov edi,ecx
00401A1F shrd edx,edi,6
00401A23 mov esi,edx
00401A25 shr edi,6
00401A28 and esi,eax
00401A2A and edi,ecx
00401A2C mov edx,esi
00401A2E mov ebx,edi
00401A30 shrd edx,ebx,0Ch
00401A34 shr ebx,0Ch
00401A37 and edx,esi
00401A39 and ebx,edi
00401A3B or edx,ebx
00401A3D je `anonymous namespace''::haswon+35h (401A45h)
00401A3F mov al,1
00401A41 pop edi
00401A42 pop esi
00401A43 pop ebx
00401A44 ret
00401A45 mov edx,eax
00401A47 mov edi,ecx
00401A49 shrd edx,edi,7
00401A4D mov esi,edx
00401A4F shr edi,7
00401A52 and esi,eax
00401A54 and edi,ecx
00401A56 mov edx,esi
00401A58 mov ebx,edi
00401A5A shrd edx,ebx,0Eh
00401A5E shr ebx,0Eh
00401A61 and edx,esi
00401A63 and ebx,edi
00401A65 or edx,ebx
00401A67 jne `anonymous namespace''::haswon+2Fh (401A3Fh)
00401A69 mov edx,eax
00401A6B mov edi,ecx
00401A6D shrd edx,edi,8
00401A71 mov esi,edx
00401A73 shr edi,8
00401A76 and esi,eax
00401A78 and edi,ecx
00401A7A mov edx,esi
00401A7C mov ebx,edi
00401A7E shrd edx,ebx,10h
00401A82 shr ebx,10h
00401A85 and edx,esi
00401A87 and ebx,edi
00401A89 or edx,ebx
00401A8B jne `anonymous namespace''::haswon+2Fh (401A3Fh)
00401A8D mov edx,eax
00401A8F mov esi,ecx
00401A91 shrd edx,esi,1
00401A95 shr esi,1
00401A97 and esi,ecx
00401A99 and edx,eax
00401A9B mov eax,edx
00401A9D mov ecx,esi
00401A9F shrd eax,ecx,2
00401AA3 shr ecx,2
00401AA6 and eax,edx
00401AA8 and ecx,esi
00401AAA or eax,ecx
00401AAC jne `anonymous namespace''::haswon+2Fh (401A3Fh)
00401AAE pop edi
00401AAF pop esi
00401AB0 xor al,al
00401AB2 pop ebx
00401AB3 ret 

Answer 1

La idea detrás de esta versión es evitar el orden de prueba estricto (los retornos intermedios obligan al compilador a evaluar las condiciones una a la vez, en orden) así como la ramificación asociada con múltiples declaraciones if:

// return whether newboard includes a win
bool haswon2(uint64_t newboard)
{
uint64_t y = newboard & (newboard >> 6);
uint64_t z = newboard & (newboard >> 7);
uint64_t w = newboard & (newboard >> 8);
uint64_t x = newboard & (newboard >> 1);
return (y & (y >> 2 * 6)) | // check / diagonal
(z & (z >> 2 * 7)) | // check horizontal -
(w & (w >> 2 * 8)) | // check / diagonal
(x & (x >> 2)); // check vertical |
}

Con un nivel de optimización decente, realmente puede pensar en w, x, y y z como "alias" para los valores desplazados. Esto significa que la declaración de devolución final arroja toda la operación en una gran sopa para que el compilador juegue. En mi sistema, esta versión solo toma el 65% del tiempo de ejecución del original (incluida la sobrecarga de generar una posición aleatoria cada vez). Puede ganar por un porcentaje mayor si las juntas son principalmente no ganadoras.

Si miramos el desmontaje de cada uno (desde gcc -O3 ), la versión original es en realidad más corta, por lo que es probable que la falta de ramificación en el circuito interno apretado sea realmente útil.