RubiMaVM を JavaScript に移植してみた

VM に興味がわいたので るびま を読んだ。
そして、 RubiMaVM を Javascript に移植してみた。

var RubiMaVM = {};

RubiMaVM.Instruction = function Instruction(code, opts) {
	this.code = code;
	this.opts = opts;
};

RubiMaVM.Instruction.prototype.toString = function toString() {
	return this.code + ' <' + this.opts.join(', ') + '>';
};

RubiMaVM.Label = function Label(label) {
	this.label = label;
	this.pos = -1;
	this.id = ++ RubiMaVM.Label.id;
};

RubiMaVM.Label.id = 0;

RubiMaVM.Label.prototype.toString = function toString() {
	return this.label + ' <' + this.id + '@' + this.pos + '>';
};

RubiMaVM.Evaluator = function Evaluator() {
	this.stack = [];
	this.pc = 0;
};

RubiMaVM.Evaluator.prototype.evaluate = function evaluate(sequence) {
	var insn;
	while((insn = sequence[this.pc])) {
		this.dispatch(insn);
	}
	return this.stack[0];
};

RubiMaVM.Evaluator.prototype.dispatch = function dispatch(insn) {
	var lhs, rhs;
	switch(insn.code) {
	case 'nop':
		break;
	case 'push':
		this.stack.push(insn.opts[0]);
		break;
	case 'pop':
		this.stack.pop();
		break;
	case 'dup':
		this.stack.push(this.stack[this.stack.length-1]);
		break;
	case 'add':
		rhs = this.stack.pop(), lhs = this.stack.pop();
		this.stack.push(lhs + rhs);
		break;
	case 'sub':
		rhs = this.stack.pop(), lhs = this.stack.pop();
		this.stack.push(lhs - rhs);
		break;
	case 'mul':
		rhs = this.stack.pop(), lhs = this.stack.pop();
		this.stack.push(lhs * rhs);
		break;
	case 'div':
		rhs = this.stack.pop(), lhs = this.stack.pop();
		this.stack.push(lhs / rhs);
		break;
	case 'not':
		this.stack.push(!this.stack.pop());
		break;
	case 'lt':
		var rhs = this.stack.pop(), lhs = this.stack.pop();
		this.stack.push(lhs < rhs);
		break;
	case 'gt':
		rhs = this.stack.pop(), lhs = this.stack.pop();
		this.stack.push(lhs > rhs);
		break;
	case 'lteq':
		rhs = this.stack.pop(), lhs = this.stack.pop();
		this.stack.push(lhs <= rhs);
		break;
	case 'gteq':
		rhs = this.stack.pop(), lhs = this.stack.pop();
		this.stack.push(lhs >= rhs);
		break;
	case 'goto':
		this.pc = insn.opts[0].pos;
		return;
	case 'ifne':
		if(this.stack.pop()) {
			this.pc = insn.opts[0].pos;
			return;
		}
		break;
	default:
		throw 'Unknown Opcode: ' + insn.code;
	}
	++ this.pc;
}

RubiMaVM.Parser = {}

RubiMaVM.Parser.parse = function parse(program) {
	var pc = 0;
	var labels = {};
	var lines = program.split('\n');
	var sequence = [];
	var label, lobj;
	for(var i = 0; i < lines.length; i ++) {
		var line = lines[i].match(/^\s*(.*?)\s*$/)[1];
		var insn = [];
		if(/^:\w+$/.test(line)) {
			label = line;
			if(!(lobj = labels[label])) {
				lobj = labels[label] = new RubiMaVM.Label(label);
			}
			lobj.pos = pc;
			continue;
		}
		while(line.length > 0) {
			var m;
			if((m = line.match(/^:[a-z]+/))) {
				label = m[0];
				if(!(lobj = labels[line])) {
					lobj = labels[line] = new RubiMaVM.Label(label);
				}
				insn.push(lobj);
			} else if((m = line.match(/^\s+/)) || (m = line.match(/^#.*/))) {
				// ignore
			} else if((m = line.match(/^[a-z]+/))) {
				insn.push(m[0]);
			} else if((m = line.match(/^\d+/))) {
				insn.push(+m[0]);
			} else {
				throw 'Parse Error: ' + line;
			}
			line = line.slice(m[0].length);
		}
		if(insn.length > 0) {
			++ pc;
			sequence.push(new RubiMaVM.Instruction(insn[0], insn.slice(1)));
		}
	}
	return sequence;
};

function main() {
	var program = [
		'  #',
		'  push 1',
		':label',
		'  push 1',
		'  add',
		'  dup',
		'  push 100000',
		'  lt',
		'  ifne :label',
		''
	].join('\n');

	var sequence = RubiMaVM.Parser.parse(program);
	for(var i = 0; i < sequence.length; i ++) {
		var insn = sequence[i];
		print((Array(4).join('0')+i).slice(-4) + '\t' + insn);
	}

	var result = new RubiMaVM.Evaluator().evaluate(sequence);
	print(result);
}

main();

命令の名前（文字列）で switch-case して命令ディスパッチしているのを、数値で switch-case したりディスパッチテーブルを使ったりしてみた。

--- rubimavm-switchname.js	2008-09-07 14:27:12.000000000 +0900
+++ rubimavm-switchval.js	2008-09-07 14:35:55.000000000 +0900
@@ -6,9 +6,32 @@
 };
 
 RubiMaVM.Instruction.prototype.toString = function toString() {
-	return this.code + ' <' + this.opts.join(', ') + '>';
+	return RubiMaVM.Instruction.CodeNames[this.code] + ' <' + this.opts.join(', ') + '>';
 };
 
+RubiMaVM.Instruction.CodeNames = [
+	'nop',
+	'push',
+	'pop',
+	'dup',
+	'add',
+	'sub',
+	'mul',
+	'div',
+	'not',
+	'lt',
+	'gt',
+	'lteq',
+	'gteq',
+	'goto',
+	'ifne'
+]
+
+RubiMaVM.Instruction.Code = {};
+RubiMaVM.Instruction.CodeNames.forEach(function(name,i){
+	RubiMaVM.Instruction.Code[name] = i;
+});
+
 RubiMaVM.Label = function Label(label) {
 	this.label = label;
 	this.pos = -1;
@@ -37,56 +60,56 @@
 RubiMaVM.Evaluator.prototype.dispatch = function dispatch(insn) {
 	var lhs, rhs;
 	switch(insn.code) {
-	case 'nop':
+	case 0: // nop
 		break;
-	case 'push':
+	case 1: // push
 		this.stack.push(insn.opts[0]);
 		break;
-	case 'pop':
+	case 2: // pop
 		this.stack.pop();
 		break;
-	case 'dup':
+	case 3: // dup
 		this.stack.push(this.stack[this.stack.length-1]);
 		break;
-	case 'add':
+	case 4: // add
 		rhs = this.stack.pop(), lhs = this.stack.pop();
 		this.stack.push(lhs + rhs);
 		break;
-	case 'sub':
+	case 5: // sub
 		rhs = this.stack.pop(), lhs = this.stack.pop();
 		this.stack.push(lhs - rhs);
 		break;
-	case 'mul':
+	case 6: // mul
 		rhs = this.stack.pop(), lhs = this.stack.pop();
 		this.stack.push(lhs * rhs);
 		break;
-	case 'div':
+	case 7: // div
 		rhs = this.stack.pop(), lhs = this.stack.pop();
 		this.stack.push(lhs / rhs);
 		break;
-	case 'not':
+	case 8: // not
 		this.stack.push(!this.stack.pop());
 		break;
-	case 'lt':
+	case 9: // lt
 		var rhs = this.stack.pop(), lhs = this.stack.pop();
 		this.stack.push(lhs < rhs);
 		break;
-	case 'gt':
+	case 10: // gt
 		rhs = this.stack.pop(), lhs = this.stack.pop();
 		this.stack.push(lhs > rhs);
 		break;
-	case 'lteq':
+	case 11: // lteq
 		rhs = this.stack.pop(), lhs = this.stack.pop();
 		this.stack.push(lhs <= rhs);
 		break;
-	case 'gteq':
+	case 12: // gteq
 		rhs = this.stack.pop(), lhs = this.stack.pop();
 		this.stack.push(lhs >= rhs);
 		break;
-	case 'goto':
+	case 13: // goto
 		this.pc = insn.opts[0].pos;
 		return;
-	case 'ifne':
+	case 14: // ifne
 		if(this.stack.pop()) {
 			this.pc = insn.opts[0].pos;
 			return;
@@ -128,7 +151,11 @@
 			} else if((m = line.match(/^\s+/)) || (m = line.match(/^#.*/))) {
 				// ignore
 			} else if((m = line.match(/^[a-z]+/))) {
-				insn.push(m[0]);
+				var code = RubiMaVM.Instruction.Code[m[0]];
+				if(code === undefined) {
+					throw 'Unknown Opcode: ' + m[0];
+				}
+				insn.push(code);
 			} else if((m = line.match(/^\d+/))) {
 				insn.push(+m[0]);
 			} else {

--- rubimavm-switchname.js	2008-09-07 14:27:12.000000000 +0900
+++ rubimavm-dispatchtable.js	2008-09-07 14:14:19.000000000 +0900
@@ -6,9 +6,32 @@
 };
 
 RubiMaVM.Instruction.prototype.toString = function toString() {
-	return this.code + ' <' + this.opts.join(', ') + '>';
+	return RubiMaVM.Instruction.CodeNames[this.code] + ' <' + this.opts.join(', ') + '>';
 };
 
+RubiMaVM.Instruction.CodeNames = [
+	'nop',
+	'push',
+	'pop',
+	'dup',
+	'add',
+	'sub',
+	'mul',
+	'div',
+	'not',
+	'lt',
+	'gt',
+	'lteq',
+	'gteq',
+	'goto',
+	'ifne'
+]
+
+RubiMaVM.Instruction.Code = {};
+RubiMaVM.Instruction.CodeNames.forEach(function(name,i){
+	RubiMaVM.Instruction.Code[name] = i;
+});
+
 RubiMaVM.Label = function Label(label) {
 	this.label = label;
 	this.pos = -1;
@@ -34,68 +57,86 @@
 	return this.stack[0];
 };
 
+RubiMaVM.Evaluator.prototype.body_nop = function body_nop() {
+};
+
+RubiMaVM.Evaluator.prototype.body_push = function body_push(val) {
+	this.stack.push(val);
+};
+
+RubiMaVM.Evaluator.prototype.body_pop = function body_pop() {
+	this.stack.pop();
+};
+
+RubiMaVM.Evaluator.prototype.body_dup = function body_dup() {
+	this.stack.push(this.stack[this.stack.length-1]);
+};
+
+RubiMaVM.Evaluator.prototype.body_add = function body_add() {
+	var rhs = this.stack.pop(), lhs = this.stack.pop();
+	this.stack.push(lhs + rhs);
+};
+
+RubiMaVM.Evaluator.prototype.body_sub = function body_sub() {
+	var rhs = this.stack.pop(), lhs = this.stack.pop();
+	this.stack.push(lhs - rhs);
+};
+
+RubiMaVM.Evaluator.prototype.body_mul = function body_mul() {
+	var rhs = this.stack.pop(), lhs = this.stack.pop();
+	this.stack.push(lhs * rhs);
+};
+
+RubiMaVM.Evaluator.prototype.body_div = function body_div() {
+	var rhs = this.stack.pop(), lhs = this.stack.pop();
+	this.stack.push(lhs / rhs);
+};
+
+RubiMaVM.Evaluator.prototype.body_not = function body_not() {
+	this.stack.push(!this.stack.pop());
+};
+
+RubiMaVM.Evaluator.prototype.body_lt = function body_lt() {
+	var rhs = this.stack.pop(), lhs = this.stack.pop();
+	this.stack.push(lhs < rhs);
+};
+
+RubiMaVM.Evaluator.prototype.body_gt = function body_gt() {
+	var rhs = this.stack.pop(), lhs = this.stack.pop();
+	this.stack.push(lhs > rhs);
+};
+
+RubiMaVM.Evaluator.prototype.body_lteq = function body_lteq() {
+	var rhs = this.stack.pop(), lhs = this.stack.pop();
+	this.stack.push(lhs <= rhs);
+};
+
+RubiMaVM.Evaluator.prototype.body_gteq = function body_gteq() {
+	var rhs = this.stack.pop(), lhs = this.stack.pop();
+	this.stack.push(lhs >= rhs);
+};
+
+RubiMaVM.Evaluator.prototype.body_goto = function body_goto(label) {
+	this.pc = label.pos;
+	return true;
+};
+
+RubiMaVM.Evaluator.prototype.body_ifne = function body_ifne(label) {
+	if(this.stack.pop()) {
+		this.pc = label.pos;
+		return true;
+	}
+};
+
+RubiMaVM.Evaluator.DispatchTable = [];
+RubiMaVM.Instruction.CodeNames.forEach(function(name, i){
+	RubiMaVM.Evaluator.DispatchTable[i] = RubiMaVM.Evaluator.prototype['body_'+name];
+});
+
 RubiMaVM.Evaluator.prototype.dispatch = function dispatch(insn) {
-	var lhs, rhs;
-	switch(insn.code) {
-	case 'nop':
-		break;
-	case 'push':
-		this.stack.push(insn.opts[0]);
-		break;
-	case 'pop':
-		this.stack.pop();
-		break;
-	case 'dup':
-		this.stack.push(this.stack[this.stack.length-1]);
-		break;
-	case 'add':
-		rhs = this.stack.pop(), lhs = this.stack.pop();
-		this.stack.push(lhs + rhs);
-		break;
-	case 'sub':
-		rhs = this.stack.pop(), lhs = this.stack.pop();
-		this.stack.push(lhs - rhs);
-		break;
-	case 'mul':
-		rhs = this.stack.pop(), lhs = this.stack.pop();
-		this.stack.push(lhs * rhs);
-		break;
-	case 'div':
-		rhs = this.stack.pop(), lhs = this.stack.pop();
-		this.stack.push(lhs / rhs);
-		break;
-	case 'not':
-		this.stack.push(!this.stack.pop());
-		break;
-	case 'lt':
-		var rhs = this.stack.pop(), lhs = this.stack.pop();
-		this.stack.push(lhs < rhs);
-		break;
-	case 'gt':
-		rhs = this.stack.pop(), lhs = this.stack.pop();
-		this.stack.push(lhs > rhs);
-		break;
-	case 'lteq':
-		rhs = this.stack.pop(), lhs = this.stack.pop();
-		this.stack.push(lhs <= rhs);
-		break;
-	case 'gteq':
-		rhs = this.stack.pop(), lhs = this.stack.pop();
-		this.stack.push(lhs >= rhs);
-		break;
-	case 'goto':
-		this.pc = insn.opts[0].pos;
-		return;
-	case 'ifne':
-		if(this.stack.pop()) {
-			this.pc = insn.opts[0].pos;
-			return;
-		}
-		break;
-	default:
-		throw 'Unknown Opcode: ' + insn.code;
+	if(!RubiMaVM.Evaluator.DispatchTable[insn.code].apply(this, insn.opts)) {
+		++ this.pc;
 	}
-	++ this.pc;
 }
 
 RubiMaVM.Parser = {}
@@ -128,7 +169,11 @@
 			} else if((m = line.match(/^\s+/)) || (m = line.match(/^#.*/))) {
 				// ignore
 			} else if((m = line.match(/^[a-z]+/))) {
-				insn.push(m[0]);
+				var code = RubiMaVM.Instruction.Code[m[0]];
+				if(code === undefined) {
+					throw 'Unknown Opcode: ' + m[0];
+				}
+				insn.push(code);
 			} else if((m = line.match(/^\d+/))) {
 				insn.push(+m[0]);
 			} else {

速度比較

$ time js rubimavm-switchname.js
0000	push <1>
0001	push <1>
0002	add <>
0003	dup <>
0004	push <100000>
0005	lt <>
0006	ifne <:label <1@1>>
100000

real	0m3.409s
user	0m3.100s
sys	0m0.000s
$ time js rubimavm-switchval.js
0000	push <1>
0001	push <1>
0002	add <>
0003	dup <>
0004	push <100000>
0005	lt <>
0006	ifne <:label <1@1>>
100000

real	0m2.790s
user	0m2.564s
sys	0m0.000s
$ time js rubimavm-dispatchtable.js 
0000	push <1>
0001	push <1>
0002	add <>
0003	dup <>
0004	push <100000>
0005	lt <>
0006	ifne <:label <1@1>>
100000

real	0m7.793s
user	0m7.640s
sys	0m0.000s

ディスパッチテーブル ＜ 文字列でswitch-case ＜ 数値でswitch-case