Author: [email protected]
Date: Tue Jun 16 23:07:49 2009
New Revision: 2195
Modified:
branches/bleeding_edge/src/heap-inl.h
branches/bleeding_edge/src/heap.cc
branches/bleeding_edge/src/heap.h
branches/bleeding_edge/src/objects-inl.h
branches/bleeding_edge/src/objects.cc
branches/bleeding_edge/src/objects.h
branches/bleeding_edge/src/runtime.cc
Log:
Reimplemented the KeyedLookupCache to speed up access.
Review URL: http://codereview.chromium.org/126262
Modified: branches/bleeding_edge/src/heap-inl.h
==============================================================================
--- branches/bleeding_edge/src/heap-inl.h (original)
+++ branches/bleeding_edge/src/heap-inl.h Tue Jun 16 23:07:49 2009
@@ -215,26 +215,6 @@
}
-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;
}
Modified: branches/bleeding_edge/src/heap.cc
==============================================================================
--- branches/bleeding_edge/src/heap.cc (original)
+++ branches/bleeding_edge/src/heap.cc Tue Jun 16 23:07:49 2009
@@ -500,7 +500,7 @@
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 @@
last_script_id_ = undefined_value();
// Initialize keyed lookup cache.
- ClearKeyedLookupCache();
+ KeyedLookupCache::Clear();
// Initialize compilation cache.
CompilationCache::Clear();
@@ -3476,6 +3476,45 @@
}
return "Unknown GC";
}
+
+
+int KeyedLookupCache::Hash(Map* map, String* name) {
+ // Uses only lower 32 bits if pointers are larger.
+ uintptr_t addr_hash =
+ static_cast<uint32_t>(reinterpret_cast<uintptr_t>(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
Modified: branches/bleeding_edge/src/heap.h
==============================================================================
--- branches/bleeding_edge/src/heap.h (original)
+++ branches/bleeding_edge/src/heap.h Tue Jun 16 23:07:49 2009
@@ -126,7 +126,6 @@
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 @@
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);
@@ -1137,6 +1131,30 @@
SpaceIterator* space_iterator_;
// Object iterator for the space currently being iterated.
ObjectIterator* object_iterator_;
+};
+
+
+// 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];
};
Modified: branches/bleeding_edge/src/objects-inl.h
==============================================================================
--- branches/bleeding_edge/src/objects-inl.h (original)
+++ branches/bleeding_edge/src/objects-inl.h Tue Jun 16 23:07:49 2009
@@ -481,11 +481,6 @@
}
-bool Object::IsLookupCache() {
- return IsHashTable();
-}
-
-
bool Object::IsPrimitive() {
return IsOddball() || IsNumber() || IsString();
}
@@ -1388,7 +1383,6 @@
CAST_ACCESSOR(SymbolTable)
CAST_ACCESSOR(CompilationCacheTable)
CAST_ACCESSOR(MapCache)
-CAST_ACCESSOR(LookupCache)
CAST_ACCESSOR(String)
CAST_ACCESSOR(SeqString)
CAST_ACCESSOR(SeqAsciiString)
Modified: branches/bleeding_edge/src/objects.cc
==============================================================================
--- branches/bleeding_edge/src/objects.cc (original)
+++ branches/bleeding_edge/src/objects.cc Tue Jun 16 23:07:49 2009
@@ -6756,60 +6756,6 @@
};
-// 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<uint32_t>(reinterpret_cast<uintptr_t>(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);
@@ -6827,31 +6773,6 @@
int entry = cache->FindInsertionEntry(array, key.Hash());
cache->set(EntryToIndex(entry), array);
cache->set(EntryToIndex(entry) + 1, value);
- cache->ElementAdded();
- return cache;
-}
-
-
-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<LookupCache*>(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;
}
Modified: branches/bleeding_edge/src/objects.h
==============================================================================
--- branches/bleeding_edge/src/objects.h (original)
+++ branches/bleeding_edge/src/objects.h Tue Jun 16 23:07:49 2009
@@ -59,7 +59,6 @@
// - SymbolTable
// - CompilationCacheTable
// - MapCache
-// - LookupCache
// - Context
// - GlobalContext
// - String
@@ -678,7 +677,6 @@
inline bool IsSymbolTable();
inline bool IsCompilationCacheTable();
inline bool IsMapCache();
- inline bool IsLookupCache();
inline bool IsPrimitive();
inline bool IsGlobalObject();
inline bool IsJSGlobalObject();
@@ -2009,27 +2007,6 @@
private:
DISALLOW_IMPLICIT_CONSTRUCTORS(MapCache);
-};
-
-
-// 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);
};
Modified: branches/bleeding_edge/src/runtime.cc
==============================================================================
--- branches/bleeding_edge/src/runtime.cc (original)
+++ branches/bleeding_edge/src/runtime.cc Tue Jun 16 23:07:49 2009
@@ -2633,12 +2633,9 @@
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 @@
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;
}
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
