mitsunari@cybozu labs

Shibuya.JSで発表したppt資料を置きました．
ppt

内容の詳細は後日．

出張Shibuya.js 24の発表資料の中の，JavaScriptで実行時に関数を書き換えることで高速化する例を紹介します．オリジナルアイデアはokuさんで，JavaScriptの勉強のために私もやってみました．

ここでは二つの関数unrollLoop()とforceInline()を作ってみました．たとえば，

add3 : function(y) {
    return y + 3;
}

と

addF : function(x) {
    var z = 2;
    for (var i = 0; i < 3; i++) {
        z += this.add3(i);
    }
    return z;
}

という関数があるとします．
addF()に対してblowfish.js(仮実装なので実用性はまだありません)にあるunrollLoop()を適用すると，addF()が書き換えられて

function(x) {
    var z = 2;
        z += this.add3(0);
        z += this.add3(1);
        z += this.add3(2);
    return z;
}

とループ展開されます．更にforceInline()を適用すると，

function(x) {
    var z = 2;
    {
        var _y = 0; z+=(_y + 3);
    }
    {
        var _y = 1; z+=(_y + 3);
    }
    {
        var _y = 2; z+=(_y + 3);
    }
    return z;
}

とインライン展開されます．
ここではBlowfish暗号化のコア部分の最適化を各種方法で試した速度比較をするデモ(JavaScriptを有効にしてください)を用意しました．
比較対象はoriginal(リファレンス実装)，自動インライン展開，自動ループ展開，自動インライン展開 + ループ展開，手動最適化の五つです．それらの処理時間を測定し，オリジナルに対する速度比を表示します．

上記のようにIE6で1.73倍，Fxで1.41倍高速化されました．特にFxでは手動最適化にかなり近い値となっています．オリジナルコードに1, 2行追加するだけこの速度向上を得たわけですから，このような手法が有効であることがわかりました．

なお，これらの関数は暫定版なので，複雑な式だとうまく展開できません(ソースをみればわかりますがかなりの手抜きです)．

# 引き数を一つしかとれない．'{}'の対応をチェックをきちんとしていない．returnで終わってないといけないなど．

しかし，比較的効率よく高速化されることが分かりましたのでライブラリとして完成度をあげてみるのも面白いかと思います．

ここでは何回かに分けてx86(IA-32)，いわゆる普通のPentiumパソコンで使われている機械語の説明をする予定です．
アセンブラ，アセンブリ言語としては拙作のXbyakを使うことにしました．
理由は，

• 普通のgasやNASMによる解説はありふれていること
• Windows，Linux，Intel Macで同じソースが使え，C++だけで閉じているためアセンブラの設定に悩まなくてすむこと
• JITなどの特殊な最適化ができること

などがあります(半分は自己満足ですね)．

内容は基本的なところから始めますが，場合によってはマニアックネタに走るかもしれません．最初のうちはx86アセンブリ言語入門と重複することも多いと思います．

以下は単なる私の価値観ですが，機械語を絶対に知っておくべきものであるとは思いません．けれども何事もかじってみるのは悪くないと思います．
必要だから勉強する，不要だから勉強しないという合理的な判断は好きではありません．知りたい，興味があるから勉強してみるという素朴な動機が大事だと思います．

閑話休題

まずXbyakをインストールしましょう．XbyakはIntel，AMDなどのPentium互換CPUが搭載されたWindows Xp，Vista，Linux，Macの32bit OSで動作し，開発にはC++コンパイラを使います．Visual C++ 6 + STLport(必須)，Visual Studio 2005 Professional/Expression, Linux gcc 4.x, Intel Macなどで動作確認をしています(もしかしたらsecure OSではセキュリティレベルを下げないと動かないかもしれません)．
zipファイルを上記ページからダウンロードしてきて展開します．

VC系の場合はxbyak.dswを開いてtest0をコンパイル，Linux，Macの場合はmakeでサンプルプログラムができます．

>./test0
xbyak version=1.06
0 + ... + 0 = 0
0 + ... + 1 = 1
0 + ... + 2 = 3
0 + ... + 3 = 6
0 + ... + 4 = 10
0 + ... + 5 = 15
0 + ... + 6 = 21
0 + ... + 7 = 28
0 + ... + 8 = 36
0 + ... + 9 = 45
0 + ... + 10 = 55
0 + 0 = 0
1 + 1 = 2
2 + 2 = 4
3 + 3 = 6
4 + 4 = 8
5 + 5 = 10
6 + 6 = 12
7 + 7 = 14
8 + 8 = 16
9 + 9 = 18
call atoi("123") = 123
jmp atoi("456") = 456
OK

の様に表示されればOKです．もし，ビルドエラーになる，動かないなどがあれば環境とエラー内容を教えていただけるとありがたいです．

インストールするにはLinux，Macの場合はrootになって

make install

とすると/usr/local/include/xbyakにインストールされます．

WindowsのVisual Studio 6の場合は[オプション]→[ディレクトリ]，Visual Studio 2005 Expressionなどの場合は[ツール]→[オプション]→[プロジェクトおよびソリューション]→[VC++ディレクトリ]→[インクルードファイル]でincludeディレクトリに展開したxbyakディレクトリを追加してください．

サンプルプログラムについて

test0

1から10までの和や，足し算，atoi()の呼び出しテストです．

quantize

JPEGやMPEGで使われる量子化のサンプルです．起動して1～100の数値を入力してください．最初にC版，次にxbyakによる演算時間が表示されます．

calc

簡単な関数計算デモです．引数に"x*(x+1)"などを与えて実行してください．このデモのコンパイルにはboostのインストールが必要です．

bf

BrainfuckJIT環境です．./bf hello.bfとしてください．

今回はXbyakのインストール方法について説明しました．次回はサンプルプログラムの説明などをする予定です．

前回言い忘れましたが，このシリーズの目標はLL魂2007デモコードのchaos.cpp程度のものを読めて理解できることを考えています．
具体的には

• レジスタやスタックを理解する
• 関数を作れる
• SIMD命令の基礎を知る
• JITのメリットを理解する

あたりを目指します．なお，JITアセンブラは通常のアセンブラに比べてワンクッション概念が必要になります．もしかしたらアセンブリ言語の本当の入門としては不適切かもしれませんが，まあご了承ください．

それでは，最初に他の言語と同様，"Hello Xbyak!"を表示してみましょう．

#include "xbyak/xbyak.h"
#include <stdio.h>
 
struct HelloGenerator : public Xbyak::CodeGenerator { // (A)
    HelloGenerator() // (B)
    {
        push((int)"Hello Xbyak!"); // (C1)
        call((int)puts); // (C2)
        add(esp, 4); // (C3)
        ret(); // (C4)
    }
};
 
int main()
{
    HelloGenerator hello; // (D)
    void (*code)() = (void (*)())hello.getCode(); // (E)
    code(); // (F)
    return 0;
}

VC系ではコンソールアプリとしてコンパイルしてください．
gccでは-fno-operator-namesをつけるのを忘れないでください．これはandやorを演算子ではなく関数として扱いたいためです．

> g++ t.cpp -g -fno-operator-names
> ./a.out
> Hello Xbyak!

# C++的には

#include <stdio.h>
int main(int argc, char *argv[])
{
    argc == 1 and puts("need option");
}

ってできたのご存じでした?

それはともかくコードの説明に入ります．Xbyakでは実行時に命令をアセンブルしてバイトコード(以下マシン語と呼ぶことにします)を生成します．それを生成するためのクラスがXbyak::CodeGeneratorであり，これを継承する(A)ことでそのクラス内でx86の殆どの命令を記述できるようになります．

今後も繰り返すことになるかと思いますが，コンパイル時ではなく実行時であることに注意してください．ここではHelloGeneratorのコンストラクタにXbyak命令(面倒なので以後asmと呼びます)を記述している(B)ので，main()内のインスタンスhelloが生成されたとき(D)にアセンブルされます．

アセンブルされたマシン語はgetCode()メソッドで取得できます(E)．この返り値は生成されたマシン語へのポインタですので，適当な関数ポインタ(詳細は後述)にキャストし，その関数を呼び出すことでマシン語を実行します(F)．

以上がXbyakを使った場合の大まかな流れです．

続いて実行時の挙動を追いかけてみましょう．

VC系ではDebugモードでコンパイルし，(F)のところにブレークポイントを置いてデバッグ実行します．停止したところでVC6なら[表示]→[デバッグウィンドウ]→[混合モード]，VC8なら[デバッグ]→[ウィンドウ]→[逆アセンブル]で

19:       code();
00401696 8B F4                mov         esi,esp
00401698 FF 95 F4 FE FF FF    call        dword ptr [ebp-10Ch]
0040169E 3B F4                cmp         esi,esp
004016A0 E8 2B 14 01 00       call        __chkesp (00412ad0)

というようなウィンドウに入ってください．[F10]を一度押し，callのところで[F11]を押すと

003730A4 68 B0 01 44 00       push        offset string "Hello Xbyak!" (004401b0)
003730A9 E8 62 FA 09 00       call        puts (00412b10)
003730AE 83 C4 04             add         esp,4
003730B1 C3                   ret

が表示されると思います．左端の数値は違うかもしれません．意味も今は分からなくて結構です．ただ上記サンプルの(C1)～(C4)に対応していることを確認してください．

gccの場合はgdbを使っておっかけましょう．まず起動してgetCode()のところでブレークポイントを置きます．

>gdb ./a.out
>b HelloGenerator.getCode
Breakpoint 1 at 0x804b2b6: file xbyak/xbyak.h, line 1307.

実行した後，[n]と[Enter]でステップ実行し，code()の直前まで進みます．

(gdb) r
Starting program: /home/shigeo/Program/xbyak/a.out
Breakpoint 1, Xbyak::CodeGenerator::getCode (this=0xbffff2e0) at xbyak/xbyak.h:1307
1307                    assert(!hasUndefinedLabel());
(gdb) n
1309                    return top_;
(gdb)([Enter]を押す)
1310            } ([Enter]を押す)
(gdb) ([Enter]を押す)
main () at t.cpp:19
19              code();

ここでコードがどうなっているか見ます．その前にデバッグに見やすいaliasを作っておきます．

(gdb) define al
Type commands for definition of "al".
End with a line saying just "end".
>x/11i $pc
>end

と定義してみてください．

(gdb) al
0x8048904 <main+52>:    mov    eax,DWORD PTR [ebp-12]
0x8048907 <main+55>:    call   eax
0x8048909 <main+57>:    mov    ebx,0x0
0x804890e <main+62>:    lea    eax,[ebp-0x108]
0x8048914 <main+68>:    mov    DWORD PTR [esp],eax
0x8048917 <main+71>:    call   0x8049c2c <~HelloGenerator>
0x804891c <main+76>:    mov    DWORD PTR [ebp-0x10c],ebx
0x8048922 <main+82>:    jmp    0x8048952 <main+130>
0x8048924 <main+84>:    mov    DWORD PTR [ebp-0x110],eax
0x804892a <main+90>:    mov    ebx,DWORD PTR [ebp-0x110]
0x8048930 <main+96>:    lea    eax,[ebp-0x108]

siを使ってasmレベルでのステップ実行をします．

(gdb) si
0x08048907      19              code();
(gdb) ([Enter]を押す)
0x0804c190 in ?? ()

call eaxが実行された瞬間からXbyakが生成したマシン語に突入しています．alで確認しましょう．

(gdb) al
0x804c194:      push   0x804b44b
0x804c199:      call   0x8048734 <puts@plt>
0x804c19e:      add    esp,0x4
0x804c1a1:      ret

やはり上記サンプルの(C1)～(C4)に対応していることを確認してください．
うっかり行き過ぎたら，最初からやり直してマシン語を一行ずつ実行する感じをつかんでください．gdbを使うときはアセンブラで遊ぶ時に便利なgdb設定を参考にすると便利だと思います．上記alもこのリンク先の.gdbinitで定義されているのを拝借しました．

今回はXbyakの基本的な書き方と実行時に確認する方法の説明をしました．長くなりましたので一端区切ります．次はコードの説明に入ります．