如何安全地实现"使用未初始化的内存来获取乐趣和利润"？

Question

我想使用https://research.swtch.com/sparse中描述的技巧在C++中构建一个密集的整数集.这种方法通过允许自己读取未初始化的内存来实现良好的性能.

如何在不触发未定义行为的情况下实现此数据结构,并且不会与Valgrand或ASAN等工具发生冲突？

编辑:似乎响应者正在关注"未初始化"这个词,并在语言标准的上下文中对其进行解释.对我而言,这可能是一个糟糕的词语选择 - 这里"未初始化"仅意味着它的价值对于算法的正确运行并不重要.显然可以安全地实现这个数据结构(LLVM在SparseMultiSet中实现它).我的问题是,最好和最有效的方法是什么？

Answer 1

我可以看到您可以采取的四种基本方法。这些不仅适用于 C++，而且适用于大多数其他低级语言，如 C，它们使未初始化的访问成为可能但不允许，最后一种甚至适用于更高级别的“安全”语言。

无视标准，照常执行

这是律师最讨厌的一种疯狂把戏！不过不要惊慌 - 遵循此解决方案的解决方案不会违反规则，因此，如果您是遵守规则的人，请跳过这一部分。

该标准大部分使用未定义的未初始化值，并且它允许的少数漏洞（例如，将一个未定义的值复制到另一个）并没有真正为您提供足够的绳索来实际实现您想要的 - 即使在限制性稍低的 C 中（例如，参见涵盖 C11 的答案，它解释了虽然访问一个indeterminiate值可能不会直接触发UB，但任何结果也是不确定的，并且实际上该值可能看起来是访问访问的机会）。

因此，您无论如何都要实现它，并且知道大多数或所有当前编译器只会将其编译为预期的代码，并且知道您的代码不符合标准。

至少在我的所有测试中gcc，clang并icc没有利用非法访问来做任何疯狂的事情。当然，该测试并不全面，即使您可以构建一个测试，在新版本的编译器中行为也可能会发生变化。

如果访问未初始化内存的方法的实现在单独的编译单元中编译一次，那么您将是最安全的 - 这可以轻松检查它是否做正确的事情（只需检查一次程序集）并且几乎不可能（在 LTGC 之外）让编译器做任何棘手的事情，因为它无法证明是否正在访问未初始化的值。

尽管如此，这种方法在理论上是不安全的，您应该非常仔细地检查编译后的输出，并在您采用时采取额外的保护措施。

如果你采用这种方法，像这样valgrind的工具很可能会报告一个未初始化的读取错误。

现在这些工具在程序集级别工作，一些未初始化的读取可能没问题（例如，参见快速标准库实现的下一项），因此它们实际上并没有立即报告未初始化的读取，而是具有各种确定是否实际使用了无效值的启发式方法。例如，他们可以避免报告错误，直到他们确定未初始化的值用于确定条件跳转的方向，或根据启发式无法跟踪/恢复的某些其他操作。您可以让编译器发出读取未初始化内存但根据此启发式安全的代码。

更有可能的是，您将无法这样做（因为这里的逻辑相当微妙，因为它依赖于两个数组中的值之间的关系），因此您可以使用您选择的工具中的抑制选项来隐藏错误. 例如，valgrind 可以基于堆栈跟踪进行抑制- 事实上，在各种标准库中，默认情况下已经有许多此类抑制条目用于隐藏误报。

由于它基于堆栈跟踪工作，如果读取发生在内联代码中，您可能会遇到困难，因为每个调用站点的堆栈顶部都会不同。你可以通过确保函数没有内联来避免这种情况。

使用组装

标准中定义不明确的内容，通常在程序集级别有明确定义。这就是为什么编译器和标准库通常可以以比使用 C 或 C++ 更快的方式实现事物的原因：libc用汇编编写的例程已经针对特定架构，不必担心语言中的各种警告使事情在各种硬件上快速运行的规范。

通常，在汇编中实现任何大量代码都是一项成本高昂的工作，但在这里只是少数，因此根据您的目标平台数量，它可能是可行的。您甚至不需要自己编写方法 - 只需编译 C++ 版本（或使用Godbolt并复制程序集。is_member例如¹的函数如下所示：

sparse_array::is_member(unsigned long):
        mov     rax, QWORD PTR [rdi+16]
        mov     rdx, QWORD PTR [rax+rsi*8]
        xor     eax, eax
        cmp     rdx, QWORD PTR [rdi]
        jnb     .L1
        mov     rax, QWORD PTR [rdi+8]
        cmp     QWORD PTR [rax+rdx*8], rsi
        sete    al

依靠calloc魔法

如果您使用²，则您明确地从底层分配器请求清零内存。现在，正确版本的可能会简单地调用然后将返回的内存归零，但实际实现依赖于这样一个事实，即操作系统级内存分配例程（和，几乎）通常会在任何具有受保护内存的操作系统上返回归零内存（即，所有大的），以避免再次清零内存。calloccallocmallocsbrkmmap

作为一个实际问题，对于大的分配，这通常是mmap通过映射一个全零的特殊零页来实现像匿名这样的调用来满足的。当（如果有的话）内存被写入时，写时复制实际上会分配一个新页面。因此，大的、归零的内存区域的分配可能是免费的，因为操作系统已经需要将页面归零。

在这种情况下，在上面实现稀疏集calloc可能与名义上未初始化的版本一样快，同时安全且符合标准。

卡洛克注意事项

您当然应该进行测试以确保其calloc行为符合预期。优化的行为通常只会在您的程序大约“预先”初始化大量长期存在的归零内存时才会发生。也就是说，优化 calloc 的典型逻辑，如果是这样的：

calloc(N)
  if (can satisfy a request for N bytes from allocated-then-freed memory)
    memset those bytes to zero and return them
  else
    ask the OS for memory, return it directly because it is zeroed

基本上，malloc基础设施（也是底层new和朋友）有一个（可能是空的）内存池，它已经从操作系统请求并通常首先尝试在那里分配。该池由来自 OS 的最后一个块请求但未分发的内存组成（例如，因为用户请求了 32 个字节，但分配的块要求来自 OS 的块为 1 MB 块，因此还有很多剩余），以及分配给进程但随后通过free或delete或其他方式返回的内存。该池中的内存具有任意值，如果 acalloc可以从该池中得到满足，您就无法获得魔法，因为必须发生零初始化。

另一方面，如果必须从操作系统分配内存，您就会获得魔力。所以这取决于你的用例：如果你经常创建和销毁sparse_set对象，你通常只会从内部malloc池中提取并支付归零成本。如果您有一个sparse_set占用大量内存的长期对象，它们可能是通过询问操作系统来分配的，并且您几乎可以免费获得归零。

好消息是，如果您不想依赖上述calloc行为（实际上，在您的操作系统或您的分配器上甚至可能不会以这种方式进行优化），您通常可以通过/dev/zero手动映射来复制行为分配。在提供它的操作系统上，这可以保证您获得“便宜”的行为。

使用延迟初始化

对于完全与平台无关的解决方案，您可以简单地使用另一个跟踪数组初始化状态的数组。

首先，您选择一些颗粒，您将在其中跟踪初始化，并使用位图，其中每个位跟踪sparse数组的该颗粒的初始化状态。

例如，假设您选择的粒度为 4 个元素，并且数组中元素的大小为 4 个字节（例如，int32_t值）：您需要 1 位来跟踪每 4 个元素 * 4 字节/元素 * 8 位/字节，这是分配内存中不到 1% ³的开销。

现在，您只需在访问sparse. 这为访问sparse数组增加了一些小成本，但不会改变整体复杂性，并且检查仍然相当快。

例如，您的is_member函数现在看起来像：

bool sparse_set::is_member(size_t i){
    bool init = is_init[i >> INIT_SHIFT] & (1UL << (i & INIT_MASK));
    return init && sparse[i] < n && dense[sparse[i]] == i;
}

x86 (gcc) 上生成的程序集现在以：

mov     rax, QWORD PTR [rdi+24]
mov     rdx, rsi
shr     rdx, 8
mov     rdx, QWORD PTR [rax+rdx*8]
xor     eax, eax
bt      rdx, rsi
jnc     .L2
...

.L2：返回

这都是与位图检查相关的。这一切都会非常快（并且经常偏离关键路径，因为它不是数据流的一部分）。

一般来说，这种方法的成本取决于您的集合的密度，以及您正在调用的函数 -is_member这种方法的最坏情况是因为某些函数（例如，clear）根本不受影响，而其他函数（例如，iterate) 可以批量is_init检查，并且每个INIT_COVERAGE元素只执行一次（这意味着对于示例值，开销将再次约为 1%）。

有时这种方法会比 OP 链接中建议的方法更快，尤其是当处理元素不在集合中时 - 在这种情况下，is_init检查将失败并且通常会缩短剩余的代码，在这种情况下，您有一个工作集比sparse阵列的大小小得多（使用示例颗粒大小的 256 倍），因此您可以大大减少对 DRAM 或外部缓存级别的未命中。

对于这种方法，颗粒大小本身是一个重要的可调参数。直观地说，当第一次访问被颗粒覆盖的元素时，较大的颗粒大小会付出更大的初始化成本，但可以节省内存和前期is_init初始化成本。您可以想出一个公式，在简单的情况下找到最佳大小 - 但行为还取决于值和其他因素的“聚类”。最后，使用动态粒度大小来覆盖不同工作负载下的基础是完全合理的 - 但它是以可变转变为代价的。

真正懒惰的解决方案

值得注意的是calloc，lazy init解决方案和lazy init解决方案之间存在相似之处：两者都在需要时延迟初始化内存块，但是该calloc解决方案通过具有页表和TLB 条目的MMU 魔术在硬件中隐式跟踪这一点，而lazy init解决方案在软件中使用位图明确跟踪哪些颗粒已被分配。

硬件方法的优点是几乎免费（对于“命中”情况，无论如何），因为它使用 CPU 中始终存在的虚拟内存支持来检测未命中，但软件情况的优点是可移植并允许精确控制颗粒大小等。

您实际上可以结合这些方法，制作一种不使用位图的懒惰方法，甚至根本不需要dense数组：只需sparse使用mmapas分配您的数组PROT_NONE，这样每当您从未分配的页面读取时就会出错在一个sparse数组中。您捕获错误并为sparse数组中的页面分配一个标记值，该值指示每个元素“不存在”。

对于“热”情况，这是最快的：您不再需要任何... && dense[sparse[i]] == i检查。

缺点是：

• 您的代码确实不可移植，因为您需要实现故障处理逻辑，这通常是特定于平台的。
• 您无法控制粒度：它必须处于页面粒度（或其某个倍数）。如果您的集合非常稀疏（比如占用的 4096 个元素中少于 1 个）并且均匀分布，您最终会支付高昂的初始化成本，因为您需要处理错误并为每个元素初始化一整页的值。
• 未命中（即，对不存在的集合元素的非插入访问）要么需要分配页面，即使该范围内不存在元素，要么每次都非常慢（导致错误）。

¹此实现没有“范围检查” - 即，它不检查是否i大于MAX_ELEM- 根据您的用例，您可能想要检查它。我的实现使用了一个模板参数 for MAX_ELEM，这可能会导致代码稍微快一些，但也会导致更多的膨胀，并且您也可以将最大大小设为类成员。

²真的，唯一的要求是你使用一些在幕后调用calloc或执行等效的零填充优化的东西，但根据我的测试，更惯用的 C++ 方法就像new int[size]()只做分配后跟一个memset. gcc 确实优化malloc后跟memsetinto calloc，但是如果您无论如何都试图避免使用 C 例程，那没有用！

³准确地说，您需要额外的 1 位来跟踪sparse阵列的每 128 位。