使用自定义过度分配分配器利用 std::vector 结束后的内存

Question

假设我有一个分配器 my_allocator，当调用 allocate(n) 时，它将始终为 n+x（而不是 n）元素分配内存。

我可以假设 [data()+n, data()+n+x) 范围内的内存（对于 std::vector<T, my_allocator<T>>）是 accessible/valid 以供进一步使用（即放置新的或 simd loads/stores 以防万一基本面（只要没有重新分配）？

注意：我知道 data()+n-1 之后的所有内容都是未初始化的存储。用例将是一个基本类型的向量（无论如何都没有构造函数），使用自定义分配器来避免在向量中抛出 simd 内在函数时出现特殊的极端情况。 my_allocator 应分配 1.) 正确对齐且 2.) 大小是所用寄存器大小的倍数的存储。

为了让事情更清楚一点：

假设我有两个向量，我想将它们相加：

std::vector<double, my_allocator<double>> a(n), b(n);
// fill them ...
auto c = a + b;
assert(c.size() == n);

如果从 my_allocator 获得的存储现在分配对齐存储，并且如果 sizeof(double)*(n+x) 始终是使用的 simd 寄存器大小的倍数（因此是每个寄存器值数的倍数）我假设我可以做类似

的事情

for(size_t i=0u; i<(n+x); i+=y) 
{ // where y is the number of doubles per register and and divisor of (n+x)
    auto ma = _aligned_load(a.data() + i);
    auto mb = _aligned_load(b.data() + i);
    _aligned_store(c.data() + i,  _simd_add(ma, mb)); 
}

我不必关心任何特殊情况，例如未对齐的负载或来自某些 n 的积压，这些情况不能被 y 整除。

但是向量仍然只包含 n 个值，并且可以像大小为 n 的向量一样处理。

Answer 1

对于您的用例，您不应该有任何疑问。但是，如果您决定在额外 space 中存储任何有用的东西，并允许向量的大小在其生命周期内发生变化，您可能运行会遇到处理重新分配可能性的问题 - 如何假设重新分配是由于单独调用 allocate() 和 deallocate() 而它们之间没有直接连接而发生的，您打算将额外数据从旧分配转移到新分配吗？

编辑（解决添加到问题中的代码）

在我最初的回答中，我的意思是您访问分配器分配的超出请求的额外字节应该没有任何问题。然而，在内存范围内写入数据，即超出向量对象当前使用的范围但属于未修改分配跨越的范围，会带来麻烦。 std::vector 的实现可以自由地向分配器请求比通过其 size()/capacity() 函数公开更多的内存，并将辅助数据存储在未使用的区域中。虽然这是高度理论化的，但不考虑这种可能性意味着打开了通往未定义行为的大门。

考虑向量分配的以下可能布局：

---====================++++++++++------.........

=== - 向量的已用容量
+++ - 向量的未使用容量
--- - 向量过度分配（但未显示为其容量的一部分）
... - 分配器过度分配

您不得在区域 2 (---) 和区域 3 (+++) 中写入任何内容。您的所有写入都必须限制在区域 4 (...) 内，否则您可能会损坏重要位。

Answer 2

退后一步，如果您要解决的问题是允许 SIMD 内在函数或展开循环或两者有效地处理底层内存，则您不一定需要分配超出已用内存的内存相当于 "round off" 分配大小为矢量宽度的倍数。

有多种方法可以处理这种情况，您提到了几种方法，例如使用特殊的引入和引出代码来处理前导和尾随部分。这里实际上有两个不同的问题——处理数据不是向量宽度的倍数这一事实，以及处理（可能）未对齐的起始地址。您的过度分配方法正在解决第一个问题 - 但可能有更好的方法...

实践中的大多数 SIMD 代码可以简单地读取超出处理区域的末尾。有些人可能会争辩说，这在技术上是 UB - 但在使用 SIMD 内在函数时，您已经在尝试超越标准 C++ 的界限。事实上，这种技术在标准库中是，因此编译器和库维护者暗中认可它。它也是一般处理 SIMD 代码的标准方法，因此您可以非常确定它不会突然中断。

他们让它工作的关键是观察到如果你可以有效地读取某个位置的单个字节 N，那么任何 自然对齐的 读取任何大小¹ 都不会触发错误。当然，您仍然需要忽略或以其他方式处理您读取的超出正式分配区域末尾的数据 - 但无论如何您都需要使用 "allocate extra" 方法来做到这一点，对吗？根据算法的不同，您可以屏蔽掉无效数据，或者在 SIMD 部分完成后排除无效数据（即，如果您正在搜索一个字节，如果您在分配的区域之后找到一个字节，则与 "not found").

要完成这项工作，您需要以一致的方式阅读，但我认为这可能是您已经想做的事情。您可以安排让您的内存分配首先对齐，或者在开始时进行重叠读取（即，首先进行一次未对齐读取，然后全部与第一个对齐读取对齐，与未对齐部分重叠），或者使用相同的技巧作为 read before 数组的尾部（与为什么这是安全的推理相同）。此外，还有各种技巧可以在无需编写自己的分配器的情况下请求对齐内存。

总的来说，我的建议是尽量避免编写自定义分配器。除非代码被相当严格地包含，否则您可能运行陷入各种陷阱，包括其他代码对您的内存分配方式做出错误假设以及 Leon 在他的回答中提到的各种其他陷阱。此外，使用自定义分配器会禁用标准容器算法使用的一系列优化，除非你在任何地方都使用它，因为其中许多只适用于使用相同分配器的容器。

此外，当我实际实现自定义分配器时²，我发现这在理论上是一个不错的想法，但有点太晦涩难懂，无法在相同的环境中得到很好的支持所有编译器的时尚。现在编译器随着时间的推移变得更加顺从（我主要看你，Visual Studio），模板支持也有所改进，所以也许这不是问题，但我觉得它仍然属于这个类别共 "do it only if you must".

另请记住，自定义分配器组合不好 - 您只能得到一个！如果您项目中的其他人出于某种其他原因想要为您的容器使用自定义分配器，他们将无法执行此操作（尽管您可以协调并创建组合分配器）。

我之前问过的这个 - 也是受 SIMD 的启发 - 涵盖了很多关于阅读结束后（并且隐含地在开始之前）的安全性的基础知识，并且可能是一个好地方如果您正在考虑这个，请开始。

¹ 从技术上讲，限制是任何对齐读取到页面大小，4K 或更大的大小对于任何当前面向矢量的通用 ISA 来说都足够了。

² 在这种情况下，我这样做不是为了 SIMD，但基本上是为了避免 malloc() 并允许容器的部分堆栈和连续快速分配有很多小节点。

使用自定义过度分配分配器利用 std::vector 结束后的内存

Utilize memory past the end of a std::vector using a custom overallocating allocator

c++

language-lawyer

stdvector

allocator