PopCntの速度再び2011
3年ほど前、popcntの速度を調べたことがありますが
http://d.hatena.ne.jp/mkomiya/20070905/p1
bitを数える
http://vivio.blog.shinobi.jp/Entry/137/
ふと思い出したので、またちょっと調べてみました。
以前は、ビット数少ないとアセンブラ速いけど
表引きC言語は安定してるよね
的な幕引きでしたが、
アセンブラでマジックで計算するコードをサイボウズラボの人が書いていたので、
http://developer.cybozu.co.jp/takesako/2006/11/binary_hacks.html
それを加えてみます。
あと、団子の人のSSEコードもあったのでそれも追加。
LS3600さんが、SSE4.2でPopCntの使い方も紹介されてましたが、
今使ってるマシン(core2duo E7500)がSSE4.1なので、SSE4.2はビルドはできるけど
実行するとエラーになりました（残念）
http://d.hatena.ne.jp/LS3600/20091218/p1
っていうか、phenomII x6もSSE4.1らしいよ。えー。
出場選手
・アセンブラでループ
・C言語でマジック
・アセンブラでマジック
・SSE命令でマジック
0x00000001 PopCnt=1 asm(loop)=0.30 asm(magic)=0.55 c++=1.25 SSE=0.45 0x00000103 PopCnt=3 asm(loop)=0.41 asm(magic)=0.53 c++=1.27 SSE=0.44 0x0000050b PopCnt=5 asm(loop)=0.47 asm(magic)=0.53 c++=1.27 SSE=0.44 0x0000152b PopCnt=7 asm(loop)=0.67 asm(magic)=0.53 c++=1.25 SSE=0.45 0x000055ab PopCnt=9 asm(loop)=0.78 asm(magic)=0.55 c++=1.25 SSE=0.44 0x000157ab PopCnt=11 asm(loop)=0.84 asm(magic)=0.53 c++=1.27 SSE=0.44 0x00055fab PopCnt=13 asm(loop)=0.97 asm(magic)=0.53 c++=1.27 SSE=0.44 0x00157fab PopCnt=15 asm(loop)=1.08 asm(magic)=0.55 c++=1.25 SSE=0.45 0x0055ffab PopCnt=17 asm(loop)=1.20 asm(magic)=0.53 c++=1.26 SSE=0.44 0x0157ffab PopCnt=19 asm(loop)=1.33 asm(magic)=0.55 c++=1.25 SSE=0.45 0x055fffab PopCnt=21 asm(loop)=1.45 asm(magic)=0.53 c++=1.25 SSE=0.45
※それぞれ9000万回実行
マジックのアセンブラ激速！ SSEにしても大差なし？
SSE版はメモリアクセスしてところが遅くなってそう？
マジックなアセンブラのソースと、SSEでマジックなソース
unsigned int PopCnt32c(unsigned int v)
{
unsigned int retVal;
__asm {
MOV EAX, [v] ;v
MOV EDX, EAX ;v
SHR EAX, 1 ;v >> 1
AND EAX, 055555555h ;(v >> 1) & 0x55555555
SUB EDX, EAX ;w = v - ((v >> 1) & 0x55555555)
MOV EAX, EDX ;w
SHR EDX, 2 ;w >> 2
AND EAX, 033333333h ;w & 0x33333333
AND EDX, 033333333h ;(w >> 2) & 0x33333333
ADD EAX, EDX ;x = (w & 0x33333333) + ((w >> 2) & 0x33333333)
MOV EDX, EAX ;x
SHR EAX, 4 ;x >> 4
ADD EAX, EDX ;x + (x >> 4)
AND EAX, 00F0F0F0Fh ;y = (x + (x >> 4) & 0x0F0F0F0F)
IMUL EAX, 001010101h ;y * 0x01010101
SHR EAX, 24 ;population count = (y * 0x01010101) >> 24
MOV retVal, EAX ;store result
}
return (retVal);
}
//・∀・）っ-○◎● ◆DanGorION6
unsigned int PopCnt32_SSE(unsigned int src)
{
unsigned int dest;
static const __m128i table = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
__asm {
movd xmm1, dword ptr [src]
movdqa xmm0, xmm1
psrlq xmm1, 4
punpckldq xmm0, xmm1
pshufb xmm0, xmmword ptr [table]
pxor xmm1, xmm1
psadbw xmm0, xmm1
movd dword ptr [dest], xmm0
}
return dest;
}
SSE4.2なCPUだと、
_mm_popcnt_u32(a)
で組み込みPopCntが可能
#include "intrin.h"
