改进 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 通常构建在较低级别的内存相关系统调用之上（例如 mmap(2) on Linux). See which mentions GNU glibc and musl-libc. Look also inside tcmalloc，因此请研究几个自由软件 malloc 实现的源代码.

对您 malloc 的一些一般性想法：

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

请注意，细节很棘手，可能很难编写比您的系统更好的 malloc 实现。实际上，写一个好的 malloc 不是一个简单的任务。你应该找到很多关于这个主题的学术论文。

另请查看 garbage collection techniques. Consider perhaps Boehm's conservative GC: you will replace malloc by GC_MALLOC and you won't bother about free... Learn about memory pools。

Answer 2

有 3 种改进方法：

让它更健壮
优化内存分配方式
优化分配内存的代码

让它更坚固

有许多很容易检测到的常见程序员错误（例如，修改超出分配块末尾的数据）。对于一个非常简单（且相对较快）的示例，可以在分配的块之前和之后插入 "canaries"，并在 free 和 realloc 期间通过检查金丝雀是否正确来检测程序员（如果不是，那么程序员就错误地丢弃了一些东西）。这仅适用于 "sometimes maybe"。问题是（对于 malloc 的简单实现）元数据与分配的块混合在一起；所以即使金丝雀没有，元数据也有可能被破坏。要解决这个问题，最好将元数据与分配的块分开。此外，仅报告 "something was corrupted" 并没有您希望的那么有用。理想情况下，您希望每个块都有某种标识符（例如分配它的函数的名称），以便 if/when 出现问题时您可以报告损坏的内容。当然这个could/should也许可以通过。一个宏，以便在不调试时可以省略这些标识符。

这里的主要问题是 malloc 提供的接口是蹩脚的和破损的 - 根本没有办法 return 可接受的错误条件（"failed to allocate" 是它唯一可以接受的错误return) 并且无法传递附加信息。你会想要更像 int malloc(void **outPointer, size_t size, char *identifier) 的东西（对 free 和 realloc 进行类似的改动，使它们能够 return 状态代码和标识符）。

优化内存分配方式

假设所有内存都相同是天真的想法。不是。缓存局部性（包括 TLB 局部性）和其他缓存效果，以及 NUMA 优化之类的东西，都很重要。举一个简单的例子，假设您正在编写一个应用程序，该应用程序具有一个描述人的结构（包括他们姓名的散列）和一个指向人名字符串的指针；并且结构和名称字符串都是通过分配的。分配。正常的最终结果是那些结构和字符串最终混合在堆中；因此，当您搜索这些结构时（例如，试图找到包含正确散列的结构），您最终会遇到高速缓存和 TLB。要正确优化它，您需要确保堆中的所有结构都靠近在一起。为此，malloc 需要区分为结构分配 32 个字节和为名称字符串分配 32 个字节之间的区别。您需要引入 "memory pools" 的概念（例如 "memory pool number 1" 中的所有内容都在堆中保持关闭）。

另一个重要的优化包括 "cache colouring"（参见 http://en.wikipedia.org/wiki/Cache_coloring）。对于 NUMA 系统，了解最大值之间的区别可能很重要。需要带宽（使用来自多个 NUMA 域的内存会增加带宽）。

最后，最好（管理堆碎片等）对 "temporary, likely to be freed soon" 分配和长期分配使用不同的策略（例如，在值得做额外工作以最小化碎片和浪费的地方 space/RAM).

注意：我估计，在特定情况下，获得所有这些权利可能意味着软件运行速度提高 20%，因为缓存未命中率大大降低，带宽增加需要等

这里的主要问题是 malloc 提供的接口是蹩脚的和破损的 - 首先根本没有办法将附加信息传递给 malloc。你会想要更像 int malloc(void **outPointer, size_t size, char *identifier, int pool, int optimisationFlags) 的东西（对 realloc 进行类似的改动）。

优化分配内存的代码

鉴于您可以假设内存的使用频率高于其分配的频率；这是最不重要的（例如，不如为分配的块正确获取缓存位置之类的东西重要）。

坦率地说，任何真正想要体面的性能或体面的调试的人都不应该使用 malloc 开始 - 针对特定问题的通用解决方案从来都不是理想的。考虑到这一点（并且不要忘记 malloc 的接口是蹩脚的和损坏的并且无论如何都会阻止所有重要的事情）我建议不要打扰 malloc 并创建一些实际上很好的东西（但不是-标准）代替。为此，您可以调整 malloc.

的现有实现所使用的算法

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

What are the next step to improve malloc() algorithm?

c

c++

algorithm

memory-management