From 43e8d5fa7faf8d16e4e89a662786bcfcd5e3a0f5 Mon Sep 17 00:00:00 2001 From: "erik.corry@gmail.com" Date: Fri, 20 Nov 2009 10:11:45 +0000 Subject: [PATCH] Some optimizations for packer.js. Review URL: http://codereview.chromium.org/409007 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@3336 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/heap.cc | 52 ++++++++++++++++++++++++++++++ src/heap.h | 1 + src/objects-inl.h | 15 +++++++-- src/objects.cc | 94 ++++++++++++++++++++++++++++++++++++++++++++++++++++--- src/objects.h | 2 ++ src/runtime.cc | 20 ++++++++---- 6 files changed, 171 insertions(+), 13 deletions(-) diff --git a/src/heap.cc b/src/heap.cc index 43886c1..06dc59c 100644 --- a/src/heap.cc +++ b/src/heap.cc @@ -1762,6 +1762,41 @@ Object* Heap::AllocateSharedFunctionInfo(Object* name) { } +// Returns true for a character in a range. Both limits are inclusive. +static inline bool Between(uint32_t character, uint32_t from, uint32_t to) { + // This makes uses of the the unsigned wraparound. + return character - from <= to - from; +} + + +static inline Object* MakeOrFindTwoCharacterString(uint32_t c1, uint32_t c2) { + String* symbol; + // Numeric strings have a different hash algorithm not known by + // LookupTwoCharsSymbolIfExists, so we skip this step for such strings. + if ((!Between(c1, '0', '9') || !Between(c2, '0', '9')) && + Heap::symbol_table()->LookupTwoCharsSymbolIfExists(c1, c2, &symbol)) { + return symbol; + // Now we know the length is 2, we might as well make use of that fact + // when building the new string. + } else if ((c1 | c2) <= String::kMaxAsciiCharCodeU) { // We can do this + ASSERT(IsPowerOf2(String::kMaxAsciiCharCodeU + 1)); // because of this. + Object* result = Heap::AllocateRawAsciiString(2); + if (result->IsFailure()) return result; + char* dest = SeqAsciiString::cast(result)->GetChars(); + dest[0] = c1; + dest[1] = c2; + return result; + } else { + Object* result = Heap::AllocateRawTwoByteString(2); + if (result->IsFailure()) return result; + uc16* dest = SeqTwoByteString::cast(result)->GetChars(); + dest[0] = c1; + dest[1] = c2; + return result; + } +} + + Object* Heap::AllocateConsString(String* first, String* second) { int first_length = first->length(); if (first_length == 0) { @@ -1774,6 +1809,16 @@ Object* Heap::AllocateConsString(String* first, String* second) { } int length = first_length + second_length; + + // Optimization for 2-byte strings often used as keys in a decompression + // dictionary. Check whether we already have the string in the symbol + // table to prevent creation of many unneccesary strings. + if (length == 2) { + unsigned c1 = first->Get(0); + unsigned c2 = second->Get(0); + return MakeOrFindTwoCharacterString(c1, c2); + } + bool is_ascii = first->IsAsciiRepresentation() && second->IsAsciiRepresentation(); @@ -1843,6 +1888,13 @@ Object* Heap::AllocateSubString(String* buffer, if (length == 1) { return Heap::LookupSingleCharacterStringFromCode( buffer->Get(start)); + } else if (length == 2) { + // Optimization for 2-byte strings often used as keys in a decompression + // dictionary. Check whether we already have the string in the symbol + // table to prevent creation of many unneccesary strings. + unsigned c1 = buffer->Get(start); + unsigned c2 = buffer->Get(start + 1); + return MakeOrFindTwoCharacterString(c1, c2); } // Make an attempt to flatten the buffer to reduce access time. diff --git a/src/heap.h b/src/heap.h index 8c1bb18..90d714c 100644 --- a/src/heap.h +++ b/src/heap.h @@ -631,6 +631,7 @@ class Heap : public AllStatic { } static Object* LookupSymbol(String* str); static bool LookupSymbolIfExists(String* str, String** symbol); + static bool LookupTwoCharsSymbolIfExists(String* str, String** symbol); // Compute the matching symbol map for a string if possible. // NULL is returned if string is in new space or not flattened. diff --git a/src/objects-inl.h b/src/objects-inl.h index 507a3ab..7a6444d 100644 --- a/src/objects-inl.h +++ b/src/objects-inl.h @@ -3103,8 +3103,19 @@ void Map::ClearCodeCache() { void JSArray::EnsureSize(int required_size) { ASSERT(HasFastElements()); - if (elements()->length() >= required_size) return; - Expand(required_size); + Array* elts = elements(); + const int kArraySizeThatFitsComfortablyInNewSpace = 128; + if (elts->length() < required_size) { + // Doubling in size would be overkill, but leave some slack to avoid + // constantly growing. + Expand(required_size + (required_size >> 3)); + // It's a performance benefit to keep a frequently used array in new-space. + } else if (!Heap::new_space()->Contains(elts) && + required_size < kArraySizeThatFitsComfortablyInNewSpace) { + // Expand will allocate a new backing store in new space even if the size + // we asked for isn't larger than what we had before. + Expand(required_size); + } } diff --git a/src/objects.cc b/src/objects.cc index 5ccacb7..f376585 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -1463,8 +1463,8 @@ Object* JSObject::SetPropertyPostInterceptor(String* name, Object* JSObject::ReplaceSlowProperty(String* name, - Object* value, - PropertyAttributes attributes) { + Object* value, + PropertyAttributes attributes) { StringDictionary* dictionary = property_dictionary(); int old_index = dictionary->FindEntry(name); int new_enumeration_index = 0; // 0 means "Use the next available index." @@ -1478,6 +1478,7 @@ Object* JSObject::ReplaceSlowProperty(String* name, return SetNormalizedProperty(name, value, new_details); } + Object* JSObject::ConvertDescriptorToFieldAndMapTransition( String* name, Object* new_value, @@ -1869,6 +1870,14 @@ Object* JSObject::SetProperty(LookupResult* result, // interceptor calls. AssertNoContextChange ncc; + // Optimization for 2-byte strings often used as keys in a decompression + // dictionary. We make these short keys into symbols to avoid constantly + // reallocating them. + if (!name->IsSymbol() && name->length() <= 2) { + Object* symbol_version = Heap::LookupSymbol(name); + if (!symbol_version->IsFailure()) name = String::cast(symbol_version); + } + // Check access rights if needed. if (IsAccessCheckNeeded() && !Top::MayNamedAccess(this, name, v8::ACCESS_SET)) { @@ -5240,9 +5249,7 @@ void JSArray::Expand(int required_size) { Handle self(this); Handle old_backing(FixedArray::cast(elements())); int old_size = old_backing->length(); - // Doubling in size would be overkill, but leave some slack to avoid - // constantly growing. - int new_size = required_size + (required_size >> 3); + int new_size = required_size > old_size ? required_size : old_size; Handle new_backing = Factory::NewFixedArray(new_size); // Can't use this any more now because we may have had a GC! for (int i = 0; i < old_size; i++) new_backing->set(i, old_backing->get(i)); @@ -7327,6 +7334,67 @@ Object* SymbolTable::LookupString(String* string, Object** s) { } +// This class is used for looking up two character strings in the symbol table. +// If we don't have a hit we don't want to waste much time so we unroll the +// string hash calculation loop here for speed. Doesn't work if the two +// characters form a decimal integer, since such strings have a different hash +// algorithm. +class TwoCharHashTableKey : public HashTableKey { + public: + TwoCharHashTableKey(uint32_t c1, uint32_t c2) + : c1_(c1), c2_(c2) { + // Char 1. + uint32_t hash = c1 + (c1 << 10); + hash ^= hash >> 6; + // Char 2. + hash += c2; + hash += hash << 10; + hash ^= hash >> 6; + // GetHash. + hash += hash << 3; + hash ^= hash >> 11; + hash += hash << 15; + if (hash == 0) hash = 27; +#ifdef DEBUG + StringHasher hasher(2); + hasher.AddCharacter(c1); + hasher.AddCharacter(c2); + // If this assert fails then we failed to reproduce the two-character + // version of the string hashing algorithm above. One reason could be + // that we were passed two digits as characters, since the hash + // algorithm is different in that case. + ASSERT_EQ(static_cast(hasher.GetHash()), static_cast(hash)); +#endif + hash_ = hash; + } + + bool IsMatch(Object* o) { + if (!o->IsString()) return false; + String* other = String::cast(o); + if (other->length() != 2) return false; + if (other->Get(0) != c1_) return false; + return other->Get(1) == c2_; + } + + uint32_t Hash() { return hash_; } + uint32_t HashForObject(Object* key) { + if (!key->IsString()) return 0; + return String::cast(key)->Hash(); + } + + Object* AsObject() { + // The TwoCharHashTableKey is only used for looking in the symbol + // table, not for adding to it. + UNREACHABLE(); + return NULL; + } + private: + uint32_t c1_; + uint32_t c2_; + uint32_t hash_; +}; + + bool SymbolTable::LookupSymbolIfExists(String* string, String** symbol) { SymbolKey key(string); int entry = FindEntry(&key); @@ -7341,6 +7409,22 @@ bool SymbolTable::LookupSymbolIfExists(String* string, String** symbol) { } +bool SymbolTable::LookupTwoCharsSymbolIfExists(uint32_t c1, + uint32_t c2, + String** symbol) { + TwoCharHashTableKey key(c1, c2); + int entry = FindEntry(&key); + if (entry == kNotFound) { + return false; + } else { + String* result = String::cast(KeyAt(entry)); + ASSERT(StringShape(result).IsSymbol()); + *symbol = result; + return true; + } +} + + Object* SymbolTable::LookupSymbol(Vector str, Object** s) { Utf8SymbolKey key(str); return LookupKey(&key, s); diff --git a/src/objects.h b/src/objects.h index 6ea0a82..d22e723 100644 --- a/src/objects.h +++ b/src/objects.h @@ -2188,6 +2188,7 @@ class SymbolTable: public HashTable { // true if it is found, assigning the symbol to the given output // parameter. bool LookupSymbolIfExists(String* str, String** symbol); + bool LookupTwoCharsSymbolIfExists(uint32_t c1, uint32_t c2, String** symbol); // Casting. static inline SymbolTable* cast(Object* obj); @@ -3846,6 +3847,7 @@ class StringHasher { bool is_array_index_; bool is_first_char_; bool is_valid_; + friend class TwoCharHashTableKey; }; diff --git a/src/runtime.cc b/src/runtime.cc index 13f6561..6ae2233 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -2356,12 +2356,20 @@ static Object* Runtime_SubString(Arguments args) { ASSERT(args.length() == 3); CONVERT_CHECKED(String, value, args[0]); - CONVERT_DOUBLE_CHECKED(from_number, args[1]); - CONVERT_DOUBLE_CHECKED(to_number, args[2]); - - int start = FastD2I(from_number); - int end = FastD2I(to_number); - + Object* from = args[1]; + Object* to = args[2]; + int start, end; + // We have a fast integer-only case here to avoid a conversion to double in + // the common case where from and to are Smis. + if (from->IsSmi() && to->IsSmi()) { + start = Smi::cast(from)->value(); + end = Smi::cast(to)->value(); + } else { + CONVERT_DOUBLE_CHECKED(from_number, from); + CONVERT_DOUBLE_CHECKED(to_number, to); + start = FastD2I(from_number); + end = FastD2I(to_number); + } RUNTIME_ASSERT(end >= start); RUNTIME_ASSERT(start >= 0); RUNTIME_ASSERT(end <= value->length()); -- 2.7.4