О дизайне распределителей памяти с нулевым копированием, используемых в быстром коде большого объема

Question

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

Я создаю библиотеку для высокопроизводительного высокопроизводительного IPC на том же компьютере, используя специальные каналы ОС (именованные каналы в Windows и доменные сокеты UNIX в UNIX). Библиотека получает сообщения и вставляет их в обработчик, и этот механизм может быть в том же процессе в C ++ или что-то вроде Erlang или Lua, или, возможно, перенесен на центральную машину.

Сообщения в данный момент поступают из веб-сервера и являются частью конвейера разрешения HTTP-запроса и должны масштабироваться вместе с веб-сервером, т. Е. Я не могу написать неэффективную систему, потому что веб-серверы рабочие потоки зависят от скорости, с которой они могут разгрузить эти сообщения. Если веб-сервер способен обрабатывать 10 тыс. Запросов статических страниц, этот механизм IPC не должен мешать ему.

Данные поступают в виде печатных сообщений, и я полагаю, что они будут иметь собственную статистику размера, которую можно было бы использовать. Распределитель Дуга Ли создает связанные списки сегментов по размерам, если я правильно помню, возможно, именно так я и должен поступить - это стандарт общего распределителя.

Я хочу семантику нулевого копирования, поэтому пока сообщение не будет обработано, его не следует копировать. С другой стороны: это, возможно, удаляет буферы протокола Googles из картинки (на данный момент не может быть уверенным), так как формат проводника отличается от формата объекта в памяти. Я буду исследовать дальше - моя текущая реализация использует мой собственный формат IPC; возможно, у кого-то есть мнение о том, как протокольные буферы работают, использует ли он нулевое копирование внутри?

Я хочу использовать этот распределитель во всех областях приложения. Мое исследование программного обеспечения сетевого стека побуждает меня к распределителю на основе выровненного по страницам процессора; мое приложение, безусловно, имеет такую ​​же семантику доступа. Я скопировал бы все сообщения на страницу и перезапустил бы страницы только тогда, когда все ссылки на элементы - которые выделены для пула - неактивны.

Чтобы немного формализовать и помочь вам понять, о чем я думаю, рассмотрите следующую структуру данных:

typedef struct _page
{
   int active_elements;            // page is returned to empty pool at zero
   int free_bytes;                 // used to sort the pages
   void * next_free_contigious;    // pointer to where next allocation may occur
   _page * next_page;              // linked list next page pointer
} page;

struct pageAllocator
{
   page * ll_empty;       // completely empty pages
   page * ll_active;      // sorted by highest_size_available, could be binary tree 
                          // continue reading for rationale.
};

Некоторые пункты:

1. Сообщения не будут задерживаться. Так что страницы скоро станут свободными.
2. Мне нужно написать пуленепробиваемый код, чтобы освободить страницы.
3. Я не знаю, должно ли page-> next_free_contigious быть совмещенным со словом.
4. Я предполагаю, что под давлением количество выделенных страниц будет стабильным.
5. Должен ли я возвращать страницы в ОС или я должен просто сохранять их? Максимальное давление будет выделяться столько, сколько ему нужно, только если будет установлено максимальное давление.
6. Должен ли я выделять сообщения первому элементу в отсортированном по размеру списке (сначала самое высокое) или найти страницу с наиболее подходящим соответствием. В этом случае мне пришлось бы использовать какое-то двоичное дерево. Я повторно реализую алгоритм Дуга здесь?

Я хочу, чтобы предложения от людей, которые лично имели дело с такими вещами, приветствуются альтернативные предложения распределителя. Было бы неплохо иметь готовые библиотеки (они должны быть реализацией мета-кода препроцессора c-ANSI-C). APR - это популярная библиотека со стратегией, основанной на иерархическом пуле, но я не занимаюсь сессиями на этом низком уровне, поэтому мне не нужна иерархия.

Не думаю, что я предварительно оптимизирую, потому что убежден, что мне это нужно. Моя текущая реализация этой системы переходит на 30% ЦП во время насыщения ЦП веб-сервера, и я знаю, что это из-за моего наивного способа программирования приложения с использованием новых и множества конструкций копирования в C ++. Я, конечно, буду тестировать приложение, прежде чем продолжить (я слишком занят, чтобы заново создать тестовую среду), но любое обсуждение здесь будет полезно независимо от результата.

--- редактировать 1 ---

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

Хорошо, сейчас я думаю о кольцевом буфере (скажем, 1mb ^ x). Состоит из элементов одинакового размера (возможно, кратных 128 байтам). Распределения происходят постепенно до конца (с пометкой на голове allocatex (A), откуда могут происходить выделения, и свободным маркером (F), отмечающим приглушенные свободные области (0), возвращаемые в пул. Рассмотрим следующую иллюстрацию ASCII:

|000000F101110001111A00000000|

0 = свободен, 1 = занят.

Некоторые конкретные:

• Свободный маркер разграничивает свободные смежные области. На рисунке F будет двигаться только два вперед, когда будет возвращен непосредственно следующий фрагмент.
• Как только выделение достигает конца, или в конце недостаточно места для выполнения непрерывного выделения, головка выделения перемещается в начало; к этому моменту большая часть буфера должна быть свободной.
• как только сообщение перемещается к месту назначения, куски немедленно возвращаются в буфер.
• При доставке на той же машине сообщения будут доставляться в короткие сроки (с некоторыми блокировками) или сразу, если для этого требуется просто вызов функции без потоков.

---

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

Answer 1

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

Предположительно, у вас есть большое количество потоков, поэтому любой распределитель должен был бы делать немного блокировки; большое количество мелких выделяет / освобождает звуки нежелательно.

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

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

Answer 2

Ответ: Подумайте, ЧТО вы хотите достичь.

• Хотите ли вы семантику нулевого копирования при обработке сообщений?
• Или вы хотите новый модный сверхбыстрый распределитель памяти?

«Нулевой распределитель памяти» не имеет смысла!

Написание распределителя памяти общего назначения затруднительно (наиболее вероятно, что распределитель памяти по умолчанию идеально подходит для ваших целей). Если вам нужна идея хорошего распределителя для ваших целей, пожалуйста, предоставьте более подробную информацию.

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

Во-первых, чтение из канала IPC: есть список буферов : read() из FIFO в buffers[current_write_buffer_idx].data+write_pos максимум (buffer_size-write_pos) байтов. Добавьте количество прочитанных байтов в write_pos и так далее. Если буфер заполнен, проверьте свой список буферов, найдете ли вы неиспользуемый (сохраняйте флаг использования для каждого буфера). Если не найдено ни одного неиспользованного, выделите новый буфер. Установите next_buffer_index в старом буфере (используется для «разбора» позже ..).

Вы получите:

size_t write_pos, read_pos;
struct Buffer {
    void* data;
    bool is_used;
    size_t number_bytes_written;
    size_t next_buffer_index;
};
Buffer *buffers;
size_t number_buffers;
size_t current_write_buffer_idx;
size_t current_read_buffer_idx;

Во-вторых, синтаксический анализ потока: найдите следующий байт в buffers[current_read_buffer_index].data+read_pos. Вы можете прочитать байты из этого буфера до buffer.number_bytes_written байтов, если количество записанных байтов равно buffer_size (фиксированный), тогда буфер заполнен, и вам нужно продолжить чтение из буфера в next_buffer_index ...

И так далее. Установите is_used true всякий раз, когда вы пишете в новый буфер, устанавливайте его в false, когда вы выполняете синтаксический анализ буфера.

Что именно означает «чтение», во многом зависит от того, как закодировано ваше сообщение!

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

• чтение информации о типе и / или размере из потока и ..
• если сообщение еще не получено полностью (read_pos, number_bytes_written, ...), тогда пропустить ...
• если сообщение (размер известен сейчас) помещается в один буфер, просто используйте указатель на этот буфер (struct MsgXYZ*)( buffers[current_read_buffer_idx].data + start_of_message_index ) и передайте его любому коду, выполняющему работу
• если сообщение порождает буферы, создает временный буфер и копирует части сообщения вместе, передает указатель на сообщение в код ... после этого освобождает временный буфер (в любом случае это редкий случай)

Ну, здесь я опустил много деталей;) Подумайте дважды, действительно ли нулевая копия имеет смысл для вашего приложения.

Нулевое копирование, когда чтение из сокета / канала /... ИМХО невозможно, возможно, через разделяемую память какого-то типа mmap, но не с помощью каналов.

Answer 3

Возможно, вы ищете что-то вроде GLib Slice Allocator ?

Предназначен для высокоскоростного размещения и освобождения объектов аналогичного размера. Он также заявляет о превосходной производительности в многопоточной среде.

Один из аспектов API, который может вызвать у вас проблемы, заключается в том, что вы должны указать размер вашего объекта во время освобождения, а также выделения.