Entry

プログラミングメモ - bswap 命令についてもう少し検証した

2010年03月11日

まだまだ気になる bswap 話。ま,ネタがあんまないというのもあるんですが。

前回使わせていただいたコードは,関数呼び出しのオーバーヘッドが気になったので,こんなテストコードを書いてみました。

#include <iostream>

#include <windows.h>

int
main(int argc, char* argv[]) {
  unsigned long n32 = 0x12345670UL;  // -4(%ebp)
  LARGE_INTEGER t1, t2, t3, t4, freq;
  const int COUNT = 100000000;

  // bit operator
  QueryPerformanceCounter(&t1);
  for (int i = 0; i < COUNT; ++i) {
    n32 = ((n32 & 0xff000000) >> 24) |
          ((n32 & 0x00ff0000) >> 8 ) | 
          ((n32 & 0x0000ff00) << 8 ) | 
          ((n32 & 0x000000ff) << 24);
  }
  QueryPerformanceCounter(&t2);

  // bswap
  QueryPerformanceCounter(&t3);
  for (int i = 0; i < COUNT; ++i) {
    asm("movl  -4(%ebp), %edx");
    asm("bswap %edx");
    asm("movl  %edx, -4(%ebp)");
  }
  QueryPerformanceCounter(&t4);

  // print result
  QueryPerformanceFrequency(&freq);
  double bitTime = static_cast<double>((t2.QuadPart - t1.QuadPart) * 1000) /
    static_cast<double>(freq.QuadPart);
  double swpTime = static_cast<double>((t4.QuadPart - t3.QuadPart) * 1000) /
    static_cast<double>(freq.QuadPart);

  std::cout << "bit  : " << bitTime << std::endl;
  std::cout << "bswap: " << swpTime << std::endl;

  return 0;
}

関数で呼び出すとオーバーヘッドが bswap の速度比に埋もれてしまう可能性があるので,main 関数ひとつにまとめて書いています。ちと読みにくいけれど,アセンブリにすると読みやすいと思う。あとは,時間計測用の関数を少し高級なもんにしたくらい。インラインアセンブリで EDX レジスタを使っているのは,変数 i のカウンタに EAX や ECX を使うことがあって,カウンタの値が上書きされてしまう可能性があるからです。カウンタを上書きしてしまうと,無限ループになってしまう可能性がある。ここでは,当て勘で空いてそうな EDX レジスタを決め打ちして使ってますけど,本当はどんなレジスタであれ push/pop して使うべきです。

一方,検証した PC のスペックは次の通り。

  • OS : Windows xp sp3 32 bit
  • CPU: AMD Athron(tm) 64 Processor 3200+ (2.0 GHz)
  • RAM: 3.06 GB (実装 4.0 GB)

で、結果は次の通りです。3回実行したときの時間を計測しました。

 最適化なし最適化あり(O1)
bit operatorbswapbit operatorbswap
1610.181483.669102.402357.152
2612.481483.639102.261354.791
3611.853482.799101.343355.630

最適化していないと,bswap の方が速いけれど,最適化すると,論理演算の方がかなり速くなるという結果に。おー……再現した(これが本当の原因かは分からないけど)。しかし,この数字はちと異常。最適化によってどんなコードが生成されているか見てみることにします。全部掲載すると長くなっちゃうので,一部だけ。g++ では次のように -S オプションを指定してアセンブリを出力することができます。

>g++ -Wall -W bswap.cpp -S

まず,最適化なし。また,コメントは aian の解説です。

    movl    $100000000, -68(%ebp)
    leal    -32(%ebp), %eax
    movl    %eax, (%esp)
    call    _QueryPerformanceCounter@4
    subl    $4, %esp
    ;; 論理演算の for-文
    movl    $0, -72(%ebp)
L11:
    cmpl    $99999999, -72(%ebp)
    jg      L12
    ;; バイト入れ替え
    movl    -20(%ebp), %eax
    andl    $-16777216, %eax
    movl    %eax, %edx
    shrl    $24, %edx
    movl    -20(%ebp), %eax
    andl    $16711680, %eax
    shrl    $8, %eax
    orl     %eax, %edx
    movl    -20(%ebp), %eax
    andl    $65280, %eax
    sall    $8, %eax
    orl     %eax, %edx
    movzbl  -20(%ebp),%eax
    sall    $24, %eax
    orl     %edx, %eax
    movl    %eax, -20(%ebp)
    leal    -72(%ebp), %eax
    incl    (%eax)
    jmp     L11
L12:
    leal    -40(%ebp), %eax
    movl    %eax, (%esp)
    call    _QueryPerformanceCounter@4
    subl    $4, %esp
    leal    -48(%ebp), %eax
    movl    %eax, (%esp)
    call    _QueryPerformanceCounter@4
    subl    $4, %esp
    ;; bswap の for-文
    movl    $0, -72(%ebp)
L14:
    cmpl    $99999999, -72(%ebp)
    jg	L15
/APP
    ;; アセンブリで挿入した箇所
    movl    -4(%ebp), %edx
    bswap   %edx
    movl    %edx, -4(%ebp)
/NO_APP
    leal    -72(%ebp), %eax
    incl    (%eax)
    jmp     L14

アセンブリを見て,うわっと思う方もいるかもしれないけれど,C/C++ のコードそのまんまなので,順番に丁寧に見ていけばどういう処理をしているか分かると思います。特に変わったコードは出力されていません。

続いて,O1 で最適化したときのコード。

    call    _QueryPerformanceCounter@4
    subl    $4, %esp

    ;; 論理演算の for-文
    movl    $0, %eax
L29:
    ;; バイト入れ替え????
    incl    %eax
    cmpl    $99999999, %eax
    jle     L29

    leal    -32(%ebp), %eax
    movl    %eax, (%esp)
    call    _QueryPerformanceCounter@4
    subl    $4, %esp
    leal    -40(%ebp), %eax
    movl    %eax, (%esp)
    call    _QueryPerformanceCounter@4
    subl    $4, %esp
    ;; bswap の for-文
    movl    $0, %eax
L33:
/APP
    ;; アセンブリで挿入した箇所
    movl    -4(%ebp), %edx
    bswap   %edx
    movl    %edx, -4(%ebp)
/NO_APP
    incl    %eax
    cmpl    $99999999, %eax
    jle	L33

えっと……強調したところを抜き出しますね。

    ;; 論理演算の for-文
    movl    $0, %eax
L29:
    ;; バイト入れ替え????
    incl    %eax
    cmpl    $99999999, %eax
    jle     L29

これ,何やってるか分かるでしょうか?最初に EAX レジスタに0を代入して,次にこいつをインクリメントします。さらにこのインクリメントした EAX レジスタの値と99999999を比べて,eax の値の方が小さかったら,L29 のラベルにジャンプする……と,こんな具合です。C/C++ で書くとこんな感じです。

  for (int i = 0; i < COUNT; ++i) {
    // 何もしない
  }

ということで,最適化の結果,バイト入れ替えの演算がごっそりとなくなってしまったのでした。そりゃ速くなるわ。空の for-文をクルクル回してるだけだもん。テストコードでは,変数 n32 をどこからも参照していないから,最適化の過程で「いらない処理」として省かれちゃったんですね。bswap の箇所は,ループの構造が少し変わっただけで,基本的な処理は残っています。

とゆことで,論理演算の方が速いという結果が出るケースのひとつとして,最適化されてコードがなくなっちゃった可能性が挙げられます。もちろん,これがテストになっていないことは明白なわけですが。もっとも,これだけが速くなる原因かというと,それは分かりません。本当に速くなるケースがあるかもしれない。

とりあえず,最適化オプションを付けた速度テストはとても難しいので,基本は付けない方がいいんだと思います。上のテストコードでコードが落ちないようにするためには,例えば,テストとテストの間に変数 n32 を参照する命令(値を出力するするとか,他の変数に代入するとか)をひとつ加えておけば,ある程度抑制することができます。もっとも,これでも足りない場合はあって,上のように即値(リテラル)を初期値として与えたような場合は,コンパイル時にあらかじめ計算しておくことで定数化してしまう最適化もあります。上のテストコードでは結果を静的に決定できるので,最適化レベルを上げると,変数 n32 を参照するコードがあっても,コンパイラが自分で計算してしまうかもしれない。

とま,bswap そのものとは関係なくなっちゃったけれども,そんな感じ。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN