TAKESAKO @ Yet another Cybozu Labs

この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」を使うというアイディア

• http://pc8.2ch.net/test/read.cgi/tech/1136527588/688-700

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」命令が追加されるという話を思い出しました。

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

参考文献

• Microsoft Visual C++ 6.0 による最適化コードの開発（難易度：低レベル）
  http://www.microsoft.com/japan/msdn/vs_previous/visualc/techmat/feature/optcodedev/
• Intel Architecture Optimizations Manual
  http://www.intel.com/design/pentiumii/manuals/242816.htm
• Intel Architecture Optimization Reference Manual (Pentium II and Pentium III)
  http://developer.intel.com/design/PentiumII/manuals/245127.htm
• IA-32 Intel Architecture Software Developer's Manuals
  http://developer.intel.com/design/pentium4/manuals/index_new.htm