ChatGPT解决这个技术问题 Extra ChatGPT

为什么 malloc+memset 比 calloc 慢?

众所周知,callocmalloc 的不同之处在于它初始化了分配的内存。使用 calloc,内存设置为零。使用 malloc,不清除内存。

所以在日常工作中,我将calloc视为malloc+memset。顺便说一下,为了好玩,我为基准测试编写了以下代码。

结果令人困惑。

代码 1:

#include<stdio.h>
#include<stdlib.h>
#define BLOCK_SIZE 1024*1024*256
int main()
{
        int i=0;
        char *buf[10];
        while(i<10)
        {
                buf[i] = (char*)calloc(1,BLOCK_SIZE);
                i++;
        }
}

代码 1 的输出:

time ./a.out  
**real 0m0.287s**  
user 0m0.095s  
sys 0m0.192s  

代码 2:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define BLOCK_SIZE 1024*1024*256
int main()
{
        int i=0;
        char *buf[10];
        while(i<10)
        {
                buf[i] = (char*)malloc(BLOCK_SIZE);
                memset(buf[i],'\0',BLOCK_SIZE);
                i++;
        }
}

代码 2 的输出:

time ./a.out   
**real 0m2.693s**  
user 0m0.973s  
sys 0m1.721s  

将代码 2 中的 memset 替换为 bzero(buf[i],BLOCK_SIZE) 会产生相同的结果。

我的问题是:为什么 malloc+memsetcalloc 慢这么多? calloc 如何做到这一点?


J
Jonathan Leffler

简短版本:始终使用 calloc() 而不是 malloc()+memset()。在大多数情况下,它们是相同的。在某些情况下,calloc() 会做更少的工作,因为它可以完全跳过 memset()。在其他情况下,calloc() 甚至可以作弊而不分配任何内存!但是,malloc()+memset() 将始终完成全部工作。

理解这一点需要对内存系统进行简短的了解。

快速浏览内存

这里有四个主要部分:程序、标准库、内核和页表。你已经知道你的程序,所以...

malloc()calloc() 这样的内存分配器主要用于进行小型分配(从 1 字节到 100 KB 的任何内容)并将它们分组到更大的内存池中。例如,如果您分配 16 个字节,malloc() 将首先尝试从其中一个池中获取 16 个字节,然后在池耗尽时向内核请求更多内存。但是,由于您要询问的程序一次分配大量内存,malloc()calloc() 将直接从内核请求该内存。此行为的阈值取决于您的系统,但我看到 1 MiB 用作阈值。

内核负责为每个进程分配实际的 RAM,并确保进程不会干扰其他进程的内存。这被称为内存保护,自 1990 年代以来它一直很常见,这就是为什么一个程序可以在不关闭整个系统的情况下崩溃的原因。因此,当程序需要更多内存时,它不能只占用内存,而是使用像 mmap()sbrk() 这样的系统调用向内核请求内存。内核会通过修改页表给每个进程分配内存。

页表将内存地址映射到实际的物理 RAM。在 32 位系统上,您的进程地址(从 0x00000000 到 0xFFFFFFFF)不是实际内存,而是虚拟内存中的地址。处理器将这些地址划分为 4 KiB 页,通过修改页表可以将每个页分配到不同的物理 RAM 中。只有内核被允许修改页表。

它是如何不起作用的

以下是分配 256 MiB 不起作用的原因:

您的进程调用 calloc() 并请求 256 MiB。标准库调用 mmap() 并要求 256 MiB。内核找到 256 MiB 的未使用 RAM 并通过修改页表将其提供给您的进程。标准库使用 memset() 将 RAM 归零并从 calloc() 返回。您的进程最终会退出,内核会回收 RAM,以便其他进程可以使用它。

它实际上是如何工作的

上述过程会起作用,但它不会以这种方式发生。有三个主要区别。

当您的进程从内核获取新内存时,该内存可能已被其他进程使用过。这是一个安全风险。如果那个记忆有密码、加密密钥或秘密莎莎食谱怎么办?为了防止敏感数据泄漏,内核总是在将内存提供给进程之前对其进行清理。我们不妨通过清零来清理内存,如果新内存被清零,我们不妨将其作为保证,因此 mmap() 保证它返回的新内存总是清零。

有很多程序分配内存但不立即使用内存。有时内存已分配但从未使用过。内核知道这一点并且很懒惰。当您分配新内存时,内核根本不会接触页表,也不会给您的进程提供任何 RAM。相反,它会在您的进程中找到一些地址空间,记下应该去那里的内容,并承诺如果您的程序实际使用它,它将把 RAM 放在那里。当您的程序尝试从这些地址读取或写入时,处理器会触发页面错误,并且内核会介入以将 RAM 分配给这些地址并恢复您的程序。如果您从不使用内存,则永远不会发生页面错误,并且您的程序永远不会真正获得 RAM。

一些进程分配内存然后从它读取而不修改它。这意味着跨不同进程的内存中的许多页面可能会被 mmap() 返回的原始零填充。由于这些页面都是相同的,内核使所有这些虚拟地址指向一个共享的 4 KiB 内存页面,其中填充了零。如果您尝试写入该内存,处理器会触发另一个页面错误,并且内核会介入,为您提供一个新的零页面,该页面不与任何其他程序共享。

最终过程看起来更像这样:

您的进程调用 calloc() 并请求 256 MiB。标准库调用 mmap() 并要求 256 MiB。内核找到 256 MiB 的未使用地址空间,记下该地址空间现在用于什么,然后返回。标准库知道 mmap() 的结果总是用零填充(或者一旦它实际获得了一些 RAM),因此它不会触及内存,因此不会出现页面错误,并且永远不会给出 RAM到你的过程。您的进程最终会退出,并且内核不需要回收 RAM,因为它从一开始就没有被分配。

如果您使用 memset() 将页面归零,memset() 将触发页面错误,导致 RAM 被分配,然后将其归零,即使它已经用零填充。这是一项巨大的额外工作,并解释了为什么 calloc()malloc()memset() 快。如果您最终还是使用了内存,calloc() 仍然比 malloc()memset() 快,但差异并不是那么可笑。

这并不总是有效

并非所有系统都有分页虚拟内存,因此并非所有系统都可以使用这些优化。这适用于 80286 等非常古老的处理器以及对于复杂的内存管理单元来说太小的嵌入式处理器。

这也不适用于较小的分配。对于较小的分配,calloc() 从共享池中获取内存,而不是直接进入内核。通常,共享池中可能存储有旧内存中的垃圾数据,这些旧内存已被 free() 使用和释放,因此 calloc() 可以获取该内存并调用 memset() 将其清除。常见的实现将跟踪共享池的哪些部分是原始的并且仍然用零填充,但并非所有实现都这样做。

消除一些错误的答案

根据操作系统的不同,内核在空闲时间可能会或可能不会将内存归零,以防您稍后需要获得一些归零的内存。 Linux 不会提前将内存归零,Dragonfly BSD recently also removed this feature from their kernel。但是,其他一些内核会提前执行零内存。无论如何,在空闲期间将页面归零并不足以解释巨大的性能差异。

calloc() 函数没有使用 memset() 的一些特殊的内存对齐版本,这不会让它变得更快。现代处理器的大多数 memset() 实现看起来像这样:

function memset(dest, c, len)
    // one byte at a time, until the dest is aligned...
    while (len > 0 && ((unsigned int)dest & 15))
        *dest++ = c
        len -= 1
    // now write big chunks at a time (processor-specific)...
    // block size might not be 16, it's just pseudocode
    while (len >= 16)
        // some optimized vector code goes here
        // glibc uses SSE2 when available
        dest += 16
        len -= 16
    // the end is not aligned, so one byte at a time
    while (len > 0)
        *dest++ = c
        len -= 1

所以您可以看到,memset() 非常快,而且对于大内存块,您并不会真正获得更好的结果。

memset() 正在将已经归零的内存归零这一事实确实意味着内存被归零了两次,但这只能解释 2 倍的性能差异。这里的性能差异要大得多(我在我的系统上测量了 malloc()+memset()calloc() 之间的三个数量级以上)。

派对把戏

不要循环 10 次,而是编写一个分配内存的程序,直到 malloc()calloc() 返回 NULL。

如果添加 memset() 会发生什么?


@Dietrich:Dietrich 关于操作系统为 calloc 多次分配相同的零填充页面的虚拟内存解释很容易检查。只需添加一些循环,在每个分配的内存页中写入垃圾数据(每 500 个字节写入一个字节就足够了)。总体结果应该会变得更接近,因为在这两种情况下系统将被迫真正分配不同的页面。
@kriss:确实,尽管在绝大多数系统上每 4096 个字节就足够了
@mirabilos:实际上,实现往往更加复杂。 mmap() 分配的内存以大块的形式分配,因此 malloc() / calloc() 实现可能会跟踪哪些块仍然是原始的并且充满了零。所以calloc()即使没有从mmap()获取内存也可以避免接触内存,即它已经是堆的一部分但还没有被使用。
@mirabilos:我还看到了具有“高水位标记”的实现,其中超过某个点的地址被归零。我不确定你所说的“容易出错”是什么意思——如果你担心应用程序会写入未分配的内存,那么除了使用 mudflap 对程序进行检测之外,你几乎无法防止潜在的错误。
虽然与速度无关,但 calloc 也不太容易出错。也就是说,如果 large_int * large_int 会导致溢出,则 calloc(large_int, large_int) 返回 NULL,但 malloc(large_int * large_int) 是未定义的行为,因为您不知道要返回的内存块的实际大小。
C
Chris Lutz

因为在许多系统上,在空闲处理时间,操作系统会自行将空闲内存设置为零并将其标记为对 calloc() 安全,因此当您调用 calloc() 时,它可能已经有空闲的归零内存给您.


你确定吗?哪些系统可以做到这一点?我认为大多数操作系统只是在处理器空闲时关闭处理器,并根据需要将内存归零,以便在写入该内存时立即分配(但不是在分配时)。
@Dietrich - 不确定。我听说过一次,这似乎是一种使 calloc() 更有效率的合理(而且相当简单)的方法。
@Pierreten - 我找不到任何关于 calloc() 特定优化的好信息,而且我不想为 OP 解释 libc 源代码。您可以查找任何内容以表明此优化不存在/不起作用吗?
@Dietrich:FreeBSD 应该在空闲时间对页面进行零填充:请参阅它的 vm.idlezero_enable 设置。
@DietrichEpp 抱歉死了,但例如 Windows 会这样做。
S
Stewart

在某些平台上,在某些模式下,malloc 在返回之前将内存初始化为一些通常非零的值,因此第二个版本可以很好地初始化内存两次