Перейти к содержимому

C#. Особенности работы StringBuilder

Исходный код:

https://referencesource.microsoft.com/#mscorlib/system/text/stringbuilder.cs,78bad93b62e6340d

Что это, зачем нужно

Что есть строка в C#? Напомню основы. Есть Value, то есть значимые типы данных. И есть Reference, то есть ссылочные типы данных.

Мы привыкли, что «базовые» типы, вроде int, bool, long и подобные — это значимые типы, которые хранятся в стеке (в стандартном сценарии).

Давайте проведем маленький эксперимент.

Вначале посмотрим на то — как себя ведёт int.

Посмотрим как себя будет вести класс

Теперь посмотрим на аналогичную картину со string

Это ref тип, однако у его поведения есть признаки value-type, что может запутать неопытного разработчика.

Также любые методы, вроде Insert, либо Replace не меняют состояния класса String. Всё правильно — это класс, а не структура. Такие методы, как и операция + пораждают новый экземпляр класса.

Давайте посмотрим на код string.Insert, опустив проверки и оставив только логику:

Создается новая строка с нужным размером, а затем происходит немного магии по переносу данных.. Но возвращается именно новая строка! А значит, что когда мы в цикле собираем данные в одну строку — мы при каждой итерации порождаем новый экземпляр класса string, который будет висеть в куче и создавать лишнюю работу для Garbage Collector‘а.

И вот мы приходим к тому, что для решения проблемы собирания мусора в памяти нужен инструмент. И разработчики C# его дали — это StringBuilder.

Конструкторы StringBuilder

Их тут аж 6. Но они, в основном, обертки друг над другом.

Первый — без параметров

Что такое DefaultCapacity? Это числовая константа со значением 16.

Второй — с параметром capacity на вход

Третий — с параметрами (String value, int capacity)

Четвертый — со строкой на вход

Пятый — с целыми 4 параметрами на вход:

Рассмотрим логику — вначале куча проверок и подмена value на string.Empty (если он был null).

Внутри ThreadSafeCopy происходит заполнение массива символов (m_ChunkChars) через string.wstrcpy (об этом как-нибудь в другой раз).

Шестой, последний конструктор, устанавливает capacity и maxCapacity

Состояние класса и константы

Вначале — константы

Стандартный размер — 16 и максимальный размер чанка — 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 (since you do need to slide characters over within a buffer).

Что в переводе:

Мы хотим держать массивы чанков вне LOH (Large Object Heap, об этом в другой статье). Если массив попадёт в LOH, меньше раз будет вызван код на выделение памяти, но вызовы insert’ов и replace’ов будут выполняться медленнее

m_ChunkCharsМассив с символами в текущем блоке/чанке.
m_ChunkPreviousСсылка на предыдущий блок/чанк
m_ChunkLengthИндекс окончания блока m_ChunkChars, сколько элементов хранится в этом блоке/чанке
m_ChunkOffsetЛогический оффсет (сколько символов во всех предыдущих блоках/чанках хранится)
m_MaxCapacityМаксимальная вместимость

Как работает заполнение StringBuilder

По факту тут очень много магии unsafe работы с буферами и строками. Фактически, для понимания, нужно знать следующее — у главного StringBuilder (тот, который мы создаем сами в коде) при его инициализации в последней версии .NET 8 имеет размер равный 16

После того, как мы положим в него 256 символов — мы увидим такую картину:

А именно — у родительского (главного) StringBuilder паровозиком прицеплены ещё 4. И тот объект, который мы видели на первом скриншоте (с m_ChunkCapacity = 16 и m_ChunkOffset = 0) — стал последним (в самой глубине списка).

Если идти от самого последнего к первому и смотреть на их m_ChunkCapacity — мы увидим, что имеет место геометрическая прогрессия: 16, 32, 64, 128, 256. А если на размерности массивов m_ChunkChars, то увидим аналогичную прогрессию: 16, 16, 32, 64, 128. Похожую логику мы разбирали уже в C# Особенности работы List.

То есть, если мы не задаём никакой размерности, то по умолчанию — это 16. Когда добавляется 17 символ — появляется новое звено в цепи, но пока тоже на 16 элементов. А вот когда это звено заполнится — пойдет прогрессия и каждое последующее звено будет в 2 раза больше предыдущего. Но не более 8000. Почему? Потому что тут, как и в случае с C# Особенности работы List — разработчики не хотят, чтобы блок попал в LOH (Large Object Heap), работа с которым идёт медленнее.

Давайте проведем эксперимент. Судя по интернету — в романе «Война и Мир» почти 3 миллиона символов. А мы возьмем число ещё больше — половина от int.MaxValue. Попробуем поэксперементировать с этим.

У последнего блока размерность массива равна 8000.

А если, вместо добавления символа в цикле использовать перегрузку метода Append, где есть возможность итерационного добавления?

Обновим код метода:

Вывод остался таким же, но есть интересный нюанс — блоков стало много меньше.. Есть два по 16 символов, один на 32, один на 64.. И один на всё оставшееся. Вот такая подстава.

Если попытаться добавить что-нибудь в этот StringBuilder ещё, то он сразу добавить новый блок на 8000 элементов.

Как работает ToString

Вот тут, как раз, всё достаточно просто.

Генерируется строка нужного размера, а затем в неё переносятся все необходимые данные из массива из родительского (основного) StringBuilder по заданному отступу.

Затем по цепочке достаются остальные StringBuilder‘ы и из них уже переносятся данные в строку.

Итого

Конкатенация строк приводит к забиванию мусором кучи, поэтому для решения этой проблемы стоит использовать StringBuilder. Стоит указывать ожидаемый размер строки при инициализации StringBuilder, но не стоит указывать более 8000, иначе первый же созданный блок будет именно заданного вами размера, и он попадёт в Large Object Heap (LOH).

То есть если не указываем ничего (тогда размер будет 16), при ожидаемом размере строки в 100 символов будет создана цепь из 4 блоков. Если укажем более 8000 — попадём в Large Object Heap. Если укажем 8000, но символов будет ожидаемо меньше, то мы выделим 8кб памяти впустую. То есть лучше стараться анализировать и предугадывать потенциальный размер строки.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *