Binary Hacks と 64bit popCount 問題

各所レポートが挙がっている通り、私の手元にも Binary Hacks の献本が届きました!

表紙
Binary Hacks サポートページ
書名 Binary Hacks
サブタイトル ハッカー秘伝のテクニック100選
著者 高林哲,
鵜飼文敏,
佐藤祐介,
浜地慎一郎,
首藤一幸
出版社 オライリー・ジャパン
定価 3,360円 (税込)
ページ数 412ページ
ISBN 4-87311-288-5
発売日 2006年11月11日
版型 A5

高林さん、オライリーさん、ありがとうございます。

ちなみにetoさん情報によると、明日11/10は「いいバイナリの日」らしいです。

  • 11 → いい
  • 10 → バイナリ

Binary Hacks の発売日は 11/11 で、ビットが全部立っている非常に縁起の良い日です。

縁起を担ぐためにも、いいバイナリの日に Binary Hacks を注文して、発売日に書店に行って本を見かけたら 11 冊買いましょう。

x86 パフォーマンスチューニング

さて、最後の HACK #100「文献案内」でマイクロプロセッサアーキテクチャマニュアルが紹介されていましたが、
x86のパフォーマンスチューニングつながりということで、
ちょうど今日ラボの社内掲示板で盛り上がった話題をこちらでも共有したいと思います。

* popCount 問題

64bitの数値の中で1になっているビット数を数える

popCount64bitA

unsigned long long popCount64bitA(unsigned long long x) 
{
    int n = 0;
    n += popTable[x & 0xff];
    n += popTable[(x >> 8) & 0xff];
    n += popTable[(x >> 16) & 0xff];
    n += popTable[(x >> 24) & 0xff];
    n += popTable[(x >> 32) & 0xff];
    n += popTable[(x >> 40) & 0xff];
    n += popTable[(x >> 48) & 0xff];
    n += popTable[(x >> 56) & 0xff];
    return n;
}

popCount64bitB

unsigned long long popCount64bitB(unsigned long long x) 
{
    x = ((x & 0xaaaaaaaaaaaaaaaaUL) >> 1)
      +  (x & 0x5555555555555555UL);
    x = ((x & 0xccccccccccccccccUL) >> 2)
      +  (x & 0x3333333333333333UL);
    x = ((x & 0xf0f0f0f0f0f0f0f0UL) >> 4)
      +  (x & 0x0f0f0f0f0f0f0f0fUL);
    x = ((x & 0xff00ff00ff00ff00UL) >> 8)
      +  (x & 0x00ff00ff00ff00ffUL);
    x = ((x & 0xffff0000ffff0000UL) >> 16)
      +  (x & 0x0000ffff0000ffffUL);
    x = ((x & 0xffffffff00000000UL) >> 32)
      +  (x & 0x00000000ffffffffUL);
    return x;
}

→ どちらが速いか?

このpopCount問題は、去年岡野原さんに教えてもらいました。

テーブル参照で分岐命令をなくす

ちなみに最近のプロセッサは分岐予測・投機実行が失敗したときのコストが非常に高いので、
popTable[] は 8bit のテーブルで予め計算しておきます。

unsigned char popTable[256];
int popCount8bit(int x)
{
int n = 0;
if (x & 0x01) n++;
if (x & 0x02) n++;
if (x & 0x04) n++;
if (x & 0x08) n++;
if (x & 0x10) n++;
if (x & 0x20) n++;
if (x & 0x40) n++;
if (x & 0x80) n++;
return n;
}
void init_popTable()
{
int i;
for (i = 0; i < 256; i++) {
popTable[i] = popCount8bit(i);
}
}

ベンチマーク結果

実行結果(AMD Opteron 240EE / CentOS 4.4 x86_64 / gcc 3.4.6)

% gcc -O0 pop.c && ./a.out
loop=1000000
popCount32bitA(fffffffe)=31: 0.027621[sec]
popCount32bitB(fffffffe)=31: 0.025511[sec]
popCount64bitA(f0f0f0f0f0f0f0e1)=32: 0.049293[sec]
popCount64bitB(f0f0f0f0f0f0f0e1)=32: 0.038641[sec]

手元のx86_64環境では、テーブル参照を行なわない popCount64bitB の方が速い、という結果になりました。面白いですね。

Efficient Implementation of Population Count Function

以上の話をラボの社内掲示板に振ってみたところ、早速奥さんから
Athlon Code Optimization Guidelines (pp.136-139) に、もっと速いMMXのアセンブリコードが載っているよ、ということを教えてもらいました。

なるほど、勉強になります。pp.136-139から該当コードを抜粋します。

Example 1 (Integer Version):

unsigned int popcount(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);
}

これはMMX命令を使わない32bitバージョン。

Efficient 64-Bit Population Count Using MMX™ Instructions

The following code sample is an MMX version of popcount()
that works on 64 bits at a time. This MMX code can do
popcounts about twice as fast as the integer version (for an
identical number of bits). Notice that the source was loaded
using two instructions instead of a simple MOVQ to avoid a bad
STLF case (size mismatch from two DWORDs feeding into a QWORD).

Example 1 (MMX version):

#include "amd3d.h"
__declspec (naked) unsigned int __stdcall popcount64_1
(unsigned __int64 v)
{
static const __int64 C55 = 0x5555555555555555;
static const __int64 C33 = 0x3333333333333333;
static const __int64 C0F = 0x0F0F0F0F0F0F0F0F;
__asm {
MOVD MM0, [ESP+4]      ;v_low
PUNPCKLDQ MM0, [ESP+8] ;v
MOVQ MM1, MM0          ;v
PSRLD MM0, 1           ;v >> 1
PAND MM0, [C55]        ;(v >> 1) & 0x55555555
PSUBD MM1, MM0         ;w = v - ((v >> 1) & 0x55555555)
MOVQ MM0, MM1          ;w
PSRLD MM1, 2           ;w >> 2
PAND MM0, [C33]        ;w & 0x33333333
PAND MM1, [C33]        ;(w >> 2) & 0x33333333
PADDD MM0, MM1         ;x = (w & 0x33333333) + ((w >> 2) & 0x33333333)
MOVQ MM1, MM0          ;x
PSRLD MM0, 4           ;x >> 4
PADDD MM0, MM1         ;x + (x >> 4)
PAND MM0, [C0F]        ;y = (x + (x >> 4) & 0x0F0F0F0F)
PXOR MM1, MM1          ;0
PSADBW (MM0, MM1)      ;sum across all 8 bytes
MOVD EAX, MM0          ;result in EAX per calling convention
EMMS                   ;clear MMX state
RET 8                  ;pop 8-byte argument off stack and return
}
}

このように64bitのpopCountでMMX命令を使えば、32bitの処理を2回実行するよりも速く実行できるというお話。

* それSSEでやればいいんじゃね?

SSE(SIMD拡張命令)の「PSADBW」を使うというアイディア

688 :・∀・)っ-○◎● ◆DanGorION6 :2006/10/07(土) 15:13:39
てけとーにでっち上げてみた 
DWORD PopCountDW_SSSE3(DWORD src) {
DWORD 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で1命令でできるよ

次の Intel CPU で拡張される SSE4 でズバリそのものの「POPCNT」命令が追加されるという話を思い出しました。

後藤弘茂のWeekly海外ニュース: SSE4命令とアクセラレータから見えるIntel CPUの方向性
http://pc.watch.impress.co.jp/docs/2006/1004/kaigai307.htm より

また、IntelはSSE4に加えて、CPUに統合するアクセラレータコア向けの命令についても言及している。
これまでの汎用(General Purpose)CPUは、できる限り汎用的に使える命令を中心にしてきた(実際にはそうでもない命令もある)。だが、アクセラレータ命令は、それとは趣が異なる。非常にアプリケーションに特化した特殊な命令になるという。
その中で、Intelが最初に実装しようとしているのは「Cyclic Redundancy Check (CRC:巡回冗長検査)」のアクセラレーション。CRCアクセラレータのために、CRCバリューのチェックを行なう命令「CRC32」を実装するという。CRCは、データの完全性、つまり、データが破損しているかどうかをチェックする仕組み。対象とするデータから生成されるCRCバリューを比較することで、チェックを行なう。
CRCは通信やストレージでよく使われており、Intelもネットワークストレージをターゲットとすると説明している。Intelによると、「iSCSI(Internet Small Computer System Interface)」や「RDMA(Remote Direct Memory Access)」といったストレージのデータトランスファプロトコルのアクセラレートが主目的だという。現在は、こうしたプロトコル処理をCPUオフロードする専用チップも使われているが、Intelの構想はそれをCPUベースで取り込むことにある。CPUの汎用コアをオフロードするか、外付けのアクセラレータカードの必要性をなくすことで、システム全体の消費電力を下げることになる。
さらにIntelは、2つ目のアクセラレータ命令としてラージデータセットのサーチ向け命令「POPCNT」を挙げている。Population Count命令で、オペランド中のビットセットの数を数える。Intelは応用例としてゲノムマイニング、手書き認識、ハミングアルゴリズムなどを挙げている。

この「POPCNT」命令が普通のPCで使えるようになれば、全文検索エンジンのスコア計算(疎なビットベクトルから1の数を数える処理)とかをPCクラスタを使って高速に処理することができるようになるかも。機械学習の分野でも役立ちそう。

私はi386の頃のハンドアセンブルしかやったことがないのですが、どんどんx86のアーキテクチャは進化しているのですね。
まだまだバイナリアンの仕事はなくならない、ということみたい。自分ももっと勉強しなきゃ。

ということで、Binary Hacks には直接的なパフォーマンスチューニングのテクニックは書かれていませんが、以下の参考文献とあわせて読むと参考になるかもしれません。
これからバイナリアンを目指す方にもお勧めです。

参考文献

コメントは受け付けていません。