Subscribed unsubscribe Subscribe Subscribe

枕を欹てて聴く

香炉峰の雪は簾を撥げて看る

Let's WeakMap

ECMAScript JavaScript ES.next

ES.nextとして入っていて, ECMAScript 6にも入りそうな気配がするWeakMap. という訳で.

WeakMapとは

WeakMapとは,
harmony:weak_maps [ES Wiki]

  1. keyへの参照が弱参照
  2. keyが任意のObject
  3. valueはなんでもあり

というものです.

弱参照であるため, WeakMapのkeyに指定されたObjectが, weakなreferenceからしか参照されていなかった場合, GCに回収されます.
また, WeakMapという名前が隠しがちですが, どちらかと言うと主機能は任意のObjectがkeyとして取れるということでしょう.

var map = new WeakMap();
var obj = {};
map[obj] = "OK";  // このとき, toString()されたりしない. Objectをとれる

従来のObjectは実質HashTableでしたが, そのkeyはStringに限定されていました. 結果, 例えば複数のObjectのidentifyをしたい(setを作りたいような)ときは,

  1. Object一つ一つにidをうち, それをkeyにしたHashTableを引く
  2. Objectを配列に格納し, 毎回線形探索する

という必要がありました. 例示します.

// part 1
function ObjectMap() {
  this.table = {};
}
ObjectMap.counter = 0;

ObjectMap.prototype.set = function ObjectMap_Set(obj, value) {
  if (typeof obj.__id__ === 'undefined') {
    obj.__id__ = ObjectMap.counter++;
  }
  this.table[obj.__id__] = value;
}

ObjectMap.prototype.get = function ObjectMap_Get(obj) {
  if (typeof obj.__id__ === 'undefined') {
    return false;
  }
  return !!this.table[obj.__id__];
}

var set = new ObjectMap();
var ident1 = {};
set.set(ident1, 10);
console.assert(set.get(ident1));

var ident2 = {};
console.assert(!set.get(ident2));

この場合, __id__がいじられたらまずいという話, そもそもobjに勝手に__id__とか生やすのは嫌という話, 及びcounterの値が2の53乗を超えるといろいろアウトというものがあります. まあ, もし範囲を広げたければ-から始めればいいとか, あふれるはずないだろとかそんなのもありますが, 別にmemory逼迫しなくても最悪溢れさせることはできるわけで, それは非常に気分が悪いものではあります.
また, __id__が打たれたObjectが回収されてもわからないので, ずっとtableに残り続けてしまいます. tableがshrinkされることはありません.

part 2

// part 1
function ObjectMap() {
  this.keys = [];
  thsi.values = [];
}

ObjectMap.prototype.set = function ObjectMap_Set(obj, value) {
  var index = this.keys.indexOf(obj);
  if (index === -1) {
    this.keys.push(obj);
    this.values.push(value);
  } else {
    this.values[index] = value;
  }
}

ObjectMap.prototype.get = function ObjectMap_Get(obj) {
  var index = this.keys.indexOf(obj);
  if (index == -1) {
    return false;
  }
  return this.values[index];
}

var set = new ObjectMap();
var ident1 = {};
set.set(ident1);
console.assert(set.get(ident1));

var ident2 = {};
console.assert(!set.get(ident2));

これは見るだけで簡単ですね. あふれるとかそういうのもないので, 持続性はあります... あります?
これはこれで問題があって, keys/valuesが参照を持っているので, まずいつまでたっても一度setしたobjはObjectMapの寿命の分だけ回収されない問題があります. また, 一目で分かる通り, 線形探索です...

外側の挙動自体はこのように再現できるのではありますがどれも問題があったのです.
実際, 先進機能を試すということで, es-labではこのような方法によって実装したWeakMap.jsが公開されています.
WeakMap.js - es-lab - Experiments with proposed extensions to EcmaScript - Google Project Hosting
これはident__というgetterを定義して, ここからclosureで__id__に当たるものを取得する. idはMath.randomで作られるというものです. そして同じidになった時のことを考えてlistを持っていて検索するというhash tableのような構成になっています.


WeakMapの場合はweak referenceなので, これが全て解消されます.

実用例

すでに様々な方が実用例をあげています.


id:mooz さんが挙げられているように, Objectがidentifyできて, それに対して値をひもづけられるので, 何らかの関係値を収納しておくという使い方(objectに新たなpropertyをはやさなくていいい)
Mozilla 勉強会で ECMAScript 6 の WeakMap について LT しました - mooz deceives you


また, id:murky-satyr さんが挙げられているように, WeakMapでidentifyが定数時間でできるので, 効率的なidentifyを実装することができ, Arrayのuniqueを高速に実装するなどといった利用法があります.
WeakMap uniq - ellaneous


また, Weakなreferenceであるということを利用すれば, 例えばある種IDとしてobjを紐づけておいて, これをkeyとしてcacheを引く. で, 利用者はこのIDを所持している間はcacheを引けますが, だれもIDを持たなくなって, 利用者がいなくなればいつの間にかcacheが消えるというような利用法もあります.

function Cache() {
  this.cache = new WeakMap();
}

Cache.prototype.set = function Cache_Set(cache) {
  var ID = {};
  this.cache.set(ID, cache);
  return ID;
}

Cache.prototype.get = function Cache_Get(ID) {
  return this.cache.get(ID);
}


さらに, eswikiには他にも多くの利用例が例示されています.
harmony:weak_maps [ES Wiki]
なんか多少とっつきにくいですが. ナチュラルにconst function declarationが利用されているのでそこだけ注意してください (constなVariableDeclarationが今まで半ば準標準として存在した中, constなFunctionDeclarationというものがなかったので, harmonyで提案されている). 紹介します.

  • Soft Own Fields
    • moozさんの例と同じく, あるobjectに対して値を紐付けるという使い方です. freezeとかされてpropertyを作ることができなくなっても利用できます
  • Explicit Soft Own Fields
    • get / setでしかpropertyのようなものを定義できないようfreezeしちゃったobjectを返してしまう. 上の実用例
  • Inherited Soft Own Fields
    • それをprototypeをたどりつつ行う. 継承機能追加
  • Trademark
    • classのようなものを実現して引数とかのclassをguardして, 特定のclassしか受け付けないようなのが簡単に書けるようにしようというもの.

ちょっとTrademarkは面白いので書いてみましょう. ES5調にES.next!!

function Trademark(msg) {
  msg || (msg = "not stamped target");
  var map = WeakMap();
  return Object.freeze({
    stamp: function(obj) { map.set(obj, true); },
    has: function(obj) { return !!map.get(obj); },
    guard: function(obj) {
      if (!map.get(obj)) {
        throw new Error(msg);
      }
    }
  });
}

// で, MyClass この時に結構面白い事を...
var MyClass = (function() {
  var trademark = Trademark("not MyClass");
  function MyClass(x, y) {
    this.x = x;
    this.y = y;
    // thisを登録. WeakMapだから, このinstanceがなくなったら自動で消えてくれるので安心
    trademark.stamp(this);
  }
  // hasとguardを公開
  MyClass.has = trademark.has;
  MyClass.guard = trademark.guard;
  return MyClass;
})();

// 例えば
MyClass.prototype.add = function(rhs) {
  // MyClassしか受け付けたくない!! => gaurd!!
  MyClass.guard(rhs);
  return new MyClass(this.x + rhs.x, this.y + rhs.y);
}

簡単にClassを厳密制限できます. これ, 結構欲しい方いるんじゃないでしょうか. すごいですね... さすがみんな大好きeswikiの例.
WeakMapなので, instanceを登録しまくっても, instanceの参照が消えれば自動で消えて行くのが素晴らしいpointですね. constructorとか不安定な値に頼らず厳密にclassを構成できます...

  • Unique Labeller
    • Object一つ一つにidを割り振るというのをWeakMapでやろうという逆転の発想的な. property増やさなくてもいいので, いいですね.
  • Sealer / Unsealer
    • さっき自分で書いたCacheみたいなものです. IDを発行する形で, そのIDから逆引きできるようにするわけですね.
  • Cyclic-tolerant graph walking
    • id:murky-satyr さんがすでに指摘している, identifyするのに使えるというのを利用して, あるnodeを一度見たことがあるかを検出するというわけです. Array.prototype.uniqueの実装がわかっていればその1利用という形ですね.


という形で利用できるわけで, 思いの外うはうはなわけです. 誰だ, よくわからずに「そんなの誰が使うの.....」とか言った奴は! (昔の自分)

実装の話

実装の話. うすうす気がついていらっしゃると思いますが, WeakMapはObjectのptrに対するHashTableです. Symbolではなく. ptrは結局は数値なのですから, 当然HashTableに格納できます. この時, WeakMapはある種特殊なGCの扱われ方をすることで, Weakなreferenceを実現します. ではSpiderMonkey, V8の実装から.

SpiderMonkey

SpiderMonkeyはcompactionがないので, ObjectはAllocateされてから回収されるまで, 常に一つのpointerを持ちます. なので, 単純にこれをkeyとして利用すればいいのですね.
で, 問題は回収. weakとはいかなるものなのか?

  1. GCが走ります. まずMark phase
  2. ひとしきりmark phaseが走ります
    1. このとき, WeakMapを見つけると, Contextに紐付けておきます. こうしてContextにliveなWeakMapの連結リストが構築されます.
  3. Weakなreferenceのための特別mark phaseが始まります ここは実はloopします (weak実現その1)
    1. WeakMap各々を見ていきます. Contextに紐づいているものから辿ります
      1. この時keyがliveであれば, valueをmarkします
    2. もしも一度もvalueをmarkする機会がなければ, step 4へjump!!
    3. valueなどmarkしたものが溜まっているので, そこからひとしきりmark phaseを走らせます.
    4. ここで, step 3にもどる
  4. WeakMapのclean up phaseが特別に設けられています. sweep phaseの前です
    1. Contextから全てのWeakMapをたどることができるので...
    2. 対象WeakMapのkey一つ一つについて見ていきます. もしもこの時点でmarkされていなければ, どこからも参照されていなかったkeyであったということです
    3. よってそのkeyのentryをWeakMapのtableからremoveします (weak実現その2)
  5. sweep phaseが走ります

というふうになっています. このようにGCが走るたびに確実にWeakMapからweakなだけのものは取り除かれなければいけません(clean up phase). GCが走ってObjectが回収されたのであれば, それに紐づいたweak mapのkeyは「絶対に」削除される必要があります. なぜなら,

var map = new WeakMap();
(function phase1() {
  var obj = {};
  map.set(obj, 1000);
})();
// ここでGCが走るとして...

// phase1のobjはどこからももう参照されていないので, 対象のmemory空間は解放されている.
// よって, ここで新しくつくるobjが全く同じptrになる可能性がある.
var obj = {};

// このとき, すでにWeakMapからkeyを取り除いていなければ, 違うobjなのに誤検出する可能性がある.
console.assert(!map.get(obj));

というわけで, sweepしたらちゃんとWeakMapをshrinkしなければいけません.

V8

V8は自分は実装がちょっと難しいのではないかと考えていました. なぜなら, V8のGCはCopy GC + Mark & Compaction GCの世代別GCという超贅沢GCなのです.
Copy GC / Compactionが走るということは, あるObjectについて指しているpointerが変更されるということです. これがWeakMapのidentifyとしてptrを使うので, 厳しいのではないかと考えていたのです.
ところが, V8はすでにWeakMapを実装しています. 使いたければ, --harmony_weakmaps とoptionをつけると使うことができます. (わからなければnode.js界隈のすごい方々に聞いてみましょう!)


ではどう実装するのか, V8のCopying GC (内部名称Scavenge GC), Mark & Compaction GC (MarkCompaction)と別に考えます.


まずScavenge GC, この時, WeakMapは実はweakでもなんでもありません.
WeakMapはobjectのpointerをkeyにしたhash tableを所持していますが, FixedArrayによって作られたHashTableで(容量がextendされるとinstanceが新たに作られるというもの. これを自分の所持品に割り当て直す), 普通にすべてCopy GCがmigrationします. よってkeyのobjectもCopy GCが走った時点では普通に残っていて, weakではありません. ただしちゃんとmigrateされるので, pointerはきちんとCopy先のものなどに更新され続けています.
でもよくよく考えるとScavenge GCが走っている時というのはmemory的に逼迫していないので, 別に回収してもらわなくても全然構わないのです. Mark & Compactionが走ったときにweakであればall okです.


で, Mark & Compaction. これは普通にmarkしていくので, ここではSpiderMonkeyとほぼ同じことをやっていきます.
よってpointerが張り替えられるGCを持つV8でもWeakMapは実現されたのです! すごい!

mark & sweep algorithm

で, このGCのalgorithm, なんとproposalに載っています. もろ載っています.
harmony:weak_maps [ES Wiki]

While any objects are fringe {
  While any objects are fringe, pick a fringe object x {
    If (x is the get() function of a weak map) {
      Note this weak map.
    } else {
      For all y's directly reachable from x {
        if y is untraced, color it fringe.
      }
    }
    Color x retained.
  }

  For each noted weak map wm {
    For each k,v pair in wm {
      If k is retained and v is untraced, color v fringe
    }
  }
}

これがmarkのalgorithmです. 全体としてloopしていますね. SpiderMonkeyの例でもloopしていました. これはなぜか?

以下のような状態の時,

w1 = {
  key1 => value1
}
w2 = {
  key2 => key1
}
key2への参照

もしもloopしなければ, おかしなことになります.


試してみます. w1から扱った場合

  1. 通常mark phaseが走る
    1. key2がmarkされる
  2. w1のkey1はどこからも参照されていない(w2のvalueがmarkされていないので)
    1. w1のkey1, value1はmarkされない
  3. w2のkey2は参照されている
    1. w2のvalueであるkey1をmarkする

あれ, key1生きてるのにvalue1がmarkされていない...
というわけで深刻なbugになります.

ここできちんとloopすれば,

  1. 通常mark phaseが走る
    1. key2がmarkされる
  2. w1のkey1はどこからも参照されていない(w2のvalueがmarkされていないので)
    1. w1のkey1, value1はmarkされない
  3. w2のkey2は参照されている
    1. w2のvalueであるkey1をmarkする
  4. valueをmarkする機会があったので, loop
  5. 通常mark phaseが走る for key1
  6. w1のkey1がmarkされている
    1. w1のvalue1をmark
  7. w2もみるけど, 特に新しいことなし
  8. value1をmarkしたので, loop
  9. 通常mark phaseが走る for value1
  10. w1, w2をみるけど, 特に新しいことなし
  11. 新しいことなかったので, 終了!

ということになります.
これですべて適切にmarkされました!

要は, WeakMapのkey checkで新しくmarkされたobjectが増えるので(valueがmark対象になるかも), 今までもう「参照されていない」と思われていたkeyが実は他のWeakMapから参照されていた(もしくはそのvalueの参照route先で参照されていた)という事態が起こり, WeakMapのcheck phaseで一度でもvalueを新たにmarkするのであれば, そのvalueから続く参照たちへのmarkingと, 新たに参照が増えた状態でのWeakMapのkeyのcheckをもう一度行う必要があるのです.

このalgorithm, SpiderMonkeyもV8もわりとそのまま実装しているので面白いです.
SpiderMonkeyの場合はjsgc.cpp, V8の場合はmark-compat.ccのMarkCompactionCollector::EmptyMarkingDequeなどを御覧ください.

Remove all ads