改进 malloc() 算法的下一步是什么？ [关闭]

我自己写的简单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);
}

请注意malloc通常构建在较低级别的内存相关系统调用之上（例如mmap(2) http://man7.org/linux/man-pages/man2/mmap.2.html在 Linux 上）。看这个答案 https://stackoverflow.com/a/30005099/841108其中提到了 GNUglibc and musl-libc。也看看里面tcmalloc http://goog-perftools.sourceforge.net/doc/tcmalloc.html，所以研究一下源码several自由软件 malloc 实现。

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

• 使用从操作系统检索内存mmap（并最终将其释放回操作系统内核munmap）。您当然不应该分配固定大小的堆（因为在具有 128GB RAM 的 64 位计算机上，您希望成功地malloc- 100 亿字节的区域）。
• 将小分配与大分配分开，因此以不同方式处理malloc16 个字节来自malloc一兆字节。小分配和大分配之间的典型阈值通常是page http://en.wikipedia.org/wiki/Page_%28computer_memory%29大小（通常为 4Kbytes）。小的分配发生在页面内部。大的分配会四舍五入到页面。你甚至可能会非常特别地处理malloc两个单词（就像许多链表一样）。
• 将请求的大小四舍五入为某个奇数（例如 2 的幂，或 2 的 3 次幂）。
• 一起管理相似大小的内存区域，即具有相同的“奇特”大小。
• 对于小内存区域，避免过早回收内存区域，因此保留之前的内存区域free-d 相同（小）大小的区域，以便在将来的调用中重用它们malloc.
• 您可能会在地址上使用一些技巧（但您的系统可能有ASLR http://en.wikipedia.org/wiki/Address_space_layout_randomization），或者在每个内存区域附近保留一个描述其所属块的元数据字。
• 一个重要的问题是，考虑到之前返回的一些地址malloc和论证free，找出该内存区域的分配大小。您可以操作地址位，您可以在之前的字中存储该大小，您可以使用一些哈希表等。详细信息are tricky.

请注意，细节很棘手，并且可能很难编写malloc实施比您的系统更好。在实践中，写出好的malloc is not一个简单的任务。您应该找到许多关于该主题的学术论文。

也看看垃圾收集 http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29技术。或许考虑一下Boehm 的保守 GC http://www.hboehm.info/gc/: 你将替换malloc by GC_MALLOC你不会担心free... 学习关于内存池 http://en.wikipedia.org/wiki/Memory_pool.