From 9e1a7e2e6f16591c7113c36ef9a1de716741902d Mon Sep 17 00:00:00 2001 From: "yangguo@chromium.org" Date: Thu, 21 Mar 2013 10:53:26 +0000 Subject: [PATCH] Unify code for fast and slow path of JSON.stringify. R=verwaest@chromium.org BUG= Review URL: https://chromiumcodereview.appspot.com/12690017 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@14023 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/heap.h | 1 + src/json-stringifier.h | 92 ++++++++++--- src/runtime.cc | 360 +------------------------------------------------ src/runtime.h | 2 - 4 files changed, 79 insertions(+), 376 deletions(-) diff --git a/src/heap.h b/src/heap.h index 90f2e60..b3be86b 100644 --- a/src/heap.h +++ b/src/heap.h @@ -220,6 +220,7 @@ namespace internal { V(undefined_string, "undefined") \ V(value_of_string, "valueOf") \ V(stack_string, "stack") \ + V(toJSON_string, "toJSON") \ V(InitializeVarGlobal_string, "InitializeVarGlobal") \ V(InitializeConstGlobal_string, "InitializeConstGlobal") \ V(KeyedLoadElementMonomorphic_string, \ diff --git a/src/json-stringifier.h b/src/json-stringifier.h index ad9ef3d..418d479 100644 --- a/src/json-stringifier.h +++ b/src/json-stringifier.h @@ -41,6 +41,9 @@ class BasicJsonStringifier BASE_EMBEDDED { MaybeObject* Stringify(Handle object); + INLINE(static MaybeObject* StringifyString(Isolate* isolate, + Handle object)); + private: static const int kInitialPartLength = 32; static const int kMaxPartLength = 16 * 1024; @@ -84,6 +87,11 @@ class BasicJsonStringifier BASE_EMBEDDED { bool deferred_comma, bool deferred_key); + template + INLINE(static MaybeObject* StringifyString_(Isolate* isolate, + Handle string, + Handle result)); + // Entry point to serialize the object. INLINE(Result SerializeObject(Handle obj)) { return Serialize_(obj, false, factory_->empty_string()); @@ -135,18 +143,18 @@ class BasicJsonStringifier BASE_EMBEDDED { void SerializeString(Handle object); template - INLINE(void SerializeStringUnchecked_(const SrcChar* src, - DestChar* dest, - int length)); + INLINE(static int SerializeStringUnchecked_(const SrcChar* src, + DestChar* dest, + int length)); template INLINE(void SerializeString_(Handle string)); template - INLINE(bool DoNotEscape(Char c)); + INLINE(static bool DoNotEscape(Char c)); template - INLINE(Vector GetCharVector(Handle string)); + INLINE(static Vector GetCharVector(Handle string)); Result StackPush(Handle object); void StackPop(); @@ -244,15 +252,15 @@ const char* const BasicJsonStringifier::JsonEscapeTable = "\370\0 \371\0 \372\0 \373\0 " "\374\0 \375\0 \376\0 \377\0 "; + BasicJsonStringifier::BasicJsonStringifier(Isolate* isolate) : isolate_(isolate), current_index_(0), is_ascii_(true) { factory_ = isolate_->factory(); accumulator_store_ = Handle::cast( factory_->ToObject(factory_->empty_string())); part_length_ = kInitialPartLength; - current_part_ = factory_->NewRawOneByteString(kInitialPartLength); - tojson_string_ = - factory_->InternalizeOneByteString(STATIC_ASCII_VECTOR("toJSON")); + current_part_ = factory_->NewRawOneByteString(part_length_); + tojson_string_ = factory_->toJSON_string(); stack_ = factory_->NewJSArray(8); } @@ -275,6 +283,57 @@ MaybeObject* BasicJsonStringifier::Stringify(Handle object) { } +MaybeObject* BasicJsonStringifier::StringifyString(Isolate* isolate, + Handle object) { + static const int kJsonQuoteWorstCaseBlowup = 6; + static const int kSpaceForQuotes = 2; + int worst_case_length = + object->length() * kJsonQuoteWorstCaseBlowup + kSpaceForQuotes; + + if (worst_case_length > 32 * KB) { // Slow path if too large. + BasicJsonStringifier stringifier(isolate); + return stringifier.Stringify(object); + } + + object = FlattenGetString(object); + if (object->IsSeqOneByteString()) { + return StringifyString_( + isolate, + object, + isolate->factory()->NewRawOneByteString(worst_case_length)); + } else { + return StringifyString_( + isolate, + object, + isolate->factory()->NewRawTwoByteString(worst_case_length)); + } +} + + +template +MaybeObject* BasicJsonStringifier::StringifyString_(Isolate* isolate, + Handle string, + Handle result) { + AssertNoAllocation no_allocation; + int final_size = 0; + StringType* dest = StringType::cast(*result); + dest->Set(final_size++, '\"'); + final_size += SerializeStringUnchecked_(StringType::cast(*string)->GetChars(), + dest->GetChars() + 1, + string->length()); + dest->Set(final_size++, '\"'); + if (isolate->heap()->InNewSpace(*result)) { + // In new space, simply lower the allocation top to fit the actual size. + isolate->heap()->new_space()->ShrinkStringAtAllocationBoundary( + *result, final_size); + return *result; + } else { + // Not in new space, need to fill the wasted space with filler objects. + return SeqString::cast(*result)->Truncate(final_size); + } +} + + template void BasicJsonStringifier::Append_(Char c) { if (is_ascii) { @@ -667,10 +726,9 @@ void BasicJsonStringifier::ChangeEncoding() { template -void BasicJsonStringifier::SerializeStringUnchecked_(const SrcChar* src, - DestChar* dest, - int length) { - dest += current_index_; +int BasicJsonStringifier::SerializeStringUnchecked_(const SrcChar* src, + DestChar* dest, + int length) { DestChar* dest_start = dest; // Assert that uc16 character is not truncated down to 8 bit. @@ -688,7 +746,7 @@ void BasicJsonStringifier::SerializeStringUnchecked_(const SrcChar* src, } } - current_index_ += static_cast(dest - dest_start); + return static_cast(dest - dest_start); } @@ -705,14 +763,14 @@ void BasicJsonStringifier::SerializeString_(Handle string) { AssertNoAllocation no_allocation; Vector vector = GetCharVector(string); if (is_ascii) { - SerializeStringUnchecked_( + current_index_ += SerializeStringUnchecked_( vector.start(), - SeqOneByteString::cast(*current_part_)->GetChars(), + SeqOneByteString::cast(*current_part_)->GetChars() + current_index_, length); } else { - SerializeStringUnchecked_( + current_index_ += SerializeStringUnchecked_( vector.start(), - SeqTwoByteString::cast(*current_part_)->GetChars(), + SeqTwoByteString::cast(*current_part_)->GetChars() + current_index_, length); } } else { diff --git a/src/runtime.cc b/src/runtime.cc index 0b5d209..b14cdbd 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -5171,365 +5171,11 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_URIUnescape) { } -static const unsigned int kQuoteTableLength = 128u; - -static const int kJsonQuotesCharactersPerEntry = 8; -static const char* const JsonQuotes = - "\\u0000 \\u0001 \\u0002 \\u0003 " - "\\u0004 \\u0005 \\u0006 \\u0007 " - "\\b \\t \\n \\u000b " - "\\f \\r \\u000e \\u000f " - "\\u0010 \\u0011 \\u0012 \\u0013 " - "\\u0014 \\u0015 \\u0016 \\u0017 " - "\\u0018 \\u0019 \\u001a \\u001b " - "\\u001c \\u001d \\u001e \\u001f " - " ! \\\" # " - "$ % & ' " - "( ) * + " - ", - . / " - "0 1 2 3 " - "4 5 6 7 " - "8 9 : ; " - "< = > ? " - "@ A B C " - "D E F G " - "H I J K " - "L M N O " - "P Q R S " - "T U V W " - "X Y Z [ " - "\\\\ ] ^ _ " - "` a b c " - "d e f g " - "h i j k " - "l m n o " - "p q r s " - "t u v w " - "x y z { " - "| } ~ \177 "; - - -// For a string that is less than 32k characters it should always be -// possible to allocate it in new space. -static const int kMaxGuaranteedNewSpaceString = 32 * 1024; - - -// Doing JSON quoting cannot make the string more than this many times larger. -static const int kJsonQuoteWorstCaseBlowup = 6; - -static const int kSpaceForQuotesAndComma = 3; -static const int kSpaceForBrackets = 2; - -// Covers the entire ASCII range (all other characters are unchanged by JSON -// quoting). -static const byte JsonQuoteLengths[kQuoteTableLength] = { - 6, 6, 6, 6, 6, 6, 6, 6, - 2, 2, 2, 6, 2, 2, 6, 6, - 6, 6, 6, 6, 6, 6, 6, 6, - 6, 6, 6, 6, 6, 6, 6, 6, - 1, 1, 2, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 2, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, -}; - - -template -MaybeObject* AllocateRawString(Isolate* isolate, int length); - - -template <> -MaybeObject* AllocateRawString(Isolate* isolate, int length) { - return isolate->heap()->AllocateRawTwoByteString(length); -} - - -template <> -MaybeObject* AllocateRawString(Isolate* isolate, int length) { - return isolate->heap()->AllocateRawOneByteString(length); -} - - -template -static MaybeObject* SlowQuoteJsonString(Isolate* isolate, - Vector characters) { - int length = characters.length(); - const Char* read_cursor = characters.start(); - const Char* end = read_cursor + length; - const int kSpaceForQuotes = 2 + (comma ? 1 :0); - int quoted_length = kSpaceForQuotes; - while (read_cursor < end) { - Char c = *(read_cursor++); - if (static_cast(c) >= kQuoteTableLength) { - quoted_length++; - } else { - quoted_length += JsonQuoteLengths[static_cast(c)]; - } - } - MaybeObject* new_alloc = AllocateRawString(isolate, - quoted_length); - Object* new_object; - if (!new_alloc->ToObject(&new_object)) { - return new_alloc; - } - StringType* new_string = StringType::cast(new_object); - - Char* write_cursor = reinterpret_cast( - new_string->address() + SeqString::kHeaderSize); - if (comma) *(write_cursor++) = ','; - *(write_cursor++) = '"'; - - read_cursor = characters.start(); - while (read_cursor < end) { - Char c = *(read_cursor++); - if (static_cast(c) >= kQuoteTableLength) { - *(write_cursor++) = c; - } else { - int len = JsonQuoteLengths[static_cast(c)]; - const char* replacement = JsonQuotes + - static_cast(c) * kJsonQuotesCharactersPerEntry; - for (int i = 0; i < len; i++) { - *write_cursor++ = *replacement++; - } - } - } - *(write_cursor++) = '"'; - return new_string; -} - - -template -static inline SinkChar* WriteQuoteJsonString( - Isolate* isolate, - SinkChar* write_cursor, - Vector characters) { - // SinkChar is only char if SourceChar is guaranteed to be char. - ASSERT(sizeof(SinkChar) >= sizeof(SourceChar)); - const SourceChar* read_cursor = characters.start(); - const SourceChar* end = read_cursor + characters.length(); - *(write_cursor++) = '"'; - while (read_cursor < end) { - SourceChar c = *(read_cursor++); - if (static_cast(c) >= kQuoteTableLength) { - *(write_cursor++) = static_cast(c); - } else { - int len = JsonQuoteLengths[static_cast(c)]; - const char* replacement = JsonQuotes + - static_cast(c) * kJsonQuotesCharactersPerEntry; - write_cursor[0] = replacement[0]; - if (len > 1) { - write_cursor[1] = replacement[1]; - if (len > 2) { - ASSERT(len == 6); - write_cursor[2] = replacement[2]; - write_cursor[3] = replacement[3]; - write_cursor[4] = replacement[4]; - write_cursor[5] = replacement[5]; - } - } - write_cursor += len; - } - } - *(write_cursor++) = '"'; - return write_cursor; -} - - -template -static MaybeObject* QuoteJsonString(Isolate* isolate, - Vector characters) { - int length = characters.length(); - isolate->counters()->quote_json_char_count()->Increment(length); - int worst_case_length = - length * kJsonQuoteWorstCaseBlowup + kSpaceForQuotesAndComma; - if (worst_case_length > kMaxGuaranteedNewSpaceString) { - return SlowQuoteJsonString(isolate, characters); - } - - MaybeObject* new_alloc = AllocateRawString(isolate, - worst_case_length); - Object* new_object; - if (!new_alloc->ToObject(&new_object)) { - return new_alloc; - } - if (!isolate->heap()->new_space()->Contains(new_object)) { - // Even if our string is small enough to fit in new space we still have to - // handle it being allocated in old space as may happen in the third - // attempt. See CALL_AND_RETRY in heap-inl.h and similar code in - // CEntryStub::GenerateCore. - return SlowQuoteJsonString(isolate, characters); - } - StringType* new_string = StringType::cast(new_object); - ASSERT(isolate->heap()->new_space()->Contains(new_string)); - - Char* write_cursor = reinterpret_cast( - new_string->address() + SeqString::kHeaderSize); - if (comma) *(write_cursor++) = ','; - write_cursor = WriteQuoteJsonString(isolate, - write_cursor, - characters); - int final_length = static_cast( - write_cursor - reinterpret_cast( - new_string->address() + SeqString::kHeaderSize)); - isolate->heap()->new_space()-> - template ShrinkStringAtAllocationBoundary( - new_string, final_length); - return new_string; -} - - RUNTIME_FUNCTION(MaybeObject*, Runtime_QuoteJSONString) { - NoHandleAllocation ha(isolate); - CONVERT_ARG_CHECKED(String, str, 0); - if (!str->IsFlat()) { - MaybeObject* try_flatten = str->TryFlatten(); - Object* flat; - if (!try_flatten->ToObject(&flat)) { - return try_flatten; - } - str = String::cast(flat); - ASSERT(str->IsFlat()); - } - String::FlatContent flat = str->GetFlatContent(); - ASSERT(flat.IsFlat()); - if (flat.IsTwoByte()) { - return QuoteJsonString(isolate, - flat.ToUC16Vector()); - } else { - return QuoteJsonString( - isolate, - flat.ToOneByteVector()); - } -} - - -RUNTIME_FUNCTION(MaybeObject*, Runtime_QuoteJSONStringComma) { - NoHandleAllocation ha(isolate); - CONVERT_ARG_CHECKED(String, str, 0); - if (!str->IsFlat()) { - MaybeObject* try_flatten = str->TryFlatten(); - Object* flat; - if (!try_flatten->ToObject(&flat)) { - return try_flatten; - } - str = String::cast(flat); - ASSERT(str->IsFlat()); - } - String::FlatContent flat = str->GetFlatContent(); - if (flat.IsTwoByte()) { - return QuoteJsonString(isolate, - flat.ToUC16Vector()); - } else { - return QuoteJsonString( - isolate, - flat.ToOneByteVector()); - } -} - - -template -static MaybeObject* QuoteJsonStringArray(Isolate* isolate, - FixedArray* array, - int worst_case_length) { - int length = array->length(); - - MaybeObject* new_alloc = AllocateRawString(isolate, - worst_case_length); - Object* new_object; - if (!new_alloc->ToObject(&new_object)) { - return new_alloc; - } - if (!isolate->heap()->new_space()->Contains(new_object)) { - // Even if our string is small enough to fit in new space we still have to - // handle it being allocated in old space as may happen in the third - // attempt. See CALL_AND_RETRY in heap-inl.h and similar code in - // CEntryStub::GenerateCore. - return isolate->heap()->undefined_value(); - } - AssertNoAllocation no_gc; - StringType* new_string = StringType::cast(new_object); - ASSERT(isolate->heap()->new_space()->Contains(new_string)); - - Char* write_cursor = reinterpret_cast( - new_string->address() + SeqString::kHeaderSize); - *(write_cursor++) = '['; - for (int i = 0; i < length; i++) { - if (i != 0) *(write_cursor++) = ','; - String* str = String::cast(array->get(i)); - String::FlatContent content = str->GetFlatContent(); - ASSERT(content.IsFlat()); - if (content.IsTwoByte()) { - write_cursor = WriteQuoteJsonString(isolate, - write_cursor, - content.ToUC16Vector()); - } else { - write_cursor = - WriteQuoteJsonString(isolate, - write_cursor, - content.ToOneByteVector()); - } - } - *(write_cursor++) = ']'; - - int final_length = static_cast( - write_cursor - reinterpret_cast( - new_string->address() + SeqString::kHeaderSize)); - isolate->heap()->new_space()-> - template ShrinkStringAtAllocationBoundary( - new_string, final_length); - return new_string; -} - - -RUNTIME_FUNCTION(MaybeObject*, Runtime_QuoteJSONStringArray) { - NoHandleAllocation ha(isolate); + HandleScope scope(isolate); + CONVERT_ARG_HANDLE_CHECKED(String, string, 0); ASSERT(args.length() == 1); - CONVERT_ARG_CHECKED(JSArray, array, 0); - - if (!array->HasFastObjectElements()) { - return isolate->heap()->undefined_value(); - } - FixedArray* elements = FixedArray::cast(array->elements()); - int n = elements->length(); - bool ascii = true; - int total_length = 0; - - for (int i = 0; i < n; i++) { - Object* elt = elements->get(i); - if (!elt->IsString()) return isolate->heap()->undefined_value(); - String* element = String::cast(elt); - if (!element->IsFlat()) return isolate->heap()->undefined_value(); - total_length += element->length(); - if (ascii && element->IsTwoByteRepresentation()) { - ascii = false; - } - } - - int worst_case_length = - kSpaceForBrackets + n * kSpaceForQuotesAndComma - + total_length * kJsonQuoteWorstCaseBlowup; - - if (worst_case_length > kMaxGuaranteedNewSpaceString) { - return isolate->heap()->undefined_value(); - } - - if (ascii) { - return QuoteJsonStringArray(isolate, - elements, - worst_case_length); - } else { - return QuoteJsonStringArray(isolate, - elements, - worst_case_length); - } + return BasicJsonStringifier::StringifyString(isolate, string); } diff --git a/src/runtime.h b/src/runtime.h index 2959fed..99ff49a 100644 --- a/src/runtime.h +++ b/src/runtime.h @@ -195,8 +195,6 @@ namespace internal { F(ParseJson, 1, 1) \ F(BasicJSONStringify, 1, 1) \ F(QuoteJSONString, 1, 1) \ - F(QuoteJSONStringComma, 1, 1) \ - F(QuoteJSONStringArray, 1, 1) \ \ /* Strings */ \ F(StringCharCodeAt, 2, 1) \ -- 2.7.4