Revision: 3878 Author: [email protected] Date: Tue Feb 16 10:56:07 2010 Log: Don't externalize fresh strings.
With the current API the embedder has to extrenalize a string each time a string is encountered to avoid the cost of repeated character copying/conversion. The issue here is that the externalization cost itself is non-negligible (both in time and space) and should not be paid for a rarely used string. This change is an attempt to predict a string's usage frequency based on its freshness. A string is considered fresh if it was recently allocated in the new space. Review URL: http://codereview.chromium.org/608006 http://code.google.com/p/v8/source/detail?r=3878 Modified: /branches/bleeding_edge/src/api.cc /branches/bleeding_edge/test/cctest/test-api.cc ======================================= --- /branches/bleeding_edge/src/api.cc Tue Feb 16 07:15:31 2010 +++ /branches/bleeding_edge/src/api.cc Tue Feb 16 10:56:07 2010 @@ -2485,6 +2485,72 @@ } +namespace { + +// Tracks string usage to help make better decisions when +// externalizing strings. +// +// Implementation note: internally this class only tracks fresh +// strings and keeps a single use counter for them. +class StringTracker { + public: + // Records that the given string's characters were copied to some + // external buffer. If this happens often we should honor + // externalization requests for the string. + static void RecordWrite(i::Handle<i::String> string) { + i::Address address = reinterpret_cast<i::Address>(*string); + i::Address top = i::Heap::NewSpaceTop(); + if (IsFreshString(address, top)) { + IncrementUseCount(top); + } + } + + // Estimates freshness and use frequency of the given string based + // on how close it is to the new space top and the recorded usage + // history. + static inline bool IsFreshUnusedString(i::Handle<i::String> string) { + i::Address address = reinterpret_cast<i::Address>(*string); + i::Address top = i::Heap::NewSpaceTop(); + return IsFreshString(address, top) && IsUseCountLow(top); + } + + private: + static inline bool IsFreshString(i::Address string, i::Address top) { + return top - kFreshnessLimit <= string && string <= top; + } + + static inline bool IsUseCountLow(i::Address top) { + if (last_top_ != top) return true; + return use_count_ < kUseLimit; + } + + static inline void IncrementUseCount(i::Address top) { + if (last_top_ != top) { + use_count_ = 0; + last_top_ = top; + } + ++use_count_; + } + + // How close to the new space top a fresh string has to be. + static const int kFreshnessLimit = 1024; + + // The number of uses required to consider a string useful. + static const int kUseLimit = 32; + + // Single use counter shared by all fresh strings. + static int use_count_; + + // Last new space top when the use count above was valid. + static i::Address last_top_; +}; + +int StringTracker::use_count_ = 0; +i::Address StringTracker::last_top_ = NULL; + +} // namespace + + int String::Length() const { if (IsDeadCheck("v8::String::Length()")) return 0; return Utils::OpenHandle(this)->length(); @@ -2502,6 +2568,7 @@ LOG_API("String::WriteUtf8"); ENTER_V8; i::Handle<i::String> str = Utils::OpenHandle(this); + StringTracker::RecordWrite(str); write_input_buffer.Reset(0, *str); int len = str->length(); // Encode the first K - 3 bytes directly into the buffer since we @@ -2545,6 +2612,7 @@ ENTER_V8; ASSERT(start >= 0 && length >= -1); i::Handle<i::String> str = Utils::OpenHandle(this); + StringTracker::RecordWrite(str); // Flatten the string for efficiency. This applies whether we are // using StringInputBuffer or Get(i) to access the characters. str->TryFlattenIfNotFlat(); @@ -2571,6 +2639,7 @@ ENTER_V8; ASSERT(start >= 0 && length >= -1); i::Handle<i::String> str = Utils::OpenHandle(this); + StringTracker::RecordWrite(str); int end = length; if ( (length == -1) || (length > str->length() - start) ) end = str->length() - start; @@ -3138,6 +3207,7 @@ if (this->IsExternal()) return false; // Already an external string. ENTER_V8; i::Handle<i::String> obj = Utils::OpenHandle(this); + if (StringTracker::IsFreshUnusedString(obj)) return false; bool result = obj->MakeExternal(resource); if (result && !obj->IsSymbol()) { i::ExternalStringTable::AddString(*obj); @@ -3163,6 +3233,7 @@ if (this->IsExternal()) return false; // Already an external string. ENTER_V8; i::Handle<i::String> obj = Utils::OpenHandle(this); + if (StringTracker::IsFreshUnusedString(obj)) return false; bool result = obj->MakeExternal(resource); if (result && !obj->IsSymbol()) { i::ExternalStringTable::AddString(*obj); @@ -3174,6 +3245,7 @@ bool v8::String::CanMakeExternal() { if (IsDeadCheck("v8::String::CanMakeExternal()")) return false; i::Handle<i::String> obj = Utils::OpenHandle(this); + if (StringTracker::IsFreshUnusedString(obj)) return false; int size = obj->Size(); // Byte size of the original string. if (size < i::ExternalString::kSize) return false; ======================================= --- /branches/bleeding_edge/test/cctest/test-api.cc Mon Feb 15 06:19:15 2010 +++ /branches/bleeding_edge/test/cctest/test-api.cc Tue Feb 16 10:56:07 2010 @@ -394,6 +394,9 @@ v8::HandleScope scope; LocalContext env; Local<String> source = String::New(two_byte_source); + // Trigger GCs so that the newly allocated string moves to old gen. + i::Heap::CollectGarbage(0, i::NEW_SPACE); // in survivor space now + i::Heap::CollectGarbage(0, i::NEW_SPACE); // in old gen now bool success = source->MakeExternal(new TestResource(two_byte_source)); CHECK(success); Local<Script> script = Script::Compile(source); @@ -416,6 +419,9 @@ v8::HandleScope scope; LocalContext env; Local<String> source = v8_str(c_source); + // Trigger GCs so that the newly allocated string moves to old gen. + i::Heap::CollectGarbage(0, i::NEW_SPACE); // in survivor space now + i::Heap::CollectGarbage(0, i::NEW_SPACE); // in old gen now bool success = source->MakeExternal( new TestAsciiResource(i::StrDup(c_source))); CHECK(success); @@ -430,6 +436,80 @@ v8::internal::Heap::CollectAllGarbage(false); CHECK_EQ(1, TestAsciiResource::dispose_count); } + + +TEST(MakingExternalStringConditions) { + v8::HandleScope scope; + LocalContext env; + + // Free some space in the new space so that we can check freshness. + i::Heap::CollectGarbage(0, i::NEW_SPACE); + i::Heap::CollectGarbage(0, i::NEW_SPACE); + + Local<String> small_string = String::New(AsciiToTwoByteString("small")); + // We should refuse to externalize newly created small string. + CHECK(!small_string->CanMakeExternal()); + // Trigger GCs so that the newly allocated string moves to old gen. + i::Heap::CollectGarbage(0, i::NEW_SPACE); // in survivor space now + i::Heap::CollectGarbage(0, i::NEW_SPACE); // in old gen now + // Old space strings should be accepted. + CHECK(small_string->CanMakeExternal()); + + small_string = String::New(AsciiToTwoByteString("small 2")); + // We should refuse externalizing newly created small string. + CHECK(!small_string->CanMakeExternal()); + for (int i = 0; i < 100; i++) { + String::Value value(small_string); + } + // Frequently used strings should be accepted. + CHECK(small_string->CanMakeExternal()); + + const int buf_size = 10 * 1024; + char* buf = i::NewArray<char>(buf_size); + memset(buf, 'a', buf_size); + buf[buf_size - 1] = '\0'; + Local<String> large_string = String::New(AsciiToTwoByteString(buf)); + i::DeleteArray(buf); + // Large strings should be immediately accepted. + CHECK(large_string->CanMakeExternal()); +} + + +TEST(MakingExternalAsciiStringConditions) { + v8::HandleScope scope; + LocalContext env; + + // Free some space in the new space so that we can check freshness. + i::Heap::CollectGarbage(0, i::NEW_SPACE); + i::Heap::CollectGarbage(0, i::NEW_SPACE); + + Local<String> small_string = String::New("small"); + // We should refuse to externalize newly created small string. + CHECK(!small_string->CanMakeExternal()); + // Trigger GCs so that the newly allocated string moves to old gen. + i::Heap::CollectGarbage(0, i::NEW_SPACE); // in survivor space now + i::Heap::CollectGarbage(0, i::NEW_SPACE); // in old gen now + // Old space strings should be accepted. + CHECK(small_string->CanMakeExternal()); + + small_string = String::New("small 2"); + // We should refuse externalizing newly created small string. + CHECK(!small_string->CanMakeExternal()); + for (int i = 0; i < 100; i++) { + String::Value value(small_string); + } + // Frequently used strings should be accepted. + CHECK(small_string->CanMakeExternal()); + + const int buf_size = 10 * 1024; + char* buf = i::NewArray<char>(buf_size); + memset(buf, 'a', buf_size); + buf[buf_size - 1] = '\0'; + Local<String> large_string = String::New(buf); + i::DeleteArray(buf); + // Large strings should be immediately accepted. + CHECK(large_string->CanMakeExternal()); +} THREADED_TEST(UsingExternalString) { -- v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev
