Пользовательский malloc для большого количества небольших блоков фиксированного размера?

Ответ 1

Вы правы, это общая проблема. [Edit: как делать фиксированное распределение по размеру, я имею в виду. "malloc замедляет мое приложение" менее часто, чем вы думаете).

Если ваш код слишком медленный и malloc правдоподобный преступник, то простой распределитель ячеек (или "пул памяти" ) может улучшить ситуацию. Вы почти наверняка можете найти где-нибудь, или легко написать:

Выделите большой блок и поместите односвязный список node в начале каждой ячейки из 16 байтов. Свяжите их все вместе. Чтобы выделить, выньте голову из списка и верните его. Чтобы освободить, добавьте ячейку в начало списка. Конечно, если вы попытаетесь выделить и список пуст, вам нужно выделить новый большой блок, разделить его на ячейки и добавить их в список.

Вы можете избежать этой большой работы, если хотите. Когда вы выделяете большой блок, просто сохраните указатель на его конец. Чтобы выделить, переместите указатель назад на 16 байтов через блок и верните новое значение. Если это уже не было в начале блока [*], конечно. Если это произойдет, и свободный список также пуст, вам нужен новый большой блок. Бесплатно не изменяется - просто добавьте node в свободный список.

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

Обратите внимание, что список node не требуется, пока ячейка выделена, поэтому на каждую ячейку по существу нулевые служебные данные. Вряд ли в стороне от скорости, это, вероятно, будет преимуществом по сравнению с malloc или другими распределителями общего назначения.

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

[*] Где "начало блока", вероятно, означает "начало блока, плюс размер некоторого node, используемого для ведения списка всех блоков, поэтому они могут быть освобождены, когда распределитель ячеек уничтожается".

Ответ 2

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

Ответ 3

Лучший способ сделать это - не предполагать, что он будет неэффективным. Вместо этого попробуйте решение с помощью malloc, измерьте производительность и убедитесь, что он эффективен или нет. Затем, как только он станет неэффективным (скорее всего, не будет), это единственный раз, когда вы должны перейти к настраиваемому распределителю. Без доказательства вы никогда не узнаете, действительно ли ваше решение быстрее или нет.

Ответ 4

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

calloc(N * 16)

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

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

Ответ 5

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

Простейшая реализация для пула данных одинакового размера - это всего лишь оболочка, содержащая буфер n * size и стек из n указателей. "malloc" из пула выводит указатель сверху. "free" в пул помещает указатель обратно в стек.

Ответ 6

Вы можете попробовать переопределить malloc/free с альтернативной реализацией, которая подходит для множества небольших распределений.

Ответ 7

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

В принципе, он работает как описанный патрон, за исключением того, что он автоматически запрашивает больше памяти, если нет свободных блоков. Код был протестирован с большим связанным списком (около 6 миллионных узлов, каждый размером 16 байт) против наивной схемы malloc()/free() и выполнялся примерно на 15% быстрее, чем это. Поэтому, возможно, это полезно для вашего намерения. Его легко настроить на разные размеры блоков, поскольку размер блока указан при создании такого большого фрагмента памяти.

Код доступен в github: challoc

Пример использования:

int main(int argc, char** argv) {
    struct node {
           int data;
       struct node *next, *prev;
    };
    // reserve memory for a large number of nodes
    // at the moment that three calls to malloc()
    ChunkAllocator*  nodes = chcreate(1024 * 1024, sizeof(struct node));

    // get some nodes from the buffer
    struct node* head = challoc(nodes);
    head->data = 1;
    struct node* cur = NULL;
    int i;
    // this loop will be fast, since no additional
    // calls to malloc are necessary
    for (i = 1; i < 1024 * 1024; i++) {
            cur = challoc(nodes);
        cur->data = i;
        cur = cur->next;
    }

    // the next call to challoc(nodes) will
    // create a new buffer to hold double
    // the amount of `nodes' currently holds

    // do something with a few nodes here

    // put a single node back into the buffer
    chfree(nodes,head);

    // mark the complete buffer as `empty'
    // this also affects any additional
    // buffers that have been created implicitly
    chclear(nodes);

    // give all memory back to the OS
    chdestroy(nodes);

    return 0;
}

Ответ 8

Уилсон, Джонстоун, Нили и Болес писали хорошую бумагу, которая просматривала всевозможные распределители.

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

Ответ 9

Следующий код довольно уродливый, но цель - не красота, а выяснить, насколько большой блок, выделенный malloc.
Я попросил 4 байта, и malloc запросил и получил 135160 байт от ОС.

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


int main()
{
  int* mem = (int*) malloc( sizeof(int) ) ;
  if(mem == 0) return 1;
  long i=1L;

  while(i)
    {
      mem[i-1] = i;
      printf("block is %d bytes\n", sizeof(int) * i++);
    }//while

  free(mem);
  return 0 ;
}

$g++ -o file file.cpp
$./file
...
блок - 135144 байт
блок - 135148 байт
блок - 135152 байт
блок - 135156 байт
блок - 135160 байт
Ошибка сегментации

Этот malloc - серьезный бизнес.
realloc не выполняет никакого системного вызова, если запрашиваемый размер меньше, чем он доступен из-за внутреннего объединения.
После того, как realloc скопировал память в большую зону, он не уничтожает предыдущий блок, а не сразу возвращает его в систему. К этому можно еще обратиться (конечно, абсолютно небезопасно). Со всем этим это не имеет смысла для меня, кому-то нужен дополнительный пул памяти.