改进malloc()算法的下一步是什么？

Question

我正在编写自己的简单malloc()函数,我想创建更快更有效的变体.我是使用线性搜索并在内存中顺序和连续分配的函数.

改进此算法的下一步是什么？我当前版本的主要缺点是什么？我将非常感谢任何反馈和建议.

typedef struct heap_block
{  
    struct heap_block* next;
    size_t size;
    bool isfree;
}header;

#define Heap_Capacity 100000
static char heap[Heap_Capacity];
size_t heap_size;

void* malloc(size_t sz) 
{
    if(sz == 0 || sz > Heap_Capacity) { return NULL; }

    header* block = (header*)heap;
    if(heap_size == 0)
    {
        set_data_to_block(block, sz);
        return (void*)(block+1);
    }

    while(block->next != NULL) { block = block->next; }

    block->next = (header*)((char*)to_end_data(block) + 8);
    header* new_block = block->next;
    set_data_to_block(new_block, sz);

    return (void*)(new_block+1);
}

void set_data_to_block(header* block, size_t sz)
{
    block->size = sz;
    block->isfree = false;
    block->next = NULL;
    heap_size += sz;
}

header* to_end_data(header* block)
{
    return (header*)((size_t)(block+1) + block->size);
}

Answer 1

请注意，它malloc通常构建在与内存相关的较低级别的系统调用之上（例如Linux 上的mmap(2) ）。请参阅此答案，其中提到了 GNUglibc和musl-libc. 还要查看tcmalloc内部，因此研究几个自由软件 malloc 实现的源代码。

为您提供的一些一般想法malloc：

• 使用从操作系统检索内存mmap（并最终使用将其释放回操作系统内核munmap）。您当然不应该分配固定大小的堆（因为在具有 128GB RAM 的 64 位计算机上，您希望成功分配malloc100 亿字节的区域）。
• 将小分配与大分配分开，因此malloc对 16 字节和 1 mallocMB 的处理方式不同。小分配和大分配之间的典型阈值通常是页面大小的一小倍（通常为 4Kbytes）。小的分配发生在页面内部。大的分配会四舍五入到页面。您甚至可以非常特殊地处理malloc两个单词（就像在许多链接列表中一样）。
• 将请求的大小四舍五入为某个奇数（例如 2 的幂，或 2 的 3 次幂）。
• 一起管理相似大小的内存区域，即具有相同的“奇特”大小。
• 对于小内存区域，避免过早回收内存区域，因此保留先前的free-d 区域相同（小）大小，以便在将来调用malloc.
• 您可以在地址上使用一些技巧（但您的系统可能有ASLR），或者在每个内存区域附近保留一个描述其所属块的元数据字。
• 一个重要的问题是，给定先前返回的某个地址malloc和 的参数free，找出该内存区域的分配大小。您可以操纵地址位，您可以在之前的字中存储该大小，您可以使用一些哈希表等。细节很棘手。

请注意，细节很棘手，并且可能很难编写malloc比您的系统更好的实现。在实践中，写一篇好的文章malloc并不是一件简单的事情。您应该找到许多关于该主题的学术论文。

还要研究垃圾收集技术。也许考虑一下Boehm 的保守 GC：您将替换malloc为GC_MALLOC并且您不会打扰free...了解内存池。