Cで実装したバックトラック型数独ソルバーを、Emscriptenを使ってJavaScript環境で実行させることから、Emscriptenの仕組みを調べていった、という話です。
Emscriptenとは
emscriptenは、LLVM/Clangを使って、CやC++のプログラムをブラウザやnodejs/iojsといったJavaScript環境で実行できるようにするシステムです。
C/C++のソースをコンパイルしたLLVMのバイトコードを元に、JavaScript上で実行させるための変換プログラムとそれを実行するためのランタイム環境の部分と、gccやmake等と互換性を高めたemccやemmakeなどのコマンドライン群を提供しています。前者はnodejsによって、後者はpythonによって実行するようになっています。
libc等のC/C++で利用するランタイムライブラリ(の関数)は、JavaScript側でエミュレートするようになっています。コンソールへの標準出力、SDL/OpenGL等の描画などをnodejs/iojs環境やブラウザ上で実現するJS実装、等が、emscriptenには標準添付されています(たとえばlibcのエミュレート実装は、/usr/local/opt/emscripten/libexec/src/library.jsで記述されています)。
Emscriptenの環境設定
OSX環境では、homebrewによってemscriptenをインストールしました(brew install emscripten)。
emscriptenを入れると、emcc(gcc/clang互換のコマンド)等のコマンドが追加され、初回にそのコマンドを実行する時、環境が設定された~/.emscriptenファイルが作られます。
しかし、OSXだと現状のシステム添付のclangコマンドを使うなど、その内容はただしく反映されません。そこで以下のように編集しなおします。
# ~/.emscripten
EMSCRIPTEN_ROOT = os.path.expanduser(
os.getenv('EMSCRIPTEN') or
'/usr/local/opt/emscripten/libexec')
LLVM_ROOT = os.path.expanduser(
os.getenv('LLVM') or
'/usr/local/opt/emscripten/libexec/llvm/bin')
NODE_JS = os.path.expanduser(
os.getenv('NODE') or
'/usr/local/opt/node/bin/node')
TMP_DIR = '/tmp'
COMPILER_ENGINE = NODE_JS
JS_ENGINES = [NODE_JS]
このようにhomebrewのパッケージのもを指定しておけくことで、homebrewのupgradeによってインストールされているemscriptenやnodejsのパッケージがバージョンアップしても、毎回の再設定せずに実行できるようになります。
この設定でemccコマンドを空実行すると、正しく設定されていていれば以下の結果になります。
$ emcc
WARNING root: (Emscripten: settings file has changed, clearing cache)
INFO root: (Emscripten: Running sanity checks)
WARNING root: no input files
C言語(C11)で数独ソルバーを書く
はじめにC11仕様でバックトラック型の9x9マスの数独ソルバーを記述します。あとでライブラリだけで利用できるよう、コードのライブラリ部分とmain部分とでファイルを分けて記述します。
// libsudoku.c
#include <stdio.h>
// helpers for board data
static inline unsigned masks(unsigned i) {return i ? 1 << (i - 1) : 0;}
static inline unsigned row(unsigned i) {return i / 9;}
static inline unsigned col(unsigned i) {return i % 9;}
static inline unsigned blk(unsigned i) {return i / 27 * 3 + i % 9 / 3;}
extern void output(unsigned board[])
{
char buffer[(9 + 3) * (9 + 3)];
char* cur = buffer;
for (unsigned y = 0; y < 9; y++) {
for (unsigned x = 0; x < 9; x++) {
*cur++ = board[y * 9 + x] > 0 ? board[y * 9 + x] + '0' : '.';
if (x % 3 == 2) *cur++ = x == 8 ? '\n' : '|';
}
if (y == 8) {
*cur++ = '\0';
} else if (y % 3 == 2) {
for (unsigned i = 0; i < 11; i++) *cur++ = i % 4 == 3 ? '+' : '-';
*cur++ = '\n';
}
}
puts(buffer);
}
// sudoku solver
typedef void (*sudoku_cb)(unsigned board[]);
typedef struct {
unsigned board[81];
unsigned rows[9], cols[9], blks[9];
sudoku_cb callback;
} sudoku_t;
static void sudoku_init(sudoku_t* s, unsigned board[])
{
for (unsigned i = 0; i < 81; i++) {
const unsigned mask = masks(board[i]);
s->rows[row(i)] |= mask, s->cols[col(i)] |= mask, s->blks[blk(i)] |= mask;
s->board[i] = board[i];
}
}
static void sudoku_solve(sudoku_t* s, unsigned i)
{
if (i == 81) {
s->callback(s->board);
} else if (s->board[i] != 0) {
sudoku_solve(s, i + 1);
} else {
const unsigned r = row(i), c = col(i), b = blk(i);
const unsigned used = s->rows[r] | s->cols[c] | s->blks[b];
for (unsigned v = 1; v <= 9; v++) {
const unsigned mask = masks(v);
if (used & mask) continue;
s->board[i] = v;
s->rows[r] |= mask, s->cols[c] |= mask, s->blks[b] |= mask;
sudoku_solve(s, i + 1);
s->rows[r] &= ~mask, s->cols[c] &= ~mask, s->blks[b] &= ~mask;
s->board[i] = 0;
}
}
}
extern void sudoku(unsigned board[], sudoku_cb callback)
{
sudoku_t s = {
.board = {0}, .rows = {0}, .cols = {0}, .blks = {0}, .callback = callback};
sudoku_init(&s, board);
sudoku_solve(&s, 0);
}
// sudoku-main.c
#include <stdio.h>
extern void output(unsigned board[]);
typedef void (*sudoku_cb)(unsigned board[]);
extern void sudoku(unsigned board[], sudoku_cb callback);
// example problem from http://rosettacode.org/wiki/Sudoku
static unsigned problem[] = {
8, 5, 0, 0, 0, 2, 4, 0, 0,
7, 2, 0, 0, 0, 0, 0, 0, 9,
0, 0, 4, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 7, 0, 0, 2,
3, 0, 5, 0, 0, 0, 9, 0, 0,
0, 4, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 8, 0, 0, 7, 0,
0, 1, 7, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 3, 6, 0, 4, 0
};
extern int main(int argc, char* argv[])
{
if (argc <= 1) {
puts("[problem]");
output(problem);
puts("[solutions]");
sudoku(problem, output);
} else {
for (int i = 1; i < argc; i++) {
char ch = -1;
for (int c = 0; c < 81; c++) {
if (ch == '\0') {
problem[c] = 0;
} else {
ch = argv[i][c];
problem[c] = '0' <= ch && ch <= '9' ? ch - '0' : 0;
}
}
puts("[problem]");
output(problem);
puts("[solution]");
sudoku(problem, output);
}
}
return 0;
}
このコードは、以下のようにgcc/clangで普通にコンパイル/実行可能なプログラムになっています。
$ clang -std=c11 -Wall -Wextra libsudoku.c sudoku-main.c -o sudoku
$ ./sudoku
[problem]
85.|..2|4..
72.|...|..9
..4|...|...
---+---+---
...|1.7|..2
3.5|...|9..
.4.|...|...
---+---+---
...|.8.|.7.
.17|...|...
...|.36|.4.
[solutions]
859|612|437
723|854|169
164|379|528
---+---+---
986|147|352
375|268|914
241|593|786
---+---+---
432|981|675
617|425|893
598|736|241
EmscriptenでCのプログラムをコンパイルし、iojsで実行する
上記ビルドでのclangの部分をemccに変え、出力ファイル名に.jsをつけるだけでJavaScriptコードにコンパイルできます。
生成されたjsファイルは、それ単体でnodejs/iojs上で実行可能になっています。
$ emcc -std=c11 -Wall -Wextra libsudoku.c sudoku-main.c -o sudoku.js
$ iojs sudoku.js
[problem]
85.|..2|4..
72.|...|..9
..4|...|...
---+---+---
...|1.7|..2
3.5|...|9..
.4.|...|...
---+---+---
...|.8.|.7.
.17|...|...
...|.36|.4.
[solutions]
859|612|437
723|854|169
164|379|528
---+---+---
986|147|352
375|268|914
241|593|786
---+---+---
432|981|675
617|425|893
598|736|241
Emscriptenでコンパイルしたライブラリの関数を、JavaScriptコードから呼び出す
Emscriptenで生成したコードは、(CoffeeScript等のトランスレータのような)普通のJavaScript関数として使えるJSコードではありません。生成されるのは、(C言語実行モデルを前提とする)LLVMバイトコードとその実行環境が合わさったものです。例えば、HEAPのような定量のメモリ領域の管理機構がJSコード中に存在しています。
これは生成するのがライブラリであっても同じで、ライブラリがもつexternな関数というのは、あくまでCの関数としてのバイトコードを、ライブラリ内に組み込んだ実行環境上で実行させるものとなっています。
そのためEmscriptenで生成したコードを、JavaScript用のライブラリとして使うには、所々で少し工夫が必要になります。公式ドキュメントの、Interacting with codeには、このために必要な情報は記述してありますが、これらがライブラリ内のCプログラム実行環境へのアクセス手段である、という大本の違いを認識していないとハマることになります。
nodejs/iojsライブラリとしてコンパイルする
libsudoku.cからnodejs/iojs上のライブラリとして使うlibsudoku.jsを生成するには、以下のように付属のオプション-s EXPORTED_FUNCTIONSと-s RESERVED_FUNCTION_POINTERSの２つを指定する必要があります。
$ emcc -Wall -Wextra -std=c11 libsudoku.c -o libsudoku.js \
-s EXPORTED_FUNCTIONS="['_sudoku','_output']" \
-s RESERVED_FUNCTION_POINTERS=20
前者のEXPORTED_FUNCTIONSでは、JavaScript側で呼び出すために、Cでのexternな関数名を指定します。ただし、Cの関数名そのままではなく、頭に_をつけた名前を列挙します。
後者のRESERVED_FUNCTION_POINTERSは、sudoku(board, callback)関数のような、コールバック関数のポインタを渡す関数をJavaScript側から呼び出す必要があるときに必要な変数です。ここで、JavaScriptのfunctionをコールバックさせるために、バイトコード実行環境上に設定できる関数ポインタの数を確保します。libsudoku.jsは並列実行されないので、libsudoku.jsの場合は1あればよいですが、ここでは20を指定しました。
Emscriptenライブラリを呼び出すJavaScriptコードを書く
ドキュメントでは、ccallやcwrapを使えとありますが、載せてあるのはやりとりするのが単純なnumberの値ときのみであって、引数で配列や関数を使うために生成されたコードを解析したりして試行錯誤しました。
ccallで配列を引数に渡して呼び出す方法
まず、libsudoku.cのvoid output(unsigned board[])を呼び出すラッパーは以下のようになりました。
var libsudoku = require("./libsudoku.js");
// use ccall to call emscripten C function
var output = function (board) {
// unsigned[] as Uint8Array view of Uint32Array
var unsignedBoard = new Uint8Array(new Uint32Array(board).buffer);
// ccall(cfuncname, return_type, argument_types, arguments)
// type: "string", "number", "array" or undefined as return type
return libsudoku.ccall("output", undefined, ["array"], [unsignedBoard]);
};
ここでは、JavaScriptのArrayを、Emscriptenのarray値としてccallを呼び出します。引数は、library.ccall(関数名, 戻り値型, 引数型リスト, 引数値リスト)です。この関数名は、コンパイルオプションのではなく、頭の_なしのCでの関数名になります。
戻り値はvoidの場合undefinedを指定します。引数の型は"number"か"string"か"array"のどれかになります。この型指定は、Cの関数宣言での型ではなく、呼び出して実行させる時に実際に渡すJavaScript値の型になります。
output()の引数のポインタの型はunsigned (int)ですが、Emscriptenでは、int型は32bit整数として扱われるようです。そしてバイトオーダーは、TypedArrayのCPU環境依存性をそのまま継承しているようです(生成コード内でCPU依存なnew Uint32Array(buffer)などが記述されている)。
C言語上で扱うのが32bit配列だろうと、ccallで呼び出すときの"array"型の引数は、8bitのInt8ArrayやUint8Arrayである必要があります。ライブラリ内のccall実装を見ると、呼び出しで渡す引数は、その値をライブラリ内のメモリ領域にコピーしてバイトコード実行させます。"string"とか"array"とかいうのは、そのコピー手段を指定するものになっています。"array"の場合は、HEAP8[...] = array[i]でコピーするので、Uint32Array等をそのままccallに渡すと8bitに切り詰められてしまいます。ちなみに"string"はCへはUTF8なchar文字列になって渡ります。
関数ポインタを渡す関数を呼び出す方法
sudoku(board, callback)へのラッパーを、もう一つのcwrapを使って実装したのが、以下のコードになります。ccall(関数名, 戻り値型、引数型リスト、引数値リスト)は、cwrap(関数名, 戻り値型, 引数型リスト)(引数値リスト)と等価です。emscriptenの関数を何度も呼び出す場合にはcwrapが返す関数をキャッシュしておいて、引数だけ渡して呼び出すほうがよいでしょう。
ここでのポイントは、JavaScriptのコールバック関数は、バイトコード実行環境にセットし、そのポインタ値を"number"としてcwrapで作った関数の引数に渡す点です。
// use cwrap to call emscripten C function with callback
var sudoku = function sudoku(board, callback) {
// NOTE: For using addFunction(),
// emcc option "-s REQUIRED_FUNCTION_POINTERS=10" (more than 1) required
var callbackPtr = libsudoku.Runtime.addFunction(function (resultPtr) {
var r = new Uint32Array(libsudoku.HEAPU8.buffer, resultPtr, 81);
// NOTE: copy memory value as array for async use in callback(like IO)
callback([].slice.call(r));
});
var unsignedBoard = new Uint8Array(new Uint32Array(board).buffer);
sudoku._cfunc(unsignedBoard, callbackPtr);
libsudoku.Runtime.removeFunction(callbackPtr);
};
// pointer as a "number"
sudoku._cfunc = libsudoku.cwrap("sudoku", undefined, ["array", "number"]);
ptr = library.Runtime.addFunction(function)を使い、JavaScript functionをバイトコード環境にセットし、そのポインタ値を受け取ります。
コンパイル時の引数のRESERVED_FUNCTION_POINTERSの数は、同時にaddFunctionで登録できるJavaScript関数の数を指します。
コールバックで呼び出される関数に渡される引数は、(ccall等のでの値ではなく)実行環境上での数値そのままです。ポインタの場合は、ランタイムのHEAP(library.HEAPU8等)のオフセット値として使うことになります。これを隠ぺいするためにはコールバック関数もまたラッパーが必要になります。このコールバックラッパーの中でメモリオフセットから通常のArrayを作って実際のコールバックを呼び出します。
var callbackPtr = libsudoku.Runtime.addFunction(function (resultPtr) {
var r = new Uint32Array(libsudoku.HEAPU8.buffer, resultPtr, 81);
callback([].slice.call(r));
});
コールバックで渡されるresultはC上でunsigned [81]なので、HEAPから81個の32bit整数の配列をUint32Arrayで切り出し、それを普通のArrayに変換してコールバック関数を呼び出すようにしています。ccallやcwrapは、中でこういったHEAPアクセスを行ってJavaScriptオブジェクトとメモリ値との相互変換をしています。
library.Runtime.addFunction(f)が返す関数ポインタに限らず、ポインタ値は、"number"としてccallやcwrapの関数の引数に渡します。
関数呼び出しが終わったあとは、library.Runtime.removeFunction(ptr)で削除し、addFunctionできる場所を開けてやります。Emscriptenなライブラリでは、Cと同様にこういったリソース管理を手動で行う必要があります。
main部分と実行
上述のラッパーを用いた、sudoku-main.cと同様の処理を行うコードが以下になります。
// sudoku-call-libsudoku.js
var libsudoku = require("./libsudoku.js");
var output = function (board) {
var unsignedBoard = new Uint8Array(new Uint32Array(board).buffer);
return libsudoku.ccall("output", undefined, ["array"], [unsignedBoard]);
};
var sudoku = function sudoku(board, callback) {
var callbackPtr = libsudoku.Runtime.addFunction(function (resultPtr) {
var r = new Uint32Array(libsudoku.HEAPU8.buffer, resultPtr, 81);
callback([].slice.call(r));
});
var unsignedBoard = new Uint8Array(new Uint32Array(board).buffer);
sudoku._cfunc(unsignedBoard, callbackPtr);
libsudoku.Runtime.removeFunction(callbackPtr);
};
sudoku._cfunc = libsudoku.cwrap("sudoku", undefined, ["array", "number"]);
// main
if (process.argv.length <= 2) {
// example problem from http://rosettacode.org/wiki/Sudoku
var problem = [
8, 5, 0, 0, 0, 2, 4, 0, 0,
7, 2, 0, 0, 0, 0, 0, 0, 9,
0, 0, 4, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 7, 0, 0, 2,
3, 0, 5, 0, 0, 0, 9, 0, 0,
0, 4, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 8, 0, 0, 7, 0,
0, 1, 7, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 3, 6, 0, 4, 0
];
console.log("[problem]");
output(problem);
console.log("[solution]");
sudoku(problem, output);
} else {
for (var i = 2; i < process.argv.length; i++) {
var problem = Array(81);
for (var j = 0; j < 81; j++) {
var ch = process.argv[i].charCodeAt(j);
problem[j] = 0 <= ch && ch <= 9 ? v : 0;
}
console.log("[problem]");
output(problem);
console.log("[solution]");
sudoku(problem, output);
}
}
以下のように、mainを含めてをコンパイルした時と同様に、外部ライブラリ不要でそのままで実行できます。
$ iojs sudoku-call-libsudoku.js
[problem]
85.|..2|4..
72.|...|..9
..4|...|...
---+---+---
...|1.7|..2
3.5|...|9..
.4.|...|...
---+---+---
...|.8.|.7.
.17|...|...
...|.36|.4.
[solution]
859|612|437
723|854|169
164|379|528
---+---+---
986|147|352
375|268|914
241|593|786
---+---+---
432|981|675
617|425|893
598|736|241
実行速度の分析
ネイティブ実行のsudoku、Cコード全部を変換したsudoku.js、ライブラリlibsudoku.jsを利用するsudoku-call-libsudoku.jsの実行時間は以下のようになりました。
$ time ./sudoku
real 0m0.020s
user 0m0.015s
sys 0m0.002s
$ time iojs sudoku-call-libsudoku.js
real 0m0.355s
user 0m0.313s
sys 0m0.037s
$ time iojs sudoku.js
real 0m0.888s
user 0m0.312s
sys 0m0.045s
Cでmainを実装するより、ライブラリ利用だけにしたほうが速いようです(外部ライブラリ関数はprintf等を避けputs()のみを使うようにしたのですが)。
ちなみに、JavaScriptでバックトラック実装したコードでの実行時間は、
$ time iojs sudoku-backtrack.js
real 0m0.723s
user 0m0.684s
sys 0m0.030s
となりました。
盤面を1回解くだけならCコード全部を変換したものより速いのですが、これはmain部分のコストが大きく影響しているからでしょう。ライブラリ利用なものからは、倍の時間がかかっており、ソルバー部分はEmscriptenで倍速になったといえます。
疑問: ccallでのstruct値渡しの方法
ccallやcwrapでは、たとえばfloat4つが入ったvec4のような(ポインタ渡しにしない)struct値を渡す手段がないように見えます。
参考: Emscriptenの最適化及びデバッグオプション
gcc/clangと同様に最適化及びデバッグのオプションには、O0-3とg1-4がありますが、その意味は別物でEmscripten固有の意味を持っています。
- O0: 最適化なし(デフォルト)
- O1: デバッグコードが削除される
- O2: 出力がminifyされる(
.js.memファイルが生成される) - O3: さらなる最適化をする(O2より若干ファイルが小さくなる)
O2やO3で同時に生成される.js.memファイルは生成した.jsコードを実行するのに必須なファイルになります。
デバッグオプションは、O2以降の最適化オプションと併用してminify化を抑制するものになっています。
- g1: 空白を保存
- g2: 関数名を保存
- g3: 変数名を保存
- g4: ソースマップ(.mapファイル)を生成
ソースコードへのリンク
完全なソースコードは、Makefileをつけてgistに置いてあります。