CPU＜（我の真の力を見せるときがきた！） -Data Oriented Programming-

今回もまさかり期待です！！図はありません！！

オブジェクト指向プログラミングはCPUに優しくないです。
データ指向プログラミングがパフォーマンス問題への解法の一つになります。

CPUの中の人

まず基本事項の確認から！
CPUに比べて、メインメモリは非常に遅いです。数倍というレベルではなく、ゼロが何個もつくレベルで遅いです。
そこでCPUの中の人は考えました。

「メインメモリは一度に全部アクセスするわけじゃない。偏ってるんだ。ならば、偏った部分だけを、小さいけど早いメモリに置けば解決するかも！？」

はい、キャッシュの誕生です。

しかし、メインメモリからキャッシュにデータを運ばないといけません。これを1byteずつチミチミ送ってたのでは、遅くて本末転倒です。
なので、アクセスがあった箇所周辺をごそっと転送するのです。 （キャッシュライン）
ごそっと取ってきた場所以外を取ってくる場合、当然キャッシュに無いので、メインメモリから取ってきます。 （キャッシュミス）

つまり、

メモリアクセスは集中したほうがよい

のです。

高級オブジェクト指向言語はCPUいじめ

さて、JavaScriptのコード片のメモリ配置を見てみましょう。

var elements = [new Hoge(), new Fuga()];

/** その後…… **/

elements[0].attr = "hoge!";
elements[1].attr = "fuga!";

まずelementsという配列がありますね。これもメモリ上に配置されます。
HogeとFugaがnewされています。つまりこの二つもメモリに配置。配列にはこの二つのオブジェクトを参照する情報が書き込まれます。
そして間を置いて、それぞれのattrに違う文字列が格納されています。これもメモリ上に置かれます。

これを中の人になって見てみましょう。

1. よーし、elementsをメインメモリに作ったよ！
2. new Hoge(), new Fuga()っと。HogeとFugaをメインメモリに確保！
3. ごにょごにょ。
4. うん、elementsがいるな、elementsをキャッシュにロード！ついでに周りのもロードしよう、後でいるかもしれないし。
5. elementsの0番目だな、キャッシュにある。楽勝楽勝。
6. あれ、これ参照情報だよ、elementsの0番目が差してるメモリを読み込みにいかないと。めんどくさいなあ。 （キャッシュミス）

つまり、オブジェクトがオブジェクトを参照していて、そのオブジェクトがメモリ配置的に近くないと、キャッシュミスが発生するのです。

メッセージパッシングはオブジェクト指向の基本パーツです。そしてメモリ配置はいじれない言語が多いです。
つまり、高級オブジェクト指向言語は CPUに優しくない のです。

実際どうなの（そして驚愕のV8）

ほんとかどうかベンチマークしましょう。そうしましょう。

var N = 100000;

function times(count, fn){
    for(var n = 0; n < count; ++n){
        fn();
    }

}

function stopWatch(disp, fn){
    var T = 10;
    var time = Date.now();
    times(T, fn);
    console.log(disp + ": " + (Date.now()-time)/T);
}

function createCanvasElements(num){
    var elements = [];
    for(var n = 0; n < N; ++n){
        elements.push(new tm.display.CanvasElement());
    }

    return elements;
}

function tmSetPosition(){
    var elements = createCanvasElements(N);
    return function(){
        for(var n = 0, l = elements.length; n < l; ++n){
            elements[n].setPosition(30, 50);
        }
    }
}

function objectSetPosition(){
    var elements = [];

    function MyObject(){
        this.x = 0;
        this.y = 0;
    }

    for(var n = 0; n < N; ++n){
        var obj = new MyObject();
        elements.push(obj);
    }

    return function(){
        for(var n = 0, l = elements.length; n < l; ++n){
            elements[n].x = n;
            elements[n].y = n;
        }
    }
}

function directSetPosition(){
    var elements = createCanvasElements(N);

    return function(){
        for(var n = 0, l = elements.length; n < l; ++n){
            elements[n]._matrix.m[0] = 30;
            elements[n]._matrix.m[1] = 50;
        }
    }
}

function rawSetPosition(factory){
    var elements = factory();
    for(var n = 0; n < N*2; ++n){
        elements[n] = 0;
    }

    return function(){
        for(var n =0; n < N; ++n){
            var b = n * 6;
            elements[b] = 30;
            elements[b+1] = 50;
        }
    }
}

tm.main(function(){
    stopWatch("object", objectSetPosition());
    stopWatch("rawTyped", rawSetPosition(function(){return new Float32Array(N*2);}));
    stopWatch("rawUntyped", rawSetPosition(function(){return [];}));
    stopWatch("direct", directSetPosition());
    stopWatch("tm", tmSetPosition());
});

Real Worldのライブラリの例としてtmlib.jsを借りています。
そしてChrome x MBP（えへん！）での実行結果がこれです。

object: 0.2 
rawTyped: 0.2 
rawUntyped: 1.9 
direct: 2.1 
tm: 1.8 

object: 配列にオブジェクトを突っ込んでアクセス
rawTyped: TypedArrayに数値を突っ込んでアクセス
rawUntyped: Arrayに数値を突っ込んでアクセス
direct: tmlib.jsのmatrix要素に直接アクセス
tm: tmlib.jsのメソッドを経由してアクセス

メモリブロックをJavaScriptで表現できるのはTypedArrayしかありませんので、それと比較しましょう。
rawTypedとtm/directの結果を比べると、実に１０倍の差がついています。
また、tmlib.jsのMatrix33クラス内部をTypedArrayに変えてみましたが、差はあまりかわりませんでした。よってTypedArrayが速いから、というわけではなさそうです。

様々な要因は考えられますが。directでも差が縮まらなかったことを考えるに、キャッシュミスの可能性が高いです。

…それよりも気になりませんか。 objectとrawTypedのスコアが同じ ことに！！

なんとV8は、Arrayに同一hidden classのオブジェクトを突っ込むと、自動的にunboxingして突っ込むようです。つまりは、内部的にはrawTypedと同じなのです。なんだこの黒魔術……

Data Oriented Programming

少し話題がそれました。（V8怖い（（（・v・））））

ではどうすればCPUに優しいプログラムになるのか。
ここではパラダイムの変換による根本的な解決法を提示します。
それがData Oriented Programmingです。(!= Data Driven Programming!)

DOPはまだ明確に定義されたものではないようですが、以下のコンセプトのようです。

• 直列に配置されたデータに、逐次データ加工を行う

コードで示します。以下は普通のオブジェクト指向。

function process(){
    for(var n = 0, l = actors.length; n < l; ++n){
        actors[n].randomizePosition();
    }
}

OneActor.prototype.randomizePosition = function(){
    this.x += Math.random() * 1000;
    this.y += Math.random() * 1000;
}

データを外部から守るのがオブジェクト指向の基本的な考え方の一つです。よってこうなります。では、DOPで実装するとどうなるのでしょうか。

function process(){
    for(var n = 0, l < actors.length; n < l; ++n){
        randomizePosition(actors[n]);
    }
}

function randomizePosition(actor){
    actor.x = Math.random() * 1000;
    actor.y = Math.random() * 1000;
}

加工関数に対して、内部データが丸見えです。
ただの手続き型に見えます。ですが、そうですね、方向データを追加した場合を見てみましょう。

function process(){
    for(var n = 0;n < numActors; ++n){
        randomizePosition(actors[n], directional[n]);
    }
}

function randomizePosition(actor, dirctional){
    actor.x = Math.random() * 1000 * directional.direction;
    actor.y = Math.rondom() * 1000 * directional.direction;
}

直列に配置されたデータが追加されたことに注目してください。OOPなら

function OneActor(){
    this.x = 0;
    this.y = 0;
    this.direction = 1;
}

のようになるはずです。

CPUに優しく

さて、これがどんな影響を及ぼすのでしょうか。tmlibのアクセスが遅かった理由を考えてみましょう。

そうです、間接参照を何度も行うことで、キャッシュミスが起きたことですね。

では、DOPではどうなるのでしょうか。

DOPでは、加工関数に対して、データが直列に並んでいます。逐次アクセスです。さらに、加工関数に対して、必要最小限のデータを渡すわけです。結果、キャッシュミスはOOPに比べておきにくいです。

やはり銀の弾丸に非ず

では全部DOPで組めば解決！！
……といけば楽なのですが、世の中そんなに甘くありません。

DOPが威力を発揮するのは、同一データに同一処理を行う場合です。例えばゲームですと、画面上に現れる移動体には、位置、姿勢、生死etc...同一のデータが大量にあります。さらに画面更新毎に実行される訳です。
まさに適任です。

ですが、画面上のUIに関しては勝手が違います。例えばボタン、OKボタンとCancelボタンは押した際の挙動が違います。似たデータですが、同一処理ではありません。ボタンという概念が、他の概念を呼び出すわけです。これはオブジェクト指向のメッセージパッシングと同じ、よってこの場合、OOPが適切です。

とよくわからないまま終了です。この考え方に基づいた、JavaScriptゲームライブラリないかなぁ（ちらちら）

では、またどこかで！