c - 固定大小类型的动态分配

Question

假设我们有一些固定长度的数据类型，例如 C 结构:

struct T
{
    ...;
}

分配 T 的一种方法是:

T* create_t() { return (T*) malloc(sizeof(T)); }

并解除分配:

void destroy_t(T* t) { free(t); }

在底层，malloc 使用一种内存分配算法，以不同的方式处理不同大小的 block 。

假设我们正在编写一个频繁调用 create_t 和 destroy_t 的程序，并且一次分配了很多 T 个项目(并且以伪随机顺序)。

鉴于所需的内存是固定大小的元素，是否可以编写优于 malloc 的通用实现的自定义内存分配方案。

例如，我们可以预先分配一个包含大小为 T 的元素的巨大数组，然后使用它们，但是跟踪哪些元素已分配哪些元素未分配的最佳方法是什么？

当使用大量相同大小的分配调用时，Linux 上的 malloc 最终使用什么算法？

与通用 malloc 相比，此自定义方法的性能大致如何？

Answer 1

至于 #1 — 其他人已经处理过，简而言之，glibc 做得相当好，而其他 mallocs 在各种情况下可能做得更好。

但是，关于您的第二个问题:定制的性能如何？

• 通常，了解应用程序自身使用模式和需求的自由列表分配器的手工编码低级实现可能会优于 GNU libc 提供的通用算法；

• 但您必须通过编写来证明这一点。

在Custom malloc for lots of small, fixed size blocks?有一些相关的回答, 顺便说一下。

您还可以查看各种文件系统驱动程序中磁盘扇区使用情况的表示，因为它们有效地解决了同一件事——固定大小的 block /扇区在各种负载下以伪随机间隔分配——而大多数 malloc 将专注于是通用的。