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

Posted on

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は大変ですね…。


Fedora18にあげたら.xmodmapが読み込まれ無くなった

Posted on

こんにちは。最近なぜかFedora17が動かなくなった(えっ)ので、Fedora18にアップデートしました。

私は~/.Xmodmapにこんな内容を置いて、キーボードのCtrlとShiftを入れ替えたりZenkaku_HankakuをEscapeにしたりしているのですが、

keysym Zenkaku_Hankaku = Escape
remove Lock = Caps_Lock
keysym Caps_Lock = Control_L
add Control = Control_L

Fedora18にアップデートしたところ、うまく動かなくなってしまいました。それを今回対策したので、メモっておきます。

原因は?

どうやら大本の原因は、どうやらgnome3.6になってから文字入力を担ってるあたりがgnomeに統合されたのが問題の原因(?)らしいです 参考

直接的な原因はxmodmap ~/.Xmodmapが自動で実行され無くなったことで、何もせずともコンソールで自分で

% xmodmap ~/.Xmodmap

って入力して実行すると今までどおりちゃんと設定が反映されるようになってるはずです。というわけで、これを自動で実行するようにしましょう。

gnome-session-propertiesを起動する

コンソールからgnome-session-propertiesを実行します。

% gnome-session-properties

そうすると、自動的に実行されるプログラムの一覧が表示されるので…

20130331_01

Addを押して、新しいエントリを追加し、

20130331_02コマンドの所に

/usr/bin/xmodmap ${YOUR_HOME}/.Xmodmap

と入力してSaveして、再ログインすれば反映されるはずです。

ここで重要なのが、xmodmapを絶対パスで指定しておくことです。どうやらPATH変数がうまく設定されてないのか、xmodmapとだけ書いても動きません。

余談:SSH key agentはここで実行されている

他のエントリを見てみると中々面白いです。ssh key agentとかどこで実行されてるのか割と不思議だったのですが、この中だったのですね。

Linux版Dropboxのクライアントなどもここで実行されています。

.bash_profileとかはターミナルを起動した瞬間でないと自動実行されない(たしか)ので、Xからログインしてすぐに発動させたいコマンドはここを使うと良さそうです


GoogleTestでマクロを使ってテストを自動生成するバッドノウハウ

Posted on

C++のテストフレームワークのGoogleTest、活用してますか!!私は大好きです!!(何

テストフレームワークを使ってると、マクロを使って似たようなテストをまとめたくなる時があると思います。前後のセットアップだけ同じで型名とテストする値だけが違うとか。できればテンプレートを使ったほうがいいと思いますが、そうもできない場合もあるでしょう。

#define _MY_TEST(TYPE, VALUE, EXPECTED) \
{ /* plus */\
TYPE result;\
ASSERT_NO_THROW( result=do_sth<TYPE>(VALUE) );\
ASSERT_EQ( EXPECTED, result );\
}\
{ /* minus */\
TYPE result;\
ASSERT_NO_THROW( result=do_sth<TYPE>(-VALUE) ); /* マイナス */\
ASSERT_EQ( EXPECTED, result );\
}

TEST(MyTest, TEST_A)
{
_MY_TEST(int, 0x7fffffff, 0x80000000); // do_sthは何するんだろう…
_MY_TEST(unsigned short, 0x7fff, 0x8000);
...
}

でも、コレは動かないのです。こんなエラーメッセージが出ちゃいます。

****.cpp: In member function ‘virtual void MyTest_TEST_A_Test::TestBody()’:
****.cpp:719:1140: error: duplicate label ‘gtest_label_testnothrow_719’
****.cpp:720:1171: error: duplicate label ‘gtest_label_testnothrow_720’

さて…GOTOのラベルがかぶっているようです。なんでなのかは、ASSERT_NO_THROWの先を見ればわかります。

#define GTEST_TEST_NO_THROW_(statement, fail) \
 GTEST_AMBIGUOUS_ELSE_BLOCKER_ \
 if (::testing::internal::AlwaysTrue()) { \
 try { \
 GTEST_SUPPRESS_UNREACHABLE_CODE_WARNING_BELOW_(statement); \
 } \
 catch (...) { \
 goto GTEST_CONCAT_TOKEN_(gtest_label_testnothrow_, __LINE__); \
 } \
 } else \
 GTEST_CONCAT_TOKEN_(gtest_label_testnothrow_, __LINE__): \
 fail("Expected: " #statement " doesn't throw an exception.\n" \
 "  Actual: it throws.")

というわけで、GOTOのラベルに__LINE__マクロで取得した行数を使っているのですが、関数風マクロで展開するソースは一行で展開されるので、先ほどの_MY_TESTの複数のASSERT_NO_THROWで同じ__LINE__が使われてしまい、GOTOのラベルがかぶるのでさっきのようなエラーでコンパイルエラーになってしまったのでした。

むー。困りましたね。

マクロ内でマクロのディレクティブは使えない

たとえばこんな事はできません。

#define _MY_TEST(TYPE, VALUE, EXPECTED, x) \
 { /* plus */\
 TYPE result;\
\
#line (x*1000) /*lineディレクティブで書き換えてしまえばよいのでは!? */\
 ASSERT_NO_THROW( result=do_sth<TYPE>(VALUE) );\
 ASSERT_EQ( EXPECTED, result );\
 }\
 { /* minus */\
 TYPE result;\
#line (x*1000)+1 /*上とは違う番号を使っている */\
 ASSERT_NO_THROW( result=do_sth<TYPE>(-VALUE) ); /* マイナス */\
 ASSERT_EQ( EXPECTED, result );\
 }

#lineというディレクティブを使うと__LINE__での行番号がこの行以降差し替わるので、これで変えてあげればかぶらなくなるのでは?と思ったのですが、やはり一行に展開されてしまうので、このように展開されてしまい…

{.... #line (x*1000)+1 ASSERT_NO_THROW(.... /*←改行なし*/

これでは文法エラーにしかなりません。

 仕方ないのでファイルを分ける

何かいい方法無いのかなーと考えていたのですが、プリプロセッサには関数風マクロ以外にもソースの繰り返しを行う方法がありました。includeです。

さっきのマクロの内容そのものの別ヘッダファイルを作り…

/* inc.h */
#define _MY_TEST(TYPE, VALUE, EXPECTED, x) 
 { /* plus */
 TYPE result;

 ASSERT_NO_THROW( result=do<TYPE>(VALUE) );
 ASSERT_EQ( EXPECTED, result );
 }
 { /* minus */
 TYPE result;
 ASSERT_NO_THROW( result=do<TYPE>(-VALUE) ); /* マイナス */
 ASSERT_EQ( EXPECTED, result );
 }

それをincludeして繰り返しすれば…

TEST(MyTest, TEST_A)
{
#define TYPE int
#define VALUE 0x7fffffff
#define EXPECTED 0x80000000
#include "inc.h"
#undef TYPE
#undef VALUE
#undef EXPECTED
}

別ファイル内でのgoto扱いになるので、さっきのエラーは出なくなります。若干不恰好ですが、手動で繰り返すよりは…。

できればテンプレートを使う方が良いと思う

マクロではなくテンプレートを使ってテストをパラメータ化すれば、このような問題は起きません。テンプレートではマクロの##(シンボル連結)とか#(シンボルの文字列化)みたいな機能は使えませんが、もっと安全だし楽なので、出来ればテンプレートで出来ないか先に考えるほうが良いと思います。。。