C ++ пользовательский распределитель, который использует базовый пул памяти - PullRequest
Новая
       41

C ++ пользовательский распределитель, который использует базовый пул памяти

7 голосов
/ 06 июля 2011

Я использую класс пула памяти, который повторно использует выделенные адреса памяти и пользовательский распределитель, который переносит этот класс. Следующий фрагмент кода дает базовое представление об интерфейсе. 

template<class alloc>
class memory_pool
    : boost::noncopyable,
      public allocator_traits<void>
{
public:
    memory_pool(typename alloc::size_type alloc_size);
    memory_pool(typename alloc::size_type alloc_size, alloc const&);
    template<typename U> memory_pool(typename alloc::size_type alloc_size,
        typename alloc::rebind<U>::other const&);
    virtual ~memory_pool();

    pointer allocate  (); /*throw(std::bad_alloc)*/
    void    collect   ();
    void    deallocate(pointer) throw(); /*noexcept*/
};

pointer allocate()
{/*
    Checks if a suitable chunk of memory is available in a internal linked list.
    If true, then the chunk is returned and the next chunk moves up.
    Otherwise, new memory is allocated by the underlying allocator.
*/}

void deallocate(pointer)
{/*
    Interprets the passed pointer as a chunk of memory and stores it in a linked list.
    Please note that memory isn't actually deallocated.
*/}

void collect()
{/*
    Effectively deallocates the cunks in the linked list.
    This will be called at least once during destruction.
*/}

Конечно, необходимость чего-то подобного ограничена. Тем не менее, это очень полезно в ситуациях, когда вам нужно чтобы: - Определить тип распределителя для класса, который использует этот распределитель очень наивно (например, избегает выделение больших кусков, даже если это будет целесообразно). - Выделяйте и освобождайте повторно один и тот же размер памяти. - Тип, для которого вы хотите использовать распределитель, имеет очень маленький размер (например, встроенные типы, такие как char, short, int и т. Д.).

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

Я протестировал оба случая со следующим действительно простым кодом: 

std::list<int, allocator<int>> list;

std::clock_t t = std::clock();
for (int i = 0; i < 1 << 16; ++i)
{
    for (int j = 0; j < 1 << 16; ++j)
        list.push_back(j);
    list.unique();
    for (int j = 0; j < 1 << 16; ++j)
        list.pop_back();
}
std::cout << (std::clock() - t) / CLOCKS_PER_SEC << std::endl;

std::list звонит allocactor::allocate(1, 0) каждый раз, когда push_back звонит. unique() гарантирует, что каждый элемент будет затронут и сравнен со следующим элементом. Однако результат оказался неутешительным. Минимальные накладные расходы, необходимые для управления пулом памяти, распределенным по блокам, превышают любые возможные преимущества, которые получает система.

Можете ли вы вспомнить сценарий, в котором это улучшит производительность?

EDIT: Конечно, это намного быстрее, чем std::allocator.

Ответы [ 2 ]

1 голос
/ 06 июля 2011

C ++ 0x имеет улучшенную поддержку распределителей области действия , таких как пулы памяти.

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

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

template <size_t ObjectSize> class allocator {
    // ...
};

template <typename T> class allocator : public allocator <sizeof (T)> {
    // ...
};

Прежде чем вы сможете спроектировать распределитель, вы должны быть уверены, что будет выделено и как. Ответы для operator new «что угодно» и «как угодно», поэтому иногда они не оптимальны. Если вы не можете ответить на эти вопросы должным образом, ваш распределитель, вероятно, не будет большим улучшением.

0 голосов
/ 06 июля 2011

Можете ли вы вспомнить сценарий, в котором это улучшит производительность?

То, что делает много (10 000+ в секунду) распределений и освобождений, выиграет от не нужно каждый раз сталкиваться со сложными запросами к выделению / освобождению, но только если Объединенная экономия на задержке распределения / освобождения в группы - это больше, чем требуется для обработки группы (в основном вам нужно амортизировать группу с учетом экономии на единицу).

использование непрерывной памяти поможет любым структурам, основанным на узлах / указателях, например деревьям (но только в точке). однако, реальные выгоды могут быть радикально разными (или вообще отсутствовать!) Исходя из того, что они планировали быть, поэтому, когда вы идете по пути создания пользовательских систем, подобных этой, вы должны профилировать свой код и уже иметь представление о том, как он будет использоваться (то есть: нет смысла создание собственного распределителя пула для чего-то, что делает так мало выделений, что увеличение скорости вообще не имеет значения).

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

...