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
の2つを指定する必要があります。
$ 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
では、たとえばfloat
4つが入った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に置いてあります。