String & StringBuilder
1,00
р.
В таких языках как Java и C# для конкатенации большого числа строк принято использовать StringBuilder, чтобы получить линейную асимптотику вместо квадратичной.
Однако, JavaScript каким-то образом справляется имея лишь один тип String. Асимптотика конкатенации там линейная, по крайней мере при циклах до 131072 итераций. Но, что странно, время не зависит от длины складываемых строк. По крайней мере, так происходит в Хроме.
Как так вышло?
И бонусный вопрос знатокам JS: а что собственно случилось при 262144?
http://ideone.com/gtm5iy
using System using System.Collections.Generic using System.Diagnostics
public class Program { private static string Test(int n, string s) { var res = ""
for (var q=0 q return res }
public static void Main() { var res = new Dictionary[10] const int N = 1024 var sw = new Stopwatch()
for (var n=0 n()
foreach (var s in new string[] {"!", "!2", "!234", "!2345678"}) { res[n][s] = 0
for (var q=0 q res[n][s] /= N } }
for (var n=0 n foreach (var kvp in res[n]) Console.Write("{0,10:0.000} ", kvp.Value / 1000)
Console.WriteLine() } } }
0 1 0.001 0.000 0.000 0.000 1 2 0.002 0.001 0.001 0.001 2 4 0.003 0.003 0.005 0.003 3 8 0.006 0.006 0.007 0.007 4 16 0.013 0.015 0.013 0.014 5 32 0.025 0.025 0.032 0.034 6 64 0.050 0.059 0.070 0.097 7 128 0.120 0.142 0.220 0.303 8 256 0.337 0.417 0.630 0.972 9 512 0.897 1.256 1.964 4.087
К сожалению, при увеличении числа итераций программа не укладывается в 5 секунд, отведённые на выполнение на ideone. Вот результаты с домашнего компа:
D:\Temp\Supertemp>C:\Windows\Microsoft.NET\Framework64\v4.0.30319\csc.exe StringConcat.cs && StringConcat.exe Microsoft (R) Visual C# Compiler version 4.7.2046.0 for C# 5 Copyright (C) Microsoft Corporation. All rights reserved.
This compiler is provided as part of the Microsoft (R) .NET Framework, but only supports language versions up to C# 5, which is no longer the latest version. For compilers that support newer versions of the C# programming language, see http://go.microsoft.com/fwlink/?LinkID=533240
0 1 0.000 0.000 0.000 0.000 1 2 0.000 0.000 0.000 0.000 2 4 0.000 0.000 0.000 0.000 3 8 0.001 0.001 0.001 0.001 4 16 0.002 0.001 0.001 0.002 5 32 0.002 0.004 0.004 0.004 6 64 0.005 0.006 0.009 0.014 7 128 0.013 0.019 0.028 0.043 8 256 0.042 0.057 0.087 0.148 9 512 0.118 0.174 0.302 0.559 10 1024 0.354 0.606 1.124 2.279 11 2048 1.220 2.242 4.545 10.041 12 4096 4.517 8.982 19.706 41.568 13 8192 17.864 39.063 82.814 169.274 14 16384 78.454 165.893 337.830 718.843
function test(n, s) { var res = '' for (var q=0 q
Ответ
Почему так происходит?
Судя по сорцам V8, строки оптимизированы для конкатенации. При конкатенации вместо создания новой строки создаётся экземпляр, который ссылается на конкатенируемые куски. Каждый кусок тоже может ссылаться на подкуски. Таким образом строится бинарное дерево.
// The ConsString class describes string values built by using the // addition operator on strings. A ConsString is a pair where the // first and second components are pointers to other string values. // One or both components of a ConsString can be pointers to other // ConsStrings, creating a binary tree of ConsStrings where the leaves // are non-ConsString string values. The string value represented by // a ConsString can be obtained by concatenating the leaf string // values in a left-to-right depth-first traversal of the tree. class ConsString : public String { public: // First string of the cons cell. inline String* first() inline void set_first(String* first, WriteBarrierMode mode = UPDATE_WRITE_BARRIER) // Second string of the cons cell. inline String* second() inline void set_second(String* second, WriteBarrierMode mode = UPDATE_WRITE_BARRIER) // Minimum length for a cons string. static const int kMinLength = 13 // ... }
Также есть подклассы строк для подстрок, явно разделяются однобайтовые и двубайтовые строки, и так далее.
// The Sliced String class describes strings that are substrings of another // sequential string. The motivation is to save time and memory when creating // a substring. A Sliced String is described as a pointer to the parent, // the offset from the start of the parent string and the length. Using // a Sliced String therefore requires unpacking of the parent string and // adding the offset to the start address. A substring of a Sliced String // are not nested since the double indirection is simplified when creating // such a substring. // Currently missing features are: // - handling externalized parent strings // - external strings as parent // - truncating sliced string to enable otherwise unneeded parent to be GC'ed. class SlicedString : public String { public: inline String* parent() inline void set_parent(String* parent, WriteBarrierMode mode = UPDATE_WRITE_BARRIER) inline int offset() const inline void set_offset(int offset) // Minimum length for a sliced string. static const int kMinLength = 13 // ... }
В результате такая простая операция как конкатенация превращается в подобное:
MaybeHandle Factory::NewConsString(Handle left, Handle right) { if (left->IsThinString()) { left = handle(Handle::cast(left)->actual(), isolate()) } if (right->IsThinString()) { right = handle(Handle::cast(right)->actual(), isolate()) } int left_length = left->length() if (left_length == 0) return right int right_length = right->length() if (right_length == 0) return left
int length = left_length + right_length
if (length == 2) { uint16_t c1 = left->Get(0) uint16_t c2 = right->Get(0) return MakeOrFindTwoCharacterString(isolate(), c1, c2) }
// Make sure that an out of memory exception is thrown if the length // of the new cons string is too large. if (length > String::kMaxLength || length < 0) { THROW_NEW_ERROR(isolate(), NewInvalidStringLengthError(), String) }
bool left_is_one_byte = left->IsOneByteRepresentation() bool right_is_one_byte = right->IsOneByteRepresentation() bool is_one_byte = left_is_one_byte && right_is_one_byte bool is_one_byte_data_in_two_byte_string = false if (!is_one_byte) { // At least one of the strings uses two-byte representation so we // can't use the fast case code for short one-byte strings below, but // we can try to save memory if all chars actually fit in one-byte. is_one_byte_data_in_two_byte_string = left->HasOnlyOneByteChars() && right->HasOnlyOneByteChars() if (is_one_byte_data_in_two_byte_string) { isolate()->counters()->string_add_runtime_ext_to_one_byte()->Increment() } }
// If the resulting string is small make a flat string. if (length < ConsString::kMinLength) { // Note that neither of the two inputs can be a slice because: STATIC_ASSERT(ConsString::kMinLength <= SlicedString::kMinLength) DCHECK(left->IsFlat()) DCHECK(right->IsFlat())
STATIC_ASSERT(ConsString::kMinLength <= String::kMaxLength) if (is_one_byte) { Handle<SeqOneByteString> result = NewRawOneByteString(length).ToHandleChecked() DisallowHeapAllocation no_gc uint8_t* dest = result->GetChars() // Copy left part. const uint8_t* src = left->IsExternalString() ? Handle::cast(left)->GetChars() : Handle::cast(left)->GetChars() for (int i = 0 i < left_length i++) *dest++ = src[i] // Copy right part. src = right->IsExternalString() ? Handle::cast(right)->GetChars() : Handle::cast(right)->GetChars() for (int i = 0 i < right_length i++) *dest++ = src[i] return result }
return (is_one_byte_data_in_two_byte_string) ? ConcatStringContent( NewRawOneByteString(length).ToHandleChecked(), left, right) : ConcatStringContent( NewRawTwoByteString(length).ToHandleChecked(), left, right) }
bool one_byte = (is_one_byte || is_one_byte_data_in_two_byte_string) return NewConsString(left, right, length, one_byte) }
Всякие подобные премудрости — всегда компромисс, обложенный эвристиками. Движок JavaScript пытается угадать, когда выгоднее использовать какой способ: когда создавать полноценную строку, когда строить бинарное дерево строк когда важнее скорость конкатенации, когда важнее скорость итерации и так далее.
Очевиден плюс: потенциально очень медленные операции становятся более быстрыми. Особенно важно это для случаев, когда некоторые паттерны использования классов часто используются программистами, например, конкатенация строк. Но очевиден и минус: другие операции становятся медленнее, кроме того движок не всегда угадывает намерения программиста и выбирает самый оптимальный способ.
Почему так сделано в JavaScript?
Потому что язык сделан намеренно простым для понимания и использования. Чем больше магии, чем меньше нужно думать о внутреннем представлении, тем проще писать программы.
Кроме того, когда язык создавался, скорость выполнения вовсе не имела значения, потому что сложных программ на языке никто не писал. Сложные программы появились намного позже. Если вы запустите эту программу не в Chrome последней версии, а в любом браузере 20-летней давности, вы обнаружите совсем другую производительность.
Почему так не сделано в других языках?
Это зависит от языка и его предназначения. Например, строки в C++ простые и топорные, от программиста требуется указывать каждое движение, появляется разница в производительности между объявлением строки в теле цикла или вне, между передачей строки в функцию по ссылке и по значению, от программиста ожидается указание заранее ожидаемой длины строки и так далее.
С другой стороны, в PHP массивы находятся в роли строк в JS и дадут фору по сложности. Массивы могут быть векторами, словарями, множествами и так далее. Они обладают сложной структурой, которая оптимизирована под каждый случай.
В целом, подход к стандартным классам меняется от языка к языку и даже между версиями одного компилятора языка. Сегодня в JavaScript и PHP появляются типизированные массивы, завтра может появиться StringBuilder.
Однако, JavaScript каким-то образом справляется имея лишь один тип String. Асимптотика конкатенации там линейная, по крайней мере при циклах до 131072 итераций. Но, что странно, время не зависит от длины складываемых строк. По крайней мере, так происходит в Хроме.
Как так вышло?
И бонусный вопрос знатокам JS: а что собственно случилось при 262144?
http://ideone.com/gtm5iy
using System using System.Collections.Generic using System.Diagnostics
public class Program { private static string Test(int n, string s) { var res = ""
for (var q=0 q return res }
public static void Main() { var res = new Dictionary[10] const int N = 1024 var sw = new Stopwatch()
for (var n=0 n()
foreach (var s in new string[] {"!", "!2", "!234", "!2345678"}) { res[n][s] = 0
for (var q=0 q res[n][s] /= N } }
for (var n=0 n foreach (var kvp in res[n]) Console.Write("{0,10:0.000} ", kvp.Value / 1000)
Console.WriteLine() } } }
0 1 0.001 0.000 0.000 0.000 1 2 0.002 0.001 0.001 0.001 2 4 0.003 0.003 0.005 0.003 3 8 0.006 0.006 0.007 0.007 4 16 0.013 0.015 0.013 0.014 5 32 0.025 0.025 0.032 0.034 6 64 0.050 0.059 0.070 0.097 7 128 0.120 0.142 0.220 0.303 8 256 0.337 0.417 0.630 0.972 9 512 0.897 1.256 1.964 4.087
К сожалению, при увеличении числа итераций программа не укладывается в 5 секунд, отведённые на выполнение на ideone. Вот результаты с домашнего компа:
D:\Temp\Supertemp>C:\Windows\Microsoft.NET\Framework64\v4.0.30319\csc.exe StringConcat.cs && StringConcat.exe Microsoft (R) Visual C# Compiler version 4.7.2046.0 for C# 5 Copyright (C) Microsoft Corporation. All rights reserved.
This compiler is provided as part of the Microsoft (R) .NET Framework, but only supports language versions up to C# 5, which is no longer the latest version. For compilers that support newer versions of the C# programming language, see http://go.microsoft.com/fwlink/?LinkID=533240
0 1 0.000 0.000 0.000 0.000 1 2 0.000 0.000 0.000 0.000 2 4 0.000 0.000 0.000 0.000 3 8 0.001 0.001 0.001 0.001 4 16 0.002 0.001 0.001 0.002 5 32 0.002 0.004 0.004 0.004 6 64 0.005 0.006 0.009 0.014 7 128 0.013 0.019 0.028 0.043 8 256 0.042 0.057 0.087 0.148 9 512 0.118 0.174 0.302 0.559 10 1024 0.354 0.606 1.124 2.279 11 2048 1.220 2.242 4.545 10.041 12 4096 4.517 8.982 19.706 41.568 13 8192 17.864 39.063 82.814 169.274 14 16384 78.454 165.893 337.830 718.843
function test(n, s) { var res = '' for (var q=0 q
Ответ
Почему так происходит?
Судя по сорцам V8, строки оптимизированы для конкатенации. При конкатенации вместо создания новой строки создаётся экземпляр, который ссылается на конкатенируемые куски. Каждый кусок тоже может ссылаться на подкуски. Таким образом строится бинарное дерево.
// The ConsString class describes string values built by using the // addition operator on strings. A ConsString is a pair where the // first and second components are pointers to other string values. // One or both components of a ConsString can be pointers to other // ConsStrings, creating a binary tree of ConsStrings where the leaves // are non-ConsString string values. The string value represented by // a ConsString can be obtained by concatenating the leaf string // values in a left-to-right depth-first traversal of the tree. class ConsString : public String { public: // First string of the cons cell. inline String* first() inline void set_first(String* first, WriteBarrierMode mode = UPDATE_WRITE_BARRIER) // Second string of the cons cell. inline String* second() inline void set_second(String* second, WriteBarrierMode mode = UPDATE_WRITE_BARRIER) // Minimum length for a cons string. static const int kMinLength = 13 // ... }
Также есть подклассы строк для подстрок, явно разделяются однобайтовые и двубайтовые строки, и так далее.
// The Sliced String class describes strings that are substrings of another // sequential string. The motivation is to save time and memory when creating // a substring. A Sliced String is described as a pointer to the parent, // the offset from the start of the parent string and the length. Using // a Sliced String therefore requires unpacking of the parent string and // adding the offset to the start address. A substring of a Sliced String // are not nested since the double indirection is simplified when creating // such a substring. // Currently missing features are: // - handling externalized parent strings // - external strings as parent // - truncating sliced string to enable otherwise unneeded parent to be GC'ed. class SlicedString : public String { public: inline String* parent() inline void set_parent(String* parent, WriteBarrierMode mode = UPDATE_WRITE_BARRIER) inline int offset() const inline void set_offset(int offset) // Minimum length for a sliced string. static const int kMinLength = 13 // ... }
В результате такая простая операция как конкатенация превращается в подобное:
MaybeHandle Factory::NewConsString(Handle left, Handle right) { if (left->IsThinString()) { left = handle(Handle::cast(left)->actual(), isolate()) } if (right->IsThinString()) { right = handle(Handle::cast(right)->actual(), isolate()) } int left_length = left->length() if (left_length == 0) return right int right_length = right->length() if (right_length == 0) return left
int length = left_length + right_length
if (length == 2) { uint16_t c1 = left->Get(0) uint16_t c2 = right->Get(0) return MakeOrFindTwoCharacterString(isolate(), c1, c2) }
// Make sure that an out of memory exception is thrown if the length // of the new cons string is too large. if (length > String::kMaxLength || length < 0) { THROW_NEW_ERROR(isolate(), NewInvalidStringLengthError(), String) }
bool left_is_one_byte = left->IsOneByteRepresentation() bool right_is_one_byte = right->IsOneByteRepresentation() bool is_one_byte = left_is_one_byte && right_is_one_byte bool is_one_byte_data_in_two_byte_string = false if (!is_one_byte) { // At least one of the strings uses two-byte representation so we // can't use the fast case code for short one-byte strings below, but // we can try to save memory if all chars actually fit in one-byte. is_one_byte_data_in_two_byte_string = left->HasOnlyOneByteChars() && right->HasOnlyOneByteChars() if (is_one_byte_data_in_two_byte_string) { isolate()->counters()->string_add_runtime_ext_to_one_byte()->Increment() } }
// If the resulting string is small make a flat string. if (length < ConsString::kMinLength) { // Note that neither of the two inputs can be a slice because: STATIC_ASSERT(ConsString::kMinLength <= SlicedString::kMinLength) DCHECK(left->IsFlat()) DCHECK(right->IsFlat())
STATIC_ASSERT(ConsString::kMinLength <= String::kMaxLength) if (is_one_byte) { Handle<SeqOneByteString> result = NewRawOneByteString(length).ToHandleChecked() DisallowHeapAllocation no_gc uint8_t* dest = result->GetChars() // Copy left part. const uint8_t* src = left->IsExternalString() ? Handle::cast(left)->GetChars() : Handle::cast(left)->GetChars() for (int i = 0 i < left_length i++) *dest++ = src[i] // Copy right part. src = right->IsExternalString() ? Handle::cast(right)->GetChars() : Handle::cast(right)->GetChars() for (int i = 0 i < right_length i++) *dest++ = src[i] return result }
return (is_one_byte_data_in_two_byte_string) ? ConcatStringContent( NewRawOneByteString(length).ToHandleChecked(), left, right) : ConcatStringContent( NewRawTwoByteString(length).ToHandleChecked(), left, right) }
bool one_byte = (is_one_byte || is_one_byte_data_in_two_byte_string) return NewConsString(left, right, length, one_byte) }
Всякие подобные премудрости — всегда компромисс, обложенный эвристиками. Движок JavaScript пытается угадать, когда выгоднее использовать какой способ: когда создавать полноценную строку, когда строить бинарное дерево строк когда важнее скорость конкатенации, когда важнее скорость итерации и так далее.
Очевиден плюс: потенциально очень медленные операции становятся более быстрыми. Особенно важно это для случаев, когда некоторые паттерны использования классов часто используются программистами, например, конкатенация строк. Но очевиден и минус: другие операции становятся медленнее, кроме того движок не всегда угадывает намерения программиста и выбирает самый оптимальный способ.
Почему так сделано в JavaScript?
Потому что язык сделан намеренно простым для понимания и использования. Чем больше магии, чем меньше нужно думать о внутреннем представлении, тем проще писать программы.
Кроме того, когда язык создавался, скорость выполнения вовсе не имела значения, потому что сложных программ на языке никто не писал. Сложные программы появились намного позже. Если вы запустите эту программу не в Chrome последней версии, а в любом браузере 20-летней давности, вы обнаружите совсем другую производительность.
Почему так не сделано в других языках?
Это зависит от языка и его предназначения. Например, строки в C++ простые и топорные, от программиста требуется указывать каждое движение, появляется разница в производительности между объявлением строки в теле цикла или вне, между передачей строки в функцию по ссылке и по значению, от программиста ожидается указание заранее ожидаемой длины строки и так далее.
С другой стороны, в PHP массивы находятся в роли строк в JS и дадут фору по сложности. Массивы могут быть векторами, словарями, множествами и так далее. Они обладают сложной структурой, которая оптимизирована под каждый случай.
В целом, подход к стандартным классам меняется от языка к языку и даже между версиями одного компилятора языка. Сегодня в JavaScript и PHP появляются типизированные массивы, завтра может появиться StringBuilder.
