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

http://www.yoda.arachsys.com/csharp/stringbuilder.html
  • Перевод

Для программистов на платформе .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-конкатенации не будет играть особой роли. Здесь скорость будет зависеть от количества участвующих в конкатенации строк, от их длины, а также от порядка, в котором строки будут конкатенироваться. Если вы полагаете, что конкатенация является «бутылочным горлышком» производительности и непременно хотите использовать быстрейший способ, то замерьте производительность обеих способов и только тогда выберите быстрейший из них.
Поделиться публикацией

Похожие публикации

Комментарии 38
    +21
    На .NET 2.0 beta 2 результаты несколько лучше, но не так уж и сильно.

    К теме статьи не относится, но .NET пора обновить)
      +1
      да, статья писалась автором довольно давно, но, полагаю, актуальности ещё не утратила
        –8
        Дочитав до этой строки сразу бросил читать.
        ЗЫ: проблему можно решить по хард-кору через указатели (unsafe code) отключив интернирование чтобы не получить неожиданные результаты :-) (кто воспримет это серьёзно — тот зануда).
          –6
          А ещё нет полезного совета:
          string left = «2+2=»;
          int right=4;
          string exp = left + right;
          в последней строке лучше сделать
          string exp = left + right.ToString();
          чтобы избежать лишней потери производительности на боксинг переменной right
        • НЛО прилетело и опубликовало эту надпись здесь
            0
            Это перевод старющей статьи Скита. Глаза разувайте перед тем как ляпать что-то.
            0
            немного огорчает в StringBuilder отсутствие перегрузок, например sb += «append»;
              +3
              Да, и, кстати, об этом (о недостаточности операторов и методов StringBuilder по сравнению со «стандартными» строками) писал Джеффри Рихтер в CLR via C#; по его мнению, типы String и StringBuilder должны иметь почти одинаковый функционал.
              0
              Если скорость критична, то надо под конкретные цели писать что то свое. Вот отличная статья на эту тематику.
                0
                Часто можно еще делать примерно так:

                int[] someArray = {1,2,3}; string s = string.Concat(someArray.Select(i => i.ToString()));

                Понятно что массив может быть чего-то поинтереснее int-ов, и вместо ToString() что-то посложнее. Также можно использовать string.Join если нужно разделить значения, например, запятыми.

                Удобно для простых сценариев, типа пройтись по коллекции и как-нибудь слепить из элементов строку.

                По производительности не проверял, но по логике должно работать примерно как StringBuilder.
                  0
                  Имхо, это даже быстрее чем если сделать:
                  foreach (var item in someArray) stringBuilder.Append(item.ToString());
                  т.к. string.Concat сразу создаст строку нужной длины через FastAllocateString и FillStringChecked-ами её заполнит.
                    0
                    Там все-таки надо еще массив сделать и переложить все в него. Как на практике будет — сложно сказать, надо мерить. Впрочем, тут уже речь процентах, так что можно смело применять.
                      0
                      Да, но если речь идёт о сферических тестах, то вот такой paste.org.ru/?tllr43 даёт интересные результаты: быстрее всего string.Join, потом String.Concat, a потом уже StringBuilder.
                      String.Join использует хитрый UnSafeCharBuffer.
                      0
                      А если у вас IEnumerable с неизвестным заранее количеством?

                      Достаточно семантично, и крайне быстро (а при желании можно состряпать «сахарное» расширение):

                      var result = someArray.Aggregate(new StringBuilder(), (a,x) => a.Append(x)).ToString();
                        +1
                        А я знаю способ еще лучше. Дать всем в этой ветке комментов сначала премию за нестандартное мышление, а потом по ушам за извращения, ведущие к нечитаемому и несопровождаемому коду.
                        А если окажется что выгода от извращений < 0.1%, то лишить премии.
                        Итого: премии ноль, уши горят.
                          +1
                          ну покажите нам пример генерации md5 hash с результатом в string hex _без извращений_
                            0
                            Тут согласен. Хотя время на любой способ сборки строки по сравнению с вычислением MD5 ничтожно, но если вычислять хеш от хеша в цикле, то становится интересно.
                            Может знаете, раньше было такое кунг-фу при проверке пароля на локальном компьютере, много раз хеш от хеша — специально, чтобы проверка пароля занимала минимум секунду — это делало простой брутфорс перебором нереальным.
                    0
                    Насчет удобочитаемости кода с билдером.
                    string name = new StringBuilder(firstName).Append(" ").Append(lastName).ToString();
                    

                    А насчет того, что стоит ли вообще пытаться оптимизировать такое место, уже столько копий сломано…
                      0
                      Такое — точно не стоит, т.к. перед
                      string name = string.Concat(firstName, " ", lastName);
                      он не имеет никаких преимуществ в затратах.
                        0
                        удалил за ненадобностью
                      0
                      Много раз натыкался на подобные статьи/обсуждения.

                      Лично я не понимаю, как можно использовать язык программирования и не иметь представления об изменяемости/неизменяемости строк и асимптотике операций над ними.
                        0
                        Неплохо, детально, но зачем?
                          0
                          На деле работа со строками очень может даже стать узким местом, особенно при разборе текста — например парсером.

                          Из своего опыта скажу, разительно помогло «не создавать новых строк», т.е. везде где можно использовалась ссылка на оригинальный текст и передавались индексы начала и конца фрагмента.

                          Благо в .NET есть порядочно методов, которые работают именно с подстроками.
                            +3
                            Поведение стринг билдера изменилось с времен .NET 2.0. Теперь вместо внутреннего буфера, он использует связанный список.

                            Вот замеры времени исполнения на моей рабочей машине. Обычный стринг конкат, 100000 итераций. Для более полного сравнения со стринг билдером, я попробовал прогнать 10 миллионов итераций, но через 5 минут мне надоело ждать.
                            using System;
                            using System.Diagnostics;
                            
                            public class Test
                            {
                            	static void Main()
                            	{
                            		Stopwatch stopwatch = new Stopwatch();
                            		stopwatch.Start();
                            		string x = "";
                            		for (int i = 0; i < 100000; i++)
                            		{
                            			x += "!";
                            		}
                            		stopwatch.Stop();
                            		Console.WriteLine("Time taken: {0}", stopwatch.ElapsedMilliseconds);
                            	}
                            }
                            

                            и
                            using System;
                            using System.Diagnostics;
                            using System.Text;
                            
                            public class Test
                            {
                            	static void Main()
                            	{
                            		Stopwatch stopwatch = new Stopwatch();
                            		stopwatch.Start();
                            		StringBuilder x = new StringBuilder();
                            		for (int i = 0; i < 10000000; i++)
                            		{
                            			x.Append("!");
                            		}
                            		stopwatch.Stop();
                            		Console.WriteLine("Time taken: {0}", stopwatch.ElapsedMilliseconds);
                            	}
                            }
                            


                            string.Concat (100 тысяч) — 3578 миллисекунд
                            StringBuilder .NET 2.0 (10 миллионов) — 425 миллисекунд
                            StringBuilder .NET 4.0 (10 миллионов) — 123 миллисекунд

                            Итого конкатенация строк отстает на световые годы от стринг билдера при большом количестве итераций. Стринг билдер из .NET 4.0 в три раза быстрее стринг билдера из .NET 2.0.
                              +1
                              После этих тестов, я обнаружил, что не переключил Debug на Release… Так что вот те же самые тесты скомпилированные в Release.

                              string.Concat (100 тысяч) — 3418 миллисекунд
                              StringBuilder .NET 2.0 (10 миллионов) — 299 миллисекунд
                              StringBuilder .NET 4.0 (10 миллионов) — 99 миллисекунд

                              По сравнению с дебаг версией, экономия порядка ста миллисекунд во всех вариантах.
                                +1
                                Мне кажется у вас ошибка в тесте — вы забыли про строчку «string result = x.ToString();». Ведь именно в ней происходит конкатенация.
                                  0
                                  Да в ней происходит единственная конкатенация, но влияния на общую производительность она практически не оказывает. Для верности, я её добавил и результат подтвердил моё утверждение.

                                  StringBuilder .NET 2.0 (10 миллионов) — 294 миллисекунд
                                  StringBuilder .NET 4.0 (10 миллионов) — 110 миллисекунд
                                  0
                                  .net 4.0, тестим string.Format, string.Concat и конкатенацию плюсом:

                                              for (int i = 0; i < 10000000; i++)
                                              {
                                                  var a = rnd.Next(10000);
                                                  var b = rnd.Next(1000);
                                  
                                                  //string s = string.Format("{0} {1}", a, b); // 9.9 seconds
                                                  //string s = string.Concat(a, " ", b); // 6.5 seconds
                                                  string s = a.ToString() + " " + b.ToString(); // 6.8 seconds
                                                  builder.Append(s);
                                              }
                                  


                                  Тестим конкатенацию билдером:
                                              for (int i = 0; i < 10000000; i++)
                                              {
                                                  var a = rnd.Next(10000);
                                                  var b = rnd.Next(1000);
                                                  
                                                  // 5.9 seconds
                                                  builder.Append(a);
                                                  builder.Append(" ");
                                                  builder.Append(b);
                                              }
                                  

                                  Так что похоже любой метод конкатенации приводит к практически одинаковым результатам. В данном случае, основное время было затрачено на a.ToString() и b.ToString() (явный или неявный).

                                  Короче, используйте то, что вам удобно, и не парьтесь. Только не используйте string.Format() — он в полтора раза медленнее, что и понятно — парсинг строки формата и подстановка параметров занимает время.
                                  +1
                                  Такой скачек производительности достигается благодаря устранению ненужной операции копирования — копируются только те данные, которые присоединяются к результирующей строке.


                                  Сдается мне, что автор не прав. И скачек производительности достигается тем, что память выделяется гораздо реже.
                                    0
                                    Нет, Скит прав. Выделение памяти — это копеечная операция.
                                      0
                                      С каких это пор выделение памяти стало копеечной операцией? По опыту — это самая дорогостоящая операция из всех возможных. Тем более, что вы никогда не знаете сколько точно она займет времени.
                                      Вот копирование — это действительно копеечная операция — как два байта переслать :)
                                        +1
                                        Там используется какой то супербыстрый алгоритм выделения памяти fast memory allocation к тому же оптимизированный под строки небольшого назмера. Посмотрите рефлектором.

                                        В дот нете выделение памяти вообще очень быстрая операция — там не нужно искать куда ее выделить благодаря работе дефрагментатора памяти. И вы точно знаете сколько времени это займет — почти ноль времени. В тоже время копирование остается копированием.

                                        Но создание временных элементов в большом количестве быстро приведет к переполнению управляемой кучи.
                                        А в случае больших строк они еще и попадают в конце концов Large Object Heap — в котором нет дефрагментации памяти при сборке мусора и последняя будет происходить скорее всего непрерывно, так как механизм выделения памяти остается прежним.

                                        Поэтому выигрыш не за счет копирования может даже или выделения памяти — а просто за счет менее активной работой с управляемой кучей.

                                        Но вообще то, если строк там тысячи конкатенируются — это актуально. Задача, которая встречается оооочень редко — к тому же решается обычно вообще избавлением от работы со строками.
                                        Для практических задач обычных конкатенаций строк никакие стринг билдеры не нужны — все это детские шалости и экономия на спичках.
                                          –1
                                          Ну для дотнета это справедливо с тех самых пор, как появился сам дотнет :).
                                      0
                                      В Java конкатенация строк оптимизируется на уровне компилятора. При этом в Java 2.0 компилятор подставляет StringBuffer, а в Java 5.0 компилятор оптимизирует конкатенацию строк с помощью StringBuilder.
                                        +1
                                        И он это делает во всех случаях?
                                          0
                                          Практически всегда, если явно не используются методы ручной оптимизации на основе того или иного варианта String.concat().
                                            0
                                            В C#.NET тоже есть оптимизация компилятором, например строка кода вида
                                            string a = b + c + d;
                                            заменится на string a = string.Concat(b,c,d) который не будет создавать лишних объектов.
                                        0
                                        Чтобы обогнать StringBuilder, нужно как-то сделать так, чтобы каждый символ копировался в среднем меньше 2.5 раз. Например, когда ограничение на длину итоговой строки заранее известна. Одно копирование — из исходных строк в char[], другое — при создании строки из фрагмента массива. Тогда у StringBuilder (с переданной конструктору той же Capacity, чтобы было честно) удается выиграть примерно 20% скорости (при благоприятных условиях, когда строки возникают в том же цикле, где они кладутся в массив). Стоит сделать хотя бы один Resize — и уже проигрыш.
                                        На 10^8 строк средней длиной 5 символов: построение через StringBuilder — 2.6 сек, а через массив — 2.2 сек. (.NET 4.0)
                                        Выиграть можно было бы, если как-нибудь захватить char[], не обнуляя его — так не дадут :(

                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                        Самое читаемое