Оптимизация программы на C с использованием SLAB-подобных технологий - PullRequest
6 голосов
/ 28 февраля 2012

У меня есть проект программирования с очень интенсивным использованием функций malloc / free. Он имеет три типа структур с очень высокой динамикой и большими числами. Таким образом, часто используются malloc и free, которые вызываются тысячи раз в секунду. Может ли замена стандартного распределения памяти версией SLAB в пользовательском пространстве решить эту проблему? Есть ли реализация таких алгоритмов?

P.S.

  1. Система ориентирована на Linux.
  2. Размеры структур меньше 100 байт.
  3. Наконец, я предпочитаю использовать готовую реализацию, потому что управление памятью - очень сложная тема.

Ответы [ 3 ]

8 голосов
/ 28 февраля 2012

Если у вас есть только три разных, вы бы значительно выиграли, используя распределитель пула (либо по индивидуальному заказу, либо что-то вроде boost::pool, но для C). Malloc, основанный на биннинге Дуга Ли , послужит очень хорошей основой для распределителя пула (используется в glibc).

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

1 голос
/ 28 февраля 2012

Я недавно внедрил свой собственный распределитель плит в пользовательском пространстве, и он оказался намного более эффективным (по скорости и по памяти), чем malloc / free для большого количества выделений фиксированного размера. Вы можете найти это здесь .

Распределение и освобождение выполняются за время O (1) и ускоряются из-за использования битвекторов для представления пустых / полных слотов. При выделении встроенная функция __builtin_ctzll GCC используется для определения местоположения первого установленного бита в битовом векторе (представляющем пустой слот), который должен преобразовываться в одну инструкцию на современном оборудовании. При освобождении выполняется некоторая умная побитовая арифметика с самим указателем, чтобы найти заголовок соответствующей плиты и пометить соответствующий слот как свободный.

1 голос
/ 28 февраля 2012

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

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

Как говорится, вот несколько упрощенных многопоточных наивных идей:

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

Я лично обнаружил, что часто заканчиваю тем, что использую довольно простой в реализации менеджер повторного использования памяти для блоков памяти одинакового размера - он поддерживает связанный список неиспользуемой памяти фиксированного размера и выделяет новый блок памяти когда это нужно. Хитрость заключается в том, чтобы хранить указатели для связанного списка в неиспользуемых блоках памяти - таким образом, существует очень маленькая служебная нагрузка в четыре байта. Весь процесс равен O (1) всякий раз, когда он повторно использует память. Когда ему нужно выделить память, он вызывает распределитель плит (что само по себе тривиально).

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

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...