From ebfa9d37b61c9e6eb5512db2b5b3dd1dd8b95e32 Mon Sep 17 00:00:00 2001 From: "feng@chromium.org" Date: Fri, 5 Sep 2008 16:27:56 +0000 Subject: [PATCH] Added a EvalCache that caches eval'ed scripts and compiled function boilerplate. The cache is a hashtable that takes String as key and JSFunction as the value. Caches are cleared before mark-compact GC's. Currently I don't put caps on cache size, string size, etc. This cuts date-parse-totfe.js runtime by half. Review URL: http://codereview.chromium.org/457 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@173 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/heap.cc | 36 ++++++++++++++++++++++++++++ src/heap.h | 28 ++++++++++++++++++++-- src/objects-inl.h | 8 +++++++ src/objects.cc | 65 ++++++++++++++++++++++++++++++++++++------------- src/objects.h | 72 +++++++++++++++++++++++++++++++++---------------------- src/runtime.cc | 22 ++++++++++++++--- src/v8-counters.h | 2 ++ 7 files changed, 182 insertions(+), 51 deletions(-) diff --git a/src/heap.cc b/src/heap.cc index cf97b59..283c59c 100644 --- a/src/heap.cc +++ b/src/heap.cc @@ -447,6 +447,10 @@ void Heap::MarkCompact(GCTracer* tracer) { void Heap::MarkCompactPrologue() { + // Empty eval caches + Heap::eval_cache_global_ = Heap::null_value(); + Heap::eval_cache_non_global_ = Heap::null_value(); + RegExpImpl::OldSpaceCollectionPrologue(); Top::MarkCompactPrologue(); ThreadManager::MarkCompactPrologue(); @@ -1204,6 +1208,10 @@ bool Heap::CreateInitialObjects() { if (obj->IsFailure()) return false; natives_source_cache_ = FixedArray::cast(obj); + // Initialized eval cache to null value. + eval_cache_global_ = null_value(); + eval_cache_non_global_ = null_value(); + return true; } @@ -2271,6 +2279,34 @@ Object* Heap::LookupSymbol(String* string) { } +Object* Heap::LookupEvalCache(bool is_global_context, String* src) { + Object* cache = is_global_context ? + eval_cache_global_ : eval_cache_non_global_; + return cache == null_value() ? + null_value() : EvalCache::cast(cache)->Lookup(src); +} + + +Object* Heap::PutInEvalCache(bool is_global_context, String* src, + JSFunction* value) { + Object** cache_ptr = is_global_context ? + &eval_cache_global_ : &eval_cache_non_global_; + + if (*cache_ptr == null_value()) { + Object* obj = EvalCache::Allocate(kInitialEvalCacheSize); + if (obj->IsFailure()) return false; + *cache_ptr = obj; + } + + Object* new_cache = + EvalCache::cast(*cache_ptr)->Put(src, value); + if (new_cache->IsFailure()) return new_cache; + *cache_ptr = new_cache; + + return value; +} + + #ifdef DEBUG void Heap::ZapFromSpace() { ASSERT(HAS_HEAP_OBJECT_TAG(kFromSpaceZapValue)); diff --git a/src/heap.h b/src/heap.h index 70e67ba..a3962bb 100644 --- a/src/heap.h +++ b/src/heap.h @@ -122,7 +122,9 @@ 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, eval_cache_global) \ + V(Object, eval_cache_non_global) #define ROOT_LIST(V) \ STRONG_ROOT_LIST(V) \ @@ -529,6 +531,28 @@ class Heap : public AllStatic { } static Object* LookupSymbol(String* str); + // EvalCache caches function boilerplates for compiled scripts + // from 'eval' function. + // Source string is used as the key, and compiled function + // boilerplate as value. Because the same source has different + // compiled code in global or local context, we use separate + // caches for global and local contexts. + // Caches are cleared before mark-compact/mark-sweep GC's. + + // Finds the function boilerplate of a source string. + // It returns a JSFunction object if found in the cache. + // The first parameter specifies whether the code is + // compiled in a global context. + static Object* LookupEvalCache(bool is_global_context, String* src); + + // Put a source string and its compiled function boilerplate + // in the eval cache. The cache may expand, and returns failure + // if it cannot expand the cache, otherwise the value is returned. + // The first parameter specifies whether the boilerplate is + // compiled in a global context. + static Object* PutInEvalCache(bool is_global_context, + String* src, JSFunction* value); + // Compute the matching symbol map for a string if possible. // NULL is returned if string is in new space or not flattened. static Map* SymbolMapForString(String* str); @@ -864,6 +888,7 @@ class Heap : public AllStatic { static void RebuildRSets(LargeObjectSpace* space); static const int kInitialSymbolTableSize = 2048; + static const int kInitialEvalCacheSize = 64; friend class Factory; friend class DisallowAllocationFailure; @@ -1165,7 +1190,6 @@ class GCTracer BASE_EMBEDDED { int previous_marked_count_; }; - } } // namespace v8::internal #endif // V8_HEAP_H_ diff --git a/src/objects-inl.h b/src/objects-inl.h index 37919f1..e9af815 100644 --- a/src/objects-inl.h +++ b/src/objects-inl.h @@ -314,6 +314,13 @@ bool Object::IsSymbolTable() { } +bool Object::IsEvalCache() { + return IsHashTable() && + (this == Heap::eval_cache_global() || + this == Heap::eval_cache_non_global()); +} + + bool Object::IsPrimitive() { return IsOddball() || IsNumber() || IsString(); } @@ -1089,6 +1096,7 @@ CAST_ACCESSOR(FixedArray) CAST_ACCESSOR(DescriptorArray) CAST_ACCESSOR(Dictionary) CAST_ACCESSOR(SymbolTable) +CAST_ACCESSOR(EvalCache) CAST_ACCESSOR(String) CAST_ACCESSOR(SeqString) CAST_ACCESSOR(AsciiString) diff --git a/src/objects.cc b/src/objects.cc index f0cefb3..7504f80 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -5251,7 +5251,7 @@ int JSObject::GetEnumElementKeys(FixedArray* storage) { // The NumberKey uses carries the uint32_t as key. // This avoids allocation in HasProperty. -class Dictionary::NumberKey : public Dictionary::Key { +class NumberKey : public HashTableKey { public: explicit NumberKey(uint32_t number) { number_ = number; @@ -5297,14 +5297,14 @@ class Dictionary::NumberKey : public Dictionary::Key { uint32_t number_; }; + // StringKey simply carries a string object as key. -class Dictionary::StringKey : public Dictionary::Key { +class StringKey : public HashTableKey { public: explicit StringKey(String* string) { string_ = string; } - private: bool IsMatch(Object* other) { if (!other->IsString()) return false; return string_->Equals(String::cast(other)); @@ -5325,10 +5325,10 @@ class Dictionary::StringKey : public Dictionary::Key { String* string_; }; -// Utf8Key carries a vector of chars as key. -class SymbolTable::Utf8Key : public SymbolTable::Key { +// Utf8SymbolKey carries a vector of chars as key. +class Utf8SymbolKey : public HashTableKey { public: - explicit Utf8Key(Vector string) + explicit Utf8SymbolKey(Vector string) : string_(string), hash_(0) { } bool IsMatch(Object* other) { @@ -5368,10 +5368,10 @@ class SymbolTable::Utf8Key : public SymbolTable::Key { }; -// StringKey carries a string object as key. -class SymbolTable::StringKey : public SymbolTable::Key { +// SymbolKey carries a string/symbol object as key. +class SymbolKey : public HashTableKey { public: - explicit StringKey(String* string) : string_(string) { } + explicit SymbolKey(String* string) : string_(string) { } HashFunction GetHashFunction() { return StringHash; @@ -5435,7 +5435,7 @@ Object* HashTable::Allocate(int at_least_space_for) { // Find entry for key otherwise return -1. template -int HashTable::FindEntry(Key* key) { +int HashTable::FindEntry(HashTableKey* key) { uint32_t nof = NumberOfElements(); if (nof == 0) return -1; // Bail out if empty. @@ -5462,7 +5462,8 @@ int HashTable::FindEntry(Key* key) { template -Object* HashTable::EnsureCapacity(int n, Key* key) { +Object* HashTable::EnsureCapacity( + int n, HashTableKey* key) { int capacity = Capacity(); int nof = NumberOfElements() + n; // Make sure 20% is free @@ -5520,19 +5521,23 @@ template class HashTable<0, 1>; template class HashTable<2, 3>; +// Force instantiation of EvalCache's base class +template class HashTable<0, 2>; + + Object* SymbolTable::LookupString(String* string, Object** s) { - StringKey key(string); + SymbolKey key(string); return LookupKey(&key, s); } Object* SymbolTable::LookupSymbol(Vector str, Object** s) { - Utf8Key key(str); + Utf8SymbolKey key(str); return LookupKey(&key, s); } -Object* SymbolTable::LookupKey(Key* key, Object** s) { +Object* SymbolTable::LookupKey(HashTableKey* key, Object** s) { int entry = FindEntry(key); // Symbol already in table. @@ -5563,6 +5568,31 @@ Object* SymbolTable::LookupKey(Key* key, Object** s) { } +Object* EvalCache::Lookup(String* src) { + StringKey key(src); + int entry = FindEntry(&key); + if (entry != -1) { + return get(EntryToIndex(entry) + 1); + } else { + return Heap::undefined_value(); + } +} + + +Object* EvalCache::Put(String* src, Object* value) { + StringKey key(src); + Object* obj = EnsureCapacity(1, &key); + if (obj->IsFailure()) return obj; + + EvalCache* cache = reinterpret_cast(obj); + int entry = cache->FindInsertionEntry(src, key.Hash()); + cache->set(EntryToIndex(entry), src); + cache->set(EntryToIndex(entry) + 1, 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. @@ -5625,7 +5655,7 @@ Object* Dictionary::GenerateNewEnumerationIndices() { } -Object* Dictionary::EnsureCapacity(int n, Key* key) { +Object* Dictionary::EnsureCapacity(int n, HashTableKey* key) { // Check whether there are enough enumeration indices to add n elements. if (key->IsStringKey() && !PropertyDetails::IsValidIndex(NextEnumerationIndex() + n)) { @@ -5681,7 +5711,7 @@ int Dictionary::FindNumberEntry(uint32_t index) { } -Object* Dictionary::AtPut(Key* key, Object* value) { +Object* Dictionary::AtPut(HashTableKey* key, Object* value) { int entry = FindEntry(key); // If the entry is present set the value; @@ -5701,7 +5731,8 @@ Object* Dictionary::AtPut(Key* key, Object* value) { } -Object* Dictionary::Add(Key* key, Object* value, PropertyDetails details) { +Object* Dictionary::Add(HashTableKey* key, Object* value, + PropertyDetails details) { // Check whether the dictionary should be extended. Object* obj = EnsureCapacity(1, key); if (obj->IsFailure()) return obj; diff --git a/src/objects.h b/src/objects.h index ba32260..109cdcc 100644 --- a/src/objects.h +++ b/src/objects.h @@ -614,6 +614,7 @@ class Object BASE_EMBEDDED { inline bool IsHashTable(); inline bool IsDictionary(); inline bool IsSymbolTable(); + inline bool IsEvalCache(); inline bool IsPrimitive(); inline bool IsGlobalObject(); inline bool IsJSGlobalObject(); @@ -1681,6 +1682,26 @@ class DescriptorArray: public FixedArray { // table. The prefix size indicates an amount of memory in the // beginning of the backing storage that can be used for non-element // information by subclasses. + +// HashTableKey is an abstract superclass keys. +class HashTableKey { + public: + // Returns whether the other object matches this key. + virtual bool IsMatch(Object* other) = 0; + typedef uint32_t (*HashFunction)(Object* obj); + // Returns the hash function used for this key. + virtual HashFunction GetHashFunction() = 0; + // Returns the hash value for this key. + virtual uint32_t Hash() = 0; + // Returns the key object for storing into the dictionary. + // If allocations fails a failure object is returned. + virtual Object* GetObject() = 0; + virtual bool IsStringKey() = 0; + // Required. + virtual ~HashTableKey() {} +}; + + template class HashTable: public FixedArray { public: @@ -1722,24 +1743,6 @@ class HashTable: public FixedArray { // Casting. static inline HashTable* cast(Object* obj); - // Key is an abstract superclass keys. - class Key { - public: - // Returns whether the other object matches this key. - virtual bool IsMatch(Object* other) = 0; - typedef uint32_t (*HashFunction)(Object* obj); - // Returns the hash function used for this key. - virtual HashFunction GetHashFunction() = 0; - // Returns the hash value for this key. - virtual uint32_t Hash() = 0; - // Returns the key object for storing into the dictionary. - // If allocations fails a failure object is returned. - virtual Object* GetObject() = 0; - virtual bool IsStringKey() = 0; - // Required. - virtual ~Key() {} - }; - // Compute the probe offset (quadratic probing). INLINE(static uint32_t GetProbeOffset(uint32_t n)) { return (n + n * n) >> 1; @@ -1755,7 +1758,7 @@ class HashTable: public FixedArray { protected: // Find entry for key otherwise return -1. - int FindEntry(Key* key); + int FindEntry(HashTableKey* key); // Find the entry at which to insert element with the given key that // has the given hash value. @@ -1788,7 +1791,7 @@ class HashTable: public FixedArray { } // Ensure enough space for n additional elements. - Object* EnsureCapacity(int n, Key* key); + Object* EnsureCapacity(int n, HashTableKey* key); }; @@ -1809,14 +1812,28 @@ class SymbolTable: public HashTable<0, 1> { static inline SymbolTable* cast(Object* obj); private: - Object* LookupKey(Key* key, Object** s); - class Utf8Key; // Key based on utf8 string. - class StringKey; // Key based on String*. + Object* LookupKey(HashTableKey* key, Object** s); DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable); }; +// EvalCache for caching eval'ed string and function. +// +// The cache is cleaned up during a mark-compact GC. +class EvalCache: public HashTable<0, 2> { + public: + // Find cached value for a string key, otherwise return null. + Object* Lookup(String* src); + Object* Put(String* src, Object* value); + + static inline EvalCache* cast(Object* obj); + + private: + DISALLOW_IMPLICIT_CONSTRUCTORS(EvalCache); +}; + + // Dictionary for keeping properties and elements in slow case. // // One element in the prefix is used for storing non-element @@ -1924,7 +1941,7 @@ class Dictionary: public DictionaryBase { static Object* Allocate(int at_least_space_for); // Ensure enough space for n additional elements. - Object* EnsureCapacity(int n, Key* key); + Object* EnsureCapacity(int n, HashTableKey* key); #ifdef DEBUG void Print(); @@ -1939,9 +1956,9 @@ class Dictionary: public DictionaryBase { private: // Generic at put operation. - Object* AtPut(Key* key, Object* value); + Object* AtPut(HashTableKey* key, Object* value); - Object* Add(Key* key, Object* value, PropertyDetails details); + Object* Add(HashTableKey* key, Object* value, PropertyDetails details); // Add entry to dictionary. void AddEntry(Object* key, @@ -1963,9 +1980,6 @@ class Dictionary: public DictionaryBase { static const int kMaxNumberKeyIndex = kPrefixStartIndex; static const int kNextEnumnerationIndexIndex = kMaxNumberKeyIndex + 1; - class NumberKey; // Key containing uint32_t. - class StringKey; // Key containing String*. - DISALLOW_IMPLICIT_CONSTRUCTORS(Dictionary); }; diff --git a/src/runtime.cc b/src/runtime.cc index 809fee0..cad5d23 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -3328,10 +3328,26 @@ static Object* Runtime_CompileString(Arguments args) { } // Compile eval() source. + bool is_global_context = context->IsGlobalContext(); Handle source(String::cast(args[0])); - Handle boilerplate = - Compiler::CompileEval(context->IsGlobalContext(), source); - if (boilerplate.is_null()) return Failure::Exception(); + Object* obj = Heap::LookupEvalCache(is_global_context, *source); + if (obj->IsFailure()) return obj; + + Handle boilerplate; + if (!obj->IsJSFunction()) { + Counters::eval_cache_misses.Increment(); + boilerplate = Compiler::CompileEval(is_global_context, source); + if (boilerplate.is_null()) return Failure::Exception(); + + Object* obj = + Heap::PutInEvalCache(is_global_context, *source, *boilerplate); + if (obj->IsFailure()) return obj; + + } else { + Counters::eval_cache_hits.Increment(); + boilerplate = Handle(JSFunction::cast(obj)); + } + Handle fun = Factory::NewFunctionFromBoilerplate(boilerplate, context); return *fun; diff --git a/src/v8-counters.h b/src/v8-counters.h index 566ed54..7bc70c1 100644 --- a/src/v8-counters.h +++ b/src/v8-counters.h @@ -71,6 +71,8 @@ namespace v8 { namespace internal { SC(call_normal_stubs, V8.CallNormalStubs) \ SC(call_megamorphic_stubs, V8.CallMegamorphicStubs) \ SC(arguments_adaptors, V8.ArgumentsAdaptors) \ + SC(eval_cache_hits, V8.EvalCacheHits) \ + SC(eval_cache_misses, V8.EvalCacheMisses) \ /* Amount of evaled source code. */ \ SC(total_eval_size, V8.TotalEvalSize) \ /* Amount of loaded source code. */ \ -- 2.7.4