Какой алгоритм применить для непрерывного перераспределения небольших кусков памяти?

Question

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

Answer 1

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

Однако если выбеспокоятся о фрагментации памяти, это другой вопрос.

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

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

Например, вот старая статья 2010 года, описывающаясовременная среда выполнения компилятора реализует malloc() и free(). Посмотрите, как работает malloc на Mac

Вот немного о GNU allocator .

Эта статья от IBM за ноябрь 2004 г.описывает некоторые аспекты управления памятью, Управление внутренней памятью и предоставляет то, что они называют «кодом для упрощенной реализации malloc и бесплатно, чтобы помочь продемонстрировать, что связано с управлением памятью».Обратите внимание, что это упрощенный пример, предназначенный для иллюстрации некоторых проблем, а не демонстрация текущей практики.

Я сделал быстрое консольное приложение с Visual Studio 2015, которое вызывало функцию C в исходном файле C, котораяперемежающиеся malloc() и free() звонки разных размеров.Я запустил это, наблюдая за процессом в диспетчере задач Windows.Максимальный рабочий набор (память) увеличен до 34 МБ.Наблюдая за измерением памяти (частного рабочего набора), я видел, как оно росло и падало во время работы программы.

#include <malloc.h>
#include <stdio.h>

void funcAlloc(void)
{
    char *p[50000] = { 0 };
    int   i;

    for (i = 0; i < 50000; i+= 2) {
        p[i] = malloc(32 + (i % 1000));
    }

    for (i = 0; i < 50000; i += 2) {
        free(p[i]); p[i] = 0;
    }
    for (i = 1; i < 50000; i += 2) {
        p[i] = malloc(32 + (i % 1000));
    }
    for (i = 1; i < 50000; i += 2) {
        free(p[i]); p[i] = 0;
    }

    for (i = 0; i < 50000; i++) {
        p[i] = malloc(32 + (i % 1000));
    }

    for (i = 0; i < 50000; i += 3) {
        free(p[i]); p[i] = 0;
    }
    for (i = 1; i < 50000; i += 3) {
        free(p[i]); p[i] = 0;
    }
    for (i = 2; i < 50000; i += 3) {
        free(p[i]); p[i] = 0;
    }
}

void funcMain(void)
{
    for (int i = 0; i < 5000; i++) {
        funcAlloc();
    }
}

Вероятно, единственное соображение, которое программист должен практиковать, чтобы помочь распределителю памяти при некоторых условиях перетекания памятис malloc() и free() - использовать набор стандартных размеров буфера для данных различной длины.

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

Answer 2

Лучшим алгоритмом в этом случае будет свободный список распределитель + дерево двоичного поиска.

Вы запрашиваете один большой кусок памяти из системы, а затем выделяете блоки памяти фиксированного размера изэтот кусок.Когда блок заполнен, вы выделяете другой блок и связываете его с красно-черным или AVL-деревом двоичного интервала поиска (в противном случае поиск фрагмента в течение free путем перебора списка фрагментов становится узким местом)

Ив то же время важна многопоточность и синхронизация потоков.Если вы просто будете использовать мьютексы или тривиальные спин-блокировки, вы обнаружите, что libc malloc работает намного быстрее, чем ваш пользовательский распределитель памяти.Решение можно найти в Указатель опасности , т.е. каждый поток имеет свой собственный распределитель памяти (или один распределитель на ядро ​​ЦП).Это добавит еще одну проблему - когда один поток выделяет память, а другой освобождает ее, это потребует поиска точного распределителя во время свободной функции, а также строковой блокировки или структуры данных без блокировки.

Лучший вариант - вы можетеиспользуйте jemalloc , tcmalloc или любой другой универсальный быстрый распределитель памяти для полной или частичной замены вашего стандартного распределителя libc (т.е. pdmalloc).