Куча оптимизирована для (но не ограничивается) однопоточным использованием

Я использую обычную реализацию кучи в одном из моих проектов. Он состоит из двух основных частей:

  • Исправлена ​​куча размерного блока. То есть куча, которая выделяет только блоки определенного размера. Он выделяет более крупные блоки памяти (страницы виртуальной памяти или из другой кучи), а затем делит их на единицы распределения атомов.

    Он выполняет распределение/освобождение быстро (в O (1)), и нет накладных расходов памяти, не принимая во внимание вещи, наложенные внешней кучей.

  • Глобальная куча общего назначения. Он состоит из ведер вышеупомянутых (фиксированных) куч. WRT запрашиваемый размер выделения, который он выбирает для соответствующего ведра, и выполняет распределение через него.

    Так как все приложение (сильно) многопоточное - глобальная куча блокирует соответствующий ковш во время его работы.

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

Пока все выглядит (и работает) хорошо.

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

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

Это заставляет меня задаться вопросом: существует ли известная методика оптимизации кучи для однопоточного использования (но не ограничивается)?

EDIT:

Особая благодарность @Voo за предложение проверить google tcmalloc.

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

Я тоже думал в этом направлении, но я думал о сохранении per-thread heaps. Затем освобождение блока памяти, выделенного из кучи, принадлежащего другому потоку, несколько сложно: нужно вставить его в виде заблокированной очереди, а другой поток должен быть уведомлен и освободить ожидающие распределения асинхронно. Асинхронное освобождение может вызвать проблемы: если этот поток занят по какой-либо причине (например, выполняет агрессивные вычисления) - фактически не происходит освобождение памяти. Плюс в многопоточном сценарии стоимость освобождения значительно выше.

OTOH идея с кэшированием кажется намного проще и эффективнее. Я постараюсь разобраться.

Большое спасибо.

P.S:.

Действительно, google tcmalloc отлично. Я считаю, что он реализован в значительной степени аналогично тому, что я сделал (по крайней мере, части с фиксированным размером).

Но, чтобы быть педантичным, есть вопрос, где моя куча выше. Согласно документам, tcmalloc налагает накладные расходы примерно на 1% (асимптотически), тогда как мои накладные расходы составляют 0,0061%. Это 4/64K, если быть точным.

:)

Ответы

Ответ 1

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

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

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

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

На стороне примечания, если вы еще не прочитали его, я предлагаю IBM Inside Memory Management для тех, кто реализует собственное управление памятью.

ОБНОВЛЕНИЕ

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

Ответ 2

Возможно, неплохо было бы прочитать классические статьи Джеффа Бонвикса на распределителе плиты и vmem. Оригинальный распределитель slab звучит несколько, что вы делаете. Хотя он не очень многопоточен, он может дать вам несколько идей.

Аллокатор Slab: Абонент памяти кэширования объектов

Затем он расширил концепцию с помощью VMEM, что, безусловно, даст вам некоторые идеи, так как это очень приятное поведение в среде с несколькими процессорами.

Журналы и Vmem: расширение Allocator Slab для многих процессоров и произвольных ресурсов