Bit İşlemlerini takip etme şansı nasıldır?

Question

Bu işlevin optimizasyonuna yer olduğunu düşünüyor musunuz (aşağıya bakınız)?

__int64 - unsigned __int64 için argüman türünü değiştirmenin işlevi daha hızlı yaptığını fark ettim, bu yüzden belki de optimizasyon için hala bir şans var.

Daha detaylı bilgi için: connect four oyununu yazıyorum. Son zamanlarda Profiler Çok Uykulu'u kullandım ve haswon işlevinin işlemci zamanının çoğunu kullandığını fark ettim. Fonksiyon, bir oyuncu için bağlantı dört kartının bir bitboard gösterimini kullanır. Fonksiyonun kendisi ben fourstones kriterlerinde bulundu. bitboard gösterimi takip ediyor:

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

fonksiyonu:

// 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; 
} 

teşekkürler!

Düzenleme: İşlemci x86, 32 Bit Mimarisi, Visual Studio 2008 Express Edition'dan Derleyici'yi kullanıyorum. Optimizasyon Bayrakları/O2/Oi/GL'dir.

Ben Jackson'ın önerdiği haswon2 işlevini denedim. Microsoft Compiler'daki derlemeler, sürüm zamanlamaları için varsayılan optimizasyon bayraklarıyla (/ O2/Oi/GL) neredeyse hiç çalışma zamanı farkı göstermiyor. VC-Derleyicisi gcc ile karşılaştırıldığında, her koşulun sıkı bir sırayla değerlendirilmemesi gerektiği konusunda avantaj sağlayamaz.

Sonuçlar: Orijinal haswon: Ben Jackson

haswon2:

Edit2: haswon ait Montaj:

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

Bu sürümde arkasındaki fikir str önlemek ıct test sırası (ara döner sırayla, teker şartlar birini değerlendirmek için derleyici zorlamak) yanı sıra dallanma çoklu bağlantılı olmadığını ifadeleri: Gerçekten düşünebiliriz optimizasyon iyi bir seviyeye sahip

// 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 | 
} 

w, x, y ve z değişkenli değerler için "diğer adlar" olarak. Bu, son dönüş ifadesinin, derleyicinin oynaması için tüm işlemi büyük bir çorbaya fırlattığı anlamına gelir. Sistemimde bu sürüm, orijinalin çalışma zamanının yalnızca% 65'ini alır (her seferinde rastgele bir konum oluşturma ek yükü dahil). Kurullar ağırlıklı olarak kazanamazsa daha büyük bir oranla kazanabilir.

Her birinin (gcc -O3'dan) sökülmesine bakıldığında, orijinal sürüm aslında daha kısadır, bu nedenle sıkı iç döngüde gerçekten yardımcı olan dallanma eksikliği olabilir.