我对 AoS 与 SoA advantages/disadvantages 的理解是否正确？
Is my understanding of AoS vs SoA advantages/disadvantages correct?
我最近一直在阅读有关 AoS vs SoA structure design and data-oriented design 的文章。奇怪的是很难找到关于这两者的信息，而且我所发现的似乎比我对处理器功能的理解更深。也就是说，我对前一个主题的理解特别导致了一些我认为我应该能够理解答案的问题。
首先，为了确保我的理解不是基于错误的前提，我对 AoS 与 SoA 的功能和优缺点的理解，应用于 'Person' 记录的集合 'Name' 和 'Age' 与之关联的字段：
数组结构
- 将数据存储为由多个数组组成的单一结构，例如作为一个
People 对象，其字段 Names 作为字符串数组，Ages 作为整数数组。
- 例如，列表中第三个人的信息将由
People.Names[2] 和 People.Ages[2] 之类的东西给出
- 优点：
- 当只处理许多 'Person' 条记录中的部分数据时，只有那些数据需要从内存中加载。
- 所述数据以同种方式存储，在大多数此类情况下允许 SIMD 指令更好地使用缓存。
- 缺点：
- 当需要同时访问多个字段时，上述优势就消失了。
- 访问一个或几个对象的所有数据变得效率较低。
- 大多数编程语言都需要更冗长和难以 read/write 的代码，因为没有明确的 'Person' 结构。
结构数组
- 将数据存储为多个结构，每个结构都有完整的字段集，它们本身存储在所有此类结构的数组中，例如
People 对象的 Person 数组，其中有Name 作为字符串字段，Age 作为整数字段。
- 第三人称的信息将由类似
People[2].Name 和 People[2].Age 的内容提供
- 优点：
- 代码是围绕一个更简单的心智模型构建的，间接寻址被抽象掉了。
- 单个记录易于访问和使用。
Person 结构的存在使得用大多数编程语言编写代码更加直接。
- 缺点：
- 当只处理大量记录中的部分数据时，需要将整个结构集加载到内存中，包括不相关的数据。
- 结构数组不是同类的，在这种情况下限制了 SIMD 指令可以提供的优势。
总而言之，假设您的性能瓶颈是数据访问，而编码的难易程度无关紧要，如果您几乎只需要一次访问一个字段在大量数据上，SoA 可能会更高效，而如果您经常需要从同一对象访问多个字段或处理单个对象而不是同时处理多个对象，则 AoS 会更高效。
就是说，我一直在阅读的一些内容似乎混淆了图片。首先，多个消息来源指出 SoA 需要索引寻址，据称这是低效的。我无法理解这一点，也找不到任何解释。在我看来，AoS 和 SoA 需要完全相同的操作来访问任何特定的数据，尽管顺序不同，除了 SoA 需要一个额外的指针（可能不止一个，具体取决于所使用的结构类型）。稍微简化一点，要在 AoS 下获取上面示例中第五个人的年龄，您首先要获取指向数组的指针，向其添加 4，获取数组该元素的结构指针，添加 a 的大小指向它的字符串指针，因为年龄是第二个字段，然后访问该指针处的整数。在 SoA 下，您将获取指向该结构的指针并将字符串数组指针的大小添加到它以获取年龄列表，然后获取指向存储在那里的整数列表的指针并向其添加 4，然后获取整数存储在那里。
其次，我不清楚 SoA 的好处在多大程度上依赖于特定的 CPU 架构。一方面，我对上述好处的理解并不依赖于任何特定的架构，只是 SIMD 指令在某些情况下可以提供 AoS 下无法提供的额外好处。另一方面，我看到有人声称 SoA 的优势可能会受到限制，具体取决于特定 SIMD 架构中可用的通道数量。同样，这似乎只影响 SIMD 指令可以提供的额外好处，而不是更一般的缓存好处。
最后，我看到了 SoA 在遍历数据时可能需要更多缓存方式的说法。我不完全确定缓存方式是什么，或者 'traversing' 数据具体指的是什么（如果有的话）。我最好的猜测是 'cache ways' 指的是关联缓存中潜在冲突的数量或与之相关，并且它与我上面提到的第二个 Con 相关。
"traversing" 就是循环遍历数据。
是的，关于缓存方式和冲突，您是对的。 64B（缓存行大小）内存块彼此偏移 2 的大幂映射到同一组，因此相互竞争该组中的路径，而不是缓存在不同的组中。 （例如 Intel 的 L1 数据缓存是 32kiB，8 路关联，64B 行。32kiB / 64 B/line = 512 lines 分组为 512 lines / 8 ways/set = 64 sets。
加载彼此偏移 4kiB 的 9 个项目（64B/line * 64 sets，不是巧合的页面大小）将逐出第一个。
L2 和 L3 缓存具有更高的关联性，如 16 或 24 路，但仍然容易受到 "aliasing" 的影响，就像散列 table 一样，其中对某些集合的需求很大(buckets) 而对其他集合 (buckets) 没有需求。对于CPU缓存，"hash function"几乎都是使用地址的一部分位作为索引，而忽略其他位。 （地址的高位用作标记，以确定集合中是否有任何方式实际缓存请求的块，低位用于缓存行中的 select 字节。）
我认为 SoA 的好处主要来自 SIMD（自动矢量化或手动），但如果您倾向于遍历您的数据，只查看大多数结构中的一个或两个字段，并且只在极少数情况下访问其余部分根据一个成员找到有趣的案例。
对于您一起查看的每个事物（或一组事物）使用单独数组的混合方法可能是有意义的，每个对象的其余数据都在一个结构数组中。我在想象一个线性搜索循环，其中大多数对象基于查看一个 int 字段而被拒绝，但对于通过该测试的少数对象，您查看所有字段。
将最常访问的字段组合在一起可为您提供这些访问的空间局部性优势，同时仍然让检查关键字段的搜索循环在连续内存上循环（而不是大步前进）。
我目前正在试验在 SIMD 矢量大小组中交错的布局。大多数遍历数据的代码需要每个对象的所有字段，这样做意味着循环只需要一个指针，所有内存都分配为一个块。
这是用于碰撞检测遮罩（在 2D space 游戏 (Endless Sky) 中，所有碰撞都是线段和船舶轮廓之间的碰撞（从 sprite 自动追踪），而不是两个多边形之间的碰撞).这是 the original which looped over a vector of double x,y pairs (and used some (non-inline!) functions to operate on them as a 16B SIMD vector, often with slow SSE3 horizontal-add instructions and stuff like that :( ).
如果不能更改数据布局，XY 对上的 SSE2/SSE3 可能总比没有好，但更改布局会消除并行执行 4 个叉积的所有混洗。 请参阅 the slides from this SIMD (SSE) intro at Insomniac Games (GDC 2015). It starts off with very basic stuff for people who haven't done anything with SIMD before, and explains exactly how structs of arrays are helpful. By the end, it gets to intermediate/advanced SSE techniques, so it's worth flipping through even if you already know some SIMD stuff. See also the sse 标记 wiki 以获取一些其他链接。
不管怎样，这就是我想出的交错数据结构：
class Mask {
...
struct xy_interleave {
static constexpr unsigned vecSize = 4;
static constexpr unsigned alignMask = vecSize-1;
alignas(64) float x[vecSize];
float y[vecSize];
// TODO: reduce cache footprint by calculating this on the fly, maybe with an unaligned load?
float dx[vecSize]; // next - current; next.x = x+dx
float dy[vecSize];
};
std::vector<xy_interleave> outline_simd;
}
然后我可以用类似的东西循环它（real code here：这是我正在进行的未清理代码，尚未准备好发送到上游）
__m128 minus_point_ps = _mm_cvtpd_ps(-point); // + is commutative, which helps the compiler with AVX
const __m128 minus_px = _mm_set1_ps(minus_point_ps[0]);
const __m128 minus_py = _mm_set1_ps(minus_point_ps[1]);
const __m128 range2 = _mm_set1_ps(float(range*range));
for(const xy_interleave &curr : outline_simd)
{
__m128 dx = _mm_load_ps(curr.x) + minus_px;
__m128 dy = _mm_load_ps(curr.y) + minus_py;
// this is using GNU Vector Extensions for + and *, instead of _mm_add_ps and _mm_mul_ps, since GNU C++ defines __m128 in terms of __v4sf
__m128 cmp = _mm_cmplt_ps(dx*dx - range2, dy*dy); // transform the inequality for more ILP
// load the x and y fields from this group of 4 objects, all of which come from the same cache line.
if(_mm_movemask_ps(cmp))
return true;
}
这编译成非常漂亮的 asm 循环，只有一个指针在 std::vector 上循环，向量从相对于该循环指针的恒定偏移量加载。
但是，对相同数据的标量回退循环不太漂亮。 （实际上，我也在手动矢量化部分中使用了这样的循环（使用 j+=4），因此我可以在不破坏代码的情况下更改交错。它完全编译掉，或者变成展开）。
// TODO: write an iterator or something to make this suck less
for(const xy_interleave &curr : outline_simd)
for (unsigned j = 0; j < curr.vecSize; ++j)
{
float dx = curr.x[j] - px;
float dy = curr.y[j] - py;
if(dx*dx + dy*dy < range2)
return true;
}
不幸的是，我没有运气让 gcc 或 clang 自动矢量化它，即使对于没有条件的简单情况（例如，只是找到从查询 x,y 到碰撞掩码中的任何点的最小范围，而不是检查一个点是否在范围内）。
我可能会放弃这个想法并使用单独的 x 和 y 数组。 （也许将头尾打包在同一个 std::vector<float> 中（使用对齐的分配器）以使其成为一次分配的一部分，但这仍然意味着循环将需要单独的 x 和 y 指针，因为 x 和 y 之间的偏移量对于给定的顶点将是一个运行时变量，而不是编译时常量。）
如果我想停止存储 x[i+1]-x[i] 并即时计算它，让所有 x 连续将是一个很大的帮助。在我的布局中，我需要在向量之间随机播放，而不是仅仅进行 1 个浮点数的未对齐偏移。
它也有望允许编译器自动向量化某些函数（例如，对于 ARM，或 AVX/AVX2 具有更宽的向量）。
当然，手动矢量化会在这里取胜，因为我正在做像 XORing floats 之类的事情，因为我只关心它们的符号位作为真值，而不是先进行比较，然后再对比较结果进行 XORing . （到目前为止，我的测试表明，将负数 0 视为负数仍然会为 Mask::Intersect 提供正确的结果，但在 C 中表达它的任何方式都将遵循 IEEE 规则，其中 x >= 0 对于 x=-0.).
if you almost exclusively need to access a single field at a time on a large amount of data AoS is likely to be more performant while if you often need to access multiple fields from the same object or deal with single objects rather than many at once, SoA will be more performant.
你完全倒过来了。这是一个错字吗？将所有 foo[i].key 字段分组到 foo.key[i] 数组中意味着它们都打包在缓存中，因此仅访问许多对象中的一个字段意味着您正在使用每个缓存行的所有 64 字节你触摸。
你之前写的是对的
When working with only some of the data from many 'Person' records, only that data needs to be loaded into memory.
（除了我认为你的意思是 "from" 内存（进入高速缓存），除非你谈论的是内存映射文件和错误页面从磁盘到内存。）
索引寻址模式:
在您查看每个对象中的两个或三个字段的情况下，
SoA 布局将绑定更多寄存器，为您要循环的每个单独的数组保存单独的基地址。
对于多个指针，您可能想要在 x86 上使用像 [reg1 + 4*reg2] 这样的寻址模式，或者您需要在循环中单独递增一堆不同的指针。索引寻址模式在英特尔 SnB 系列上可能 稍微 慢，因为它们 can't stay micro-fused with ALU uops in the out-of-order core (only in the decoders and uop cache)。 Skylake 可以让它们保持微融合，但需要进一步测试才能确定英特尔何时进行了此更改。当 FMA 之外的三输入指令（如 CMOV 和 ADC）解码为单个 uop 时，也许使用 Broadwell，但这纯粹是猜测。需要在 Haswell 和 Broadwell 上进行测试。
我最近一直在阅读有关 AoS vs SoA structure design and data-oriented design 的文章。奇怪的是很难找到关于这两者的信息，而且我所发现的似乎比我对处理器功能的理解更深。也就是说，我对前一个主题的理解特别导致了一些我认为我应该能够理解答案的问题。
首先，为了确保我的理解不是基于错误的前提，我对 AoS 与 SoA 的功能和优缺点的理解，应用于 'Person' 记录的集合 'Name' 和 'Age' 与之关联的字段：
数组结构
- 将数据存储为由多个数组组成的单一结构，例如作为一个
People对象，其字段Names作为字符串数组，Ages作为整数数组。 - 例如，列表中第三个人的信息将由
People.Names[2]和People.Ages[2] 之类的东西给出
- 优点：
- 当只处理许多 'Person' 条记录中的部分数据时，只有那些数据需要从内存中加载。
- 所述数据以同种方式存储，在大多数此类情况下允许 SIMD 指令更好地使用缓存。
- 缺点： - 当需要同时访问多个字段时，上述优势就消失了。 - 访问一个或几个对象的所有数据变得效率较低。 - 大多数编程语言都需要更冗长和难以 read/write 的代码，因为没有明确的 'Person' 结构。
结构数组
- 将数据存储为多个结构，每个结构都有完整的字段集，它们本身存储在所有此类结构的数组中，例如
People对象的Person数组，其中有Name作为字符串字段，Age作为整数字段。 - 第三人称的信息将由类似
People[2].Name和People[2].Age 的内容提供
- 优点：
- 代码是围绕一个更简单的心智模型构建的，间接寻址被抽象掉了。
- 单个记录易于访问和使用。
Person结构的存在使得用大多数编程语言编写代码更加直接。
- 缺点：
- 当只处理大量记录中的部分数据时，需要将整个结构集加载到内存中，包括不相关的数据。
- 结构数组不是同类的，在这种情况下限制了 SIMD 指令可以提供的优势。
总而言之，假设您的性能瓶颈是数据访问，而编码的难易程度无关紧要，如果您几乎只需要一次访问一个字段在大量数据上，SoA 可能会更高效，而如果您经常需要从同一对象访问多个字段或处理单个对象而不是同时处理多个对象，则 AoS 会更高效。
就是说，我一直在阅读的一些内容似乎混淆了图片。首先，多个消息来源指出 SoA 需要索引寻址，据称这是低效的。我无法理解这一点，也找不到任何解释。在我看来，AoS 和 SoA 需要完全相同的操作来访问任何特定的数据，尽管顺序不同，除了 SoA 需要一个额外的指针（可能不止一个，具体取决于所使用的结构类型）。稍微简化一点，要在 AoS 下获取上面示例中第五个人的年龄，您首先要获取指向数组的指针，向其添加 4，获取数组该元素的结构指针，添加 a 的大小指向它的字符串指针，因为年龄是第二个字段，然后访问该指针处的整数。在 SoA 下，您将获取指向该结构的指针并将字符串数组指针的大小添加到它以获取年龄列表，然后获取指向存储在那里的整数列表的指针并向其添加 4，然后获取整数存储在那里。
其次，我不清楚 SoA 的好处在多大程度上依赖于特定的 CPU 架构。一方面，我对上述好处的理解并不依赖于任何特定的架构，只是 SIMD 指令在某些情况下可以提供 AoS 下无法提供的额外好处。另一方面，我看到有人声称 SoA 的优势可能会受到限制，具体取决于特定 SIMD 架构中可用的通道数量。同样，这似乎只影响 SIMD 指令可以提供的额外好处，而不是更一般的缓存好处。
最后，我看到了 SoA 在遍历数据时可能需要更多缓存方式的说法。我不完全确定缓存方式是什么，或者 'traversing' 数据具体指的是什么（如果有的话）。我最好的猜测是 'cache ways' 指的是关联缓存中潜在冲突的数量或与之相关，并且它与我上面提到的第二个 Con 相关。
"traversing" 就是循环遍历数据。
是的，关于缓存方式和冲突，您是对的。 64B（缓存行大小）内存块彼此偏移 2 的大幂映射到同一组，因此相互竞争该组中的路径，而不是缓存在不同的组中。 （例如 Intel 的 L1 数据缓存是 32kiB，8 路关联，64B 行。32kiB / 64 B/line = 512 lines 分组为 512 lines / 8 ways/set = 64 sets。
加载彼此偏移 4kiB 的 9 个项目（64B/line * 64 sets，不是巧合的页面大小）将逐出第一个。
L2 和 L3 缓存具有更高的关联性，如 16 或 24 路，但仍然容易受到 "aliasing" 的影响，就像散列 table 一样，其中对某些集合的需求很大(buckets) 而对其他集合 (buckets) 没有需求。对于CPU缓存，"hash function"几乎都是使用地址的一部分位作为索引，而忽略其他位。 （地址的高位用作标记，以确定集合中是否有任何方式实际缓存请求的块，低位用于缓存行中的 select 字节。）
我认为 SoA 的好处主要来自 SIMD（自动矢量化或手动），但如果您倾向于遍历您的数据，只查看大多数结构中的一个或两个字段，并且只在极少数情况下访问其余部分根据一个成员找到有趣的案例。
对于您一起查看的每个事物（或一组事物）使用单独数组的混合方法可能是有意义的，每个对象的其余数据都在一个结构数组中。我在想象一个线性搜索循环，其中大多数对象基于查看一个 int 字段而被拒绝，但对于通过该测试的少数对象，您查看所有字段。
将最常访问的字段组合在一起可为您提供这些访问的空间局部性优势，同时仍然让检查关键字段的搜索循环在连续内存上循环（而不是大步前进）。
我目前正在试验在 SIMD 矢量大小组中交错的布局。大多数遍历数据的代码需要每个对象的所有字段，这样做意味着循环只需要一个指针，所有内存都分配为一个块。
这是用于碰撞检测遮罩（在 2D space 游戏 (Endless Sky) 中，所有碰撞都是线段和船舶轮廓之间的碰撞（从 sprite 自动追踪），而不是两个多边形之间的碰撞).这是 the original which looped over a vector of double x,y pairs (and used some (non-inline!) functions to operate on them as a 16B SIMD vector, often with slow SSE3 horizontal-add instructions and stuff like that :( ).
SSE2/SSE3 可能总比没有好，但更改布局会消除并行执行 4 个叉积的所有混洗。 请参阅 the slides from this SIMD (SSE) intro at Insomniac Games (GDC 2015). It starts off with very basic stuff for people who haven't done anything with SIMD before, and explains exactly how structs of arrays are helpful. By the end, it gets to intermediate/advanced SSE techniques, so it's worth flipping through even if you already know some SIMD stuff. See also the sse 标记 wiki 以获取一些其他链接。
不管怎样，这就是我想出的交错数据结构：
class Mask {
...
struct xy_interleave {
static constexpr unsigned vecSize = 4;
static constexpr unsigned alignMask = vecSize-1;
alignas(64) float x[vecSize];
float y[vecSize];
// TODO: reduce cache footprint by calculating this on the fly, maybe with an unaligned load?
float dx[vecSize]; // next - current; next.x = x+dx
float dy[vecSize];
};
std::vector<xy_interleave> outline_simd;
}
然后我可以用类似的东西循环它（real code here：这是我正在进行的未清理代码，尚未准备好发送到上游）
__m128 minus_point_ps = _mm_cvtpd_ps(-point); // + is commutative, which helps the compiler with AVX
const __m128 minus_px = _mm_set1_ps(minus_point_ps[0]);
const __m128 minus_py = _mm_set1_ps(minus_point_ps[1]);
const __m128 range2 = _mm_set1_ps(float(range*range));
for(const xy_interleave &curr : outline_simd)
{
__m128 dx = _mm_load_ps(curr.x) + minus_px;
__m128 dy = _mm_load_ps(curr.y) + minus_py;
// this is using GNU Vector Extensions for + and *, instead of _mm_add_ps and _mm_mul_ps, since GNU C++ defines __m128 in terms of __v4sf
__m128 cmp = _mm_cmplt_ps(dx*dx - range2, dy*dy); // transform the inequality for more ILP
// load the x and y fields from this group of 4 objects, all of which come from the same cache line.
if(_mm_movemask_ps(cmp))
return true;
}
这编译成非常漂亮的 asm 循环，只有一个指针在 std::vector 上循环，向量从相对于该循环指针的恒定偏移量加载。
但是，对相同数据的标量回退循环不太漂亮。 （实际上，我也在手动矢量化部分中使用了这样的循环（使用 j+=4），因此我可以在不破坏代码的情况下更改交错。它完全编译掉，或者变成展开）。
// TODO: write an iterator or something to make this suck less
for(const xy_interleave &curr : outline_simd)
for (unsigned j = 0; j < curr.vecSize; ++j)
{
float dx = curr.x[j] - px;
float dy = curr.y[j] - py;
if(dx*dx + dy*dy < range2)
return true;
}
不幸的是，我没有运气让 gcc 或 clang 自动矢量化它，即使对于没有条件的简单情况（例如，只是找到从查询 x,y 到碰撞掩码中的任何点的最小范围，而不是检查一个点是否在范围内）。
我可能会放弃这个想法并使用单独的 x 和 y 数组。 （也许将头尾打包在同一个 std::vector<float> 中（使用对齐的分配器）以使其成为一次分配的一部分，但这仍然意味着循环将需要单独的 x 和 y 指针，因为 x 和 y 之间的偏移量对于给定的顶点将是一个运行时变量，而不是编译时常量。）
如果我想停止存储 x[i+1]-x[i] 并即时计算它，让所有 x 连续将是一个很大的帮助。在我的布局中，我需要在向量之间随机播放，而不是仅仅进行 1 个浮点数的未对齐偏移。
它也有望允许编译器自动向量化某些函数（例如，对于 ARM，或 AVX/AVX2 具有更宽的向量）。
当然，手动矢量化会在这里取胜，因为我正在做像 XORing floats 之类的事情，因为我只关心它们的符号位作为真值，而不是先进行比较，然后再对比较结果进行 XORing . （到目前为止，我的测试表明，将负数 0 视为负数仍然会为 Mask::Intersect 提供正确的结果，但在 C 中表达它的任何方式都将遵循 IEEE 规则，其中 x >= 0 对于 x=-0.).
if you almost exclusively need to access a single field at a time on a large amount of data AoS is likely to be more performant while if you often need to access multiple fields from the same object or deal with single objects rather than many at once, SoA will be more performant.
你完全倒过来了。这是一个错字吗？将所有 foo[i].key 字段分组到 foo.key[i] 数组中意味着它们都打包在缓存中，因此仅访问许多对象中的一个字段意味着您正在使用每个缓存行的所有 64 字节你触摸。
你之前写的是对的
When working with only some of the data from many 'Person' records, only that data needs to be loaded into memory.
（除了我认为你的意思是 "from" 内存（进入高速缓存），除非你谈论的是内存映射文件和错误页面从磁盘到内存。）
索引寻址模式:
在您查看每个对象中的两个或三个字段的情况下， SoA 布局将绑定更多寄存器，为您要循环的每个单独的数组保存单独的基地址。
对于多个指针，您可能想要在 x86 上使用像 [reg1 + 4*reg2] 这样的寻址模式，或者您需要在循环中单独递增一堆不同的指针。索引寻址模式在英特尔 SnB 系列上可能 稍微 慢，因为它们 can't stay micro-fused with ALU uops in the out-of-order core (only in the decoders and uop cache)。 Skylake 可以让它们保持微融合，但需要进一步测试才能确定英特尔何时进行了此更改。当 FMA 之外的三输入指令（如 CMOV 和 ADC）解码为单个 uop 时，也许使用 Broadwell，但这纯粹是猜测。需要在 Haswell 和 Broadwell 上进行测试。