From 331e6102e615f5454f362b76ebe1fb1cc8e3ce6b Mon Sep 17 00:00:00 2001 From: "sandholm@chromium.org" Date: Thu, 26 May 2011 13:58:48 +0000 Subject: [PATCH] JSON.stringify improvement. Fast case in C++ for string arrays. Review URL: http://codereview.chromium.org/7077004 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@8081 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/json.js | 25 ++++---- src/runtime.cc | 177 +++++++++++++++++++++++++++++++++++++++++++++------------ src/runtime.h | 1 + 3 files changed, 157 insertions(+), 46 deletions(-) diff --git a/src/json.js b/src/json.js index 7a6189c..d06bd8f 100644 --- a/src/json.js +++ b/src/json.js @@ -191,16 +191,21 @@ function BasicSerializeArray(value, stack, builder) { var val = value[0]; if (IS_STRING(val)) { // First entry is a string. Remaining entries are likely to be strings too. - builder.push(%QuoteJSONString(val)); - for (var i = 1; i < len; i++) { - val = value[i]; - if (IS_STRING(val)) { - builder.push(%QuoteJSONStringComma(val)); - } else { - builder.push(","); - var before = builder.length; - BasicJSONSerialize(i, value[i], stack, builder); - if (before == builder.length) builder[before - 1] = ",null"; + var array_string = %QuoteJSONStringArray(value); + if (!IS_UNDEFINED(array_string)) { + builder[builder.length - 1] = array_string; + } else { + builder.push(%QuoteJSONString(val)); + for (var i = 1; i < len; i++) { + val = value[i]; + if (IS_STRING(val)) { + builder.push(%QuoteJSONStringComma(val)); + } else { + builder.push(","); + var before = builder.length; + BasicJSONSerialize(i, value[i], stack, builder); + if (before == builder.length) builder[before - 1] = ",null"; + } } } } else if (IS_NUMBER(val)) { diff --git a/src/runtime.cc b/src/runtime.cc index 56b7a90..8ee4102 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -3534,13 +3534,13 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpExecMultiple) { RUNTIME_FUNCTION(MaybeObject*, Runtime_NumberToRadixString) { NoHandleAllocation ha; ASSERT(args.length() == 2); + CONVERT_SMI_CHECKED(radix, args[1]); + RUNTIME_ASSERT(2 <= radix && radix <= 36); // Fast case where the result is a one character string. - if (args[0]->IsSmi() && args[1]->IsSmi()) { + if (args[0]->IsSmi()) { int value = Smi::cast(args[0])->value(); - int radix = Smi::cast(args[1])->value(); if (value >= 0 && value < radix) { - RUNTIME_ASSERT(radix <= 36); // Character array used for conversion. static const char kCharTable[] = "0123456789abcdefghijklmnopqrstuvwxyz"; return isolate->heap()-> @@ -3559,9 +3559,6 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_NumberToRadixString) { } return isolate->heap()->AllocateStringFromAscii(CStrVector("Infinity")); } - CONVERT_DOUBLE_CHECKED(radix_number, args[1]); - int radix = FastD2I(radix_number); - RUNTIME_ASSERT(2 <= radix && radix <= 36); char* str = DoubleToRadixCString(value, radix); MaybeObject* result = isolate->heap()->AllocateStringFromAscii(CStrVector(str)); @@ -5011,6 +5008,8 @@ 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). @@ -5098,13 +5097,49 @@ static MaybeObject* SlowQuoteJsonString(Isolate* isolate, } +template +static inline SinkChar* WriteQuoteJsonString( + Isolate* isolate, + SinkChar* write_cursor, + Vector characters) { + const SourceChar* read_cursor = characters.start(); + const SourceChar* end = read_cursor + characters.length(); + *(write_cursor++) = '"'; + while (read_cursor < end) { + SourceChar c = *(read_cursor++); + if (sizeof(SourceChar) > 1u && + static_cast(c) >= kQuoteTableLength) { + *(write_cursor++) = 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); - const int kSpaceForQuotes = 2 + (comma ? 1 :0); - int worst_case_length = length * kJsonQuoteWorstCaseBlowup + kSpaceForQuotes; + int worst_case_length = + length * kJsonQuoteWorstCaseBlowup + kSpaceForQuotesAndComma; if (worst_case_length > kMaxGuaranteedNewSpaceString) { return SlowQuoteJsonString(isolate, characters); } @@ -5129,34 +5164,9 @@ static MaybeObject* QuoteJsonString(Isolate* isolate, Char* write_cursor = reinterpret_cast( new_string->address() + SeqAsciiString::kHeaderSize); if (comma) *(write_cursor++) = ','; - *(write_cursor++) = '"'; - - const Char* read_cursor = characters.start(); - const Char* end = read_cursor + length; - while (read_cursor < end) { - Char c = *(read_cursor++); - if (sizeof(Char) > 1u && static_cast(c) >= kQuoteTableLength) { - *(write_cursor++) = 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++) = '"'; - + write_cursor = WriteQuoteJsonString(isolate, + write_cursor, + characters); int final_length = static_cast( write_cursor - reinterpret_cast( new_string->address() + SeqAsciiString::kHeaderSize)); @@ -5210,6 +5220,101 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_QuoteJSONStringComma) { } } + +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)); + + STATIC_ASSERT(SeqTwoByteString::kHeaderSize == SeqAsciiString::kHeaderSize); + Char* write_cursor = reinterpret_cast( + new_string->address() + SeqAsciiString::kHeaderSize); + *(write_cursor++) = '['; + for (int i = 0; i < length; i++) { + if (i != 0) *(write_cursor++) = ','; + String* str = String::cast(array->get(i)); + if (str->IsTwoByteRepresentation()) { + write_cursor = WriteQuoteJsonString(isolate, + write_cursor, + str->ToUC16Vector()); + } else { + write_cursor = WriteQuoteJsonString(isolate, + write_cursor, + str->ToAsciiVector()); + } + } + *(write_cursor++) = ']'; + + int final_length = static_cast( + write_cursor - reinterpret_cast( + new_string->address() + SeqAsciiString::kHeaderSize)); + isolate->heap()->new_space()-> + template ShrinkStringAtAllocationBoundary( + new_string, final_length); + return new_string; +} + + +RUNTIME_FUNCTION(MaybeObject*, Runtime_QuoteJSONStringArray) { + NoHandleAllocation ha; + ASSERT(args.length() == 1); + CONVERT_CHECKED(JSArray, array, args[0]); + + if (!array->HasFastElements()) 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); + } +} + + RUNTIME_FUNCTION(MaybeObject*, Runtime_StringParseInt) { NoHandleAllocation ha; diff --git a/src/runtime.h b/src/runtime.h index d3223d1..0d776b6 100644 --- a/src/runtime.h +++ b/src/runtime.h @@ -114,6 +114,7 @@ namespace internal { F(URIUnescape, 1, 1) \ F(QuoteJSONString, 1, 1) \ F(QuoteJSONStringComma, 1, 1) \ + F(QuoteJSONStringArray, 1, 1) \ \ F(NumberToString, 1, 1) \ F(NumberToStringSkipCache, 1, 1) \ -- 2.7.4