Posibilidad de optimización para seguir operaciones de bits?

Question

¿Cree 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 la función más rápida, por lo tanto, quizás todavía haya una posibilidad de optimización.

Más detalladamente: Estoy escribiendo un juego de connect four. Recientemente utilicé el Profiler Very Sleepy y reconocí que la función haswon utiliza 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í que encontré en las fuentes del punto de referencia fourstones. La representación bitboard sigue:

. . . . . . . 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!

Edit: 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: haswon el original:

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 la str Para las pruebas de las TIC (los rendimientos intermedios obligar al compilador para evaluar las condiciones de uno en uno, en orden), así como las ramificaciones asociadas con múltiples sentencias 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 buen nivel de optimización que realmente puede pensar de 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.

En cuanto al 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 realmente lo ayude.