您认为函数 haswon(见下文)还有优化空间吗?
我认识到将参数类型从 __int64
更改为 unsigned __int64
会使函数更快,因此我认为也许还有优化的机会。
更详细: 我正在写 connect four游戏。最近我使用了 Profiler Very Sleepy,发现函数 haswon 占用了很多 CPU 时间。该函数为一个玩家使用连接四板的位板表示。我在 fourstones 的来源中找到的函数本身基准。位板表示如下:
. . . . . . . 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
功能:
// 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;
}
谢谢!
编辑: CPU 是 x86,32 位架构,我使用的是 Visual Studio 2008 Express Edition 的编译器。优化标志是/O2/Oi/GL。
我尝试了 Ben Jackson 建议的函数 haswon2。来自 Microsoft 编译器的程序集,带有用于发布版本 (/O2/Oi/GL) 的默认优化标志,几乎没有运行时差异。与 gcc 相比,VC 编译器似乎无法利用它不能严格按顺序评估每个条件。
结果: 哈斯温原件:
来自本 jackson 的haswon2:
编辑2: 哈斯旺大会:
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
最佳答案
此版本背后的想法是避免严格的测试顺序(中间返回迫使编译器按顺序一次评估一个条件)以及与多个 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 |
}
通过相当程度的优化,您可以真正将 w、x、y 和 z 视为移位值的“别名”。这意味着最终的 return 语句将整个操作扔进了一大堆供编译器使用的汤。在我的系统上,这个版本只占用原始版本运行时间的 65%(包括每次生成随机位置的开销)。如果棋盘主要是非获胜,它可能会以更大的百分比获胜。
查看每个(来自gcc -O3
)的反汇编,原始版本实际上更短,因此很可能是紧密内部循环中缺少分支确实有帮助。
关于c++ - 跟随位操作的优化机会?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4261332/