JavaScriptのTypedArrayで高速にmemsetするには

JavaScriptでパフォーマンスを出すことを…強いられるんだ!!!(カッ

で、今回はその関係で色々試したことの一つについて、昔やった結果を纏めたのを書きました。

TypedArray

最近のJavaScriptにはTypedArrayというのがあります。通常のJavaScriptの配列は、要素にどんな型でも入れられる上、厳密には配列ではなくハッシュであるため効率が悪いのですが、このTypedArrayでは配列の型を指定した本物の配列であるため、高速・効率的に処理できます。

もともとはJSでOpenGLを使うWebGLという技術向けに策定された仕様なのですが、別にWebGLでなくても使用できて、以前開発したJSのファミコンエミュレータでも、ファミコンのRAMやフレームバッファをこれで表現しています。

さて、このTypedArray、色々とメソッドが定義されていて、よく使う処理は大体網羅されているのですが、memset(メモリ全体を特定のデータで塗りつぶす)を行うようなメソッドがありません。結構使う処理だと思うのですが、無いのでなんとかJSで塗りつぶさないといけない、という事になります。

今回はTypedArrayのmemset処理について色々と試してみた結果を書きます。

条件

  • Let’s note SX-1 SSD Edition CF-SX1GETDR
  • Intel Core i5-2540M
  • Windows 7 64bit
  • Firefox 18 x86

方法1:普通にループで回す

var memory = new Uint8Array(1024*1024);
log("normal: "+cycloa.probe.measure(function(){
    var m = memory;
    for(var i=0;i<5000;++i){
        for(var j=0;j<1024*1024;++j){
            m[j] = i;
        }
    }
}));

一番遅そうですが、一番オーソドックスな方法です。5000回、1MBのデータを0で埋めてみると、5回試行してそれぞれ
5008ms, 4950ms, 4955ms, 4949ms, 4957ms
になりました。

ということで、5000ms前後がベースラインということになります。これから遅くなったらむしろ逆効果ということでです。

方法2:小さい配列をループで初期化してsetで回す

setというメソッドがあって、これを使うと複数の要素を一気に上書きすることができます。

var mem = new Uint8Array(1024*1024);
var another_mem = new Uint8Array(1024);
var offset  = 100;
mem.set(another_mem, offset);  -> 100バイト目から1,024バイトがanother_memの内容に上書きされる

さらにこのanother_memの作り方として、上のようにnewで作る方法とsubarrayを使って元の配列を部分的に共有したものを使う方法があります。

ver another_mem = mem.subarray(100,100+1024); -> memの100から100+1024バイト目までを共有したメモリ配列を作

全部ネイティブで0にするより、一旦小さな配列を0で埋めてからsetでセットしたほうが速い気がしませんか。私はそう思いました。

全部JSのループで回すのは遅いというのがわかりましたし、かといってあんまり小さな配列を使って何度もsetを呼び出してもネイティブ呼び出しのオーバーヘッドが重いだろうと思われるので、このバランスをどうするかが問題になります。今回は、1KBから1MB(意味なし)まで変化させて測定しました。

new Uint8Arrayで配列を作ってコピーする方法

for(var z=10;z<=20;++z){
    log(""+cycloa.probe.measure(function(){
        var m = memory;
        var bsize = 1<<z;
        var copy_times = 1024*1024/bsize;
        var buff = new Uint8Array(bsize);
        for(var i=0;i<5000;++i){
            for(var j=0;j<bsize;++j){
                buff[j] = i;
            }
            for(var j=0;j<copy_times;++j){
                m.set(buff, j*bsize);
            }
        }
    })+",");
}
1 2 3 4 5 平均
1024 557 559 547 553 543 551.8
2048 399 397 395 399 398 397.6
4096 340 343 340 342 342 341.4
8192 322 319 319 328 331 323.8
16384 367 369 373 369 372 370
32768 477 480 478 483 482 480
65536 630 630 631 632 638 632.2
131072 919 928 926 929 939 928.2
262144 1598 1583 1584 1589 1619 1594.6
524288 2854 2831 2821 2834 2935 2855
1048576 5624 5396 5326 5437 5418 5440.2

subarrayを使って小さな配列を作る方法

for(var z=10;z<=20;++z){
    log(""+cycloa.probe.measure(function(){
        var m = memory;
        var bsize = 1<<z;
        var copy_times = 1024*1024/bsize;
        var buff = m.subarray(0, bsize);
        for(var i=0;i<5000;++i){
            for(var j=0;j<bsize;++j){
                buff[j] = i;
            }
            for(var j=1;j<copy_times;++j){
                m.set(buff, j*bsize);
            }
        }
    })+",");
}
1 2 3 4 5 平均
1024 640 564 553 565 557 575.8
2048 417 404 401 405 404 406.2
4096 343 348 342 347 341 344.2
8192 319 320 319 320 318 319.2
16384 369 377 367 362 369 368.8
32768 468 471 470 467 465 468.2
65536 611 614 610 610 607 610.4
131072 891 882 873 876 888 882
262144 1516 1502 1498 1493 1520 1505.8
524288 2678 2653 2652 2667 2658 2661.6
1048576 4993 4934 4922 4972 4923 4948.8

 グラフ

new Uint8Arrayで配列を作ってコピーする方法

20130129_01

subarrayを使って小さな配列を作る方法

20130129_02

やっぱり小さな配列を作ったほうが速い

と、いうわけで、8192くらいの配列を作ってsetで回したほうが大体17倍くらい速いです。subarrayの方が配列生成コストが変わってくるのかなぁ、と思ったのですが、あんまり変わらないようですね。

ただこの8192という数字は2013年のFirefox18のWindows7でCore i5(Ivy Bridge)というひっっっっっっじょうに限られた環境での値なので、あんまり鵜呑みにしないほうがいいと思います。もし、JSの実行速度がネイティブ関数呼び出しのコストに対して相対的に速い環境があればこの値は大きくなるかもしれませんし、ネイティブ関数呼び出しのコストがJS実行速度よりも相対的に安い環境があれば、この値は小さくなってくると予想されます。

結論

  • HTML5のTypedArrayでは、メモリの内容を特定の値で塗りつぶすとき、subarrayでも新しくつくるのでも、他のTypedArrayを用意してそれを特定の値で塗りつぶしてからsetを繰り返す方がとても速い
  • 8192bytesの配列を用意すると一番速かったけど、他の環境では分からない。
  • ターゲットの環境で調べれば良いのでは(クロスプラットフォームを無視した言い方)

JSは大変ですね…。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください