Рейтинг@Mail.ru

Наши друзья и партнеры

UnixForum
купить дешевый 
компьютер родом из Dhgate.com




Библиотека сайта rus-linux.net

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

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

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

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

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

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

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

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

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

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

Второй прием заключается в хранении сдвига зарезервированного для хранения элемента блока памяти по отношению к началу страницы, что позволяет нам получать адрес указателя страницы следующим образом:
(allocator_page*)((char*)(object) -
    object->offset - offsetof(allocator_page, data))

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

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

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


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

Поделиться: