From 8e0979e2ff424a49b636391923c82edbca9ce8aa Mon Sep 17 00:00:00 2001 From: "ager@chromium.org" Date: Thu, 23 Oct 2008 07:04:56 +0000 Subject: [PATCH] Introduce a lookup cache class in the runtime system and use it for keyed loads that enter the runtime. Review URL: http://codereview.chromium.org/7879 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@561 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/heap-inl.h | 20 ++++++++++ src/heap.cc | 4 ++ src/heap.h | 8 +++- src/objects-inl.h | 6 +++ src/objects.cc | 113 +++++++++++++++++++++++++++++++++++++++++++----------- src/objects.h | 25 ++++++++++++ src/runtime.cc | 60 ++++++++++++++++++++++------- 7 files changed, 199 insertions(+), 37 deletions(-) diff --git a/src/heap-inl.h b/src/heap-inl.h index 16870a7..bfa2b65 100644 --- a/src/heap-inl.h +++ b/src/heap-inl.h @@ -165,6 +165,26 @@ void Heap::CopyBlock(Object** dst, Object** src, int byte_size) { } +Object* Heap::GetKeyedLookupCache() { + if (keyed_lookup_cache()->IsUndefined()) { + Object* obj = LookupCache::Allocate(4); + if (obj->IsFailure()) return obj; + keyed_lookup_cache_ = obj; + } + return keyed_lookup_cache(); +} + + +void Heap::SetKeyedLookupCache(LookupCache* cache) { + keyed_lookup_cache_ = cache; +} + + +void Heap::ClearKeyedLookupCache() { + keyed_lookup_cache_ = undefined_value(); +} + + #define GC_GREEDY_CHECK() \ ASSERT(!FLAG_gc_greedy || v8::internal::Heap::GarbageCollectionGreedyCheck()) diff --git a/src/heap.cc b/src/heap.cc index f389976..bc8dd76 100644 --- a/src/heap.cc +++ b/src/heap.cc @@ -421,6 +421,7 @@ void Heap::MarkCompact(GCTracer* tracer) { void Heap::MarkCompactPrologue() { + ClearKeyedLookupCache(); CompilationCache::MarkCompactPrologue(); RegExpImpl::OldSpaceCollectionPrologue(); Top::MarkCompactPrologue(); @@ -1195,6 +1196,9 @@ bool Heap::CreateInitialObjects() { if (obj->IsFailure()) return false; natives_source_cache_ = FixedArray::cast(obj); + // Initialize keyed lookup cache. + ClearKeyedLookupCache(); + // Initialize compilation cache. CompilationCache::Clear(); diff --git a/src/heap.h b/src/heap.h index 802d9c6..c619e9f 100644 --- a/src/heap.h +++ b/src/heap.h @@ -122,7 +122,8 @@ namespace v8 { namespace internal { V(Code, c_entry_debug_break_code) \ V(FixedArray, number_string_cache) \ V(FixedArray, single_character_string_cache) \ - V(FixedArray, natives_source_cache) + V(FixedArray, natives_source_cache) \ + V(Object, keyed_lookup_cache) #define ROOT_LIST(V) \ @@ -639,6 +640,11 @@ class Heap : public AllStatic { non_monomorphic_cache_ = value; } + // Gets, sets and clears the lookup cache used for keyed access. + static inline Object* GetKeyedLookupCache(); + static inline void SetKeyedLookupCache(LookupCache* cache); + static inline void ClearKeyedLookupCache(); + #ifdef DEBUG static void Print(); static void PrintHandles(); diff --git a/src/objects-inl.h b/src/objects-inl.h index 9efbe8a..152d1c3 100644 --- a/src/objects-inl.h +++ b/src/objects-inl.h @@ -354,6 +354,11 @@ bool Object::IsMapCache() { } +bool Object::IsLookupCache() { + return IsHashTable(); +} + + bool Object::IsPrimitive() { return IsOddball() || IsNumber() || IsString(); } @@ -1186,6 +1191,7 @@ CAST_ACCESSOR(Dictionary) CAST_ACCESSOR(SymbolTable) CAST_ACCESSOR(CompilationCacheTable) CAST_ACCESSOR(MapCache) +CAST_ACCESSOR(LookupCache) CAST_ACCESSOR(String) CAST_ACCESSOR(SeqString) CAST_ACCESSOR(SeqAsciiString) diff --git a/src/objects.cc b/src/objects.cc index 50b89d5..5777367 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -5490,9 +5490,7 @@ int JSObject::GetEnumElementKeys(FixedArray* storage) { // This avoids allocation in HasProperty. class NumberKey : public HashTableKey { public: - explicit NumberKey(uint32_t number) { - number_ = number; - } + explicit NumberKey(uint32_t number) : number_(number) { } private: bool IsMatch(Object* number) { @@ -5538,9 +5536,7 @@ class NumberKey : public HashTableKey { // StringKey simply carries a string object as key. class StringKey : public HashTableKey { public: - explicit StringKey(String* string) { - string_ = string; - } + explicit StringKey(String* string) : string_(string) { } bool IsMatch(Object* string) { return string_->Equals(String::cast(string)); @@ -5830,11 +5826,8 @@ Object* SymbolTable::LookupKey(HashTableKey* key, Object** s) { Object* CompilationCacheTable::Lookup(String* src) { StringKey key(src); int entry = FindEntry(&key); - if (entry != -1) { - return get(EntryToIndex(entry) + 1); - } else { - return Heap::undefined_value(); - } + if (entry == -1) return Heap::undefined_value(); + return get(EntryToIndex(entry) + 1); } @@ -5856,9 +5849,7 @@ Object* CompilationCacheTable::Put(String* src, Object* value) { // SymbolsKey used for HashTable where key is array of symbols. class SymbolsKey : public HashTableKey { public: - explicit SymbolsKey(FixedArray* symbols) { - symbols_ = symbols; - } + explicit SymbolsKey(FixedArray* symbols) : symbols_(symbols) { } bool IsMatch(Object* symbols) { FixedArray* o = FixedArray::cast(symbols); @@ -5877,28 +5868,78 @@ class SymbolsKey : public HashTableKey { Object* GetObject() { return symbols_; } static uint32_t SymbolsHash(Object* obj) { - FixedArray* symbols_ = FixedArray::cast(obj); - int len = symbols_->length(); - uint32_t hash = 0; + FixedArray* symbols = FixedArray::cast(obj); + int len = symbols->length(); + uint32_t hash = 0; for (int i = 0; i < len; i++) { - hash ^= String::cast(symbols_->get(i))->Hash(); + hash ^= String::cast(symbols->get(i))->Hash(); } return hash; } bool IsStringKey() { return false; } + private: FixedArray* symbols_; }; + +// MapNameKeys are used as keys in lookup caches. +class MapNameKey : public HashTableKey { + public: + MapNameKey(Map* map, String* name) + : map_(map), name_(name) { } + + bool IsMatch(Object* other) { + if (!other->IsFixedArray()) return false; + FixedArray* pair = FixedArray::cast(other); + Map* map = Map::cast(pair->get(0)); + if (map != map_) return false; + String* name = String::cast(pair->get(1)); + return name->Equals(name_); + } + + typedef uint32_t (*HashFunction)(Object* obj); + + virtual HashFunction GetHashFunction() { return MapNameHash; } + + static uint32_t MapNameHashHelper(Map* map, String* name) { + return reinterpret_cast(map) ^ name->Hash(); + } + + static uint32_t MapNameHash(Object* obj) { + FixedArray* pair = FixedArray::cast(obj); + Map* map = Map::cast(pair->get(0)); + String* name = String::cast(pair->get(1)); + return MapNameHashHelper(map, name); + } + + virtual uint32_t Hash() { + return MapNameHashHelper(map_, name_); + } + + virtual Object* GetObject() { + Object* obj = Heap::AllocateFixedArray(2); + if (obj->IsFailure()) return obj; + FixedArray* pair = FixedArray::cast(obj); + pair->set(0, map_); + pair->set(1, name_); + return pair; + } + + virtual bool IsStringKey() { return false; } + + private: + Map* map_; + String* name_; +}; + + Object* MapCache::Lookup(FixedArray* array) { SymbolsKey key(array); int entry = FindEntry(&key); - if (entry != -1) { - return get(EntryToIndex(entry) + 1); - } else { - return Heap::undefined_value(); - } + if (entry == -1) return Heap::undefined_value(); + return get(EntryToIndex(entry) + 1); } @@ -5916,6 +5957,31 @@ Object* MapCache::Put(FixedArray* array, Map* value) { } +int LookupCache::Lookup(Map* map, String* name) { + MapNameKey key(map, name); + int entry = FindEntry(&key); + if (entry == -1) return kNotFound; + return Smi::cast(get(EntryToIndex(entry) + 1))->value(); +} + + +Object* LookupCache::Put(Map* map, String* name, int value) { + MapNameKey key(map, name); + Object* obj = EnsureCapacity(1, &key); + if (obj->IsFailure()) return obj; + Object* k = key.GetObject(); + if (k->IsFailure()) return k; + + LookupCache* cache = reinterpret_cast(obj); + int entry = cache->FindInsertionEntry(k, key.Hash()); + int index = EntryToIndex(entry); + cache->set(index, k); + cache->set(index + 1, Smi::FromInt(value)); + cache->ElementAdded(); + return cache; +} + + Object* Dictionary::Allocate(int at_least_space_for) { Object* obj = DictionaryBase::Allocate(at_least_space_for); // Initialize the next enumeration index. @@ -5926,6 +5992,7 @@ Object* Dictionary::Allocate(int at_least_space_for) { return obj; } + Object* Dictionary::GenerateNewEnumerationIndices() { int length = NumberOfElements(); diff --git a/src/objects.h b/src/objects.h index 7193a35..3e9e966 100644 --- a/src/objects.h +++ b/src/objects.h @@ -58,6 +58,9 @@ // - HashTable // - Dictionary // - SymbolTable +// - CompilationCacheTable +// - MapCache +// - LookupCache // - Context // - GlobalContext // - String @@ -626,6 +629,7 @@ class Object BASE_EMBEDDED { inline bool IsSymbolTable(); inline bool IsCompilationCacheTable(); inline bool IsMapCache(); + inline bool IsLookupCache(); inline bool IsPrimitive(); inline bool IsGlobalObject(); inline bool IsJSGlobalObject(); @@ -1870,6 +1874,27 @@ class MapCache: public HashTable<0, 2> { }; +// LookupCache. +// +// Maps a key consisting of a map and a name to an index within a +// fast-case properties array. +// +// LookupCaches are used to avoid repeatedly searching instance +// descriptors. +class LookupCache: public HashTable<0, 2> { + public: + int Lookup(Map* map, String* name); + Object* Put(Map* map, String* name, int offset); + static inline LookupCache* cast(Object* obj); + + // Constant returned by Lookup when the key was not found. + static const int kNotFound = -1; + + private: + DISALLOW_IMPLICIT_CONSTRUCTORS(LookupCache); +}; + + // Dictionary for keeping properties and elements in slow case. // // One element in the prefix is used for storing non-element diff --git a/src/runtime.cc b/src/runtime.cc index 936518a..48122d4 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -113,8 +113,8 @@ static Handle ComputeObjectLiteralMap( // Based on the number of prefix symbols key we decide whether // to use the map cache in the global context. const int kMaxKeys = 10; - if ((number_of_symbol_keys == number_of_properties) - && (number_of_symbol_keys < kMaxKeys)) { + if ((number_of_symbol_keys == number_of_properties) && + (number_of_symbol_keys < kMaxKeys)) { // Create the fixed array with the key. Handle keys = Factory::NewFixedArray(number_of_symbol_keys); for (int i = 0; i < number_of_symbol_keys; i++) { @@ -1669,23 +1669,57 @@ static Object* Runtime_GetProperty(Arguments args) { -// KeyedStringGetProperty is called from KeyedLoadIC::GenerateGeneric +// KeyedStringGetProperty is called from KeyedLoadIC::GenerateGeneric. static Object* Runtime_KeyedGetProperty(Arguments args) { NoHandleAllocation ha; ASSERT(args.length() == 2); - Object* receiver = args[0]; - Object* key = args[1]; - if (receiver->IsJSObject() && - key->IsString() && - !JSObject::cast(receiver)->HasFastProperties()) { - Dictionary* dictionary = JSObject::cast(receiver)->property_dictionary(); - int entry = dictionary->FindStringEntry(String::cast(key)); - if ((entry != DescriptorArray::kNotFound) - && (dictionary->DetailsAt(entry).type() == NORMAL)) { - return dictionary->ValueAt(entry); + // Fast cases for getting named properties of the receiver JSObject + // itself. The global proxy objects has to be excluded since + // LocalLookup on the global proxy object can return a valid result + // eventhough the global proxy object never has properties. This is + // the case because the global proxy object forwards everything to + // its hidden prototype including local lookups. + if (args[0]->IsJSObject() && + !args[0]->IsJSGlobalProxy() && + args[1]->IsString()) { + JSObject* receiver = JSObject::cast(args[0]); + String* key = String::cast(args[1]); + if (receiver->HasFastProperties()) { + // Attempt to use lookup cache. + Object* obj = Heap::GetKeyedLookupCache(); + if (obj->IsFailure()) return obj; + LookupCache* cache = LookupCache::cast(obj); + Map* receiver_map = receiver->map(); + int offset = cache->Lookup(receiver_map, key); + if (offset != LookupCache::kNotFound) { + Object* value = receiver->FastPropertyAt(offset); + return value->IsTheHole() ? Heap::undefined_value() : value; + } + // Lookup cache miss. Perform lookup and update the cache if + // appropriate. + LookupResult result; + receiver->LocalLookup(key, &result); + if (result.IsProperty() && result.IsLoaded() && result.type() == FIELD) { + int offset = result.GetFieldIndex(); + Object* obj = cache->Put(receiver_map, key, offset); + if (obj->IsFailure()) return obj; + Heap::SetKeyedLookupCache(LookupCache::cast(obj)); + Object* value = receiver->FastPropertyAt(offset); + return value->IsTheHole() ? Heap::undefined_value() : value; + } + } else { + // Attempt dictionary lookup. + Dictionary* dictionary = receiver->property_dictionary(); + int entry = dictionary->FindStringEntry(key); + if ((entry != DescriptorArray::kNotFound) && + (dictionary->DetailsAt(entry).type() == NORMAL)) { + return dictionary->ValueAt(entry); + } } } + + // Fall back to GetObjectProperty. return Runtime::GetObjectProperty(args.at(0), args.at(1)); } -- 2.7.4