c - 如何避免为链表中的每个节点调用 malloc

Question

这个问题的灵感来自于

Prevent malloc function wrapping

我编写了一个程序，通过调用 malloc 为链表中的各个节点分配内存。

有一些速度测试，其中 malloc 被一个函数包装，导致 malloc 调用比正常情况下花费更多的时间。这允许测试检测 malloc 的频繁使用。

如何避免为每个节点调用 malloc？

Answer 1

There are speed tests in which malloc is called by wrapped function which is written to take more time and allocate memory. So every time when I call malloc in my pogram it is called but it takes more time so the tests can detect very often usage of malloc. The problem is that I use linked lists so the memory is allocated separately for every node of the list. I don't know how to change this implementation because it is really comfortable to use linked lists in my structure.

您也许可以改用数组。

举个简单的例子:

#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