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

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

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

Метод резервирования памяти на основе стека

Быстрая система резервирования памяти является критичным элементом производительной системы разбора на основе DOM. Непосредственный разбор устраняет необходимость резервирования памяти для строковых данных, но узлы DOM все еще должны сохраняться в зарезервированных для них блоках памяти. Зарезервированные для хранения строк различных размеров блоки памяти также необходимы для поддержки функций изменения древовидной структуры представления документа. Компактное расположение резервируемых блоков памяти важно для поддержания высокой производительности функций обхода дерева: в случае, когда в результате успешных запросов резервирования памяти возвращаются смежные блоки памяти, становится просто гарантировать компактное размещение древовидной структуры в памяти при ее построении. Наконец, скорость освобождения памяти также важна: в дополнение к освобождению блоков памяти в течение фиксированных временных интервалов времени, возможность быстрого освобождения всей памяти, зарезервированной для текущего документа, без освобождения блоков памяти каждого узла по отдельности может значительно сократить время, необходимое для освобождения зарезервированных для документов большого размера ресурсов.

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

Так как узлы DOM могут сохраняться в зарезервированных блоках памяти нескольких необходимых фиксированных размеров, должно представляться возможным использование стандартного пула памяти, основанного на списках свободных фрагментов для каждого размера. В таком пуле должен использоваться отдельный связанный список свободных блоков, в котором все блоки имеют одинаковый размер. При выполнении запроса резервирования памяти в случае, когда список свободных блоков пуст, резервируется новая страница памяти с массивом блоков. Блоки объединяются друг с другом в форме отдельного связанного списка, который впоследствии становится списком свободных блоков для системы резервирования памяти. В том случае, если список свободных блоков не пуст, первый блок удаляется из списка и возвращается пользователю. Запрос освобождения блока просто добавляет блок в начало списка свободных блоков.

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

Так как библиотека pugixml поддерживает возможность изменения древовидной структуры представления документа, требуется поддержка функций резервирования блоков памяти произвольных размеров. Было непонятно, должна ли эта система резервирования памяти просто расширяться для поддержки резервирования фрагментов произвольных размеров и других требуемых библиотекой pugixml возможностей без снижения производительности механизма разбора документов. Добавление сложной схемы резервирования памяти общего назначения, аналогичной алгоритмам, реализованным в рамках системы dlmalloc и других систем резервирования памяти общего назначения, также не было приемлемо - такие системы резервирования чаще всего работают медленнее, чем простые системы на основе списков свободных блоков, не говоря уже о том, что они сложнее в реализации. Для библиотеки pugixml нужно было что-то более простое и быстрое.

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

const size_t allocator_page_size = 32768;
struct allocator_page {
  allocator_page* next_page;
  size_t offset;
  char data[allocator_page_size];
};
struct allocator_state {
  allocator_page* current;
};

void* allocate_new_page_data(size_t size) {
  size_t extra_size = (size > allocator_page_size) ?
    size - allocator_page_size : 0;
  return malloc(sizeof(allocator_page) + extra_size);
}

void* allocate_oob(allocator_state* state, size_t size) {
  allocator_page* page = (allocator_page*)allocate_new_page_data(size);
  // добавить страницу в список страниц
  page->next_page = state->current;
  state->current = page;
  // пользовательские данные располагаются в начале страницы
  page->offset = size;
  return page->data;
}

void* allocate(allocator_state* state, size_t size) {
  if (state->current->offset + size <= allocator_page_size) {
    void* result = state->current->data + state->current->offset;
    state->current->offset += size;
    return result;
  }
  return allocate_oob(state, size);
}

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

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

В случае резервирования небольших фрагментов памяти данная системе не теряет память. Однако, существует возможность создания гипотетической ситуации резервирования памяти (которая может возникнуть и в реальности), в ходе которой эта система будет терять память. Последовательность операций резервирования фрагментов памяти с размерами, изменяющимися от 64 до 65535 байт, может привести к резервированию новой страницы в ходе каждого вызова и в результате 30% объема памяти будут потеряны. По этой причине реализация данной системы резервирования памяти в рамках pugixml ведет себя немного по-другому: в том случае, если размер резервируемого блока больше четверти стандартного размера страницы, она резервирует полную страницу для хранения этого блока и, вместо добавления его в начало списка страниц, добавляет его после первого элемента списка. В этом случае фрагменты памяти небольших размеров, которые резервируются после фрагмента памяти большого размера, будут также размещаться на рабочей странице памяти.

Следует отметить, что код функции allocate_oob() является "холодным кодом" - это утверждение справедливо, так как он выполняется тогда, когда мы расширяем текущую страницу памяти, что должно быть достаточно редким событием. По этой причине четкий запрет генерации inline-функции для компилятора может повысить производительность.¹⁸ Это также означает, что размещение более сложной логики в функции allocate_oob() - например, логики, которая позволяет обрабатывать операции резервирования фрагментов памяти большого размера отличным образом - не окажет никакого влияния на среднюю производительность системы резервирования.

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

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