枕を欹てて聴く

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

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含む)に影響があります. なぜなら, protoArray.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を指定しないようにしましょう.