YieldExpression with delegate

In the latest ECMA262 6th draft (rev15), YieldExpression with delegate detailed algorithm is defined.

Reading the spec algortithm, I think this is very useful to put together iterators to make a complex iterator.

edit: I've reported issues in the spec about this section. https://bugs.ecmascript.org/show_bug.cgi?id=1486 https://bugs.ecmascript.org/show_bug.cgi?id=1487

For example,

function* gen() {
    for (let i = 0; i < 100; ++i) {
        yield i;
    }
}

function* main() {
     yield * gen();
}

for (let i of main()) {
    console.log(i);  // 0 -> 99
}

function* gen() {
    for (var i = 0; i < 100; ++i) {
        var receive = yield i;
        console.log(receive);    // 0, 1, 4, 9, ... , 9801
    }
}

function* main() {
    yield* gen();
}

let result = { done: false, value: undefined };
let iterator = main();
do {
    result = iterator.next(result.value * result.value);
    if (result.done) {
        break;
    }
    console.log(result.value);  // 0, 1, 2, 3, ..., 99
} while (true);
// the result of console is interleaved,
// 0, 0, 1, 1, 2, 4, 3, 9, ...

So we can easily create a new iterator for our data types.

function MapWithArray() {
    this.map = new Map();
    this.array = [];
}

function* MapWithArrayIterator(obj) {
    yield * obj.map;
    yield * obj.array;
}

let data = new MapWithArray;
let iterator = MapWithArrayIterator(data);

Polymorphic Inline Cache implementation of iv / lv5

This is a blog post for 12/22 VM advent calendar.

See http://qiita.com/advent-calendar/2012/vm for more nice blog posts :)

この記事は更新中です... 完成しました

Introduction

ECMA262 engine, iv / lv5 には, Polymorphic Inline Cache(以下PIC)が実装されています. ということで, ここではPIC, 特にLoadPropertyICの実装について記述したいと思います. PICのsystem本体についてはかなり多くの場所で記述されていると思うので, ここでは, かなり実践的な方向で記述したいと思います. そのため, 多くの前提知識を要求していますのでご容赦ください.

LoadOwnPropertyIC & PIC overview

iv / lv5におけるICの実装を紹介します. lv5/breaker/compiler.h

      asm_->mov(rdi, r14);
      LoadPropertyIC* ic(new LoadPropertyIC(native_code(), name));
      native_code()->BindIC(ic);
      asm_->mov(rdx, core::BitCast<uint64_t>(ic));
      const std::size_t offset = PolyIC::Generate64Mov(asm_);
      ic->BindOriginal(offset);
      asm_->call(rax);

raxに設定されているのは, 通常のLOAD_PROP関数です. このため, 一番最初の場合, LOAD_PROP関数が呼ばれます. そしてそこでは, 通常通りhashtableを引いてlookupします, 問題はここからです.

lv5/breaker/stub.h

  // cache phase
  // own property / proto property / chain lookup property
  if (slot.base() == obj) {
    // own property
    ic->LoadOwnProperty(ctx, obj->map(), slot.offset());
    return Extract(res);
  }

cacheableでown propertyであることが発覚すると, offsetを使って, ICを構築し始めます. lv5/breaker/poly_ic.h

    as.inLocalLabel();
    gen(this, &as, ".EXIT");  // ここでmain codeが作成される
    // fail path
    as.L(".EXIT");  // TestMapContentsなどで失敗するとここへjmpする
    // ここでIC末尾のjmpを生成, fallback pathへjmp
    const std::size_t pos = GenerateTail(&as);
    ic->set_tail(const_cast<uint8_t*>(as.getCode()) + pos);
    as.outLocalLabel();

      // main code

      // map一致を検査
      IC::TestMapConstant(as, map_, r8, r10, fail);
      // load
      LoadPropertyIC::GenerateFastLoad(as, r8, offset_);

    // GenerateFastLoad
    const std::ptrdiff_t data_offset =
        JSObject::SlotsOffset() +
        JSObject::Slots::DataOffset();

    // dataのpointerを取得し
    as->mov(rax, qword[reg + data_offset]);

    // offset access. 結果はraxに入れる
    // これはx64 calling convension参照
    as->mov(rax, qword[rax + kJSValSize * offset]);

    // retはICがpassした時に行われる
    as->ret();

r8にobjectが入っているので, cache対象のmapと一致するかどうかをtestします. そして一致した場合にGenerateFastLoadでoffset accessを行います. ここでretが最後に入っているところに注目です.

そして, ICの末尾をLOAD_PROP関数へのjmpにして, また, 一番初めのcallのraxをICのcallに書き換えます

  void ChainingObjectLoad(Unit* ic, uintptr_t code) {
    // このICが呼ばれるようにする
    if (empty()) {  // ICが初めて生成された時
      // rewrite original
      // LOAD_PROP呼び出しのcallを書き換え
      native_code()->assembler()->rewrite(from_original_, code, k64Size);
    } else {
      if (!object_chain()) {
        // rewrite object guard
        Rewrite(from_object_guard_, code, k64Size);
      } else {
        // 一つ前のICの最後のjmpを自分に書き換え
        object_chain()->Redirect(code);
      }
    }

    // このICの最後のjmpを設定する
    if ((size() + 1) == kMaxPolyICSize) {
      // last one
      // kMaxPolyICSizeより多くのICがぶら下がっている時
      // ICを生成しないLOAD_PROPにjmpするようにする
      ic->Redirect(core::BitCast<uintptr_t>(&stub::LOAD_PROP_GENERIC));
    } else {
      // それ以外の場合は, LOAD_PROPへjmpする
      ic->Redirect(core::BitCast<uintptr_t>(&stub::LOAD_PROP));
    }
  }

iv / lv5のICにおいては, 次々とtestをしながら条件が合うかどうかをcheckしていきます, そして, passすると, propertyをloadしてretするのです. これによって, ICが成功次第, もとのprogramのpathに戻ることができます.

ICが徐々に構築されていくさまを図で表します. 初回. 通常のLOAD_PROP stub function callになっています.

ICが構築されると, 最初のcallの対象がICになり, ICのtestで失敗するとLOAD_PROPへfallbackします.

また, LOAD_PROPは, 新たにICを構築し, 前に構築したICの最後のjmpを書き換え, 自分をchainにつなぎます. これによって, 一つのcallsiteで幾つものmapをhandleすることができます, これこそ, Polymorphicであるということです.

LoadProto/ChainPropertyIC & Map transition system

LoadOwnPropertyICにおいては, objectのmapが期待値かどうかをtestします, このtestにpassすれば, 対象のobjectのshapeはcacheをとった時のobjectのshapeと同じということであり, offset lookupによってpropertyを引っ張りだすことができます. では, prototypeにある場合, あるいはもっと上にある場合はどうでしょうか?

もっと上にあった場合, ICはその道中たどったobjectのshape全てが期待値を維持していることをtestしなければいけません. それは, 途中のobjectのshapeが変わることで, lookup先が変わる場合があるからです. ECMAScriptで例を示します.

function getToString(instance) {
  return instance.toString;
}
function Test() { }
var instance = new Test;
getToString(instance);    // lookup Object.prototype.toString
Test.prototype.toString = function() { };
getToString(instance);    // lookup Test.prototype.toString

一度目のtoString lookupでは,

1. instance object
2. Test.prototype
3. Object.prototype

とたどってlookupしました. その後Test.prototype.toStringへの代入によってTest.prototypeのshapeが変わった事によって, Object.prototypeに至らずにlookupが終了するようになっています. ここでTest.prototypeのmap testをしなければ, この変更を検知できません.

では, 実際にLoadChainPropertyICのcodeを紹介します.

lv5/breaker/poly_ic.h

    void operator()(LoadPropertyIC* site, Xbyak::CodeGenerator* as, const char* fail) const {
      JSObject* prototype = NULL;
      as->mov(r11, r8);  // r11に対象のobject
      for (Chain::const_iterator it = chain_->begin(),
           last = chain_->end(); it != last; ++it) {
        // mapの数だけtestを出力
        Map* map = *it;
        IC::TestMapConstant(as, map, r11, r10, fail, Xbyak::CodeGenerator::T_NEAR);
        prototype = map->prototype();
        as->mov(r11, core::BitCast<uintptr_t>(prototype));
      }
      // last check
      IC::TestMapConstant(as, map_, r11, r10, fail, Xbyak::CodeGenerator::T_NEAR);
      // load
      LoadPropertyIC::GenerateFastLoad(as, r11, offset_);
    }

objectがlookupされた時, own objectからtarget objectに至るまでのmapをchainとして取得し, それに合わせてtestを出力しています. chainにはmapが詰まっており, このguardのcheckしているのは道中のobjectが全てあるときのmapと同じmapを持っているか?を確認しているのです.

注意して欲しいのは, 一番初めは, 実行時に与えられるobject, r11のmapを検査していますが, その後r11のprototypeを取るのではなく, chainからprototypeを取得しています. つまり, 実はこのguardではprototypeの探索をやっておらず, IC作成時に取得されたchainに属するobjectのmapが変わっていないかを確認しているだけなのです

なぜr11のprototypeを動的にたどる必要がないのでしょうか?

それは, Mapの中にprototypeが含まれているからです. iv / lv5ではobjectのprototypeが変更されるとMap transitionが起こるようになっており, MapのIDの表す同じShapeの中には同じPrototypeであるという保証も含まれているからです. これによってmapが一致することを検査すると, 一つ上のprototype objectも変わっていないことも同時に検査できるのです.

Storing ALL information into Map ID

ICにおいてはMapのtestが重要となります. このため, Mapが何の一意性を表しているのかが非常に重要になります. 例えば, prototypeをMapに持たせてprototypeの変更によってMap transitionを起こすことにより, MapのIDのtestはprototypeが変わっていないことを保証することができるのです.

このため, 一般にECMAScript engineでは, Objectを以下のように設計します.

Mapがhashtableを持っており, hashtableにはkeyに対してattributesとoffsetが格納されています. そしてoffsetがObjectのslotを表しているというふうな実装です. 注目して欲しいのは, hashtableのvalueがoffsetだけではなく, attributesも含んでいるところです. slotの方には, property descriptorでいうところのvalueしか存在しません. なぜslotの方でattributesとvalueを持たないのでしょうか?

それはこのようにすることで, attributesをMapの管理下に置くことができるからです. そしてiv / lv5ではこのattributesが変わるだけでもMap transitionが起きます. writable:trueをwritable:falseにするとMap transitionが起こるのです. その結果, MapのIDはattributesが変わっていないことをも保証することができるのです

例えば, propertyをstoreするとします.

var obj = {};
for (var i = 0; i < 100; ++i) {
  obj.test = i;
}

この時, StorePropertyICを構築するとして, StoreOwnPropertyICが構築された時, ICは何をcheckすれば良いのでしょうか?

答えはなんと, Map checkをするだけで良いのです. もしもMapにattributesの情報が入っていなければ, lv5はstoreするたびにwritableがtrueであるかどうかを検査する必要があります. しかし, attributesの情報がMapに入っており, ICが構築されたとすれば, そのIC構築対象のMapのslotは当然writableであり, このMap checkをするだけで, writableなattributesかどうかのtestをも行なっていることになるのです.

Conclusion

iv / lv5におけるLoadPropertyPICの具体的なcodeを用いて, Map transitionの設計, PICの設計について説明しました.

ホワイトクリスマスイブになるそうですが, あずにゃんと一緒に楽しく過ごす予定です. iv / lv5はまだまだ高速化を予定しております, Context Threading JITが終了すると, 自作GC, SSA based optimizing JIT compilerへと進もうと考えております. また, ES6本格対応も検討しており, Meta Object Protocol(MOP, ECMAScripterにとって今熱い言葉の一つ)によるrewrite, cleanupも考えております. 来年度もiv / lv5にご期待ください＞＜

Introducing ibrik - code coverage tool for CoffeeScript by using istanbul

Image: © lorises 2010

Istanbul made by Krishnan Anantheswaran from the Yahoo! Cocktail team is great code coverage tool for JavaScript. (see usage by Ariya Hidayat)

Internally it uses Esprima to parse JavaScript code and Escodegen to generate instrumented JavaScript code.

These modules use Mozilla JavaScript AST as Internal Representation. Therefore, if we prepare Mozilla JavaScript AST, istanbul can generate instrumented code and coverage result.

I've created ibrik, the code coverage tool for CoffeeScript by using istanbul and CoffeeScriptRedux compiler.

We can install it by

npm install -g ibrik

write test.coffee

call = ->
  console.log 'this is function'

a = 200

if no
  call()

if yes
  do -> console.log('hello')
  if no
    console.log 'out'

and use it by

ibrik cover test.coffee

We gets summary.

Statements   : 72.73% ( 8/11 )
Branches     : 50% ( 3/6 )
Functions    : 50% ( 1/2 )
Lines        : 66.67% ( 6/9 )

And by using istanbul, we can see coverage result on browser.

istanbul report html && open coverage/index.html

Internal

CoffeeScriptRedux made by Michael Ficarra generates Mozilla JS AST and generate JavaScript code by using Escodegen as its backend.

So ibrik generates Mozilla JS AST by using CoffeeScriptRedux compiler and passes it to istanbul instrumenter.

istanbul instrumenter refers line & column information attached to AST, so by attaching line & column information to original (CoffeeScript) code, we can get instrumented JavaScript code and trace CoffeeScript execution. This is the same logic to how CoffeeScriptRedux compiler generates SourceMap.

Future

ibrik implementation is still at very experimental stage. Check the ibrik project on GitHub.

Contributions are welcome.

JSC Array optimization for adding new property

This is a blog post for 12/6 VM advent calendar.

See http://qiita.com/advent-calendar/2012/vm for more nice blog posts :)

Introduction

ECMA262にとってArrayは最も重要なObjectの1つであり, loop内で高い頻度でアクセスされる性質上, Arrayの最適化はengineの実行速度に多大な影響を及ぼします.

ここではJavaScriptCoreの行なっているArrayに対して新しいpropertyを追加する処理の最適化を紹介します.

Background

ECMA262において, Arrayはliteral形式ならばown propertyを最初から定義できますが,

var array = [0, 1, 2, 3, 4];
console.log(array.hasOwnProperty('0'));  // true

それ以外の場合, lengthをconstructorに与えようと, lengthを増やそうと, 最初はemptyな状態で定義されます.

var array = Array(10);
console.log(array.length);  // 10
console.log(array.hasOwnProperty('0'));  // false

var array = [];
array.length = 10;
console.log(array.length);  // 10
console.log(array.hasOwnProperty('0'));  // false

また, ECMA262において, 代入は, [[Put]] internal method callとして表現されます. その[[Put]] step 1では [[CanPut]]によって, 実行可能かどうかを判断する項目があります.

1. If the result of calling the [[CanPut]] internal method of O with argument P is false, then

[[CanPut]] は何のためにあるのか? これは, writableがfalseな書き込みのreject, getterだけ定義されていてsetterの無いpropertyへの代入の阻止, unextensibleなobjectのpropertyを増やす行為の阻止, といった判断をするためのpredicateです.

var obj = {};
Object.defineProperty(obj, 'a', { value: 1, writable: false });
obj.a = 2;
console.log(obj.a);  // 1

var obj = {};
Object.defineProperty(obj, 'a', { get: function() { } });
obj.a = 2;
console.log(obj.a);  // undefined

Problem

[[CanPut]] is very very slow

しかし, [[CanPut]], own propertyが見つからないときは, [[Prototype]]をたどる必要があります. というのも, setterやwritableをhandleしなければいけないからです. 簡単に説明すると以下のような形になります.

1. If own propertyがある
   1. If data propertyならwritableをreturn
   2. Else accessorなのでsetterがあるかどうかをreturn
2. Else If own propertyが無いなら, [[Prototype]]をたどって見つけてくる
   1. If data propertyなら, own propertyを新たに増やすので, own extensible && writableをreturn
   2. Else accessorならsetterがあるかどうかをreturn
3. Else 見つからないのであれば, own propertyを新たに増やすので, own extensibleをreturn

これは, 以下のようなcaseに対応する必要があるからです.

writable: false

Object.defineProperty(Array.prototype, '0', { value: 100, writable: false });
var array = [];
array[0] = 200;
console.log(array[0]);  // 100

setter

Object.defineProperty(Array.prototype, '0', { get: function() { return 42; }, set: function() { } });
var array = [];
array[0] = 200;  // setter called
console.log(array[0]);  // 42

このため[[CanPut]]はもしも対象のpropertyがemptyであると[[Prototype]]ひとつひとつさかのぼって見ていかないといけません. もちろん一度対象indexにown propertyが作成されれば次回からはown propertyを見るだけで良いです.

しかしこれはつまり, 新しいpropertyを追加する際にはprototype chainを登って検証する必要があるということです. 新たなpropertyの追加はprogramにとって非常に多く実行される処理の1つであり, ここでchainをいちいち登るようなことがあってはperformance上大きな問題を抱えてしまいます またこのような複雑な行動ではICを構築することが難しくなります.

Adding new indexed property is executed frequently

一般にECMA262 engineではobjectのindexed propertyとnamed propertyを別々に管理します. これはindexed propertyとnamed propertyではその扱われ方の特徴が異なるからです. named propertyがmemberとして扱われその形状が暗黙的classを表す一方, indexed propertyは配列などのデータのindexとして扱われる傾向があります.

さて, propertyの代入が非常に多く行われるのはindexed propertyです. というのもindexed propertyではloop内で挿入/削除されることが考えられるからです. このようなArray的扱われ方をするobjectにおいて, new propertyを追加するたびに[[Prototype]]のchainを通るのは非常に高いコストとなります.

このため, indexed propertyを新たに追加する際に[[Prototype]]探索を省くことが出来れば, 大幅な高速化が見込まれます. これが今回の主題です.

JSC Array optimization

これを実現するためJSCはindexed property全般に対して前提条件を定め, これを満たすobjectについて最適化を行なっています. この前提は,

[[Prototype]]に設定されるobjectのindexed propertyには, writable:falseやaccessorは存在しない

です. これが成立すると, 新たなindexed propertyを追加するときに, [[Prototype]]をたどる必要がなくなり, 全てobject単体で判断できます.

[[Prototype]]たどってないけどindexed propertyにaccessorがないなら問題ないよねっ

この最適化は, JSCのruntime/JSObject.cpp, JSObject::putByIndex, JSObject::putByIndexBeyondVectorLength の処理にあらわれます.

NonArrayWithSlowPutArrayStorage, ArrayWithSlowPutArrayStorage 以外の場合は, [[Prototype]]を見ずに処理しています.

JSObject::putByIndex より抜粋

     // JSObject::putByIndexより抜粋. 殆どの場合, このpathに入る
     case NonArrayWithArrayStorage:
     case ArrayWithArrayStorage: {
         ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();

         // 超えていたら, breakしてputByIndexBeyondVectorLengthへ
         if (propertyName >= storage->vectorLength())
             break;

         WriteBarrier<Unknown>& valueSlot = storage->m_vector[propertyName];
         unsigned length = storage->length();

         // Update length & m_numValuesInVector as necessary.
         if (propertyName >= length) {
             length = propertyName + 1;
             storage->setLength(length);
             ++storage->m_numValuesInVector;
         } else if (!valueSlot)
             ++storage->m_numValuesInVector;

         // それ以外の場合は単純にsetするだけ
         valueSlot.set(exec->globalData(), thisObject, value);
         return;
     }

これと同じようなことをJIT codeでも行なっています. さあめくるめくMacroAssemblerによる機械語生成codeへ!

jit/JITPropertyAccess.cpp, JIT::emitArrayStoragePutByVal

JIT::JumpList JIT::emitArrayStoragePutByVal(Instruction* currentInstruction, PatchableJump& badType)
{
    unsigned value = currentInstruction[3].u.operand;
    ArrayProfile* profile = currentInstruction[4].u.arrayProfile;

    JumpList slowCases;

    // ArrayStorageShapeかどうかのguard
    // ここで上記前提が成り立っているかどうかがcheckされる
    badType = patchableBranch32(NotEqual, regT2, TrustedImm32(ArrayStorageShape));
    loadPtr(Address(regT0, JSObject::butterflyOffset()), regT2);

    // storageの長さ以内に収まっているかguard
    // 収まっていなかったら, allocateしないといけない
    slowCases.append(branch32(AboveOrEqual, regT1, Address(regT2, ArrayStorage::vectorLengthOffset())));

    // indexでvalueを直接引っ張って, その値がemptyかどうかを検査
    // emptyならば, array hole
    Jump empty = branchTest64(Zero, BaseIndex(regT2, regT1, TimesEight, OBJECT_OFFSETOF(ArrayStorage, m_vector[0])));

    // valueをstore
    Label storeResult(this);
    // 値を持ってきて,
    emitGetVirtualRegister(value, regT3);
    // indexの場所にstore
    store64(regT3, BaseIndex(regT2, regT1, TimesEight, OBJECT_OFFSETOF(ArrayStorage, m_vector[0])));
    // endまでjump
    Jump end = jump();

    // emptyの時は
    empty.link(this);
    // array holeがあるよとarrayに記録しつつ (for further optimization)
    emitArrayProfileStoreToHoleSpecialCase(profile);
    // valueの数を更新して (+1)
    add32(TrustedImm32(1), Address(regT2, ArrayStorage::numValuesInVectorOffset()));
    // もしもlength以下だったら, lengthを増やす必要はないので, 上のstoreResultの位置にjump
    branch32(Below, regT1, Address(regT2, ArrayStorage::lengthOffset())).linkTo(storeResult, this);

    // lengthをindex + 1の値に変更して...
    add32(TrustedImm32(1), regT1);
    store32(regT1, Address(regT2, ArrayStorage::lengthOffset()));
    sub32(TrustedImm32(1), regT1);
    // storeResultの位置にjump
    jump().linkTo(storeResult, this);

    // end
    end.link(this);

    return slowCases;
}

このように非常に高速な機械語に展開されます.

見事, [[Prototype]]を一切たどらずに, 高速なnew property creationを達成しました.

End of Eden

上の最適化は, 当然前提が成り立っていることを前提としているわけで, 崩れてしまえば全く成り立たなくなります. JSCは, この前提が成り立っているobjectを注意深くmarkingして, 前提が成立しているobjectに対して最適化を行なっています.

では, この前提が守られているobjectかどうか, 以下にして追跡するのでしょうか?

[[Prototype]] and array storage state

[[Prototype]]にsetされるobjectというのは非常に限られています. 入り口としては, __proto__と, cunstroctor.prototype, またObject.createの引数といったものがあります.

ここで条件を注意深く絞ります. 例えば以下のようにされた場合,

var array = [];
var proto = {};
Object.defineProperty(proto, '0', { value: 0, writable: false });
var obj = Object.create(proto);

arrayには影響がありません. この場合前提が崩れるのはobjだけです. objは前提の崩れたobjectとして最初から作成されます.

このようにobject作成後に前提が変更されなければ良いのですが, 残念ながら作成後のobjectの前提を崩すことができます. [[Prototype]]に設定されているobjectが変更された時です. 例えば以下のような場合です.

var array = [];
var obj = Object.create({});
var proto = Object.getPrototypeOf(obj);
Object.defineProperty(proto, '0', { value: 0, writable: false });

var array = [];
Object.defineProperty(Array.prototype, '0', { value: 0, writable: false });

これはheap中にある全てのobject(array含む)に影響があります. なぜなら, protoやArray.prototypeは[[Prototype]]に設定されたことのあるobjectという情報はあっても, どのobjectの[[Prototype]]なのかという情報は持っていないからです(それを持っていては, 巨大な辞書が必要になります). そのため, 現在heapにある全てのobjectの前提が崩れたとみなさざるを得なくなります.

とはいってもarrayはもう作成してしまいました. これをたどる術がないのにどうやってarrayに「前提が崩れたobjectである」とmarkingするのでしょう?

実はたどる術はあります, だってGCはたどってますよね?

Switch heap objects storage to slow kind

runtime/JSObject.cpp, JSObject::notifyPresenceOfIndexedAccessorsはその名の通り, indexed propertyにreadonly OR accessorが定義された時に呼ばれます.

void JSObject::notifyPresenceOfIndexedAccessors(JSGlobalData& globalData)
{
    // もうこのobjectの[[Prototype]]より上でindexed propertyにaccessorがあるから,
    // もうすでに前提が崩れたことはheapに反映されていますよというcheck
    if (mayInterceptIndexedAccesses())
        return;

    // structure (HiddenClass / Map / Shapeお好きなように) をtransitさせる
    setStructure(globalData, Structure::nonPropertyTransition(globalData, structure(), AddIndexedAccessors));

    // [[Prototype]]に設定されたことがなければ無害
    if (!mayBeUsedAsPrototype(globalData))
        return;

    // 残念...
    globalObject()->haveABadTime(globalData);
}

そして, runtime/JSGlobalObject.cpp, JSGlobalObject::haveABadTimeが呼ばれます. 前提が崩れたことが反映されます. 大技.

void JSGlobalObject::haveABadTime(JSGlobalData& globalData)
{
    ASSERT(&globalData == &this->globalData());

    if (isHavingABadTime())
        return;

    // Make sure that all allocations or indexed storage transitions that are inlining
    // the assumption that it's safe to transition to a non-SlowPut array storage don't
    // do so anymore.
    m_havingABadTimeWatchpoint->notifyWrite();
    ASSERT(isHavingABadTime()); // The watchpoint is what tells us that we're having a bad time.

    // Make sure that all JSArray allocations that load the appropriate structure from
    // this object now load a structure that uses SlowPut.
    for (unsigned i = 0; i < NumberOfIndexingShapes; ++i)
        m_arrayStructureForIndexingShapeDuringAllocation[i].set(globalData, this, originalArrayStructureForIndexin    gType(ArrayWithSlowPutArrayStorage));

    // Heapにあるobjectを全部探してきて, 片っ端から最適化flagをoffにして回る!!
    //
    // Make sure that all objects that have indexed storage switch to the slow kind of
    // indexed storage.
    MarkedArgumentBuffer foundObjects; // Use MarkedArgumentBuffer because switchToSlowPutArrayStorage() may GC.
    ObjectsWithBrokenIndexingFinder finder(foundObjects, this);
    globalData.heap.objectSpace().forEachLiveCell(finder);
    while (!foundObjects.isEmpty()) {
        JSObject* object = asObject(foundObjects.last());
        foundObjects.removeLast();
        ASSERT(hasBrokenIndexing(object));
        object->switchToSlowPutArrayStorage(globalData);
    }
}

GCと同じくheap上のobjectをすべて探してきて, 片っ端から前提が崩れたことを反映させます. これによりすでに作られてしまったJIT codeもすべてArrayShape guardの時点でfailさせることによってinvalidateし, putByIndexなどもslow patternに変わり, で一件落着ですね.

Conclusion

というわけで, JSCは前提を定めてそれに対する最適化を行い, この前提が崩れた際にはHeapを無理やり修正するという手段でもって最適化を行なっているのでした.

くれぐれも, indexed propertyにaccessorを指定しないようにしましょう.

LL Decadeに参加してきました

LL Decadeに参加してきましたー!
プログラミング言語処理系を自作してわかったこと | LL Decade

このメンツ, サンドバックになる気配を敏感に感じ取り, 「やばいっ!」と思っていたのですが, 皆さん優しい方ばかりで, 意外にサンドバックになりませんでした. よかったですです...

資料は以下のものになります.

x86 / x64最適化勉強会の際よりも, engine全体を俯瞰する形で, また, ES.next方面の話を入れる等の構成にしました.

shibuya: the ES.next engineの話

shibuya

概要としては, esprima harmony branchを用いてES.next engineを作り, 最適化可能ポイントを探りlv5での実装のための知識の蓄積を行い, 同時にES.nextの仕様のbugを発見, また非効率的, パフォーマンス上問題になり得る場所を特定し, 仕様へ貢献していこうという趣旨のprojectです.
yieldなどどうしても無理なところ以外は, 完全に仕様のAbstract Operationと実装が一致することを目指しており, この点lv5とまた少し毛色の違う, より原理主義的な仕様準拠を掲げています.

まだ, あまり実装が出来上がっていませんが, どんどん実装していこうと思います.

また, もちろん, 主に自分が楽しいというのが入っているのも当然あります...

感想

mruby が非常に気になっていて, 是非お聞きしてみたいと思っていたことを聞くことができ, とてもためになりました. ありがとうございます. IC (いもうとコンプレックス, a.k.a. Inline Caching), かわいいですね... LowLevelに落としてすみません...

うさみみがインパクトすごかったです, Functional City Nagoya怖い...
LLの文化を感じ取ることのできる, 非常に刺激的なイベントでした. 参加者, 運営の皆様, 本当にありがとうございました. とても楽しかったです!

補足

鈍器購入しました.

サイボウズ・ラボユースの最終成果報告会にて発表しました

3/26に発表してきました. 資料は以下にあります.

iv / lv5, ECMA262 Engine

内容は主に, ECMA262 5.1th Engine, lv5の独自性である仕様準拠性, Register VM概説, またrailgun::Compilerの独自のRegisterの割り当て方による効率的なRegister Allocation(個人的には, ゆるゆりメソッドと呼んでいます), Stack VM / Register VMの論争点の一つであるcode sizeについての考察などです.

時間があれば, JavaScriptの変数の解析, 及び参照の解析などについても話したかったのですが, それをやるとスライド数が爆発するのでやめています...(direct call to eval, with, argumentsがあるとどうなるかとか, immutable bindingとの兼ね合いだとか, strict mode下でできる最適化だとか, argumentsという変数が隠された場合にはargumentsを作る必要がなくなることが静的解析可能な場合があるとか...)

参加して

サイボウズ・ラボユースに1年間参加させていただきました.

書籍, LuaやPython, JSCやRubyなど様々なsource codeを読んでVMの仕組みなどを勉強したり, 論文を読んだり, 非常に有意義な時間を過ごすことが出来ました.

それにより, Engineも当初のECMA262のInterpretation Algorithmを実行するAST Interpreterから, Stack VM, そしてRegister VMを構築するなど, VMの基礎的なことや, VM levelでの最適化のやり方, Bytecode Compilerについての知識など, 非常に勉強になりました.
また, JavaScript Engineには必ず必要になってきつつある, Polymorphic Inline Cacheの実装などの知識を得ることが出来ました.

また, 新屋さん, 林さんら, 同期の方々のすごさに圧倒され, 非常に刺激的でした!

サイボウズ・ラボのみなさまには, 非常に多くのアドバイスを頂き, とても感謝しております.
asmなどについて非常に基礎的な知識も持っていなかったのですが, x86/x64についてや, Xbyakについてメモリ自動伸長optionをつけていただくなど, 様々な点でアドバイスを頂き, とてもためになりました.
また, ECMA262についても, 様々なことを教えていただきました.

謝辞

この1年間, 参加して非常に有意義な時間を過ごすことが出来ました. 本当にありがとうございました!

サイボウズ・ラボユース 最終成果報告会

が, 3/26にあります.
サイボウズ・ラボユース学生支援制度: 3/26(月)第1期サイボウズ・ラボユース最終成果報告会＆第2期募集説明会を開催します

自分は主にRegisterVMの話をしていると思います.
特に, 副作用を含んだexpressionにおける適切なRegisterの割り当て方について話しているかと...
ので, ご興味ある方は是非お越しくださいー.

■ 第1期サイボウズ・ラボユース 最終成果報告会

　開催日時：2012年 3/26(月) 13:00〜17:00
　開催場所：秋葉原ダイビル5階（カンファレンスフロア）
　参加人数：70名
　事前申込：必要（無料）申し込みフォーム→ http://bit.ly/ArZrGm

【タイムテーブル】

　13:00　開場（受付）
　13:15　サイボウズ・ラボユース第1期生5名による成果発表
　 (1) 桐井祐樹「Ruby・Raccを使用した言語処理系の日本語プログラミング化」
　 (2) 新屋良磨「世界最速の正規表現JITエンジンの実装」@sinya8282
　 (3) 林　拓人「型システムの拡張と型推論」
　 (4) 鈴木勇介「世界で一番仕様に忠実なJavaScript処理系の作成」
　 (5) 粟本真一「現役高校生の考えるクラウドOSの設計と実装」
　15:30　ライトニングトーク大会
　16:00　サイボウズ・ラボユース第2期生の募集について
　16:30　卒業式
　16:50　自由解散
　17:00　懇親会（希望者のみ別の会場に移動して開催予定）
　19:30　解散