From 1155ba8e8ee788b6f381da09a37327b23e2335ad Mon Sep 17 00:00:00 2001 From: "bak@chromium.org" Date: Wed, 17 Jun 2009 06:07:49 +0000 Subject: [PATCH] Reimplemented the KeyedLookupCache to speed up access. Review URL: http://codereview.chromium.org/126262 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@2195 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/heap-inl.h | 20 ------------ src/heap.cc | 43 ++++++++++++++++++++++++-- src/heap.h | 30 ++++++++++++++---- src/objects-inl.h | 6 ---- src/objects.cc | 79 ----------------------------------------------- src/objects.h | 23 -------------- src/runtime.cc | 11 ++----- 7 files changed, 68 insertions(+), 144 deletions(-) diff --git a/src/heap-inl.h b/src/heap-inl.h index 8dd09d77d..016d64d61 100644 --- a/src/heap-inl.h +++ b/src/heap-inl.h @@ -215,26 +215,6 @@ void Heap::ScavengeObject(HeapObject** p, HeapObject* object) { } -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(); -} - - void Heap::SetLastScriptId(Object* last_script_id) { last_script_id_ = last_script_id; } diff --git a/src/heap.cc b/src/heap.cc index eb70f21a8..1f7df1f76 100644 --- a/src/heap.cc +++ b/src/heap.cc @@ -500,7 +500,7 @@ void Heap::MarkCompact(GCTracer* tracer) { void Heap::MarkCompactPrologue(bool is_compacting) { // At any old GC clear the keyed lookup cache to enable collection of unused // maps. - ClearKeyedLookupCache(); + KeyedLookupCache::Clear(); CompilationCache::MarkCompactPrologue(); @@ -1364,7 +1364,7 @@ bool Heap::CreateInitialObjects() { last_script_id_ = undefined_value(); // Initialize keyed lookup cache. - ClearKeyedLookupCache(); + KeyedLookupCache::Clear(); // Initialize compilation cache. CompilationCache::Clear(); @@ -3478,6 +3478,45 @@ const char* GCTracer::CollectorString() { } +int KeyedLookupCache::Hash(Map* map, String* name) { + // Uses only lower 32 bits if pointers are larger. + uintptr_t addr_hash = + static_cast(reinterpret_cast(map)) >> 2; + return (addr_hash ^ name->Hash()) % kLength; +} + + +int KeyedLookupCache::Lookup(Map* map, String* name) { + int index = Hash(map, name); + Key& key = keys_[index]; + if ((key.map == map) && key.name->Equals(name)) { + return field_offsets_[index]; + } + return -1; +} + + +void KeyedLookupCache::Update(Map* map, String* name, int field_offset) { + String* symbol; + if (Heap::LookupSymbolIfExists(name, &symbol)) { + int index = Hash(map, symbol); + Key& key = keys_[index]; + key.map = map; + key.name = symbol; + field_offsets_[index] = field_offset; + } +} + + +void KeyedLookupCache::Clear() { + for (int index = 0; index < kLength; index++) keys_[index].map = NULL; +} + +KeyedLookupCache::Key KeyedLookupCache::keys_[KeyedLookupCache::kLength]; + +int KeyedLookupCache::field_offsets_[KeyedLookupCache::kLength]; + + #ifdef DEBUG bool Heap::GarbageCollectionGreedyCheck() { ASSERT(FLAG_gc_greedy); diff --git a/src/heap.h b/src/heap.h index 08b2a9935..e3289fcaa 100644 --- a/src/heap.h +++ b/src/heap.h @@ -126,7 +126,6 @@ namespace internal { V(FixedArray, number_string_cache) \ V(FixedArray, single_character_string_cache) \ V(FixedArray, natives_source_cache) \ - V(Object, keyed_lookup_cache) \ V(Object, last_script_id) @@ -700,11 +699,6 @@ 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(); - // Update the next script id. static inline void SetLastScriptId(Object* last_script_id); @@ -1140,6 +1134,30 @@ class HeapIterator BASE_EMBEDDED { }; +// Cache for mapping (map, property name) into field offset. +// Cleared at startup and prior to mark sweep collection. +class KeyedLookupCache { + public: + // Lookup field offset for (map, name). If absent, -1 is returned. + static int Lookup(Map* map, String* name); + + // Update an element in the cache. + static void Update(Map* map, String* name, int field_offset); + + // Clear the cache. + static void Clear(); + private: + inline static int Hash(Map* map, String* name); + static const int kLength = 128; + struct Key { + Map* map; + String* name; + }; + static Key keys_[kLength]; + static int field_offsets_[kLength]; +}; + + // ---------------------------------------------------------------------------- // Marking stack for tracing live objects. diff --git a/src/objects-inl.h b/src/objects-inl.h index bac0d559d..6345400d8 100644 --- a/src/objects-inl.h +++ b/src/objects-inl.h @@ -481,11 +481,6 @@ bool Object::IsMapCache() { } -bool Object::IsLookupCache() { - return IsHashTable(); -} - - bool Object::IsPrimitive() { return IsOddball() || IsNumber() || IsString(); } @@ -1388,7 +1383,6 @@ 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 cbd36e0a3..96a2fe251 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -6756,60 +6756,6 @@ class SymbolsKey : public HashTableKey { }; -// 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) { - // Uses only lower 32 bits if pointers are larger. - uintptr_t addr_hash = - static_cast(reinterpret_cast(map)); - return addr_hash ^ 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); @@ -6832,31 +6778,6 @@ 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), SKIP_WRITE_BARRIER); - 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. diff --git a/src/objects.h b/src/objects.h index 21907f8f3..2275a1184 100644 --- a/src/objects.h +++ b/src/objects.h @@ -59,7 +59,6 @@ // - SymbolTable // - CompilationCacheTable // - MapCache -// - LookupCache // - Context // - GlobalContext // - String @@ -678,7 +677,6 @@ 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(); @@ -2012,27 +2010,6 @@ 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 d1c9162d1..4a47ae5df 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -2633,12 +2633,9 @@ static Object* Runtime_KeyedGetProperty(Arguments args) { 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) { + int offset = KeyedLookupCache::Lookup(receiver_map, key); + if (offset != -1) { Object* value = receiver->FastPropertyAt(offset); return value->IsTheHole() ? Heap::undefined_value() : value; } @@ -2648,9 +2645,7 @@ static Object* Runtime_KeyedGetProperty(Arguments args) { 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)); + KeyedLookupCache::Update(receiver_map, key, offset); Object* value = receiver->FastPropertyAt(offset); return value->IsTheHole() ? Heap::undefined_value() : value; } -- 2.34.1