2

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

struct T
{
    ...;
}

分配 T 的一种方法是：

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

并解除分配：

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

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

假设我们正在编写一个经常调用 create_t 和 destroy_t 的程序，并且一次分配了非常多的 T 个项目（并且以伪随机顺序）。

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

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

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

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

4

4 回答 4

3

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

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

• 一般而言，了解应用程序自身使用模式和需求的自由列表分配器的手工编码的低级实现可能会胜过像 GNU libc 提供的一般情况算法。

• 但是你必须通过写东西来证明它。

Custom malloc有一些相关答案，用于许多固定大小的小块？， 顺便一提。

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

于 2012-09-28T22:21:15.130 回答
2

首先，您可以有多个malloc. 例如，Glibc malloc（解释here）是here，但是musl libc malloc is here。C 动态内存实现的多样性是众所周知的。

还要注意一个简单的实现

void *malloc (size_t sz)
{
   errno = ENNOMEM;
   return 0;
}

可能符合malloc 标准规范（例如在 Posix 和 C99 中）的字母，但不符合精神。

实际上，它是通过系统调用（如mmap(2)和有时sbrk(2)等都与虚拟内存和地址空间相关的）向Linux 内核malloc询问一些内存块来实现的。由于ASLR ，您的程序运行一次到下一次运行的结果可能会有所不同。能够处理许多相同大小的分配，但是您最终可能会在运行时间很长的程序上产生内存碎片。munmap(2)mallocmalloc

您也可以使用例如glib 内存切片中的切片分配器，但它可能很少有用。您还可以使用Boehm 的保守垃圾收集器（例如，使用GC_malloc而不是显式地malloc打扰free您的数据）。

实际上，在 Linux 上，malloc效果很好。我认为你不应该为此烦恼。当然，它旨在最大限度地减少内存分配低级操作，例如mmap（这很昂贵；一个好的实现可以很好地管理内存池，并在从内核询问之前malloc尝试重新使用-d 内存）。free还有与多线程等相关的问题。

在担心降低malloc应用程序的成本之前，您应该测量它（valgrind很有用，也可以调试malloc相关的错误）。很多时候，成本malloc在应用程序中并不重要。如果你真的想要，你可以管理自己的记忆领域，但我不确定你应该打扰。（优化前先测量）。在当今的机器上，缓存考虑因素也对代码的实际性能起主导作用。

于 2012-09-28T22:07:02.350 回答
2

据我所知，所使用的内存管理是一种“桶”管理。

malloc将空闲内存段保存在桶中，并在被调用时尝试将最适合的块之一传递给调用者。

但是只需下载 libc 的源代码并自己查看即可。

而且编写内存管理是相当棘手的，并且在当前使用的算法上投入了大量精力。我确实相信很难（尤其是作为一个人）想出比所有这些人做得更好的东西。

于 2012-09-28T21:54:29.837 回答
0

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

答：也许吧。这可能是一项不平凡的工作。

任何给定的操作系统都可能有不同的“malloc()”实现。Linux 的标准（例如）是 Gnu Libc。你可以在这里找到源代码：

'希望有帮助！

于 2012-09-28T22:03:25.927 回答