改进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通常构建在低级内存相关的系统调用之上（例如Linux上的mmap（2） ）。 看到这个答案提到了GNU glibc和musl-libc 。 看看tcmalloc里面，所以研究几个免费软件malloc实现的源代码。
你的malloc一些一般想法：
- 使用
mmap从操作系统中检索内存（并最终使用munmap将其释放回操作系统内核）。 你当然不应该分配一个固定大小的堆（因为在具有128G字节RAM的64位计算机上，你希望成功地在一个100亿字节的区域内成功）。 - 将小分配与大分配分开，因此处理来自一兆字节的
malloc的16字节的malloc。 小分配和大分配之间的典型阈值通常是页面大小的小倍数（通常为4K字节）。 页面内部发生小分配。 大型分配四舍五入到页面。 你甚至可能特别处理两个单词的malloc（就像许多链表一样）。 - 将所要求的大小向上舍入到一些奇特的数字（例如，2的幂，或2的幂的3倍）。
- 管理相似大小的内存区域，具有相同的“花式”大小。
- 对于小内存区域，避免过早回收内存区域，因此请保留以前相同（小）大小的
free区域，以便在将来调用malloc重用它们。 - 您可能会在地址上使用一些技巧（但您的系统可能具有ASLR ），或者在每个内存区域附近保留一个描述其所属组块的元数据。
- 一个重要的问题是，给定一些先前由
malloc返回的地址和free参数，以找出该内存区域的已分配大小。 您可以操作地址位，您可以在之前的单词中存储该大小，您可以使用一些哈希表等。详细信息很棘手。
请注意，细节很棘手，编写malloc实现可能比系统更好。 在实践中，编写好的malloc 并不是一项简单的任务。 你应该找到很多关于这个主题的学术论文。
另请参阅垃圾收集技术。 考虑一下Boehm的保守GC ：您将用GC_MALLOC替换malloc并且您不会为free而烦恼…了解内存池 。
有三种方法可以改进：
- 使它更健壮
- 优化内存分配方式
- 优化分配内存的代码
让它更健壮
有许多常见的程序员错误可以很容易地被检测到（例如，修改超出分配块结束的数据）。 对于一个非常简单（且相对较快）的例子，可以在分配的块之前和之后插入“canaries”，并在free和realloc期间通过检查canary是否正确来检测程序员（如果它们不是那么程序员已经被删除）一些错误的东西）。 这只适用于“有时可能”。 问题是（对于malloc的简单实现），元数据与分配的块混合在一起; 因此，即使金丝雀没有，元数据也有可能被破坏。 要解决这个问题，将元数据与已分配的块分开是个好主意。 此外，仅报告“某些内容已损坏”并没有像您希望的那样有所帮助。 理想情况下，您希望为每个块提供某种标识符（例如，分配它的函数的名称），以便在出现问题时，您可以报告已损坏的内容。 当然，这可能/应该通过。 一个宏，以便在不调试时可以省略这些标识符。
这里的主要问题是malloc提供的接口是蹩脚和破坏的 – 根本没有办法返回可接受的错误条件（“失败分配”是它可以返回的唯一错误）并且无法传递其他信息。 你需要更像int malloc(void **outPointer, size_t size, char *identifier) （对free和realloc类似改动使它们能够返回状态代码和标识符）。
优化分配内存的方式
假设所有内存都是相同的，这是天真的。 不是。 缓存局部性（包括TLB局部性）和其他缓存效果，以及像NUMA优化这样的事情都很重要。 举一个简单的例子，想象一下你正在编写一个应用程序，它有一个描述一个人的结构（包括他们名字的哈希）和一个指向一个人名字串的指针; 并且结构和名称字符串都是通过分配的。 malloc的。 正常的最终结果是那些结构和字符串最终在堆中混合在一起; 因此，当您搜索这些结构时（例如，尝试查找包含正确哈希的结构），您最终会敲击缓存和TLB。 要正确优化这一点，您需要确保所有结构在堆中靠近。 为了工作， malloc需要为结构分配32个字节和为名称字符串分配32个字节之间的区别。 您需要引入“内存池”的概念（例如，“内存池编号1”中的所有内容都在堆中保持关闭）。
另一个重要的优化包括“缓存着色”（请参阅http://en.wikipedia.org/wiki/Cache_coloring ）。 对于NUMA系统，了解最大值之间的差异非常重要。 需要带宽（使用来自多个NUMA域的内存增加带宽）。
最后，对于“临时的，可能很快被释放”的分配和长期分配（例如，为了最大限度地减少碎片和浪费的空间/ RAM而需要额外的策略），使用不同的策略是很好的（管理堆碎片等） ）。
注意：我估计所有这一切都可能意味着在特定情况下软件运行速度提高20％，因为缓存丢失率更低，需要的带宽更多，等等。
这里的主要问题是malloc提供的接口是蹩脚和破坏的 – 首先没有办法将附加信息传递给malloc 。 你想要的东西更像int malloc(void **outPointer, size_t size, char *identifier, int pool, int optimisationFlags) （对realloc有类似的改动）。
优化分配内存的代码
鉴于您可以假设内存的使用频率高于其分配的内存; 这是最不重要的（例如，比正确分配块的缓存局部性更重要）。
坦率地说，任何真正想要体面性能或体面调试的人都不应该开始使用malloc针对特定问题的通用解决方案永远不会理想。 考虑到这一点（并且不要忘记malloc的界面是蹩脚和破坏并且无论如何都要防止一切重要）我建议不要费心去使用malloc并创建一些实际上很好（但非标准）的东西。 为此，您可以调整现有malloc实现所使用的算法。