Ich habe den Mechanismus von Emscripten untersucht, indem ich den in C implementierten deutschen Backtrack-Solver in der JavaScript-Umgebung mit Emscripten ausgeführt habe. Ist die Geschichte.
emscripten verwendet LLVM / Clang, um C- und C ++ - Programme in Browsern und nodejs/[iojs](https :: Es ist ein System, das die Ausführung in einer JavaScript-Umgebung wie //iojs.org/) ermöglicht.
Basierend auf dem Bytecode von LLVM, der die C / C ++ - Quelle kompiliert, sind das ** Konvertierungsprogramm zur Ausführung unter JavaScript und der Teil der Laufzeitumgebung zur Ausführung ** kompatibel mit gcc, make usw. Verbesserte emcc und emmake ) Und andere ** Befehlszeilen ** sind vorhanden. Ersteres wird von nodejs und letzteres von python ausgeführt.
Die in C / C ++ verwendete ** Laufzeitbibliothek (Funktion) wie libc kann auf der JavaScript-Seite emuliert werden **. .. Standardausgabe an die Konsole, Zeichnung von SDL/OpenGL usw. in der Umgebung oder im Browser von nodejs / iojs Die zu realisierende JS-Implementierung usw. werden standardmäßig an emscripten angehängt (die emulierte Implementierung von libc lautet beispielsweise [/ usr / local / opt / emscripten / libexec / src / library.js](https: //) github.com/kripken/emscripten/blob/master/src/library.js)).
In der OSX-Umgebung habe ich emscripten von homebrew installiert (Brew Install Emscripten).
Wenn emscripten eingefügt wird, werden Befehle wie "emcc" (gcc / clang-kompatibler Befehl) hinzugefügt, und wenn der Befehl zum ersten Mal ausgeführt wird, wird eine "~ / .emscripten" -Datei mit dem festgelegten Umgebungssatz erstellt.
In OSX werden die Inhalte jedoch nicht richtig wiedergegeben, z. B. mit dem Befehl "clang", der an das aktuelle System angehängt ist. Bearbeiten Sie es daher erneut wie folgt.
# ~/.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]
Wenn Sie das Homebrew-Paket auf diese Weise angeben, kann es auch dann ausgeführt werden, wenn das durch das Homebrew-Upgrade installierte emscripten- oder nodejs-Paket aktualisiert wird, ohne jedes Mal zurückgesetzt zu werden. ..
Wenn Sie den Befehl emcc mit dieser Einstellung leer ausführen, erhalten Sie das folgende Ergebnis, wenn er richtig eingestellt ist.
$ emcc
WARNING root: (Emscripten: settings file has changed, clearing cache)
INFO root: (Emscripten: Running sanity checks)
WARNING root: no input files
Beschreiben Sie zunächst in C11 Specifications einen deutschen 9,5-Quadrat-Backtrack-Löser. Trennen Sie die Dateien in den Bibliotheksteil und den Hauptteil des Codes, damit sie später nur von der Bibliothek verwendet werden können.
// 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;
}
Dieser Code ist ein Programm, das normalerweise mit gcc / clang kompiliert / ausgeführt werden kann, wie unten gezeigt.
$ 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
Sie können es in JavaScript-Code kompilieren, indem Sie den clang Teil im obigen Build in emcc ändern und ** .js` zum Namen der Ausgabedatei hinzufügen **.
Die generierte js-Datei ist ** eigenständig und auf nodejs / iojs ** ausführbar.
$ 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
Der von Emscripten generierte Code ist kein ** JS-Code, der als normale JavaScript-Funktion verwendet werden kann (wie ein Übersetzer wie CoffeeScript) **. Was generiert wird, ist eine Kombination aus dem LLVM-Bytecode (unter der Annahme des Ausführungsmodells der C-Sprache) und seiner Ausführungsumgebung. Beispielsweise ist im JS-Code ein quantitativer Speicherbereichsverwaltungsmechanismus wie HEAP vorhanden.
Dies ist auch dann der Fall, wenn die Bibliothek generiert wird und die externe Funktion der Bibliothek den Bytecode als ** C-Funktion in der in die Bibliothek eingebetteten Ausführungsumgebung ausführt. Es ist **.
Um den von Emscripten generierten Code als Bibliothek für JavaScript verwenden zu können, ist daher an einigen Stellen ein gewisser Einfallsreichtum erforderlich. Die offizielle Dokumentation Interaktion mit Code enthält die dafür erforderlichen Informationen Wenn Sie jedoch den Hauptunterschied nicht erkennen, dass dies ** Mittel für den Zugriff auf die C-Programmausführungsumgebung in der Bibliothek ** sind, sind Sie süchtig danach.
Um "libsudoku.js" zu generieren, das als Bibliothek für nodejs / iojs aus "libsudoku.c" verwendet werden soll, müssen Sie die angehängten Optionen "-s EXPORTED_FUNCTIONS" und "-s RESERVED_FUNCTION_POINTERS" wie folgt angeben. es gibt.
$ emcc -Wall -Wextra -std=c11 libsudoku.c -o libsudoku.js \
-s EXPORTED_FUNCTIONS="['_sudoku','_output']" \
-s RESERVED_FUNCTION_POINTERS=20
Geben Sie im vorherigen "EXPORTED_FUNCTIONS" den Funktionsnamen "extern" in C an, um ihn auf der JavaScript-Seite aufzurufen. Anstatt die C-Funktionsnamen so aufzulisten, wie sie sind, listen Sie die Namen ** mit dem Präfix _ ** auf.
Letzteres, "RESERVED_FUNCTION_POINTERS", ist eine notwendige Variable für **, wenn Sie eine Funktion aufrufen müssen, die einen Zeiger auf eine Rückruffunktion wie die Funktion "sudoku (board, callback)" von der JavaScript-Seite übergibt. Reservieren Sie hier die Anzahl der Funktionszeiger, die in der Bytecode-Ausführungsumgebung festgelegt werden können, um die JavaScript-Funktion zurückzurufen. Da "libsudoku.js" nicht parallel ausgeführt wird, ist "1" für libsudoku.js ausreichend, aber "20" wird hier angegeben.
Die Dokumentation besagt, dass Sie "ccall" und "cwrap" verwenden können, diese werden jedoch nur aufgelistet, wenn der einfache Wert "number" ausgetauscht wird, und wurden generiert, um ein Array oder eine Funktion als Argument zu verwenden. Ich analysierte den Code und machte Versuch und Irrtum.
ccall übergebenErstens lautet der Wrapper, der "void output (unsigned board [])" von "libsudoku.c" aufruft, wie folgt.
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]);
};
Hier nennen wir "Array" in JavaScript als Array-Wert in Emscripten. Das Argument lautet library.ccall (Funktionsname, Rückgabetyp, Argumenttypliste, Argumentwertliste). Dieser Funktionsname ist ** ein Funktionsname in C ohne ein führendes _ **, keine Kompilierungsoption.
Wenn der Rückgabewert "void" ist, geben Sie "undefined" an. Der Argumenttyp kann entweder "Zahl", "Zeichenfolge" oder "Array" sein. Diese Typspezifikation ist nicht der Typ in der C-Funktionsdeklaration, sondern der ** JavaScript-Werttyp **, der beim Aufrufen und Ausführen tatsächlich übergeben wird.
Der Zeigertyp des Arguments von "output ()" ist "unsigned (int)", aber ** Emscripten scheint den Typ "int" als 32-Bit-Ganzzahl ** zu behandeln. Und ** Bytereihenfolge scheint die CPU-Umgebungsabhängigkeit von "TypedArray" so zu erben, wie sie ist ** (CPU-abhängiges "neues Uint32Array (Puffer)" usw. wird im generierten Code beschrieben).
Wenn das 32-Bit-Array in der Sprache C behandelt wird, muss das Argument vom Typ ** " array " beim Aufruf mit ccall 8bit Int8Array oder Uint8Array ** sein. Bei der Implementierung von "ccall" in der Bibliothek kopiert das im Aufruf übergebene Argument ** seinen Wert in den Speicherbereich in der Bibliothek und bewirkt die Ausführung von Bytecode **. Der "String" und das "Array" geben die Kopiermethode an. Im Fall von "Array" wird es mit "HEAP8 [...] = Array [i]" kopiert. Wenn Sie also "Uint32Array" usw. an "ccall" übergeben, wird es auf 8 Bit abgeschnitten. Übrigens wird "string" als UTF8-Zeichenzeichenfolge an C übergeben.
Der folgende Code implementiert einen Wrapper für "sudoku (board, callback)" unter Verwendung eines anderen "cwrap". "ccall (Funktionsname, Rückgabetyp, Argumenttypliste, Argumentwertliste)" entspricht "cwrap (Funktionsname, Rückgabetyp, Argumenttypliste) (Argumentwertliste)". Wenn Sie die emscripten-Funktion mehrmals aufrufen, ist es besser, die von cwrap zurückgegebene Funktion zwischenzuspeichern und nur das Argument zu übergeben.
Der Punkt hier ist, dass die JavaScript-Rückruffunktion in der Bytecode-Ausführungsumgebung festgelegt ist und ihr Zeigerwert als Argument der von cwrap erstellten Funktion als" number " übergeben wird.
// 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"]);
Verwenden Sie "ptr = library.Runtime.addFunction (function)", um die JavaScript-Funktion in der Bytecode-Umgebung festzulegen und den Zeigerwert zu erhalten. Die Anzahl der Argumente zur Kompilierungszeit "RESERVED_FUNCTION_POINTERS" bezieht sich auf die Anzahl der JavaScript-Funktionen, die gleichzeitig bei "addFunction" registriert werden können.
Die Argumente, die an die im Rückruf aufgerufene Funktion übergeben werden, sind die genauen Zahlen in der Ausführungsumgebung (nicht die Werte in "ccall" usw.). ** Wenn es sich um einen Zeiger handelt, wird er zur Laufzeit als Versatzwert von HEAP (library.HEAPU8 usw.) verwendet **. Um dies zu verbergen, ** benötigt die Rückruffunktion auch einen Wrapper **. In diesem Callback-Wrapper erstellen wir aus dem Speicheroffset ein reguläres Array und rufen den eigentlichen Callback auf.
var callbackPtr = libsudoku.Runtime.addFunction(function (resultPtr) {
var r = new Uint32Array(libsudoku.HEAPU8.buffer, resultPtr, 81);
callback([].slice.call(r));
});
Da das im Rückruf übergebene "Ergebnis" auf C "ohne Vorzeichen" [81] ist, schneiden Sie mit "Uint32Array" ein Array von 81 32-Bit-Ganzzahlen aus HEAP aus, konvertieren Sie es in ein normales "Array" und verwenden Sie die Rückruffunktion. Ich versuche anzurufen. ccall und cwrap führen einen solchen HEAP-Zugriff im Inneren durch, um zwischen JavaScript-Objekten und Speicherwerten zu konvertieren.
Der Zeigerwert ist nicht auf den von "library.Runtime.addFunction (f)" zurückgegebenen Funktionszeiger beschränkt, sondern wird als "Zahl" an das Argument der Funktion "ccall" oder "cwrap" übergeben.
Nachdem der Funktionsaufruf beendet ist, löschen Sie ihn mit "library.Runtime.removeFunction (ptr)" und öffnen Sie eine Stelle, an der Sie "addFunction" hinzufügen können. Emscripten-Bibliotheken erfordern diese ** Ressourcenverwaltung manuell ** wie in C.
Der Code, der den obigen Wrapper verwendet und die gleiche Verarbeitung wie "sudoku-main.c" ausführt, lautet wie folgt.
// 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);
}
}
Wie unten gezeigt, kann es so ausgeführt werden, wie es ist, ohne dass eine ** externe Bibliothek erforderlich ist **, genau wie beim Kompilieren einschließlich 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
Die Ausführungszeit von "sudoku" für die native Ausführung, "sudoku.js", die den gesamten C-Code konvertiert hat, und "sudoku-call-libsudoku.js", die die Bibliothek "libsudoku.js" verwendet, ist wie folgt.
$ 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
Es scheint, dass es schneller ist, nur die Bibliothek zu verwenden, als main in C zu implementieren (obwohl die externe Bibliotheksfunktion printf usw. vermeidet und nur put () verwendet).
Die Ausführungszeit in Code implementiert Backtrack mit JavaScript beträgt übrigens
$ time iojs sudoku-backtrack.js
real 0m0.723s
user 0m0.684s
sys 0m0.030s
ist geworden.
Das nur einmalige Lösen der Karte ist schneller als das Konvertieren des gesamten C-Codes, wahrscheinlich weil die Kosten des Hauptteils einen großen Einfluss haben. Die Nutzung der Bibliothek dauerte doppelt so lange, und man kann sagen, dass der Solver-Teil mit Emscripten verdoppelt wurde.
Bei ccall und cwrap scheint es keine Möglichkeit zu geben, einen ** (nicht vom Zeiger übergebenen) struct-Wert ** zu übergeben, z. B. vec4 mit vier floats.
Ähnlich wie bei gcc / clang umfassen die Optimierungs- und Debugging-Optionen O0-3 und g1-4, aber ihre Bedeutungen sind unterschiedlich und haben Emscripten-spezifische Bedeutungen.
--O0: Keine Optimierung (Standard)
--O1: Debug-Code wird gelöscht
--O2: Ausgabe wird minimiert (.js.mem Datei wird generiert)
--O3: Weitere Optimierung (etwas kleinere Datei als O2)
Die von O2 und O3 gleichzeitig generierte Datei ".js.mem" ist eine wesentliche Datei für die Ausführung des generierten ".js" -Codes.
Die Debug-Option wird in Kombination mit der Optimierungsoption nach O2 verwendet, um die Minimierung ** zu unterdrücken.
--g1: Leer speichern --g2: Funktionsname speichern --g3: Variablennamen speichern --g4: Quellkarte generieren (.map Datei)
Der vollständige Quellcode enthält "Makefile".
Recommended Posts