airheadの日記: code:ringnode benchmark
ノードを表すオブジェクトのメソッド (receive) が次のノードのメソッドを呼んでいくと、関数スタックがたまりすぎてしまう。ここでは配達人役の関数sendを用意し、メッセージを引数としてノードのメソッドを呼び、戻り値として次のノードへの参照と次に渡すメッセージ(通常は引数として受け取ったメッセージそのまま)を受け取る形にした。規定周回数に達したらメソッドreceiveはfalseを返し、それを受け取った関数sendは処理を終了する。
list 1-4で、sendに参照とメッセージを返す方法を変えている。list 1ではreceive内で参照とメッセージを束ねたオブジェクトを毎回生成している。
// list 1
var send = function (dest, msg) {
var relay;
while (relay = dest.receive(msg)) {
dest = relay.dest;
msg = relay.msg;
}
return msg;
};
var Node = function () {
var id = 0;
return function () {
this.id = id++;
this.dest = this;
this.receive = function (msg) {
if (typeof this.count == "number") {
if (this.count == 0) return false;
this.count--;
}
return {dest: this.dest, msg: msg};
};
};
}();
var n = 1000, m = 1000;
var ring = [];
ring[0] = new Node();
for (var i = 1; i < n; i++) {
ring[i] = new Node();
ring[i - 1].dest = ring[i];
}
ring[n - 1].dest = ring[0];
ring[0].count = m;
var t = new Date();
var lastMsg = send(ring[0], "read me in turn.");
t = new Date() - t;
alert("elapsed time:\n" + t + "[ms]\n\nmessage:\n" + lastMsg);
list 2ではsend内でオブジェクトを用意しておき、各receiveがそこに書き込むようにして一つのオブジェクトを使いまわしている。
// list 2
var send = function (dest, msg) {
var relay = {dest: dest, msg: msg};
while (relay.dest.receive(relay.msg, relay));
return relay.msg;
};
var Node = function () {
var id = 0;
return function () {
this.id = id++;
this.dest = this;
this.receive = function (msg, relay) {
if (typeof this.count == "number") {
if (this.count == 0) return false;
this.count--;
}
relay.dest = this.dest;
relay.msg = msg;
return true;
};
};
}();
var n = 1000, m = 1000;
// 以下list 1と同じ
list 3では各ノードのメソッドreceiveおよび関数から見える変数で受け渡している。この変数をクロージャによりグローバルから隠蔽しようと、関数sendもノードのメソッドにしてしまった。
// list 3
var Node = function () {
var id = 0;
var relayDest, relayMsg;
return function () {
this.id = id++;
this.dest = this;
this.receive = function (msg) {
if (typeof this.count == "number") {
if (this.count == 0) return false;
this.count--;
}
relayDest = this.dest;
relayMsg = msg;
return true;
};
this.send = function (msg) {
relayDest = this;
relayMsg = msg;
while (relayDest.receive(relayMsg));
return relayMsg;
};
};
}();
var n = 1000, m = 1000;
var ring = [];
ring[0] = new Node();
for (var i = 1; i < n; i++) {
ring[i] = new Node();
ring[i - 1].dest = ring[i];
}
ring[n - 1].dest = ring[0];
ring[0].count = m;
var t = new Date();
var lastMsg = ring[0].send("read me in turn.");
t = new Date() - t;
alert("elapsed time:\n" + t + "[ms]\n\nmessage:\n" + lastMsg);
list 3のようにメソッドsendを全オブジェクトに付加しても呼ばれるのは一つだけでメモリ効率が悪いので、list 4ではプロトタイプで付加するようにした。
// list 4
var send;
var Node = function () {
var id = 0;
var relayDest, relayMsg;
send = function (msg) {
relayDest = this;
relayMsg = msg;
while (relayDest.receive(relayMsg));
return relayMsg;
}
return function () {
this.id = id++;
this.dest = this;
this.receive = function (msg) {
if (typeof this.count == "number") {
if (this.count == 0) return false;
this.count--;
}
relayDest = this.dest;
relayMsg = msg;
return true;
};
};
}();
Node.prototype.send = send;
var n = 1000, m = 1000;
// 以下list 3と同じ
list 5。list 1-4で用いたコメントアウト部のコードに替えて前半部のコードを用い、配列生成を回避した。変数n2が次のノード(新規オブジェクト)を参照しても、一つ前のノードにはさらに前のノードからの参照が残っており、オブジェクトが開放されることはなくリングが形成される。
// list 5
var n0 = new Node();
var n1 = n0;
for (var i = 1; i < n; i++) {
n2 = new Node();
n1.dest = n2;
n1 = n2;
}
n1.dest = n0;
n0.count = m;
/*
var ring = [];
ring[0] = new Node();
for (var i = 1; i < n; i++) {
ring[i] = new Node();
ring[i - 1].dest = ring[i];
}
ring[n - 1].dest = ring[0];
ring[0].count = m;
*/
(07/12 13:30 追記) 書き忘れていたlist 6。各ノードにメッセージを保持するプロパティmsgを持たせ、次ノードへのメッセージ伝達はノード自身が行い、メソッドsendは次順のみを管理する。もっとも素直に実装すればこの形になるかと思うが、list 3より若干遅い。(list 3を書き換えて再現したのでメソッド名と動作内容がかけ離れているが、差異がわかりやすいと思い、そのままにしておく)
// list 6
var Node = function () {
var id = 0;
var relayDest;
return function () {
this.id = id++;
this.dest = this;
this.msg = "";
this.receive = function () {
if (typeof this.count == "number") {
if (this.count == 0) return false;
this.count--;
}
relayDest = this.dest;
this.dest.msg = this.msg;
this.msg = "";
return true;
};
this.send = function (msg) {
relayDest = this;
relayDest.msg = msg;
while (relayDest.receive());
return relayDest.msg;
};
};
}();
var n = 1000, m = 1000;
// 以下list 3と同じ