为 SIMD 分配内存对齐缓冲区； |16 如何给出 16 的奇数倍数，为什么要这样做？
Allocating memory aligned buffers for SIMD; how does |16 give an odd multiple of 16, and why do it?
我正在使用 C++ 函数在内存中分配多个缓冲区。
缓冲区必须是 N 字节对齐的，因为它们保存的数据将使用各种类型的 SIMD 指令集（SSE、AVX、AVX512 等）进行处理
在Apple Core Audio Utility 类网上找到了这段代码：
void CABufferList::AllocateBuffers(UInt32 nBytes)
{
if (nBytes <= GetNumBytes()) return;
if (mABL.mNumberBuffers > 1) {
// align successive buffers for Altivec and to take alternating
// cache line hits by spacing them by odd multiples of 16
nBytes = ((nBytes + 15) & ~15) | 16;
}
UInt32 memorySize = nBytes * mABL.mNumberBuffers;
Byte *newMemory = new Byte[memorySize], *p = newMemory;
memset(newMemory, 0, memorySize); // get page faults now, not later
AudioBuffer *buf = mABL.mBuffers;
for (UInt32 i = mABL.mNumberBuffers; i--; ++buf) {
if (buf->mData != NULL && buf->mDataByteSize > 0) {
// preserve existing buffer contents
memcpy(p, buf->mData, buf->mDataByteSize);
}
buf->mDataByteSize = nBytes;
buf->mData = p;
p += nBytes;
}
Byte *oldMemory = mBufferMemory;
mBufferMemory = newMemory;
mBufferCapacity = nBytes;
delete[] oldMemory;
}
代码非常简单，但是有一行我没有完全理解：
nBytes = ((nBytes + 15) & ~15) | 16;
我理解它是 aligning/quantizing 到 16 的字节数，但是我不明白为什么它在最后使用按位或 16。评论说："to take alternating cache line hits by spacing them by odd multiples of 16"。原谅我厚，还是没看懂
所以我有三个问题：
1) | 16; 究竟做了什么，为什么要这样做？
2) 考虑到内存分配和数据访问的上下文，| 16; 如何以及在哪些方面改进了代码？从代码中的注释我可以猜到它与缓存访问有关，但我不理解整个 "alternating cache line hits" 位。将内存分配地址间隔为 16 的奇数倍数如何改善缓存访问？
3) 我是否认为上述函数只能基于新运算符 return 至少 16 字节对齐内存的假设才能正常工作？在 C++ 中，new 运算符被定义为 return 指向存储的指针，其对齐适用于具有基本对齐要求的任何对象，可能不一定是 16 个字节。
免责声明
根据提到 Altivec 的评论，这是特定于我不熟悉的 Power 架构。另外，代码不完整，但看起来分配的内存组织在一个或多个相邻的缓冲区中，并且大小调整只有在有多个缓冲区时才有效。我们不知道这些缓冲区中的数据是如何被访问的。这个答案会有很多假设，以至于它可能完全不正确。我发布它主要是因为它太大而无法发表评论。
回答（某种程度上）
我可以看到尺寸修改的一个可能优势。首先，让我们记住一些关于Power架构的细节：
- Altivec 向量大小为 16 字节（128 位）
- 缓存行大小为 128 字节
现在，让我们举个例子，AllocateBuffers分配内存给4个缓冲区（即mABL.mNumberBuffers是4个），nBytes是256个。让我们看看这些缓冲区是如何布局的内存：
| Buffer 1: 256+16=272 bytes | Buffer 2: 272 bytes | Buffer 3: 272 bytes | Buffer 4: 272 bytes |
^ ^ ^ ^
| | | |
offset: 0 272 544 816
注意偏移值并将它们与缓存行边界进行比较。为简单起见，我们假设内存是在缓存行边界分配的。这并不重要，如下所示。
- 缓冲区 1 从偏移量 0 开始，这是缓存行的开头。
- 缓冲区 2 从缓存行边界（偏移量为 2*128=256）开始 16 个字节处开始。
- 缓冲区 3 从缓存行边界（偏移量为 4*128=512）开始 32 个字节。
- 缓冲区 4 从缓存行边界（偏移量 6*128=768）开始 48 个字节处开始。
注意距离最近的高速缓存行边界的偏移量如何增加 16 个字节。现在，如果我们假设每个缓冲区中的数据将以 16 字节块的形式在循环中向前访问，那么缓存行将以相当特定的顺序从内存中获取。让我们考虑循环的中间部分（因为在开始时 CPU 必须为每个缓冲区的开头获取缓存行）：
- 迭代 5
- 从偏移量 5*16=80 处的缓冲区 1 加载，我们仍在使用在先前迭代中获取的缓存行。
- 从缓冲区 2 的偏移量 352 处加载，我们仍在使用在之前的迭代中获取的缓存行。缓存行边界位于偏移量 256，我们位于其偏移量 96。
- 从缓冲区 3 的偏移量 624 处加载，我们仍在使用在之前的迭代中获取的缓存行。缓存行边界位于偏移量 512，我们位于其偏移量 112。
- 从缓冲区 4 的偏移量 896 加载，我们命中一个新的缓存行边界并从内存中获取一个新的缓存行。
- 迭代 6
- 从缓冲区 1 的偏移量 6*16=96 加载，我们仍在使用在之前迭代中获取的缓存行。
- 从偏移量 368 处的缓冲区 2 加载，我们仍在使用在先前迭代中获取的缓存行。缓存行边界位于偏移量 256，我们位于其偏移量 112。
- 从缓冲区 3 的偏移量 640 处加载，我们命中一个新的缓存行 边界并从内存中获取一个新的缓存行。
- 从偏移量 896 处的缓冲区 4 加载，我们仍在使用上次迭代获取的缓存行。缓存行边界位于偏移量 896，我们位于其偏移量 16。
- 迭代 7
- 从缓冲区 1 的偏移量 7*16=112 加载，我们仍在使用在之前迭代中获取的缓存行。
- 从缓冲区 2 的偏移量 384 处加载，我们命中一个新的缓存行 边界并从内存中获取一个新的缓存行。
- 从缓冲区 3 的偏移量 656 处加载，我们仍在使用上次迭代中获取的缓存行。缓存行边界位于偏移量 640，我们位于其偏移量 16。
- 从偏移量 912 处的缓冲区 4 加载，我们仍在使用在先前迭代中获取的缓存行。缓存行边界位于偏移量 896，我们位于其偏移量 32。
- 迭代 8
- 从缓冲区 1 的偏移量 8*16=128 加载，我们命中一个新的缓存行边界并从内存中获取一个新的缓存行。
- 从缓冲区 2 的偏移量 400 处加载，我们仍在使用在之前的迭代中获取的缓存行。缓存行边界位于偏移量 384，我们位于其偏移量 16。
- 从偏移量 672 处的缓冲区 3 加载，我们仍在使用在先前迭代中获取的缓存行。缓存行边界位于偏移量 640，我们位于其偏移量 32。
- 从偏移量 944 处的缓冲区 4 加载，我们仍在使用在先前迭代中获取的缓存行。高速缓存行边界位于偏移量 896，我们位于其偏移量 48。
请注意，从内存中获取新缓存行的顺序不取决于每次循环迭代中访问缓冲区的顺序。此外，它不依赖于整个内存分配是否与缓存行边界对齐。另请注意，如果以相反顺序访问缓冲区内容，则缓存行将以正向顺序获取，但仍按顺序获取。
这种有序的缓存行提取可能有助于 CPU 中的硬件偏好器，因此，当执行下一个循环迭代时，所需的缓存行已经被预取。没有它，无论程序访问缓冲区的顺序如何，循环的每 8 次迭代都需要 4 个新的缓存行，这可能被解释为对内存的随机访问并妨碍预取器。根据循环复杂性，这 4 个缓存行提取可能不会被乱序执行模型隐藏并引入停顿。当您每次迭代最多只获取 1 个缓存行时，这种情况不太可能发生。
另一个可能的好处是避免 address aliasing. I don't know cache organization of Power, but if nBytes is a multiple of a page size, using multiple buffers at once, when each buffer is page-aligned, could result in lots of false dependencies and hamper store-to-load forwarding。尽管代码不仅在 nBytes 是页面大小的倍数时进行了调整，所以别名可能不是主要问题。
- Am I right thinking that the above function will only work correctly based on the assumption that the new operator will return at least 16-byte aligned memory? In C++ the new operator is defined as returning a pointer to storage with alignment suitable for any object with a fundamental alignment requirement, which might not necessarily be 16 bytes.
是的，除了适合存储任何基本类型的对象外，C++ 不保证任何特定的对齐方式。 C++17 添加了对过度对齐类型的动态分配的支持。
然而，即使使用较旧的 C++ 版本，每个编译器也遵守目标系统 ABI 规范，该规范可能指定内存分配的对齐方式。实际上，在许多系统上 malloc returns 至少 16 字节对齐的指针和 operator new 使用由 malloc 或类似的较低级别 API 返回的内存。
虽然它不可移植，因此不推荐使用。如果您需要特定的对齐方式，请确保您正在为 C++17 编译或使用专门的 APIs，例如 posix_memalign.
回复："how" 部分：在一组位中进行或运算（0x10 又名 16）使其成为 16 的 奇数 倍数. 即使是 16 的倍数也清除了该位，即它们也是 32 的倍数。这确保不是这种情况。
例如：32 | 16 = 48。48 | 16 = 48。无论其他高位是否设置为 16 对齐后的值，均适用。
请注意，此处调整的是分配大小。因此，如果多个缓冲区从一个大的分配中连续划分出来，它们将不会全部以相对于缓存行边界的相同对齐方式开始。正如安德烈的回答所指出的那样，如果它们最终的大小为 n * line_size + 16.
，它们可能会错开
如果它们都通过分配器分配到缓冲区的开头，并在页面的开头对齐，该分配器回退到直接使用 mmap 用于 large 分配（例如 glibc 的 malloc）。据推测（至少在撰写本文时），Apple 并没有这样做。
缓冲区大小为 2 的大幂次方的请求可能并不少见。
请注意，此评论可能已过时：Altivec 是 Apple 第一个带有 SIMD 的 ISA，在他们采用 x86 之前，在他们使用 ARM + NEON 制作 iPhone 之前。
倾斜您的缓冲区（因此它们相对于页面或缓存行的对齐方式并不完全相同）在 x86 上仍然有用，并且可能在 ARM 上也有用。
这些缓冲区的用例必须包括在相同索引处访问其中两个或多个缓冲区的循环。例如A[i] = f(B[i]).
性能方面的原因可能包括：
- 避免 x86 Sandybridge 系列 (https://www.agner.org/optimize/blog/read.php?i=142 ; and Agner Fog's microarch pdf) 上的缓存库冲突
- 避免
在一个循环中访问比 L1 或 L2 缓存关联性更多的数组。如果一个数组必须被逐出以腾出空间来缓存另一个数组，它可能每整行发生一次，而不是一行中每个 SIMD 向量发生一次。
- 避免存储（4k 别名）的内存消歧错误依赖项。例如L1 memory bandwidth: 50% drop in efficiency using addresses which differ by 4096+64 bytes。 x86 Intel CPU 仅查看存储/加载地址的低 12 位作为快速检查加载是否与正在运行的存储重叠。具有相同偏移量 within 的存储作为加载有效地将其别名化，直到硬件发现它实际上没有，但这会延迟加载。如果 PPC 上的内存消歧有类似的快速路径，我不会感到惊讶。
- Andrey 关于惊人的高速缓存未命中的猜测：我喜欢这个想法，并且它在乱序执行有限的早期 PowerPC CPU 上更为重要windows（并且可能有限的内存级并行性）相比到现代高端 x86 和 Apple 的高端 ARM。 https://en.wikipedia.org/wiki/AltiVec#Implementations。它也可能有助于现代有序 ARM CPU（它也可能具有有限的内存级并行性）。我敢肯定，一些 Apple 设备使用了有序 ARM，至少作为 big.LITTLE 设置的低功耗内核。
（当我说 "avoid" 时，有时这只是 "reduce the likelihood of"。）
我正在使用 C++ 函数在内存中分配多个缓冲区。 缓冲区必须是 N 字节对齐的，因为它们保存的数据将使用各种类型的 SIMD 指令集（SSE、AVX、AVX512 等）进行处理
在Apple Core Audio Utility 类网上找到了这段代码：
void CABufferList::AllocateBuffers(UInt32 nBytes)
{
if (nBytes <= GetNumBytes()) return;
if (mABL.mNumberBuffers > 1) {
// align successive buffers for Altivec and to take alternating
// cache line hits by spacing them by odd multiples of 16
nBytes = ((nBytes + 15) & ~15) | 16;
}
UInt32 memorySize = nBytes * mABL.mNumberBuffers;
Byte *newMemory = new Byte[memorySize], *p = newMemory;
memset(newMemory, 0, memorySize); // get page faults now, not later
AudioBuffer *buf = mABL.mBuffers;
for (UInt32 i = mABL.mNumberBuffers; i--; ++buf) {
if (buf->mData != NULL && buf->mDataByteSize > 0) {
// preserve existing buffer contents
memcpy(p, buf->mData, buf->mDataByteSize);
}
buf->mDataByteSize = nBytes;
buf->mData = p;
p += nBytes;
}
Byte *oldMemory = mBufferMemory;
mBufferMemory = newMemory;
mBufferCapacity = nBytes;
delete[] oldMemory;
}
代码非常简单，但是有一行我没有完全理解：
nBytes = ((nBytes + 15) & ~15) | 16;
我理解它是 aligning/quantizing 到 16 的字节数，但是我不明白为什么它在最后使用按位或 16。评论说："to take alternating cache line hits by spacing them by odd multiples of 16"。原谅我厚，还是没看懂
所以我有三个问题：
1) | 16; 究竟做了什么，为什么要这样做？
2) 考虑到内存分配和数据访问的上下文，| 16; 如何以及在哪些方面改进了代码？从代码中的注释我可以猜到它与缓存访问有关，但我不理解整个 "alternating cache line hits" 位。将内存分配地址间隔为 16 的奇数倍数如何改善缓存访问？
3) 我是否认为上述函数只能基于新运算符 return 至少 16 字节对齐内存的假设才能正常工作？在 C++ 中，new 运算符被定义为 return 指向存储的指针，其对齐适用于具有基本对齐要求的任何对象，可能不一定是 16 个字节。
免责声明
根据提到 Altivec 的评论，这是特定于我不熟悉的 Power 架构。另外，代码不完整，但看起来分配的内存组织在一个或多个相邻的缓冲区中，并且大小调整只有在有多个缓冲区时才有效。我们不知道这些缓冲区中的数据是如何被访问的。这个答案会有很多假设，以至于它可能完全不正确。我发布它主要是因为它太大而无法发表评论。
回答（某种程度上）
我可以看到尺寸修改的一个可能优势。首先，让我们记住一些关于Power架构的细节：
- Altivec 向量大小为 16 字节（128 位）
- 缓存行大小为 128 字节
现在，让我们举个例子，AllocateBuffers分配内存给4个缓冲区（即mABL.mNumberBuffers是4个），nBytes是256个。让我们看看这些缓冲区是如何布局的内存：
| Buffer 1: 256+16=272 bytes | Buffer 2: 272 bytes | Buffer 3: 272 bytes | Buffer 4: 272 bytes |
^ ^ ^ ^
| | | |
offset: 0 272 544 816
注意偏移值并将它们与缓存行边界进行比较。为简单起见，我们假设内存是在缓存行边界分配的。这并不重要，如下所示。
- 缓冲区 1 从偏移量 0 开始，这是缓存行的开头。
- 缓冲区 2 从缓存行边界（偏移量为 2*128=256）开始 16 个字节处开始。
- 缓冲区 3 从缓存行边界（偏移量为 4*128=512）开始 32 个字节。
- 缓冲区 4 从缓存行边界（偏移量 6*128=768）开始 48 个字节处开始。
注意距离最近的高速缓存行边界的偏移量如何增加 16 个字节。现在，如果我们假设每个缓冲区中的数据将以 16 字节块的形式在循环中向前访问，那么缓存行将以相当特定的顺序从内存中获取。让我们考虑循环的中间部分（因为在开始时 CPU 必须为每个缓冲区的开头获取缓存行）：
- 迭代 5
- 从偏移量 5*16=80 处的缓冲区 1 加载，我们仍在使用在先前迭代中获取的缓存行。
- 从缓冲区 2 的偏移量 352 处加载，我们仍在使用在之前的迭代中获取的缓存行。缓存行边界位于偏移量 256，我们位于其偏移量 96。
- 从缓冲区 3 的偏移量 624 处加载，我们仍在使用在之前的迭代中获取的缓存行。缓存行边界位于偏移量 512，我们位于其偏移量 112。
- 从缓冲区 4 的偏移量 896 加载，我们命中一个新的缓存行边界并从内存中获取一个新的缓存行。
- 迭代 6
- 从缓冲区 1 的偏移量 6*16=96 加载，我们仍在使用在之前迭代中获取的缓存行。
- 从偏移量 368 处的缓冲区 2 加载，我们仍在使用在先前迭代中获取的缓存行。缓存行边界位于偏移量 256，我们位于其偏移量 112。
- 从缓冲区 3 的偏移量 640 处加载，我们命中一个新的缓存行 边界并从内存中获取一个新的缓存行。
- 从偏移量 896 处的缓冲区 4 加载，我们仍在使用上次迭代获取的缓存行。缓存行边界位于偏移量 896，我们位于其偏移量 16。
- 迭代 7
- 从缓冲区 1 的偏移量 7*16=112 加载，我们仍在使用在之前迭代中获取的缓存行。
- 从缓冲区 2 的偏移量 384 处加载，我们命中一个新的缓存行 边界并从内存中获取一个新的缓存行。
- 从缓冲区 3 的偏移量 656 处加载，我们仍在使用上次迭代中获取的缓存行。缓存行边界位于偏移量 640，我们位于其偏移量 16。
- 从偏移量 912 处的缓冲区 4 加载，我们仍在使用在先前迭代中获取的缓存行。缓存行边界位于偏移量 896，我们位于其偏移量 32。
- 迭代 8
- 从缓冲区 1 的偏移量 8*16=128 加载，我们命中一个新的缓存行边界并从内存中获取一个新的缓存行。
- 从缓冲区 2 的偏移量 400 处加载，我们仍在使用在之前的迭代中获取的缓存行。缓存行边界位于偏移量 384，我们位于其偏移量 16。
- 从偏移量 672 处的缓冲区 3 加载，我们仍在使用在先前迭代中获取的缓存行。缓存行边界位于偏移量 640，我们位于其偏移量 32。
- 从偏移量 944 处的缓冲区 4 加载，我们仍在使用在先前迭代中获取的缓存行。高速缓存行边界位于偏移量 896，我们位于其偏移量 48。
请注意，从内存中获取新缓存行的顺序不取决于每次循环迭代中访问缓冲区的顺序。此外，它不依赖于整个内存分配是否与缓存行边界对齐。另请注意，如果以相反顺序访问缓冲区内容，则缓存行将以正向顺序获取，但仍按顺序获取。
这种有序的缓存行提取可能有助于 CPU 中的硬件偏好器，因此，当执行下一个循环迭代时，所需的缓存行已经被预取。没有它，无论程序访问缓冲区的顺序如何，循环的每 8 次迭代都需要 4 个新的缓存行，这可能被解释为对内存的随机访问并妨碍预取器。根据循环复杂性，这 4 个缓存行提取可能不会被乱序执行模型隐藏并引入停顿。当您每次迭代最多只获取 1 个缓存行时，这种情况不太可能发生。
另一个可能的好处是避免 address aliasing. I don't know cache organization of Power, but if nBytes is a multiple of a page size, using multiple buffers at once, when each buffer is page-aligned, could result in lots of false dependencies and hamper store-to-load forwarding。尽管代码不仅在 nBytes 是页面大小的倍数时进行了调整，所以别名可能不是主要问题。
- Am I right thinking that the above function will only work correctly based on the assumption that the new operator will return at least 16-byte aligned memory? In C++ the new operator is defined as returning a pointer to storage with alignment suitable for any object with a fundamental alignment requirement, which might not necessarily be 16 bytes.
是的，除了适合存储任何基本类型的对象外，C++ 不保证任何特定的对齐方式。 C++17 添加了对过度对齐类型的动态分配的支持。
然而，即使使用较旧的 C++ 版本，每个编译器也遵守目标系统 ABI 规范，该规范可能指定内存分配的对齐方式。实际上，在许多系统上 malloc returns 至少 16 字节对齐的指针和 operator new 使用由 malloc 或类似的较低级别 API 返回的内存。
虽然它不可移植，因此不推荐使用。如果您需要特定的对齐方式，请确保您正在为 C++17 编译或使用专门的 APIs，例如 posix_memalign.
回复："how" 部分：在一组位中进行或运算（0x10 又名 16）使其成为 16 的 奇数 倍数. 即使是 16 的倍数也清除了该位，即它们也是 32 的倍数。这确保不是这种情况。
例如：32 | 16 = 48。48 | 16 = 48。无论其他高位是否设置为 16 对齐后的值，均适用。
请注意，此处调整的是分配大小。因此，如果多个缓冲区从一个大的分配中连续划分出来，它们将不会全部以相对于缓存行边界的相同对齐方式开始。正如安德烈的回答所指出的那样，如果它们最终的大小为 n * line_size + 16.
，它们可能会错开
如果它们都通过分配器分配到缓冲区的开头，并在页面的开头对齐，该分配器回退到直接使用 mmap 用于 large 分配（例如 glibc 的 malloc）。据推测（至少在撰写本文时），Apple 并没有这样做。
缓冲区大小为 2 的大幂次方的请求可能并不少见。
请注意，此评论可能已过时：Altivec 是 Apple 第一个带有 SIMD 的 ISA，在他们采用 x86 之前，在他们使用 ARM + NEON 制作 iPhone 之前。
倾斜您的缓冲区（因此它们相对于页面或缓存行的对齐方式并不完全相同）在 x86 上仍然有用，并且可能在 ARM 上也有用。
这些缓冲区的用例必须包括在相同索引处访问其中两个或多个缓冲区的循环。例如A[i] = f(B[i]).
性能方面的原因可能包括：
- 避免 x86 Sandybridge 系列 (https://www.agner.org/optimize/blog/read.php?i=142 ; and Agner Fog's microarch pdf) 上的缓存库冲突
- 避免
- 避免存储（4k 别名）的内存消歧错误依赖项。例如L1 memory bandwidth: 50% drop in efficiency using addresses which differ by 4096+64 bytes。 x86 Intel CPU 仅查看存储/加载地址的低 12 位作为快速检查加载是否与正在运行的存储重叠。具有相同偏移量 within 的存储作为加载有效地将其别名化，直到硬件发现它实际上没有，但这会延迟加载。如果 PPC 上的内存消歧有类似的快速路径，我不会感到惊讶。
- Andrey 关于惊人的高速缓存未命中的猜测：我喜欢这个想法，并且它在乱序执行有限的早期 PowerPC CPU 上更为重要windows（并且可能有限的内存级并行性）相比到现代高端 x86 和 Apple 的高端 ARM。 https://en.wikipedia.org/wiki/AltiVec#Implementations。它也可能有助于现代有序 ARM CPU（它也可能具有有限的内存级并行性）。我敢肯定，一些 Apple 设备使用了有序 ARM，至少作为 big.LITTLE 设置的低功耗内核。
（当我说 "avoid" 时，有时这只是 "reduce the likelihood of"。）