Разбор документов XML со скоростью света

Глава 4 из книги "Производительность приложений с открытым исходным кодом".

Оригинал: Parsing XML at the Speed of Light
Автор: Arseny Kapoulkine
Перевод: А.Панин

Поддержка функций освобождения памяти в системе резервирования памяти на основе стека

Описанная в предыдущем разделе реализация не предоставляет какой-либо возможности освобождения или повторного использования памяти.

Любопытно, что во многих случаях это обстоятельство не имеет значения. Так как мы можем освободить память в момент закрытия документа путем освобождения всех страниц¹⁹, разбор документа или открытие нового документа не приводит к потреблению дополнительной памяти. Однако, проблема проявляется тогда, кода мы освобождаем значительную часть данных документа, после чего добавляем дополнительные узлы в его представление. Так как мы никогда не использовали память повторно, пиковое потребление памяти будет очень заметным.

Реализация механизма повторного использования малых фрагментов памяти с сохранением высокой производительности механизма резервирования памяти кажется невозможной. Однако, компромисс может быть достигнут. В процессе резервирования фрагментов памяти мы подсчитываем количество зарезервированных фрагментов для каждой рассматриваемой страницы. После этого запросы на освобождение памяти будут сопровождаться получением ссылки на страницу с освобождаемым фрагментом и уменьшением значения этого счетчика. В том случае, если значение счетчика достигает нуля, страница считается более не используемой и может быть освобождена.

Для того, чтобы сделать такой подход возможным, нам необходимо знать о том, на какой странице резервируется память для каждого из объектов. Эту информацию можно сохранять без хранения указателя на страницу, но данный подход достаточно сложен.²⁰ Поэтому библиотека pugixml хранит указатель на страницу для каждого из зарезервированных фрагментов памяти.

В pugixml используются два различных приема для сокращения затрат памяти на хранение указателя на страницу, ассоциированного с каждым из зарезервированных фрагментов памяти.

Первый прием заключается в хранении указателя на страницу в одном поле размера указателя с несколькими битами несвязанных данных, которые должны использоваться в любом случае. Система резервирования гарантирует, что все страницы будут выровнены по границе в 32 байта и это означает, что пять младших битов каждого указателя страницы равны нулю; в таком случае они могут использоваться для хранения произвольных данных. Пять бит являются подходящим объемом данных, так как они вмещают метаданные узла XML: три бита используются для типа узла и два бита используются для указания того, находятся ли имя и данные узла во внутреннем буфере.

(allocator_page*)((char*)(object) -
    object->offset - offsetof(allocator_page, data))

Размер наших страниц ограничен значением 2¹⁶ = 65535 байт и этот сдвиг умещается в 16 бит, поэтому мы можем потратить 2 байта вместо 4 для его хранения. Библиотека pugixml использует этот прием для резервирования данных для строк.

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

Конечно же, в определенных случаях использования библиотеки никакие из данных не удаляются до того момента, когда уничтожается весь документ. Например, в том случае, если размер страницы равен 32000 байт, мы можем зарезервировать один миллион фрагментов памяти по 32 байта, используя в процессе 1000 страниц. Если мы сохраним каждый 1000-й объект и удалим все остальные объекты, на каждой страннице останется ровно по одному объекту и это значит, что несмотря на то, что объем памяти, занимаемый используемыми объектами на данный момент равен 1000 · 32 = 32000 байт, мы все еще храним все использованные страницы в памяти (занимающие 32 миллиона байт). В результате память используется крайне не оптимально. Однако, такие сценарии использования очень маловероятны и преимущества алгоритма в рамках библиотеки pugixml более весомы, нежели данная проблема.

Продолжение статьи: Заключение.