我正在编写自己的简单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
一些一般想法:
请注意,细节很棘手,编写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”中的所有内容都在堆中保持关闭)。
另一个重要的优化包括“缓存着色”(请参阅https://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
实现所使用的算法。
需要了解更多c/c++开发分享改进malloc()算法的下一步是什么?,也可以关注C/ C++技术分享栏目—计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享改进malloc()算法的下一步是什么?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/979602.html