Author: [EMAIL PROTECTED]
Date: Thu Oct 23 00:04:56 2008
New Revision: 561
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:
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
Modified: branches/bleeding_edge/src/heap-inl.h
==============================================================================
--- branches/bleeding_edge/src/heap-inl.h (original)
+++ branches/bleeding_edge/src/heap-inl.h Thu Oct 23 00:04:56 2008
@@ -165,6 +165,26 @@
}
+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())
Modified: branches/bleeding_edge/src/heap.cc
==============================================================================
--- branches/bleeding_edge/src/heap.cc (original)
+++ branches/bleeding_edge/src/heap.cc Thu Oct 23 00:04:56 2008
@@ -421,6 +421,7 @@
void Heap::MarkCompactPrologue() {
+ ClearKeyedLookupCache();
CompilationCache::MarkCompactPrologue();
RegExpImpl::OldSpaceCollectionPrologue();
Top::MarkCompactPrologue();
@@ -1194,6 +1195,9 @@
obj = AllocateFixedArray(Natives::GetBuiltinsCount());
if (obj->IsFailure()) return false;
natives_source_cache_ = FixedArray::cast(obj);
+
+ // Initialize keyed lookup cache.
+ ClearKeyedLookupCache();
// Initialize compilation cache.
CompilationCache::Clear();
Modified: branches/bleeding_edge/src/heap.h
==============================================================================
--- branches/bleeding_edge/src/heap.h (original)
+++ branches/bleeding_edge/src/heap.h Thu Oct 23 00:04:56 2008
@@ -122,7 +122,8 @@
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) \
@@ -638,6 +639,11 @@
static void set_non_monomorphic_cache(Dictionary* value) {
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();
Modified: branches/bleeding_edge/src/objects-inl.h
==============================================================================
--- branches/bleeding_edge/src/objects-inl.h (original)
+++ branches/bleeding_edge/src/objects-inl.h Thu Oct 23 00:04:56 2008
@@ -354,6 +354,11 @@
}
+bool Object::IsLookupCache() {
+ return IsHashTable();
+}
+
+
bool Object::IsPrimitive() {
return IsOddball() || IsNumber() || IsString();
}
@@ -1186,6 +1191,7 @@
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 Thu Oct 23 00:04:56 2008
@@ -5490,9 +5490,7 @@
// 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 @@
// 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* 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 @@
// 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 @@
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<uint32_t>(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 @@
}
+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));
+ 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.
@@ -5925,6 +5991,7 @@
}
return obj;
}
+
Object* Dictionary::GenerateNewEnumerationIndices() {
int length = NumberOfElements();
Modified: branches/bleeding_edge/src/objects.h
==============================================================================
--- branches/bleeding_edge/src/objects.h (original)
+++ branches/bleeding_edge/src/objects.h Thu Oct 23 00:04:56 2008
@@ -58,6 +58,9 @@
// - HashTable
// - Dictionary
// - SymbolTable
+// - CompilationCacheTable
+// - MapCache
+// - LookupCache
// - Context
// - GlobalContext
// - String
@@ -626,6 +629,7 @@
inline bool IsSymbolTable();
inline bool IsCompilationCacheTable();
inline bool IsMapCache();
+ inline bool IsLookupCache();
inline bool IsPrimitive();
inline bool IsGlobalObject();
inline bool IsJSGlobalObject();
@@ -1867,6 +1871,27 @@
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 Thu Oct 23 00:04:56 2008
@@ -113,8 +113,8 @@
// 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<FixedArray> keys =
Factory::NewFixedArray(number_of_symbol_keys);
for (int i = 0; i < number_of_symbol_keys; i++) {
@@ -1669,23 +1669,57 @@
-// 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<Object>(0),
args.at<Object>(1));
}
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
