Вступление
Моя прошлая статья была посвящена особенностям строкового типа данных String в .NET. Эта статья продолжает традицию, однако на этот раз мы рассмотрим класс StringBuilder.
Как известно, строки в .NET являются неизменяемыми (не используя unsafe), а поэтому проводить с ними операцию конкатенации в больших количествах не самая лучшая идея. Это значит, что следующий код имеет весьма серьезные проблемы с нагрузкой на память:
string s = string.Empty;
for (int i = 0; i < 100; i++)
{
s += "T";
}
Что же плохого в этом коде? А то, что на каждой итерации создается строка длиною на единицу больше чем на предыдущем шаге с последующим копированием символов из старой строки. Таким образом, суммарное количество задействованных символов равно:
Данная формула есть не что иное, как сумма арифметической прогрессии:
То есть такой сценарий конкатенации требует памяти пропорционально O(n2), n — длина строки.
Для устранения проблем в подобном коде мы используем класс StringBuilder, зная, что операции с ним не приводят к таким растратам памяти как со String. Фактически StringBuilder представляет собой изменяемую строку.
var strB = new StringBuilder();
for (int i = 0; i < 100; i++)
{
strB.Append("T");
}
string str = strB.ToString();
Такой код хоть и не лишен всех недостатков и тратит некоторую память на ветер, но делает это более сдержанно, по сравнению с предыдущим кодом.
Реализация класса StringBuilder координально изменилась в .NET 4.0 по сравнению с предыдущими версиями, а потому я думаю, будет интересно написать, что же с ним случилось.
StringBuilder в .NET 2.0
Класс StringBuilder в .NET 2.0 имеет следующие поля:
public sealed class StringBuilder : ISerializable
{
internal const int DefaultCapacity = 16;
private const string CapacityField = "Capacity";
private const string MaxCapacityField = "m_MaxCapacity";
private const string StringValueField = "m_StringValue";
private const string ThreadIDField = "m_currentThread";
internal IntPtr m_currentThread;
internal int m_MaxCapacity;
internal volatile string m_StringValue; <-------------------------------------
}
m_currentThread — идентификатор потока, в котором создавался экземпляр объекта;
m_MaxCapacity — максимальная емкость данного экземпляра;
m_StringValue — строка, содержащая символы.
Фактически класс StringBuilder внутри работает со строковым типом данных String. Поскольку строки со стороны mscorlib.dll являются изменяемыми, то StringBuilder-у ничего не стоит изменить строку, находящуюся в m_StringValue.
Первоначальная длина составляет 16 символов, а при нехватке места для добавления новых символов StringBuilder заменяет внутреннюю строку на строку длиною в два раза больше и копирует во вновь созданную все символы из предыдущей + новые. Удвоение длины строки приводит к линейной сложности (O(n)) по памяти, в отличие от квадратичной, которая присуща обычным строкам.
Важным дополнением к увеличению производительности является задание нужной емкости при создании экземпляра класса StringBuilder. Тем самым нам не требуется очередное удвоение размера и копирование данных при нехватке памяти. Однако, это возможно лишь в том случае, если мы заранее знаем размер получаемой строки.
Рассмотрим реализации наиболее часто используемых методов. Для читаемости кода я убрал условия проверки входных параметров.
Метод Append()
public StringBuilder Append(string value)
{
if (value == null)
return this;
string currentString = this.m_StringValue;
IntPtr currentThread = Thread.InternalGetCurrentThread();
if (this.m_currentThread != currentThread)
currentString = string.GetStringForStringBuilder(currentString, currentString.Capacity);
int length = currentString.Length;
int requiredLength = length + value.Length;
if (this.NeedsAllocation(currentString, requiredLength)) //проверка хватает ли места для добавления символов
{
//создаем строку длиною в 2 раза больше и копируем все символы из старой строки
string newString = this.GetNewString(currentString, requiredLength);
newString.AppendInPlace(value, length);
this.ReplaceString(currentThread, newString); //заменяем старую строку новой
}
else
{
currentString.AppendInPlace(value, length);
this.ReplaceString(currentThread, currentString);
}
return this;
}
Данный метод просто проверяет, хватает ли места в текущем экземпляре для добавления новой строки, если да, то просто происходит копирование на месте в незанятую часть строки, иначе удвоение размера и копирование старой и новой строки.
Метод Insert()
public StringBuilder Insert(int index, string value)
{
if (value == null)
return this.Insert(index, value, 0);
else
return this.Insert(index, value, 1);
}
public StringBuilder Insert(int index, string value, int count)
{
IntPtr tid;
string threadSafeString = this.GetThreadSafeString(out tid);
int length = threadSafeString.Length;
if (value != null && value.Length != 0)
{
if (count != 0)
{
int requiredLength;
try
{
requiredLength = checked (length + value.Length * count);//вычисляем длину новой строки
}
catch (OverflowException ex)
{
throw new OutOfMemoryException();
}
if (this.NeedsAllocation(threadSafeString, requiredLength))//проверка хватает ли места для добавления символов
{
//создаем строку длиною в 2 раза больше и копируем все символы из старой строки
string newString = this.GetNewString(threadSafeString, requiredLength);
newString.InsertInPlace(index, value, count, length, requiredLength);//вставляем новые символы
this.ReplaceString(tid, newString);//заменяем старую строку новой
}
else
{
threadSafeString.InsertInPlace(index, value, count, length, requiredLength);
this.ReplaceString(tid, threadSafeString);
}
return this;
}
}
return this;
}
Данный метод аналогично предыдущему проверяет, хватает ли места в текущем экземпляре для вставки новой строки и в зависимости от этого удваивает размер строки или же вставляет на месте в исходную строку без изменения размера.
Метод Remove()
public StringBuilder Remove(int startIndex, int length)
{
IntPtr tid;
string threadSafeString = this.GetThreadSafeString(out tid);
int length1 = threadSafeString.Length;
//удаляем ненужные символы, сдвигая оставшуюся часть строки влево
threadSafeString.RemoveInPlace(startIndex, length, length1);
this.ReplaceString(tid, threadSafeString);//заменяем старую строку новой
return this;
}
Данный метод удаляет ненужные символы, сдвигая оставшуюся часть строки влево. При удалении последнего символа фактически ничего сдвигать не надо, поэтому удаление с конца происходит намного быстрее, чем из любой другой части строки.
Метод ToString()
public override string ToString()
{
string str = this.m_StringValue;
if (this.m_currentThread != Thread.InternalGetCurrentThread() || 2 * str.Length < str.ArrayLength)
return string.InternalCopy(str);//возвращаем копию строки
str.ClearPostNullChar();
this.m_currentThread = IntPtr.Zero;
return str; //возвращаем ссылку на текущую строку
}
Данный метод, как видно из реализации, возвращает либо копию строки, либо строку, которой оперирует. Как правило, первый вызов данного метода возвращает ссылку на исходную строку, поэтому выполняется очень быстро, однако каждый последующий вызов приводит к копированию строки. Класс StringBuilder в .NET 2.0 делает упор именно на быстроту работы этого метода.
В общем, класс StringBuilder в .NET 2.0 реализован достаточно просто. Он использует изменяемую строку, а при нехватке места создает новую строку, длина которой в два раза больше предыдущей. Такой сценарий удвоения длины приводит к линейной сложности по памяти, что на порядок лучше квадратичной. Однако, при больших длинах строк и это не эффективно. Кстати, из-за своего большего размера, строка часто может располагаться в куче для больших объектов(LOH), что так же ни есть хорошо.
StringBuilder в .NET 4.0
Как я уже сказал, в .NET 4.0 реализация класса StringBuilder поменялась. Теперь для хранения символов вместо String используется Char[], а сам класс представляет собой связный список StringBuilder-ов подобно RopeString.
Причина такого изменения достаточно очевидна: при такой реализации не требуется перевыделять память при ее нехватке, что присуще предыдущей реализации. Это так же означает, что метод ToString() работает немного медленнее, поскольку окончательную строку необходимо сначала сформировать, а метод Append() работает быстрее, поскольку не требует копирования. Однако это вписывается в типичный сценарий использования для StringBuilder: много вызовов Append(), а затем один вызов ToString().
Класс StringBuilder в .NET 4.0 имеет следующие поля:
public sealed class StringBuilder : ISerializable
{
internal const int DefaultCapacity = 16;
internal const int MaxChunkSize = 8000;
internal char[] m_ChunkChars; <-------------------------------------
internal StringBuilder m_ChunkPrevious; <-------------------------------------
internal int m_ChunkLength;
internal int m_ChunkOffset;
internal int m_MaxCapacity;
private const string CapacityField = "Capacity";
private const string MaxCapacityField = "m_MaxCapacity";
private const string StringValueField = "m_StringValue";
private const string ThreadIDField = "m_currentThread";
}
m_ChunkChars — массив содержащий символы текущего элемента связного списка (кусочка строки);
m_ChunkPrevious — ссылка на предыдущий элемент (StringBuilder) в списке;
m_ChunkLength — реальная длина текущего элемента списка (количество используемых символов);
m_ChunkOffset — суммарное количество используемых строкой символов (логическая длина);
m_MaxCapacity — максимальная емкость текущего экземпляра StringBuilder.
В .NET Framework 4 и .NET Framework 4.5 при создании экземпляра объекта StringBuilder путем вызова конструктора StringBuilder(Int32, Int32) и длина и емкость экземпляра StringBuilder может увеличиваться за значением его свойства MaxCapacity. Это может произойти в частности, при вызове методов Append и AppendFormat.
Максимальная длина элемента списка MaxChunkSize равна 8000. Как вы понимаете это сделано не просто так. Вот комментарий разработчиков класса:
We want to keep chunk arrays out of large object heap (< 85K bytes ~ 40K chars) to be sure. Making the maximum chunk size big means less allocation code called, but also more waste in unused characters and slower inserts / replaces.
Мы хотим, чтобы массив символов не попадал в кучу для больших объектов. Делая максимальный размер элемента списка (кусочка) большим, значило бы, что нужно меньше аллокации памяти, но больше символов остаются не используемыми и операции insert / replace выполняются медленнее.
Рассмотрим реализации наиболее часто используемых методов.
Метод Append()
public unsafe StringBuilder Append(string value)
{
if (value != null)
{
char[] chArray = this.m_ChunkChars;
int index = this.m_ChunkLength;
int length = value.Length;
int num = index + length;
if (num < chArray.Length)// Если хватает места в текущем экземпляре для вставки новой строки
{
if (length <= 2)
{
if (length > 0)
chArray[index] = value[0];
if (length > 1)
chArray[index + 1] = value[1];
}
else
{
fixed (char* smem = value)
fixed (char* dmem = &chArray[index])
string.wstrcpy(dmem, smem, length);
}
this.m_ChunkLength = num;
}
else
this.AppendHelper(value);
}
return this;
}
private unsafe void AppendHelper(string value)
{
fixed (char* chPtr = value)
this.Append(chPtr, value.Length);
}
internal unsafe StringBuilder Append(char* value, int valueCount)
{
// Оптимизация
int num1 = valueCount + this.m_ChunkLength;
if (num1 <= this.m_ChunkChars.Length)
{
StringBuilder.ThreadSafeCopy(value, this.m_ChunkChars, this.m_ChunkLength, valueCount);
this.m_ChunkLength = num1;
}
else
{
// Копируем первую часть(кусочек)
int count = this.m_ChunkChars.Length - this.m_ChunkLength;
if (count > 0)
{
StringBuilder.ThreadSafeCopy(value, this.m_ChunkChars, this.m_ChunkLength, count);
this.m_ChunkLength = this.m_ChunkChars.Length;
}
// Увеличиваем билдер, добавляя еще один кусочек
int num2 = valueCount - count;
this.ExpandByABlock(num2);
// Копируем вторую часть (кусочек)
StringBuilder.ThreadSafeCopy(value + count, this.m_ChunkChars, 0, num2);
this.m_ChunkLength = num2;
}
return this;
}
Метод Append() работает следующим образом: если в текущем элементе списка хватает символов для вставки новой строки, то происходит копирование в нее, если же нет, то копируется та часть которая помещается, а для того, что не поместилось, создается новый элемент списка (экземпляр StringBuilder-a), у которого длина массива равна длине всей исходной строки либо длине оставшейся строки в зависимости от того что больше. Однако, как было сказано, выше максимальная длина массива составляет 8000.
В общем, формула для вычисления длины нового элемента списка выглядит так:
int length = Math.Max(minBlockCharCount, Math.Min(this.Length, 8000))
где minBlockCharCount — оставшаяся длина строки после копирования ее части которая помещается в текущий экземпляр.
Таким образом, в результате работы такого кода
StringBuilder s = new StringBuilder ();
for (int i = 0; i < 10000; i++) {
s.Append ("T");
}
длины массивов у элементов списка будут равны: 8000, 4092, 2048, 1024, 512, 256, 128, 64, 32, 16, 16.
При таких длинах массивов операция обращения к определенному символу в исходной строке выполняется достаточно быстро практически за O(1), так как элементов списка не так много.
Метод Insert()
public unsafe StringBuilder Insert(int index, string value)
{
if (value != null)
{
fixed (char* chPtr = value)
this.Insert(index, chPtr, value.Length);
}
return this;
}
private unsafe void Insert(int index, char* value, int valueCount)
{
if (valueCount <= 0)
return;
StringBuilder chunk;
int indexInChunk;
//Вставляет символы в строку при необходимости создавая новый элемент списка (StringBuilder)
this.MakeRoom(index, valueCount, out chunk, out indexInChunk, false);
this.ReplaceInPlaceAtChunk(ref chunk, ref indexInChunk, value, valueCount);
}
Метод Insert() работает следующим образом: если в текущем элементе списка(StringBuilder-е) хватает места для вставки, то имеющиеся символы сдвигаются, чтобы дать место новому тексту. Иначе же создается новый элемент списка (StringBuilder), в который копируется часть символов из предыдущего элемента, которые не поместились. Последующие символы не смещаются влево.
Что будет в результате такого кода?
StringBuilder s = new StringBuilder ();
for (int i = 0; i < 10000; i++) {
s.Insert (0, "T");
}
Результат будет отличаться от кода использующего Append(), причем весьма серьезно!
Мы получим очень большой список StringBuilder-ов каждый элемент, которого будет иметь длину 16 символов. В результате чего операция обращения к определенному символу по индексу будет выполняться медленней, чем ожидалось, а именно пропорционально длине списка, то есть O(n).
Метод Remove()
public StringBuilder Remove(int startIndex, int length)
{
if (this.Length == length && startIndex == 0)
{
// Оптимизация. Если мы удаляем всю строку.
this.Length = 0;
return this;
}
else
{
if (length > 0)
{
StringBuilder chunk;
int indexInChunk;
this.Remove(startIndex, length, out chunk, out indexInChunk);
}
return this;
}
}
private void Remove(int startIndex, int count, out StringBuilder chunk, out int indexInChunk)
{
int num = startIndex + count;
//Находим элементы списка(кусочки) в которых находятся начальный и конечный символ для удаления.
chunk = this;
StringBuilder stringBuilder = (StringBuilder) null;
int sourceIndex = 0;
while (true)
{
if (num - chunk.m_ChunkOffset >= 0)
{
if (stringBuilder == null)
{
stringBuilder = chunk;
sourceIndex = num - stringBuilder.m_ChunkOffset;
}
if (startIndex - chunk.m_ChunkOffset >= 0)
break;
}
else
chunk.m_ChunkOffset -= count;
chunk = chunk.m_ChunkPrevious;
}
indexInChunk = startIndex - chunk.m_ChunkOffset;
int destinationIndex = indexInChunk;
int count1 = stringBuilder.m_ChunkLength - sourceIndex;
//Если начальный и конечный кусочки не равны
if (stringBuilder != chunk)
{
destinationIndex = 0;
// Удаляем символы после startIndex до конца начального элемента списка(кусочка)
chunk.m_ChunkLength = indexInChunk;
// Удаляем символы между начальным и конечным кусочком.
stringBuilder.m_ChunkPrevious = chunk;
stringBuilder.m_ChunkOffset = chunk.m_ChunkOffset + chunk.m_ChunkLength;
// Если стартовый индекс для удаления ноль в начальном кусочке то мы можем выкинуть весь элемент списка(кусочек)
if (indexInChunk == 0)
{
stringBuilder.m_ChunkPrevious = chunk.m_ChunkPrevious;
chunk = stringBuilder;
}
}
stringBuilder.m_ChunkLength -= sourceIndex - destinationIndex;
if (destinationIndex == sourceIndex) // Иногда не требуется перемещения
return;
// Удаляем символы в конечном кусочке перемещая оставшиеся символы влево
StringBuilder.ThreadSafeCopy(stringBuilder.m_ChunkChars, sourceIndex, stringBuilder.m_ChunkChars, destinationIndex, count1);
}
Реализация данного метода существенно усложнилась. Однако надо учесть, что предыдущая реализация копировала большое количество символов, смещая их влево. Здесь же необходимо производить смещение только в пределах одного элемента (StringBuilder-а) в списке.
Метод ToString()
public override unsafe string ToString()
{
if (this.Length == 0)
return string.Empty;
string str = string.FastAllocateString(this.Length);
StringBuilder stringBuilder = this;
fixed (char* chPtr = str)
{
do
{
if (stringBuilder.m_ChunkLength > 0)
{
char[] chArray = stringBuilder.m_ChunkChars;
int num = stringBuilder.m_ChunkOffset;
int charCount = stringBuilder.m_ChunkLength;
fixed (char* smem = chArray)
string.wstrcpy(chPtr + num, smem, charCount);
}
stringBuilder = stringBuilder.m_ChunkPrevious;
}
while (stringBuilder != null);
}
return str;
}
Данный метод проходит по всему связному списку StringBuilder-ов и последовательно копирует символы каждого из элементов списка в результирующую строку.
Сравнение производительности
Пожалуй, самая интересная часть — это сравнение производительности между двумя версиями класса.
Тест 1. Сколько требуется памяти для хранения строки заданной длины.
Как видите, при небольшой длине строки новая реализация проигрывает старой. Оно и понятно, ведь для каждого элемента списка(StringBuilder) требуется информация о длине, емкости, смещении от начала строки + для массива символов overhead. Но как только длина строки становится больше 16384, старая реализация начинает проигрывать (из-за удвоения размера строки, она содержит много неиспользуемых символов).
Тест 2. Метод Append()
Пожалуй, это тот самый метод, в котором новая реализация побеждает. Поскольку при нехватке памяти теперь удваивать длину строки и копировать в нее символы не требуется, то данный метод выполняется значительно быстрее, почти в два раза (точнее в 1,8 раз).
Тест 3. Метод Insert()
Будем производить вставку в строку уже заполненную символами, длиною 1000 символов.
1. Вставка в начало строки
2. Вставка в середину строки
3. Вставка в конец строки
Комментарии излишне — новая реализация проигрывает при вставке в любое место.
Тест 4. Метод Remove()
Будем производить удаление 10 символов из строки уже заполненной символами до тех пор, пока не исчерпаем ее.
Новая реализация выигрывает при удалении почти из любого места, так как теперь не требуется смещать символы оставшейся строки влево (точнее требуется, но не так часто и много как раньше).
Тест 5. Метод ToString()
Как было сказано выше, данный метод проигрывает предыдущей реализации. Предыдущая реализация возвращала просто ссылку на строку, которой она оперировала (при первом вызове), а новая вынуждена собирать результирующую строку по кускам, обходя каждый элемент связного списка.
Новая реализация работает заметно медленнее, если строка формировалась с помощью метода Insert(), поскольку список будет состоять из множества элементов(StringBuilder-ов) длиною в 16 символов.
Тест 6. Обращение по определенному индексу
Учитывая, что теперь StringBuilder представляет собой связный список, операция обращения к строке по определенному индексу становится дорогостоящей. Особенно если он формировался с помощью метода Insert.
Тест 7. Обычный сценарий: множество вызовов Append(), а затем вызов ToString()
Как правило, мы работаем с данным классом по определенному сценарию: множественный вызов метода Append(), за которым следует один вызов ToString(). Реализации данного класса поменялась именно в расчете на данный сценарий.
Вывод
Как мы увидели, класс StringBuilder в .NET 2.0 был оптимизирован на быстроту работы метода ToString(), в то время как в .NET 4.0 на быстроту метода Append(). Новая реализация метода Append() работает почти в 2 раза быстрее, в то время как методы Insert() и ToString() работают медленнее. Но поскольку, мы работаем с данным классом по определенному сценарию: вызываем множественно раз метод Append(), за которым последует единственный вызов метода ToString(), то увеличение производительности имеет место.
Учитывая новую реализацию класса, при которой лишь множественный вызов метода Append() приводит к увеличению производительности, класс теперь можно было бы назвать StringAppender *)
Автор: timyrik20
