自定义分配器和内存对齐

Question

我正在尝试实现自定义分配器以与 std 容器配合使用，具体要求在此处: https://en.cppreference.com/w/cpp/named_req/Allocator 我目前正在尝试实现一个线性分配器，但是在内存对齐方面遇到了困难。 在分配了一块内存后，我想知道每个对象之间需要多少填充，以优化 CPU 的读写。 我不确定地址对齐是否应该是可被以下内容整除：

- CPU 字长（32 位机器上的 4 个字节和 64 位机器上的 8 个字节） - sizeof(T) - alignof(T) 我在不同的地方阅读到了不同的答案。 例如，在 这个 问题中，被接受的答案说:

“通常的经验法则（直接从英特尔和 AMD 的优化手册中得出）是每种数据类型都应该按其自身大小对齐。int32 应该在 32 位边界上对齐，int64 在 64 位边界上对齐，等等。char 在任何位置都可以适合。”

因此，根据这个答案，地址对齐看起来应该是可以被 sizeof(T) 整除的。

在 这个 问题中，第二个答案说明:

“CPU 总是按照其字长读取（32 位处理器上为 4 字节），因此当您进行非对齐地址访问时，在支持它的处理器上，处理器将读取多个字。”

因此，根据这个答案，地址对齐看起来应该是可被 CPU 字长整除的。

因此，我看到了一些关于如何优化数据对齐以进行 CPU 读写的冲突陈述，不确定是否理解有误或是否存在错误的答案？也许有人可以为我澄清地址对齐应该被以下内容整除。

- Jorayen

---

这取决于你打算如何使用RAM，如果你分配大块内存，最好进行页面对齐。没有一种适用于所有情况的解决方案，这就是为什么编译器在编译时根据类型填充结构体，除非另有指示。如果你想在32位和64位实例中都保险起见，只需以64位对齐，尽管会浪费一些RAM。 - undefined

@Geoffrey 所以根据你的回答，我可以假设我应该将数据与 CPU 的字长对齐，而不是 sizeof(T) 吗？ - undefined

sizeof(T)可能是3个字节，这取决于类型，所以是的，请按照CPU字大小对齐。不过，如果你正在处理大块数据的副本，对齐到页面大小会更好。 - undefined

@Geoffrey 不，只是普通的对象数据。 另外，对齐方式是我传递给分配器的参数，所以我可以直接实例化它，而不是这样写：m_Alignment = sizeof(T*)，对吗？ 如果我按照4字节或8字节（取决于CPU字长）对齐，那么如果第一个地址可被4/8整除，是否总会有0填充？如果是这样的话，如果我能保证起始地址可被4/8整除，那么是否可以优化以确保在池中容纳更多的对象？如果是这样的话，我如何使用malloc来保证这种地址划分呢？ - undefined

Answer 1

作为一般的经验法则（即，除非你有充分的理由做出不同的选择），你希望将给定C++类型的元素对齐到它们的对齐方式，即alignof(T)。如果类型想要对齐到32位边界（如大多数常见的c++实现中的int），它将呈现适合的（4字节）对齐方式。

当然，在两个不同类型T的对象的基地址之间必须至少有sizeof(T)字节的空间，这通常是其对齐方式的整数倍（实际上很难将过度对齐的类型传递给模板函数，因为它会剥离任何外部的alignas属性）。

在大多数情况下，因此你只需要进行以下操作：找到底层存储中对齐到alignof(T)的第一个基地址，然后从那里开始每次按sizeof(T)前进。

This way, you will rely on the users of your allocator to tell you what they want. This is exactly what you want, as the optimizer may rely on knowledge about alignment and, e.g., emit SSE aligned loads for arrays of double-precision floats, which will cause your program to crash if they are aligned wrongly.

Going down the rabbit hole This gives rise to the following possible situations:

1. 简单类型，具有字长和字对齐（例如，int，sizeof(int) = 4 和 alignof(int) = 4）：

sizeof(T) = 4 and alignof(T) = 4
 0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F 
[aaaaaaaaaa][bbbbbbbbbb][cccccccccc][dddddddddd]

2. 大小是其对齐方式的倍数的类型（例如，using T = int[2]）。

sizeof(T) = 8 and alignof(T) = 4
 0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F 
[aaaaaaaaaaaaaaaaaaaaaa][bbbbbbbbbbbbbbbbbbbbbb]

3. 超对齐类型，其对齐方式大于其大小（例如：using T = alignas(8) char[3]）。这里存在风险！

sizeof(T) = 3 and alignof(T) = 8
 0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F 
[aaaaaaa]               [bbbbbbb]

请注意，过度对齐示例中存在未使用的空间。这是必要的，因为对齐到8字节边界的对象可能无法放置在其他位置，导致潜在的浪费。此类类型最常见的用途是针对特定CPU进行优化，例如防止伪共享。

最后，还有一种稍微奇怪的情况，即大小大于但不是其对齐方式的整数倍的对象（例如，using T = alignas(4) char[5];）。这基本上只是对过度对齐类型的前一个示例的小扩展：

sizeof(T) = 5 and alignof(T) = 4
 0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F 
[aaaaaaaaaaaaa]         [bbbbbbbbbbbbb]

虽然对齐可以使第二个对象位于基地址4，但那里已经有一个对象了。

将所有这些示例放在一起，类型T的两个对象之间需要的字节数为：

inline auto object_distance = sizeof(T) % alignof(T) == 0 ? sizeof(T) : sizeof(T) + (alignof(T) - sizeof(T) % alignof(T));

- danielschemmel

---

不是这样吗？auto object_distance = (sizeof(T) + alignof(T) - 1) / alignof(T) * alignof(T); 这实际上等同于 ceil(sizeof(T), alignof(T))。 - undefined

现在我使用-((int)sizeof(T)) & (alignment - 1)来计算填充，这对你展示的所有情况都有效。问题是alignment的值应该是多少。目前我使用alignment = sizeof(T*)来在4字节和8字节之间切换，具体取决于CPU的字长。我这样做是正确的吗？ - undefined

@MooingDuck 如果我没有犯错的话，这两个表达式将产生相同的结果。 - undefined

@Jorayen 对于2的幂次方对齐，x & (alignment - 1) 等同于 x % alignment，这应该能帮助你理解你的表达式与我提出的表达式之间的关系。类型 T 的对齐方式应始终为 alignof(T)。 - undefined

@gha.st：哦，我以为你的数学是对的。我只是提供了一个没有三元运算符的变体。三元运算符很难阅读。实际上，再看一遍，你的 sizeof(T) + (alignof(T) - sizeof(T) % alignof(T) 比我的更简单。 - undefined

@gha.st 是的，我理解 T 的对齐方式应该始终是 aligof(T)。但有一点我不确定（也许你在回答中已经提到了，但我没能理解），就是使用 malloc 分配的内存块的对齐方式应该是 CPU 字长吗？比如说我们有一个内存池，我们给用户的地址是否应该与 CPU 字长对齐？例如 Allocator.Allocate(20); // 请求 20 字节 返回的地址应该可以被指针的大小整除（即在 x32 上为 4 字节，在 x64 上为 8 字节），我理解得对吗？ - undefined

Answer 2

在分配内存块后，我想知道每个对象之间需要多少填充来优化CPU的读写。在C++标准库分配器模型中，您的allocator::allocate(count)方法需要分配足够的空间以存储类型为T、数量为count的对象数组。在C++中，数组是紧密打包的；从数组中的一个T到另一个T的偏移量必须是sizeof(T)。因此，在分配的存储空间中不能插入对象之间的填充。您可以在分配的内存块的开头插入填充，以便可以准确地使用alignof(T)(您的allocator::allocate也必须遵守)。但返回的指针必须是指向T的对齐存储的指针。因此，如果在分配的空间前面有填充，则在调用deallocate时需要某种方式来撤消填充，因为它只得到对齐存储地址。

当涉及到包含基本类型的结构体对齐时，您依靠编译器将其对齐要求强加在这些结构体上。因此，对于以下定义：

struct U
{
  std::int32_t i;
  std::int64_t j;
};

如果编译器认为将 int64_t 对齐到8字节更优，则编译器会在 U 的 i 和 j 之间插入适当的填充。此时，U 的 sizeof(U) 为16，alignof(U) 为8。

创建这种对齐不是你的工作，你也不能代替编译器完成。你必须仅仅尊重在 allocator<T>::allocate 调用中给定的任何类型的对齐方式。

- Nicol Bolas

---

我的最终目的是优化空间局部性，这就是为什么我尝试为以下情况创建不同的分配器：std::vector<std::unique_ptr<A>>，其中所有指针都线性存储，但所有*A却分散在内存中。如果分配器模型要求为T类型的数组分配紧密打包的内存，并且我无法添加填充以实现更快的读/写速度，则该怎么办？ - undefined

@Jorayen：针对哪种容器的“池/线性分配器”？基本的内存分配器无法改变指向对象的指针向量的离散性质。你可以从一个池中分配这些A，但这与vector无关，所以也与vector的分配器无关。 - undefined

是的，我已经理解了这一点，并在我的第二条评论中提到了这一点：“也许我应该创建这些自定义分配器，在其中插入填充以便于CPU进行更容易的读写，但不要让它们遵循标准的分配器模型并与STL容器一起工作？然后，我可以使用自定义删除函数从中提供内存给unique_ptr？”我还在等待答案，看这是否是我正在寻找的正确方法。 - undefined

@Jorayen：我不明白“对CPU来说更容易读写”的观点是从哪里得出的。这意味着这些A必须被分配为不对齐的。C++要求你按照alignof(A)的规定在存储中构造A。如果你没有这样做，就会进入未定义行为的领域。 - undefined

让我们在聊天中继续这个讨论。 - undefined