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

Question

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

Answer 4

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

calloc(N * 16) 

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

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

Answer 5

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

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

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

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

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

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

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

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

Answer 6

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

Answer 7

Wilson, Johnstone, Neely, and Boles написал a nice paper surveying all sorts of different allocators.

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

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 ; 
} 

$ г ++ -o файл file.cpp
$ ./file
...
блок 135144 байт
блок является 135148 байт
блок 135152 байт
блок является 135156 байт
блок 135160 байт
разломов Сегментация

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

Answer 9

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

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