понедельник, 6 апреля 2015 г.

Кэширование объектов StringBuilder

В текущем проекте народ очень серьезно подходит к вопросам производительности: куча структур, кастомный внешний кэш, и свой собственный object pool для хранения тяжеловесных объектов. Одним из типов объектов, которые хранятся в пуле и используются повторно являются объекты StringBuilder. И я задался вопросом, насколько это полезно.

Начиная с .NET 4.0 реализация StringBuilder-а была существенно переработана. В первых версиях реализация напоминала классический вектор – для хранения создаваемой строки использовалась изменяемый объект System.String (*), размер которой увеличивался вдвое при ее полном заполнении.

(*) Строки являются неизменяемыми лишь с точки зрения внешних кода, но с точки зрения внутреннего (internal) кода pre-.NET4.0 строки были очень даже изменяемыми.

Кэширование StringBuilder-ов с такой реализацией имело смысл. В этом случае приложение могло прийти к устойчивому состоянию своей работы, когда в памяти хранилось лишь небольшое число объектов StringBuilder с большим внутренним буфером (многопоточное обращение к пулу приведет к тому, что число объектов в пуле будет более одного). Это позволит использовать повторно внутренний буфер строки и не плодить объекты в куче больших объектов.

Однако, начиная с .NET 4.0 реализация объекта StringBuilder изменилась. Теперь, вместо вектора, реализация напоминает Rope Strings, когда каждый экземпляр содержит массив символов и указатель на предыдущий объект StringBuilder:

public sealed class StringBuilder
{
   
// Содержимое текущего блока
    internal char[] m_ChunkChars
;
   
// Предыдущий блок
    internal StringBuilder m_ChunkPrevious
;
   
// Количество символов в текущем блоке
    internal int m_ChunkLength
;
   
// Суммарный объем предыдущих блоков
    internal int m_ChunkOffset
;
   
// Мы хотим гарантировать непопадание массива символов в большую кучу
    // (<85К bytes ~ 40К символов).
    // Слишком большой размер блока приведет к меньшему числу аллокаций,
    // но приведет к бесполезному расходу памяти за счет неиспользуемых символов,
    // а также замдлит вставку/замену (поскольку это требует сдвиг всех символов
    // внутри буффера).
    internal const int MaxChunkSize = 8000
;
   
// Много букафф!
}

При этом, для более эффективного роста, каждый новый экземпляр StringBuilder, содержит внутренний буфер удвоенного размера. Увеличение размера будет происходить до тех пор, пока внутренний размер буфера не упрется в лимит (8К). Таким образом, если последовательно добавлять в объект StringBuilder 20К символов, то его внутреннее представление будет примерно таким:

clip_image002

Зная о такой реализации может закрасться сомнение в том, что кэширование объектов StringBuilder вообще является разумным. Ведь в этом случае, все, что мы можем использовать повторно – это объект с внутренним буфером в 8К символов. Однако все несколько сложнее.

Начиная с .NET 4.0 у класса StringBuilder появился метод Clear. Его реализация очень проста: она просто устанавливает свойство размер в 0 (полный исходный код StringBuilder):

// Convenience method for sb.Length=0;
public StringBuilder Clear
()
{
   
this.Length = 0
;
   
return this;
}

Вопрос в другом: что происходит во время исполнения при установки Length в 0? А вот во время исполнения происходит дополнительная магия. Вместо простого обнуления размеров (m_ChunkLength = m_ChunkOffset = 0) и «отвязки» от предыдущего блока (m_ChunkPrevious = null), происходит более сложная работа.

Изменение размера не влияет на емкость объекта, т.е. свойство Capasity после вызова метода Clear должен возвращать то же самое значение. Это значит, что добавление новых элементов не должно приводить к новому выделению памяти, пока текущий размер не превысит емкость.

Обнулять все предыдущие объекты в цепочке довольно сложно, поэтому, чтобы обеспечить это поведение, происходит выделение одного массива символов, способного вместить все текущие данные объекта! Это значит, что если до вызова метод Clear объект StringBuilder представлял собой связный список кусков, размер каждого из которых не превышал 8К символов, то после вызова метода Clear, текущий объект стал содержать огромный массив, способный линейно вместить все старые данные!

clip_image004

Текущая реализация методов Clear и свойства Length, позволяет использовать повторно куски, большие 8К символов. С другой стороны, кэширование и повторное использование объектов StringBuilder меняют картину использования большой кучи объектов. Если без кэширования, мы получим довольно много мелких объектов, каждый из которых не будет превосходить 8К, то после использования кэширования, мы, по сути, вернемся к реализации StringBuilder из .NET 2.0, когда большие объекты будут постепенно расти, попадая постоянно в большую кучу.

Будет ли в этом смысл – сильно зависит от приложения и его поведения во время исполнения. Я пока не могу ответить на вопрос, является ли такое кэширование полезным для текущего приложения. Но я постараюсь ответить на этот вопрос в ближайшее время.

Ссылки

2 комментария:

  1. Каждый новый экземпляр StringBuilder содержит внутренний буфер равный суммарном размеру буферов всех предыдущих StringBuilder-ов в цепочке (но не более чем на 8к символов). То есть корректней будет говорит о том, что каждый новый StringBuilder удваивает суммарный буфер всей цепочки (если он, опять-таки, не уперся в лимит в 8к).

    Цитата:
    // We make the new chunk at least big enough for the current need (minBlockCharCount)
    // But also as big as the current length (thus doubling capacity), up to a maximum

    Исходя из этого второй экземпляр StringBuilder будет иметь внутренний буфер такого же размера как и первый (и все так же помним про <= 8к). То есть внутреннее представление будет приблизительно таким:

    sb1: m_ChunksChar[16]
    m_ChunkPrevious: null

    sb2: m_ChunksChar[16]
    m_ChunkPrevious: sb1

    sb3: m_ChunksChar[32]
    m_ChunkPrevious: sb2

    sb4: m_ChunksChar[64]
    m_ChunkPrevious: sb3


    ....

    sb100: m_ChunksChar[8000]
    m_ChunkPrevious: sb99

    sb: m_ChunksChar[8000]
    m_ChunkPrevious: sb100


    А вообще спасибо за статью, нравится как вы пишите.

    ОтветитьУдалить
    Ответы
    1. там везде вместо m_ChunksChar[xxx] - m_ChunksChar: char[xxx]. Но думаю суть и так ясна

      Удалить