Эффективная конкатенация строк в .NET

Для программистов на платформе .NET одним из первых советов, направленных на повышение производительности их программ, является «Используй StringBuilder для конкатенации строк». Как и «Использование исключений затратно», утверждение о конкатенации часто неправильно понимается и превращается в догму. К счастью, оно не столь деструктивно, как миф о производительности исключений, но встречается заметно чаще.

Было бы неплохо, если бы вы перед прочтением данной статьи прочли мою предыдущую статью о строках в .NET. И, во имя удобочитаемости, дальше я буду обозначать строки в .NET просто строками, а не «string» или «System.String».

Я включил эту статью в список статей, посвящённых .NET Framework в общем, а не в список C#-специфичных статей, так как полагаю, что все языки на платформе .NET под капотом содержат один и тот же механизм конкатенации строк.

Проблема, которую пытаются решить

Проблема конкатенации большого массива строк, при которой результирующая строка очень быстро и сильно растёт, очень реальна, и совет использовать StringBuilder для конкатенации очень правильный. Вот пример:

using System;

public class Test
{
    static void Main()
    {
        DateTime start = DateTime.Now;
        string x = "";
        for (int i=0; i < 100000; i++)
        {
            x += "!";
        }
        DateTime end = DateTime.Now;
        Console.WriteLine ("Time taken: {0}", end-start);
    }
}

На моём относительно быстром ноутбуке выполнение данной программы заняло около 10 секунд. Если удвоить количество итераций, то время выполнения возрастёт до минуты. На .NET 2.0 beta 2 результаты несколько лучше, но не так уж и сильно. Проблема низкой производительности в том, что строки неизменяемы (immutable), и поэтому при применении оператора «+=» строка на следующей итерации не добавляется в конец первой. На самом деле выражение x += "!"; абсолютно эквивалентно выражению x = x+"!";. Здесь конкатенация — это создание полностью новой строки, для которой выделяется нужный объём памяти, в который копируется содержимое существующего значения x, а потом копируется содержимое конкатенируемой строки ("!"). По мере того, как результирующая строка растёт, возрастает и количество данных, которые всё время копируются туда-сюда, и именно поэтому когда я увеличил количество итераций вдвое, время выросло больше, чем в два раза.

Данный алгоритм конкатенации определённо неэффективен. Ведь если кто-то попросит вас добавить что-то в список покупок, вы же не будете перед добавлением копировать весь список, правда? Вот так мы и подходим к StringBuilder.

Используем StringBuilder

А вот эквивалент (эквивалент в смысле идентичного конечного значения x) вышеприведённой программы, который намного-намного быстрее:

using System;
using System.Text;

public class Test
{
    static void Main()
    {
        DateTime start = DateTime.Now;
        StringBuilder builder = new StringBuilder();
        for (int i=0; i < 100000; i++)
        {
            builder.Append("!");
        }
        string x = builder.ToString();
        DateTime end = DateTime.Now;
        Console.WriteLine ("Time taken: {0}", end-start);
    }
}

На моём ноутбуке данный код выполняется настолько быстро, что тот механизм замера времени, который я использую, неэффективен и не даёт удовлетворительных результатов. При увеличении количества итераций до одного миллиона (т.е. в 10 раз больше от изначального количества, при котором первая версия программы выполнялась 10 секунд) время выполнения вырастает до 30-40 миллисекунд. Причём время выполнения растёт приблизительно линейно количеству итераций (т.е. удвоив количество итераций, время выполнения также удвоится). Такой скачек производительности достигается благодаря устранению ненужной операции копирования — копируются только те данные, которые присоединяются к результирующей строке. StringBuilder содержит и обслуживает свой внутренний буфер и при добавлении строки копирует её содержимое в буфер. Когда новые присоединяемые строки не вмещаются в буфер, он копируется со всем своим содержимым, но уже с большим размером. По сути, внутренний буфер StringBuilder — это та же самая обычная строка; строки неизменяемы лишь с точки зрения своих публичных интерфейсов, но изменяемы со стороны сборки mscorlib. Можно было бы сделать данный код ещё более производительным, указав конечный размер (длину) строки (ведь в данном случае мы можем вычислить размер строки ещё до начала конкатенации) в конструкторе StringBuilder, благодаря чему внутренний буфер StringBuilder’а был бы создан с точно подходящим для результирующей строки размером, и в процессе конкатенации ему бы не прошлось увеличиваться через копирование. В данной ситуации вы можете определить длину результирующей строки до конкатенации, но даже если и не можете, то не беда — при заполнении буфера и его копировании StringBuilder удваивает размер новой копии, поэтому заполнений и копирований буфера не будет так уж и много.

Значит, при конкатенации я должен всегда использовать StringBuilder?

Кратко говоря — нет. Всё вышеприведённое разъясняет, почему утверждение «Используй StringBuilder для конкатенации строк» в некоторых ситуациях бывает правильным. Вместе с тем, некоторые люди принимают данное утверждение за догму, не разобравшись в основах, и вследствие этого начинают переделывать такой код:

string name = firstName + " " + lastName;
Person person = new Person (name);

вот в такое:

// Bad code! Do not use!
StringBuilder builder = new StringBuilder();
builder.Append (firstName);
builder.Append (" ");
builder.Append (lastName);
string name = builder.ToString();
Person person = new Person (name);  

И всё это во имя производительности. Если взглянуть на проблему в общем, то даже если вторая версия была бы более быстрой, нежели первая, то, очевидно, она не была бы намного быстрее, ведь конкатенаций всего несколько. Смысл в использовании второй версии может быть только в случае, если данный кусок кода вызывается очень, очень большое количество раз. Ухудшение удобочитаемости кода (а я думаю, вы все согласитесь, что вторая версия намного менее удобочитаемая, нежели первая) ради микроскопической прибавки производительности — это очень плохая идея.

Более того, на самом деле вторая версия, со StringBuilder’ом, менее производительна, нежели первая, хотя и не намного. И если бы вторая версия была более легко воспринимаемой, нежели первая, то вслед за аргументацией из предыдущего абзаца я бы сказал — используйте её; но когда версия со StringBuilder’ом и менее удобочитаемая, и менее производительная, то использовать её — это просто бред.

Если предположить, что firstName и lastName являются «настоящими» переменными, а не константами (об этом будет ниже), то первая версия будет скомпилирована в вызов String.Concat, как-то так:

string name = String.Concat (firstName, " ", lastName);
Person person = new Person (name);

Метод String.Concat принимает на вход набор строк (или объектов) и «склеивает» их в одну новую строку, просто и чётко. String.Concat имеет разные перегрузки — некоторые принимают несколько строк, некоторые — несколько переменных типа Object (которые при конкатенации конвертируются в строки), а некоторые принимают массивы строк или массивы Object. Все перегрузки делают одно и то же. Перед собственно началом процесса конкатенации String.Concat считывает длины всех переданных ему строк (по крайней мере, если вы передали ему строки — если вы передали переменные типа Object, то String.Concat для каждой такой переменной создаст новую временну́ю строку и будет конкатенировать уже её). Благодаря этому на момент конкатенации String.Concat точно «знает» длину результирующей строки, благодаря чему выделяет для неё точно подходящий по размерам буфер, а поэтому нет никаких лишних операций копирования и т.д.

Сравните этот алгоритм со второй StringBuilder-версией. На момент своего создания StringBuilder не знает размер результирующей строки (и мы ему этот размер не «сказали»; а если бы и сказали, то сделали бы код ещё менее понятным), а это значит, что, скорее всего, размер стартового буфера будет превышен, и StringBuilder’у придётся его увеличивать посредством создания нового и копированием содержимого. Более того, как мы помним, StringBuilder увеличивает буфер в два раза, а это значит, что, в конечном счёте, буфер окажется намного большим, нежели того требует результирующая строка. Кроме этого, не следует забывать о накладных расходах, связанных с созданием дополнительного объекта, которого нет в первой версии (этим объектом и есть StringBuilder). Так чем же вторая версия лучше?

Важным различием между примером из этого раздела и примером из начала статьи является то, что в этом мы сразу имеем в наличии все строки, которые надо конкатенировать, и поэтому можем все их передать в String.Concat, который, в свою очередь, выдаст результат максимально эффективно, без всяких промежуточных строк. В раннем же примере мы не имеем доступ ко всем строкам сразу, и поэтому нуждаемся во временно́м хранилище промежуточных результатов, на роль которого наилучше подходит именно StringBuilder. Т.е., обобщая, StringBuilder эффективен как контейнер с промежуточным результатом, так как позволяет избавиться от внутреннего копирования строк; если же все строки доступны сразу и промежуточных результатов нет, то от StringBuilder’а не будет никакой пользы.

Константы

Ситуация накаляется ещё сильнее, когда дело доходит до констант (я говорю о строковых литералах, объявленных как const string). Как вы думаете, во что будет скомпилировано выражение string x = "hello" + " " + "there";? Логично предположить, что будет произведён вызов String.Concat, но это не так. На самом деле данное выражение будет скомпилировано вот в такое: string x = "hello there";. Компилятор знает, что все составные части строки x являются константами времени компиляции, и поэтому все они будут конкатенированы ещё в момент компиляции программы, и в скомпилированном коде будет храниться строка x со значением "hello there". Перевод подобного кода под StringBuilder неэффективен и в аспекте потребляемой памяти, и в аспекте ресурсов CPU, не говоря уже об удобочитаемости.

Эмпирические правила конкатенации

Итак, когда же использовать StringBuilder, а когда «простую» конкатенацию?

• Определённо используйте StringBuilder, когда вы конкатенируете строки в нетривиальном цикле, и особенно, когда вы не знаете (на момент компиляции), сколько именно итераций будет произведено. К примеру, чтение содержимого текстового файла путём считывания по одному символу внутри одной итерации в цикле, и конкатенация этого символа через оператор += предположительно «убьёт» ваше приложение в плане производительности.
• Определённо используйте оператор +=, если вы можете указать все необходимые для конкатенации строки в одном утверждении. Если вам нужно конкатенировать массив строк, используйте явный вызов String.Concat, а если между этими строками нужен разделитель — используйте String.Join.
• Не бойтесь в коде разбивать литералы на несколько частей и связывать их через + — результат будет тот же самый. Если у вас в коде содержится длинная литеральная строка, то, разбив её на несколько подстрок, вы тем самым улучшите удобочитаемость кода.
• Если промежуточные результаты конкатенации нужны вам где-нибудь ещё, кроме собственно быть промежуточными результатами, то StringBuilder вам не поможет. К примеру, если вы создаёте полное имя путём конкатенации имени и фамилии, а потом добавляете третий элемент (к примеру, логин) в конец строки, то StringBuilder будет полезен, только если вам не нужно использовать строку (имя + фамилия) саму по себе, без логина, где-нибудь ещё (как мы это делали в примере, создавая экземпляр Person на основании имени и фамилии).
• Если вам нужно конкатенировать несколько подстрок, и вы не можете их конкатенировать в одном утверждении через String.Concat, то выбор «классической»- или StringBuilder-конкатенации не будет играть особой роли. Здесь скорость будет зависеть от количества участвующих в конкатенации строк, от их длины, а также от порядка, в котором строки будут конкатенироваться. Если вы полагаете, что конкатенация является «бутылочным горлышком» производительности и непременно хотите использовать быстрейший способ, то замерьте производительность обеих способов и только тогда выберите быстрейший из них.

Автор: Klotos

Источник