V8 の For In の話

V8 blogに話が出ていたが、V8のfor in構文が高速化したらしいので、
コードと共におっていこうと思う。

For In とは

for (const key in object) {

}

このような構文でObjectのキーをイテレーションする機能。
この構文を何故高速化したかというと、Facebookのコード実行の7% Wikipediaのコード実行の8%をForIn構文が占めていたらしく、
実行に負荷のかかる部分だったらしい。

一見この構文は単純に見えるが、処理系が行わなければならない仕事は以外に多く複雑だ。

まずはForIn構文の定義を見てみよう。上記のBlogにかかれているSpecを抜粋する。

EnumerateObjectProperties ( O ) 抽象命令であるEnumerateObjectPropertiesが引数Oを伴って呼び出される時、以下のステップをとる。
1. Type(O)がObjectか確認する。
2. Iteratorを返却する。IteratorのnextメソッドはOのenumerableな文字列のプロパティを全て列挙する。
IteratorオブジェクトはECMAScriptのコード中からアクセス不能である。プロパティの列挙順及びその方法は特に規定しないが、以下の規定に沿わなければならない。
A. Iteratorのthrowとreturnメソッドはnullであり、決して呼び出されない。
B. Iteratorのnextメソッドはオブジェクトのプロパティを処理して、次にiteratorの値として返すプロパティのキーを決める。
C. 戻り値のプロパティキーはSymbolを含まない
D. ターゲットのオブジェクトのプロパティは列挙中に削除されるかもしれない。
E. Iteratorのnextメソッドに処理される前に削除されたプロパティは無視される。もし、列挙中に新たなプロパティが追加された場合、新たに追加されたプロパティは現在の列挙中に処理される保証はない。
F. プロパティ名は列挙中に一度しかIteratorのnextメソッドによって返却されない。
G. 列挙するターゲットのオブジェクトのプロパティは、ターゲットのprototype、そのprototypeのprototypeも含むが、一度でも列挙されたプロパティのキーと同じキーを含んだprototypeのキーは列挙されない。（シャドウイングされたprototypeは列挙されない）
H. ptototypeのプロパティが既に処理されていた場合、[[Enumerable]]属性は考慮しない。
I. prototypeの列挙可能プロパティ名を取得する場合は、必ず、EnumerateObjectPropertiesをprototypeを引数に呼び出して取得しなければならない。
J. EnumerateObjectPropertiesはターゲットオブジェクトのプロパティを[[OwnPropertyKeys]]内部メソッドを呼び出して取得しなければならない。

かなり要件が複雑なのがわかる。

概要

Blogから抜粋

Map                               Descriptors              Enum Cache
--------------------------   ->   -------------------   -> -----------------  -> -------
|enumLength        |  3  |   |    | length    |   3 |   |  | Keys    | ptr | -|  | 'a' |
--------------------------   |    -------------------   |  -----------------     -------
|nofOwnDescriptors |  3  |   |    | EnumCache | ptr | --|  | indices | ptr |     | 'b' |
--------------------------   |    -------------------      -----------------     -------
|DescriptorArray   | ptr |---     | ...       | ... |                            | 'c' |
--------------------------        -------------------                            -------

MapのDescriptorが持っているEnumCacheからプロパティのキーリストを取得するようにしたので、高速になったらしい。

実装

さて実装はどうなっているか。

V8のForInはRuntime呼び出しで実装されている。
試しにd8で確認すると…

./d8 --print_code -e "for (const i in {__proto__: {a:1}}){}"

この行でForInEnumerateをRuntimeから呼び出しているのが確認できる。

0x1cb5dca0476e   398  b801000000     movl rax,0x1
0x1cb5dca04773   403  48bbc0ddc70001000000 REX.W movq rbx,0x100c7ddc0    ;; external reference (Runtime::ForInEnumerate)
0x1cb5dca0477d   413  e81efadfff     call 0x1cb5dc8041a0     ;; code: STUB, CEntryStub, minor: 8

ではRuntime::ForInEnumerateを確認しよう。

ちなみにMapとかV8の基礎情報は V8祭りを参照してほしい。

では確認ー

ForInEnumerateはsrc/runtime/runtime-forin.ccにある。

Runtime::ForInEnumerateを確認する前にこのファイルにある他のRuntimeも確認しておく。

このRuntimeに用意されているのは、

Runtime_ForInEnumerate
Runtime_ForInPrepare
Runtime_ForInHasProperty
Runtime_ForInFilter

の4つ。
ForInEnumerate以外はIgnitionインタープリタから呼び出されているようだが、今回はFullCodegenから呼び出されるコードをメインに見ていく。

RUNTIME_FUNCTION(Runtime_ForInEnumerate) {
  HandleScope scope(isolate);
  DCHECK_EQ(1, args.length());
  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, receiver, 0);
  RETURN_RESULT_OR_FAILURE(isolate, Enumerate(receiver));
}

これがForInEnumerateの本体だ。
中ではさらにEnumerateをreceiverを引数に呼び出している。

次はEnumerate

// Returns either a FixedArray or, if the given {receiver} has an enum cache
// that contains all enumerable properties of the {receiver} and its prototypes
// have none, the map of the {receiver}. This is used to speed up the check for
// deletions during a for-in.
MaybeHandle<HeapObject> Enumerate(Handle<JSReceiver> receiver) {
  Isolate* const isolate = receiver->GetIsolate();
  JSObject::MakePrototypesFast(receiver, kStartAtReceiver, isolate);
  FastKeyAccumulator accumulator(isolate, receiver,
                                 KeyCollectionMode::kIncludePrototypes,
                                 ENUMERABLE_STRINGS);
  accumulator.set_is_for_in(true);
  // Test if we have an enum cache for {receiver}.
  if (!accumulator.is_receiver_simple_enum()) {
    Handle<FixedArray> keys;
    ASSIGN_RETURN_ON_EXCEPTION(
        isolate, keys, accumulator.GetKeys(GetKeysConversion::kKeepNumbers),
        HeapObject);
    // Test again, since cache may have been built by GetKeys() calls above.
    if (!accumulator.is_receiver_simple_enum()) return keys;
  }
  return handle(receiver->map(), isolate);
}

さて、このEnumerateで注目したいのは、FastKeyAccumulatorである。このFastKeyAccumulatorがオブジェクトのprototypeの情報、プロパティの情報を取得し、
最適な処理に振り分けている。

void FastKeyAccumulator::Prepare() {
  DisallowHeapAllocation no_gc;
  // Directly go for the fast path for OWN_ONLY keys.
  if (mode_ == KeyCollectionMode::kOwnOnly) return;
  // Fully walk the prototype chain and find the last prototype with keys.
  is_receiver_simple_enum_ = false;
  has_empty_prototype_ = true;
  JSReceiver* last_prototype = nullptr;
  for (PrototypeIterator iter(isolate_, *receiver_); !iter.IsAtEnd();
       iter.Advance()) {
    JSReceiver* current = iter.GetCurrent<JSReceiver>();
    bool has_no_properties = CheckAndInitalizeEmptyEnumCache(current);
    if (has_no_properties) continue;
    last_prototype = current;
    has_empty_prototype_ = false;
  }
  if (has_empty_prototype_) {
    is_receiver_simple_enum_ =
        receiver_->map()->EnumLength() != kInvalidEnumCacheSentinel &&
        !JSObject::cast(*receiver_)->HasEnumerableElements();
  } else if (last_prototype != nullptr) {
    last_non_empty_prototype_ = handle(last_prototype, isolate_);
  }
}

これがFastKeyAccumulatorの初期化処理。やっていることは

Receiverオブジェクトのprototypeを辿る
prototypeにプロパティがあれば、has_empty_prototype_をfalseにする。
そして、全てのprototypeを辿り終わったら、has_empty_prototype_ == trueの場合は、receiverのMapオブジェクトがEnumを持っていて、Enumerableなプロパティを持っていないければ、is_receiver_simple_enum_ = trueになる。
それ以外の場合はlast_non_empty_prototype_に最後のprototypeを渡す。

さて、runtime-forinのEnumerate関数に戻ると、

if (!accumulator.is_receiver_simple_enum()) {

FastKeyAccumulator::is_receiver_simple_enum()で処理を分けている。
つまり、自身にEnumerableなプロパティを持たず、prototypeにも持たず、MapにEnumを持っているオブジェクトはこのファストパスに入る。
このパスではFastKeyAccumulator::GetKeys()でObjectのプロパティキーを取得する。

MaybeHandle<FixedArray> FastKeyAccumulator::GetKeys(
    GetKeysConversion keys_conversion) {
  if (filter_ == ENUMERABLE_STRINGS) {
    Handle<FixedArray> keys;
    if (GetKeysFast(keys_conversion).ToHandle(&keys)) {
      return keys;
    }
    if (isolate_->has_pending_exception()) return MaybeHandle<FixedArray>();
  }

  return GetKeysSlow(keys_conversion);
}

GetKeysの定義は結構簡単で、filter_プロパティは今回はENUMERABLE_STRINGSなのでifに入る。
そしたらFastKeyAccumulator::GetKeysFastを呼び出してHandle<FixedArray>に変換する。

MaybeHandle<FixedArray> FastKeyAccumulator::GetKeysFast(
    GetKeysConversion keys_conversion) {
  bool own_only = has_empty_prototype_ || mode_ == KeyCollectionMode::kOwnOnly;
  Map* map = receiver_->map();
  if (!own_only || !OnlyHasSimpleProperties(map)) {
    return MaybeHandle<FixedArray>();
  }

  // From this point on we are certiain to only collect own keys.
  DCHECK(receiver_->IsJSObject());
  Handle<JSObject> object = Handle<JSObject>::cast(receiver_);

  // Do not try to use the enum-cache for dict-mode objects.
  if (map->is_dictionary_map()) {
    return GetOwnKeysWithElements<false>(isolate_, object, keys_conversion);
  }
  int enum_length = receiver_->map()->EnumLength();
  if (enum_length == kInvalidEnumCacheSentinel) {
    Handle<FixedArray> keys;
    // Try initializing the enum cache and return own properties.
    if (GetOwnKeysWithUninitializedEnumCache().ToHandle(&keys)) {
      if (FLAG_trace_for_in_enumerate) {
        PrintF("| strings=%d symbols=0 elements=0 || prototypes>=1 ||\n",
               keys->length());
      }
      is_receiver_simple_enum_ =
          object->map()->EnumLength() != kInvalidEnumCacheSentinel;
      return keys;
    }
  }
  // The properties-only case failed because there were probably elements on the
  // receiver.
  return GetOwnKeysWithElements<true>(isolate_, object, keys_conversion);
}

FastKeyAccumulator::GetKeysFastの定義がこちら。
いろいろコードがあるのだが、重要なのは、is_dictionary_mapのチェックである。
is_dictionary_mapは拡張されるObjectの場合trueになっている。

現在の所、

グローバルオブジェクトのMap、
Object.create(null)の戻り値のMap

がdictionary_mapという扱いになっている。

このオブジェクトの場合はそもそもTransitionするMapを持っていない、EnumCacheも持っていないので、
GetOwnKeysWithElementsのtemplate引数をfalseで呼び出す。
それ以外のオブジェクトの場合は、enum_cacheの有無をチェックし、
存在しなければGetOwnKeysWithUninitializedEnumCacheを呼び出し、その場で作成する。 GetOwnKeysWithUninitializedEnumCacheは省略するが、enum_cacheをdescriptorから作成し、プロパティ一覧を返す。 enum_cacheを既に持っているオブジェクトの場合、GetOwnKeysWithElementsがtemplate引数にtrueを渡して呼び出される。

template <bool fast_properties>
MaybeHandle<FixedArray> GetOwnKeysWithElements(Isolate* isolate,
                                               Handle<JSObject> object,
                                               GetKeysConversion convert) {
  Handle<FixedArray> keys;
  ElementsAccessor* accessor = object->GetElementsAccessor();
  if (fast_properties) {
    keys = GetFastEnumPropertyKeys(isolate, object);
  } else {
    // TODO(cbruni): preallocate big enough array to also hold elements.
    keys = KeyAccumulator::GetOwnEnumPropertyKeys(isolate, object);
  }
  MaybeHandle<FixedArray> result =
      accessor->PrependElementIndices(object, keys, convert, ONLY_ENUMERABLE);

  if (FLAG_trace_for_in_enumerate) {
    PrintF("| strings=%d symbols=0 elements=%u || prototypes>=1 ||\n",
           keys->length(), result.ToHandleChecked()->length() - keys->length());
  }
  return result;
}

これがGetOwnKeysWithElementsの実装。
template引数がtrueの場合はGetFastEnumPropertyKeysを呼び出す。

// Initializes and directly returns the enume cache. Users of this function
// have to make sure to never directly leak the enum cache.
Handle<FixedArray> GetFastEnumPropertyKeys(Isolate* isolate,
                                           Handle<JSObject> object) {
  Handle<Map> map(object->map());
  bool cache_enum_length = map->OnlyHasSimpleProperties();

  Handle<DescriptorArray> descs =
      Handle<DescriptorArray>(map->instance_descriptors(), isolate);
  int own_property_count = map->EnumLength();
  // If the enum length of the given map is set to kInvalidEnumCache, this
  // means that the map itself has never used the present enum cache. The
  // first step to using the cache is to set the enum length of the map by
  // counting the number of own descriptors that are ENUMERABLE_STRINGS.
  if (own_property_count == kInvalidEnumCacheSentinel) {
    own_property_count =
        map->NumberOfDescribedProperties(OWN_DESCRIPTORS, ENUMERABLE_STRINGS);
  } else {
    DCHECK(
        own_property_count ==
        map->NumberOfDescribedProperties(OWN_DESCRIPTORS, ENUMERABLE_STRINGS));
  }

  if (descs->HasEnumCache()) {
    Handle<FixedArray> keys(descs->GetEnumCache(), isolate);
    // In case the number of properties required in the enum are actually
    // present, we can reuse the enum cache. Otherwise, this means that the
    // enum cache was generated for a previous (smaller) version of the
    // Descriptor Array. In that case we regenerate the enum cache.
    if (own_property_count <= keys->length()) {
      isolate->counters()->enum_cache_hits()->Increment();
      if (cache_enum_length) map->SetEnumLength(own_property_count);
      return ReduceFixedArrayTo(isolate, keys, own_property_count);
    }
  }

  if (descs->IsEmpty()) {
    isolate->counters()->enum_cache_hits()->Increment();
    if (cache_enum_length) map->SetEnumLength(0);
    return isolate->factory()->empty_fixed_array();
  }

  isolate->counters()->enum_cache_misses()->Increment();

  Handle<FixedArray> storage =
      isolate->factory()->NewFixedArray(own_property_count);
  Handle<FixedArray> indices =
      isolate->factory()->NewFixedArray(own_property_count);

  int size = map->NumberOfOwnDescriptors();
  int index = 0;

  for (int i = 0; i < size; i++) {
    PropertyDetails details = descs->GetDetails(i);
    if (details.IsDontEnum()) continue;
    Object* key = descs->GetKey(i);
    if (key->IsSymbol()) continue;
    storage->set(index, key);
    if (!indices.is_null()) {
      if (details.location() == kField) {
        DCHECK_EQ(kData, details.kind());
        FieldIndex field_index = FieldIndex::ForDescriptor(*map, i);
        int load_by_field_index = field_index.GetLoadByFieldIndex();
        indices->set(index, Smi::FromInt(load_by_field_index));
      } else {
        indices = Handle<FixedArray>();
      }
    }
    index++;
  }
  DCHECK(index == storage->length());

  DescriptorArray::SetEnumCache(descs, isolate, storage, indices);
  if (cache_enum_length) {
    map->SetEnumLength(own_property_count);
  }
  return storage;
}

でGetFastEnumPropertyKeysがこれ。
実はGetFastEnumPropertyKeysは先程省略した、GetOwnKeysWithUninitializedEnumCacheからも呼び出される。
とても長いコードだが、やっていることはdescriptorがenum_cacheを持っていれば、それを返すし、なければ作成して返す。
これだけ。

さて、これがForInでキーを列挙する最速のパスなのだが、遅いパターンはどうだろうか。 GetOwnKeysWithElementsのに戻るが、

keys = KeyAccumulator::GetOwnEnumPropertyKeys(isolate, object);

と、KeyAccumulator::GetOwnEnumPropertyKeysを呼び出すらしい。

Handle<FixedArray> KeyAccumulator::GetOwnEnumPropertyKeys(
    Isolate* isolate, Handle<JSObject> object) {
  if (object->HasFastProperties()) {
    return GetFastEnumPropertyKeys(isolate, object);
  } else if (object->IsJSGlobalObject()) {
    return GetOwnEnumPropertyDictionaryKeys(
        isolate, KeyCollectionMode::kOwnOnly, nullptr, object,
        object->global_dictionary());
  } else {
    return GetOwnEnumPropertyDictionaryKeys(
        isolate, KeyCollectionMode::kOwnOnly, nullptr, object,
        object->property_dictionary());
  }
}

これが実装
object->HasFastPropertiesであれば、GetFastEnumPropertyKeysに戻れるらしい。
HasFastPropertiesである条件は、

mapがHashTableでなく、StringTableでも無いこと。

その条件の場合はやはり、enum_cacheから取得される。
それ以外のグローバルオブジェクトの場合、GetOwnEnumPropertyDictionaryKeysのパスに入る。
GetOwnEnumPropertyDictionaryKeysでは
各dictionaryのCopyEnumKeysToが呼び出されプロパティのコピーが行われる。

template <typename Derived, typename Shape, typename Key>
void Dictionary<Derived, Shape, Key>::CopyEnumKeysTo(
    Handle<Dictionary<Derived, Shape, Key>> dictionary,
    Handle<FixedArray> storage, KeyCollectionMode mode,
    KeyAccumulator* accumulator) {
  DCHECK_IMPLIES(mode != KeyCollectionMode::kOwnOnly, accumulator != nullptr);
  Isolate* isolate = dictionary->GetIsolate();
  int length = storage->length();
  int capacity = dictionary->Capacity();
  int properties = 0;
  for (int i = 0; i < capacity; i++) {
    Object* key = dictionary->KeyAt(i);
    bool is_shadowing_key = false;
    if (!dictionary->IsKey(isolate, key)) continue;
    if (key->IsSymbol()) continue;
    PropertyDetails details = dictionary->DetailsAt(i);
    if (details.IsDontEnum()) {
      if (mode == KeyCollectionMode::kIncludePrototypes) {
        is_shadowing_key = true;
      } else {
        continue;
      }
    }
    if (dictionary->IsDeleted(i)) continue;
    if (is_shadowing_key) {
      accumulator->AddShadowingKey(key);
      continue;
    } else {
      storage->set(properties, Smi::FromInt(i));
    }
    properties++;
    if (mode == KeyCollectionMode::kOwnOnly && properties == length) break;
  }

  CHECK_EQ(length, properties);
  DisallowHeapAllocation no_gc;
  Dictionary<Derived, Shape, Key>* raw_dictionary = *dictionary;
  FixedArray* raw_storage = *storage;
  EnumIndexComparator<Derived> cmp(static_cast<Derived*>(*dictionary));
  Smi** start = reinterpret_cast<Smi**>(storage->GetFirstElementAddress());
  std::sort(start, start + length, cmp);
  for (int i = 0; i < length; i++) {
    int index = Smi::cast(raw_storage->get(i))->value();
    raw_storage->set(i, raw_dictionary->KeyAt(index));
  }
}

でこれが、CopyEnumKeysToの実装。
forでループを回してプロパティをコピーしている。
まあこれが早いわけないよねということで、ForInの高速化の実装を確かめた。

まとめ

ForInのRuntime呼び出しでは、レシーバオブジェクトがFastPropertiesさえ持っていれば、
EnumCacheから値を取得するので高速。 IgnitionがForInを処理するパスについてはまたそのうち。

abcdefGets

ゲッツ！

V8 の For In の話

For In とは

概要

実装

まとめ