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

Question

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

Вопрос в том, как лучше это сделать?

Кажется, что это не должно быть очень необычной проблемой или редкой проблемой, и что это должно было быть "решено", но я не могу ничего найти. Есть указатели?

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

Answer 1

Вы правы, это распространенная проблема [Править: как сделать фиксированное распределение, я имею в виду. «malloc замедляет мое приложение» встречается реже, чем вы думаете].

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

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

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

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

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

calloc(N * 16)

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

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

Answer 5

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

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

Answer 6

Из-за академического интереса я работал над решением этой проблемы несколько дней назад.Реализация очень проста, но завершена, и вы упомянули, что ищете замену, поэтому я думаю, что моя реализация могла бы работать для вас.память, если больше нет свободных блоков.Код был протестирован с большим связным списком (около 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's 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;
}

Answer 7

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

Answer 8

Следующий код довольно уродлив, но его цель не в том, а в том, чтобы выяснить, насколько велик блок, выделенный 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.cpp
$ ./file
...
блок 135144 байта
блок 135148 байт
блок 135152 байта
блок 135156 байт
блок 135160 байт
Ошибка сегментации

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

Answer 9

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

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