通过 Growing Buffers 避免数据拷贝

Growing Buffers to Avoid Copying Data

Source | HN Comments

文章探讨了通过“Growing Buffers”技术避免数据拷贝，以提升程序性能。核心思想是，在C++中，通过自定义`resize_buffer`函数，利用操作系统提供的`mmap` (Linux) 或 `VirtualAlloc` (Windows) 等机制，尝试原地调整缓冲区大小，避免数据复制。文章还对比了不同实现方式的性能，并指出了该技术可能遇到的问题，如虚拟内存碎片、系统兼容性等。最后，强调了在实际应用中需要谨慎测试和实现。

Johnny's Software Lab 我们帮助你交付快速的软件

通过 Growing Buffers 避免数据拷贝

发布于 2025年3月31日作者 Ivica Bogosavljević 发布在 Standard Library and Performance 发表评论

Johnny’s Software Lab LLC 是性能方面的专家。如果性能是您软件项目中关注的问题，请随时联系我们。

在某些情况下，复制数据的代价可能很高，特别是当它不改变数据，只是移动数据时。因此，我们这些对性能感兴趣的工程师，希望尽可能避免复制数据。

我们之前已经讨论过在 C++ 中避免数据复制。在那篇文章中，我们讨论了 C++ 在避免或最小化复制方面提供了哪些机制。在这篇文章中，我们将更多地关注操作系统可以为我们提供什么来避免数据复制。

简单介绍

在 C 库的内存分配函数中，有一个函数很特别：realloc。此函数允许我们增长或缩小使用 malloc 或 calloc 分配的缓冲区：如果 realloc 可以就地完成，它将避免复制数据。否则，它将分配一个新缓冲区，将数据复制到那里，然后释放旧缓冲区。

如果您正在使用 C，这就是您所需要的。在 C++ 中，事情变得复杂起来。C++ 没有专门的 realloc 函数。它只为用户提供 new 和 delete。容器使用 std::allocator 来分配内存，但同样，那里没有缓冲区增长可用。

如果您需要增长缓冲区，您可以选择使用 realloc 自定义容器实现。但是，存在非平凡可复制类型的问题：某些类型不能使用 realloc 复制，而是需要正确构造和销毁它们。因此，对于某些类型，realloc 甚至不是一种选择。相反，需要手动构造 new-destroy old 序列才能使事情正常工作。

用于扩大缓冲区的 API

如果我们想在 C++ 中避免复制，我们需要一个名为 resize_buffer 的函数，其签名如下：

bool resize_buffer(void* ptr, size_t new_size)

此函数尝试就地调整缓冲区的大小。如果成功，它将返回 true，并且不需要复制。如果失败，它将返回 false，我们需要分配另一个缓冲区，将数据移动到那里，然后使用 free 释放此缓冲区。

此函数不存在；尽管如此，我们将在本文中尝试构建它！

您需要在您的项目中讨论性能问题吗？或者您是否需要为您自己或您的团队提供向量化培训？联系我们或在 LinkedIn , Twitter 或 Mastodon 上关注我们，并在新内容发布后立即收到通知。

如何构建 `resize_buffer`？

如果您正在处理小于内存页面大小（通常为 4 kB）的缓冲区，并且您想为所有缓冲区大小实现 resize_buffer，这可能会带来巨大的内存开销。本质上，您需要保留整个内存页面（例如 4 kB）以允许您的缓冲区从 1 字节增长到 4 kB。

增长较大的缓冲区更容易。具有虚拟内存支持的常见 64 位系统（基本上是所有桌面和服务器 CPU 以及一些更强大的嵌入式 CPU）具有 2^48 位或 256x4GB 数据的内存地址空间。如果我们要分配一个可增长的缓冲区，我们需要在此空间中的某个位置选择一个地址，在该地址分配我们的缓冲区。假设我们选择了地址 X，并且缓冲区的大小为 1 MB。

现在假设我们想将缓冲区从 1 MB 增长到 4 MB。为了实现这一点，需要满足以下条件：

从地址 X + 1MB 到 X + 3 MB 的虚拟内存需要未使用 - 之前没有人应该分配此虚拟内存空间。
系统应该有额外的 3 MB 物理内存来备份虚拟内存

然后，我们可以要求操作系统将原始虚拟内存块从 X + 1 MB 扩展到 X + 3 MB。或者，我们可以要求操作系统在地址 X + 1 MB 处分配一个新的 3 MB 内存块。

在 32 位系统上增长缓冲区是相同的，除了我们有 4 GB 的虚拟内存空间可供使用，而不是 256×4 GB。在这里也可以增长内存，但是我们想要增长到的虚拟地址空间被其他人使用的可能性要大得多。

在 Linux 上

在 Linux 上，内存使用 mmap 系统调用分配。此调用返回一个内存块，该内存块是页面大小的倍数（以字节为单位的大小，但实际分配的内存将向上舍入到页面大小的倍数，因此例如 20 字节的分配实际上将是 4 kB 的分配）。以下是如何使用 mmap 分配内存的示例：

void * res = mmap(base_addr, size, PROT_READ | PROT_WRITE,
        MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

重要的参数是 base_addr，它向 mmap 建议我们想要使用的地址 - 如果是 nullptr，操作系统将为我们选择一个地址；否则，操作系统将尝试分配指定的地址（如果四舍五入到页面大小）。

不幸的是，在我们的测试环境中，我们无法让 Linux 为我们选择基本地址：如果我们这样做，下次调用 mremap 将会失败。失败的原因是 mmap 试图保守 - 它会在您的块之后保留内存，因此您的块无法增长。

因此，我们必须为 mmap 提供基本地址，以使分配的块可增长。

在 Windows 上

Windows 上缺少对增长缓冲区的内置支持，类似于 Linux 上的 mremap。Windows 上没有与 mremap 等效的功能。幸运的是，我们可以解决这个问题。

Linux mmap 的等效项是 VirtualAlloc。函数 mremap 不存在，但是我们可以分配连续的虚拟内存块，并且出于用户程序的需要，将它们视为一个连续的块。因此，要分配内存，我们将使用：

ptr0 = VirtualAlloc(base_ptr, size0, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);

然后附加额外的 VirtualAlloc 调用以使其增长：

ptr1 = VirtualAlloc(ptr0 + size0, increment1, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
ptr2 = VirtualAlloc(ptr1 + increment1, increment2, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);

在释放这样的内存时，我们一定不要忘记为每个指针 ptr0, ptr1 ... 调用 VirtualFree。这意味着我们需要维护所有指针的列表，并在不再需要它们时正确地处置它们（顺便说一句，如果您不想使用 mremap，则可以在 Linux 上使用相同的方法）。

系统分配器支持调整内存缓冲区的大小？

如前所述，标准库不提供允许您调整缓冲区大小的 API。唯一这样做的分配器是 jemalloc – 系统 malloc 和 free 的直接替代品。它提供了一个具有以下签名的函数：

size_t allocated_size = xallocx(old_ptr, new_size, 0, 0);

如果成功，该函数将增长（或缩小您的缓冲区）。如果 new_size <= allocated_size，则该函数将成功。该函数听起来像是 C 标准库中应该拥有的东西。

实验

我想了解避免复制可以节省多少时间。为此，我编写了一个简单的 jsl::vector 实现，该实现与 std::vector 类似。当我们向向量中推送新数据时，如果没有足够的空间用于新数据，则向量将增长。与 std::vector 的不同之处在于，jsl::vector 首先尝试调整底层缓冲区的大小以避免复制，并且只有在失败时，它才会分配新缓冲区。源代码可在此处获得 here。

我们实现了四种类型的分配：

Simple：不重新增长。在 Linux 和 Windows 上均有效。
Resize：如果可能，通过分配另一个相邻的内存块来重新增长。在 Linux 和 Windows 上均有效。
Posix：使用 mremap 重新增长。仅在 Linux 上有效。
Jemalloc：使用 jemalloc 中的 xallocx 调用重新增长。在 Linux 和 Windows 上均有效，但我们仅在 Linux 上进行了测试。

我们测试了使用 push_back 方法将 256M 个值写入 jsl::vector<float> 中，而没有 reserve。Linux 和 Windows 系统不同，因此不直接可比。这是 Linux 系统上的运行时（g++，10 次重复，平均时间）：

配置 | 运行时 ---|--- std::vector | 0.998 s Simple | 0.899 s Resize | 0.495 s Posix | 0.522 s Jemalloc | 0.547 s

就数字而言，避免复制绝对是值得的。Resize 和 Posix 配置都能够完全避免复制，并将其字节从 0 增长到 256 M。另一方面，Jemalloc 无法增长缓冲区，并且需要进行一些复制：必须复制小缓冲区（小于 32 kB），并且偶尔，调整较大缓冲区的大小也会失败：在 15 次连续增长尝试（从大小 X 到大小 2X）中，有 4 次失败。

相同的测量，在带有 MSVC 编译器的 Windows 上：

配置 | 运行时 ---|--- std::vector | 0.64 s Simple | 0.54 s Resize | 平均值：0.415 s，但是有两个数字的结果聚集在一起：0.46 s（6 次测量）0.34 s（4 次测量）

同样，我们在这里看到了类似的行为。调整缓冲区大小而不是复制有所帮助，但不如在 Linux 上那么有效。我们注意到在 Resize 中，我们实际上有两个数字。原因是 Windows 上的 Resize 无法就地增长缓冲区 - 有时 VirtualAlloc 无法分配我们缓冲区增长所需的内存地址，因此我们需要复制它。如果发生在缓冲区相对较小的情况下 - 我们会得到较短的运行时。如果发生在缓冲区较大的情况下 - 我们会得到较长的运行时。

缓冲区增长的问题？

我故意描绘了一幅没有过多细节的图画。这会出错吗？绝对可以。以下是一些可能的问题，我既在撰写本文时遇到过，或者如果您尝试将此方法用于许多缓冲区，则可能会发生以下问题，根据我的经验：

在不同系统上的不同行为：您可能会测试此方法，并且它在您的开发系统上有效，但是当您尝试在生产系统上运行它时，它会失败。在最坏的情况下，系统可能会遇到虚拟内存短缺，即使有足够的物理内存。
静默失败：如果此方法失败，它将是静默的。您改善性能的努力将白费。
虚拟空间碎片：为了允许缓冲区增长，您的缓冲区将彼此远离。这导致虚拟地址空间碎片和较低的性能，原因有两个：（1）操作系统需要更多时间来分配和释放内存，并且（2）将会有更多的数据缓存未命中和 TLB 缓存未命中，这可能导致系统整体缓慢，而没有明显的原因。
mmap 怪癖：我们需要为 mmap 提供基本地址，以便以后 mremap 成功。这引入了我们程序中内存管理的问题：现在我们的程序必须决定它希望如何安排内存中的缓冲区，这并非易事。在此实验中，我们为 mmap 选择了一个随机地址，但这绝对不是希望增长的许多缓冲区的好解决方案。
VirtualAlloc 怪癖：Windows 的分配函数并非没有自身的问题。尽管 VirtualAlloc 以页面大小分配内存，但缓冲区只能在 SYSTEM_INFO::dwAllocationGranularity 的倍数的偏移量处开始，在 Windows 11 上为 64 kB。因此，我们需要以 64 kB 的块分配我们的内存才能增长它们，这进一步导致更多的内存浪费。
无法很好地扩展：想象一下有成千上万的分配可能增长。在存在许多分配的情况下，维护缓冲区增长的潜力可能非常具有挑战性。
未标准化：这在不同的系统上以不同的方式工作，如果您希望将其移植到不同的系统，则需要非常小心。