Как избежать вызова malloc для каждого узла в связанном списке

Question

Этот вопрос был вдохновлен

Предотвращение переноса функции malloc

Я написал программу, которая выделяет память для отдельных узлов в связанном списке, вызывая malloc.

Существуют скоростные тесты, в которых malloc оборачивается функцией, которая заставляет malloc вызывать больше времени, чем обычно. Это позволяет тестам обнаруживать частое использование malloc.

Как мне избежать вызова malloc для каждого узла?

Answer 1

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

Вы можете использовать вместо этого массив.

Дляпростой пример:

#include <stdio.h>
#include <stdlib.h>

struct list_entry {
    struct list_entry *next;
    int foo;
};

#define MAX_THINGS 1234567
struct list_entry myArray[MAX_THINGS];
int firstFreeEntry = 0;

struct list_entry *freeListHead = NULL;

struct list_entry *listHead = NULL;

struct list_entry *allocEntry(void) {
    struct list_entry *temp;

    if(freeListHead != NULL) {
        // Recycle a previously freed entry
        temp = freeListHead;
        freeListHead = temp->next;
        return temp;
    }
    // Try to take a new entry from the array
    if(firstFreeEntry < MAX_THINGS) {
        return &myArray[firstFreeEntry++];
    }
    // Give up (no free entries)
    return NULL;
}

void freeEntry(struct list_entry *entry) {
    int offset;

    // Try to give it back to the array
    offset = entry - myArray;
    if(offset == firstFreeEntry - 1) {
        firstFreeEntry--;
        return;
    }
    // Put it on the list of freed things
    entry->next = freeListHead;
    freeListHead = entry;
}

// Allocate an entry, initialize/construct it, and put it on the linked list

struct list_entry *createEntry(int value) {
    struct list_entry *newEntry;
    newEntry = allocEntry();
    if(newEntry != NULL) {
        newEntry->foo = value;
        newEntry->next = listHead;
        listHead = newEntry;
    }
    return newEntry;
}

int main() {
    const int node_count = 1000 * 1000;
    struct list_entry *head = NULL;
    for (int index = 0; index < node_count; index++) {
        head = createEntry(0xdeadbeef);
        printf("address of head = %p\n", head);
    }
    while (head) {
        struct list_entry *next = head->next;
        printf("address of head = %p\n", head);
        freeEntry(head);
        head = next;
    }
    return 0;
}

Вывод

address of head = 0x101d32040
address of head = 0x101d32050
address of head = 0x101d32060
...
address of head = 0x101d32040

Проверка

$ ./test > storage.txt
$ split -l 1000000 storage.txt
$ tac xab > xac
$ diff xaa xac

Answer 2

Простым решением является реализация альтернативных функций динамической памяти с использованием mmap().

void* alt_malloc( size_t size )
{
    void* mem = mmap( NULL, size + sizeof(size_t),
                      PROT_READ | PROT_WRITE, 
                      MAP_PRIVATE | MAP_ANONYMOUS, -1, 0 ) ;

    if( mem != MAP_FAILED )
    {
        *(size_t*)mem = size ;
    }
    else
    {
        mem = NULL ;
    }

    return mem + sizeof( size_t) ;
}

void* alt_calloc( size_t nitems, size_t size)
{
    return alt_malloc( nitems * size ) ;
}

void alt_free( void* mem )
{
    if( mem != NULL) munmap( mem, *((size_t*)mem - 1) ) ;
} 

void* alt_realloc( void *old_mem, size_t new_size )
{
    void* new_mem = alt_malloc( new_size ) ;
    if( new_mem != NULL )
    {
        size_t old_size = *((size_t*)old_mem - 1) ;
        size_t copy_size = old_size > new_size ? new_size : old_size ;
        memcpy( new_mem, old_mem, copy_size ) ;
        alt_free( old_mem ) ;
    }   

    return new_mem ;
}

Следующий тест:

#define ALLOC_SIZE 1024 * 1024
int main()
{
    char* test = alt_malloc( ALLOC_SIZE ) ;
    memset( test, 'X', ALLOC_SIZE ) ;
    printf( "%p : %c %c\n", test, test[0], test[ALLOC_SIZE-1] ) ;
    test = alt_realloc( test, ALLOC_SIZE * 2 ) ;
    printf( "%p : %c %c\n", test, test[0], test[ALLOC_SIZE-1] ) ;
    alt_free( test ) ;

    return 0;
}

Выходы:

0x7f102957d008 : X X
0x7f1028ea3008 : X X

Демонстрация того, что memset() охватывает экстент начального блока и что realloc создал новый блок и скопировал данные.

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

Например, вы можете взять распределитель библиотек Newlib C с измененными именами и реализовать системный вызов sbrk() (снова переименованный для предотвращения конфликтов), используя mmap() для предоставления памяти альтернативной куче.

Answer 3

Это похоже на ответ от @Brendan, но не имеет фиксированного ограничения на количество узлов. Он получен из кода, который я уже написал.

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

#include <stdio.h>
#include <stdlib.h>

#define CHUNK 8192

typedef struct Node {
    int data;
    struct Node *next;
} node;

node *array;
node *pool;
int nodes_avail;
int nodes_used;

node *getnode(void)
{
    node *newnode;
    if(pool) {                              // any in the recycled pool?
        newnode = pool;
        pool = pool->next;
    }
    else if(nodes_used < nodes_avail) {     // any in the array?
        newnode = &array[nodes_used];
        nodes_used++;
    }
    else {                                  // extend the array?
        nodes_avail += CHUNK;
        node *temp = realloc(array, nodes_avail * sizeof *temp);
        if(temp == NULL) {
            exit(1);                        // or recovery
        }
        array = temp;
        newnode = &array[nodes_used];
        nodes_used++;
    }
    return newnode;
}

void freenode(node *nptr)
{
    nptr->next = pool;                      // add to recycled pool
    pool = nptr;
}

int main() {
    const int node_count = 1000 * 1000;
    node *head = NULL;
    for (int index = 0; index < node_count; index++) {
        node *new = getnode();
        new->next = head;
        head = new;
        printf("address of head = %p\n", head);
    }
    while (head) {
        node *next = head->next;
        freenode(head);
        head = next;
    }
    for (int index = 0; index < node_count; index++) {
        node *new = getnode();
        new->next = head;
        head = new;
        printf("address of head = %p\n", head);
    }
    return 0;
}

выход

address of head = 0x100bc7000
address of head = 0x100bc7010
address of head = 0x100bc7020
...
address of head = 0x101b2a3f0

Проверка

$ ./test > storage.txt
$ split -l 1000000 storage.txt
$ diff xaa xab

Answer 4

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

#include <stdio.h>
#include <stdlib.h>

// An imaginary node because the original question did not provide one
struct node {
    struct node *next, *prev;
    int numbers[1024];
    char string[1024];
};

struct node_storage {
    int count;
    int total;
    struct node *node_list;
    struct node_storage *next;
};

struct node_storage *add_storage(int count) {
    struct node_storage *pstorage = malloc(sizeof(struct node_storage));
    // We could avoid a malloc here by making node_list an array
    pstorage->node_list = malloc(sizeof(struct node) * count);
    pstorage->count = count;
    pstorage->total = count;
    pstorage->next = NULL;
    return pstorage;
}

void free_storage(struct node_storage *storage) {
    while (storage) {
        struct node_storage *next = storage->next;
        free(storage->node_list);
        free(storage);
        storage = next;
    }
}

struct node *new_node(struct node **free_list, struct node_storage **storage) {
    struct node *free_node = *free_list;
    struct node_storage *pstorage = *storage;
    struct node *result;
    // If there is a free node
    if (free_node) {
        // Get the new node from the free list
        result = free_node;
        *free_list = free_node->next;
    }
    else {
        // Get the new node from the pre-allocated storage
        result = &pstorage->node_list[pstorage->total - pstorage->count];
        pstorage->count--;
        // If that was the last pre-allocated node
        if (0 == pstorage->count) {
            // Allocate the next chunk of nodes
            pstorage->next = add_storage(pstorage->total);
            *storage = pstorage->next;
        }
    }
    return result;
}

void free_node(struct node **free_list, struct node *node) {
    struct node *pfree_list = *free_list;
    if (pfree_list) {
        node->next = pfree_list;
    }
    *free_list = node;
}

int main() {
    const int node_count = 1000 * 1000;
    struct node_storage *head;
    struct node_storage *curr;
    struct node *free_list = NULL;
    struct node *node_list = NULL;
    head = add_storage(100);
    curr = head;
    // Allocate a lot of nodes and put them in a list
    for (int index = 0; index < node_count; index++) {
        struct node *new = new_node(&free_list, &curr);
        printf("address of new = %p\n", new);
        new->next = node_list;
        node_list = new;
    }
    // Free all of the allocated nodes
    while (node_list) {
        struct node *pnode = node_list;
        node_list = node_list->next;
        free_node(&free_list, pnode);
    }
    // Allocate a lot of nodes so that we can verify that they come from
    // the free list
    for (int index = 0; index < node_count; index ++) {
        struct node *new = new_node(&free_list, &curr);
        printf("address of new = %p\n", new);
    }
    free_storage(head);
    return 0;
}

Выход

address of new = 0x10f972000
address of new = 0x10f973410
...
address of new = 0x243570230

Предупреждение

Этот код не проверяет ошибки и не должен использоваться в производственной среде.

Примечание

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

$ ./test > storage.txt
$ split -l 1000000 storage.txt
$ diff xaa xab

Answer 5

Самое простое, что вы можете сделать, это продолжать вызывать malloc для отдельных узлов связанного списка, но когда узлы освобождены, поместите их в список свободных узлов.

node *free_list = 0;

node *node_alloc(void)
{
   /* get a node fast from the free list, if available */
   if (free_list != 0) {
      node *ret = free_list;
      free_list = free_list->next;
      return ret;
   } else {
      node *ret = malloc(sizeof *ret);
      /* check for non-null, initialize */
      return ret;
   }
}

void node_free(node *node)
{
   node->next = free_list;
   free_list = node;
}

Еслив вашей программе есть несколько объектов, которые находятся только в одном списке в любой момент времени, вы можете поместить узлы списка прямо в эти объекты, чтобы они не требовали отдельного выделения:

struct process {
   node queue_node; /* list links for putting process into queues */
   ...
};