c - 实现用户定义的 malloc() 函数？

Question

如何创建一个用 C 语言定义的新的 malloc() 函数？

我什至没有关于如何做到这一点的 Sprite 提示，如何将虚拟空间地址映射到物理空间，遵循什么算法？我知道 malloc() 效率不高，因为它会导致碎片。所以可以创建一些有效的东西。即使效率不高，如何实现一个朴素的 C malloc 函数？

最近在采访中被问到。

Answer 1

维基百科实际上提供了各种 malloc 实现的一个很好的总结，包括针对特定条件优化的实现，以及用于了解有关实现的更多信息的链接。

http://en.wikipedia.org/wiki/C_dynamic_memory_allocation

dlmalloc

A general-purpose allocator. The GNU C library (glibc) uses an allocator based on dlmalloc.

jemalloc

In order to avoid lock contention, jemalloc uses separate "arenas" for each CPU. Experiments measuring number of allocations per second in multithreading application have shown that this makes it scale linearly with the number of threads, while for both phkmalloc and dlmalloc performance was inversely proportional to the number of threads.

Hoard memory allocator

Hoard uses mmap exclusively, but manages memory in chunks of 64 kilobytes called superblocks. Hoard's heap is logically divided into a single global heap and a number of per-processor heaps. In addition, there is a thread-local cache that can hold a limited number of superblocks. By allocating only from superblocks on the local per-thread or per-processor heap, and moving mostly-empty superblocks to the global heap so they can be reused by other processors, Hoard keeps fragmentation low while achieving near linear scalability with the number of threads.

tcmalloc

Every thread has local storage for small allocations. For large allocations mmap or sbrk can be used. TCMalloc, a malloc developed by Google, has garbage-collection for local storage of dead threads. The TCMalloc is considered to be more than twice as fast as glibc's ptmalloc for multithreaded programs.

dmalloc (维基百科未涵盖)

The debug memory allocation or dmalloc library has been designed as a drop in replacement for the system's malloc, realloc, calloc, free and other memory management routines while providing powerful debugging facilities configurable at runtime. These facilities include such things as memory-leak tracking, fence-post write detection, file/line number reporting, and general logging of statistics.