24

我最近一直在阅读有关AoS 与 SoA结构设计和面向数据的设计的文章。很难找到有关两者的信息，而且我发现的似乎假设对处理器功能的了解比我拥有的更多。也就是说，我对前一个主题的理解尤其会导致一些我认为我应该能够理解答案的问题。

首先，为了确保我的理解不是基于一个错误的前提，我对 AoS 与 SoA 的功能和优缺点的理解，适用于具有“姓名”和“年龄”字段的“人员”记录集合与他们相关的：

数组的结构

  • 将数据存储为由多个数组组成的单个结构，例如作为People具有字段的对象Names作为字符串Ages数组和整数数组。
  • 例如，列表中第三人的信息将由类似People.Names[2]和People.Ages[2]
  • 优点：
    • 当只处理来自许多“人员”记录的部分数据时，只需要从内存中加载这些数据。
    • 所述数据以同质方式存储，允许在大多数此类情况下SIMD指令更好地使用高速缓存。
  • 缺点： - 当需要一次访问多个字段时，上述优点就消失了。- 访问一个或几个对象的所有数据变得效率降低。- 大多数编程语言需要更冗长且难以读/写的代码，因为没有明确的“人”结构。

结构数组

  • 将数据存储为多个结构，每个结构都有完整的字段集，它们本身存储在所有此类结构的数组中，例如对象数组，具有People字符串字段和整数字段。PersonNameAge
  • 第三人的信息将由类似People[2].Name和People[2].Age
  • 优点：
    • 代码是围绕一个更简单的心理模型构建的，间接性被抽象掉了。
    • 单个记录易于访问和使用。
    • 结构的存在Person使得在大多数编程语言中编写代码更加简单。
  • 缺点：
    • 当只处理大量记录中的一些数据时，需要将整个结构集加载到内存中，包括不相关的数据。
    • 结构数组不是同质的，这在这种情况下限制了 SIMD 指令可以提供的优势。

总而言之，如果您几乎只需要一次访问大量的单个字段数据 SoA 的性能可能更高，而如果您经常需要从同一个对象访问多个字段或处理单个对象而不是一次处理多个对象，那么 AoS 的性能会更高。

也就是说，我一直在阅读的一些内容似乎使情况变得混乱。首先，多个消息来源指出，SoA 需要索引寻址，据称这是低效的。我无法理解这一点，也找不到任何解释。在我看来，AoS 和 SoA 需要完全相同的操作来访问任何特定的数据，尽管顺序不同，除了 SoA 需要一个额外的指针（可能不止一个，取决于所使用的结构类型）。稍微简化一下，要在 AoS 下的上述示例中获取第五个人的年龄，您将首先获取指向数组的指针，向其添加 4，获取该数组元素的结构指针，添加大小指向它的字符串指针，因为年龄是第二个字段，然后访问该指针处的整数。在 SoA 下，

其次，我不清楚 SoA 的好处在多大程度上依赖于特定的 CPU 架构。一方面，我对上述好处的理解不依赖于任何特定的架构，除了 SIMD 指令可以提供在某些情况下在 AoS 下不可用的额外好处。另一方面，我看到有人声称 SoA 的优势可能会受到限制，具体取决于特定 SIMD 架构中可用的通道数量。同样，这似乎只影响 SIMD 指令可以提供的额外好处，而不是更一般的缓存好处。

最后，我看到了 SoA 在遍历数据时可能需要更多缓存方式的说法。我不完全确定缓存方式是什么，或者如果有的话，具体是指“遍历”数据。我最好的猜测是“缓存方式”是指关联缓存中潜在冲突的数量或与之相关，并且它与我上面提到的第二个 Con 相关。

4

1 回答 1

18

“遍历”只是意味着循环数据。

是的，关于缓存方式和冲突，你是对的。64B（高速缓存行大小）内存块彼此偏移大 2 次方映射到同一组，因此彼此竞争该组中的方式，而不是缓存在不同组中。（例如 Intel 的 L1 数据缓存是 32kiB，8-way associative，有 64B 行。32kiB / 64 B/line = 512 lines分为512 lines / 8 ways/set = 64 sets.

加载 9 个相互偏移 4kiB 的项目（64B/line * 64 sets不是巧合的页面大小）将驱逐第一个。

L2 和 L3 缓存具有更高的关联性，例如 16 或 24 路，但仍然容易受到这样的“别名”的影响，就像哈希表一样，其中对某些集合（桶）有大量需求，而对其他集合（桶）没有需求）。对于 CPU 缓存，“散列函数”几乎总是使用一些地址位作为索引，而忽略其他位。（地址的高位用作标记，以确定集合中是否有任何方式实际缓存请求的块，低位用于选择缓存行中的字节。）

我认为 SoA 的好处主要来自 SIMD（自动矢量化或手动），但如果您倾向于遍历数据，只查看大多数结构中的一个或两个字段，并且仅在您发现一个基于一个成员的有趣的。

为您一起查看的每个事物（或事物组）使用单独的数组的混合方法可能是有意义的，而每个对象的其余数据都在一个结构数组中。我在想象一个线性搜索循环，其中大多数对象基于查看一个int字段而被拒绝，但对于通过该测试的少数对象，您查看所有字段。

将最常被访问的字段组合在一起可以为这些访问带来空间局部性的好处，同时仍然让检查关键字段的搜索循环在连续内存上循环（而不是大步前进）。

我目前正在试验一种在 SIMD 矢量大小的组中交错的布局。大多数遍历数据的代码都需要来自每个对象的所有字段，这样做意味着循环只需要一个指针，并且所有内存都被分配为一个块。

这适用于碰撞检测蒙版（在 2D 空间游戏（Endless Sky）中，线段和船轮廓（从精灵自动追踪）之间的所有碰撞，而不是两个多边形之间的碰撞）。这是在 x,y 对的向量上循环的原始double代码（并使用一些（非内联！）函数将它们作为 16B SIMD 向量进行操作，通常使用缓慢的 SSE3 水平加法指令和类似的东西:()。

如果您无法更改数据布局，XY 对上的 SSE2/SSE3 可能总比没有好，但更改布局消除了并行执行 4 个交叉产品的所有改组。 请参阅Insomniac Games (GDC 2015) 上此 SIMD (SSE) 介绍中的幻灯片。它从非常基本的东西开始，供以前没有使用过 SIMD 的人使用，并准确解释了数组结构的帮助。最后，它涉及中级/高级 SSE 技术，因此即使您已经了解一些 SIMD 知识，也值得翻阅一下。另请参阅标签 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;

}

然后我可以用类似的东西循环它（这里的真实代码：这是我正在进行的未清理代码，尚未准备好发送到上游）

__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如果我想停止存储 sx[i+1]-x[i]并即时计算它，让所有s 连续将是一个很大的帮助。使用我的布局，我需要在向量之间进行洗牌，而不是仅仅做一个未对齐的偏移量 1 个浮点数。

它还有望允许编译器自动矢量化某些函数（例如，对于 ARM，或者对于具有更宽矢量的 AVX/AVX2）。

当然，手动矢量化将在这里获胜，因为我正在做类似 XORing 浮点数之类的事情，因为我只关心它们的符号位作为真值，而不是进行比较然后对比较结果进行异或。（到目前为止，我的测试表明，将负 0 视为负数仍然可以为 Mask::Intersect 提供正确的结果，但是在 C 中表达它的任何方式都将遵循 IEEE 规则，其中x >= 0为 true x=-0.）。

如果您几乎只需要一次访问大量数据的单个字段 AoS 可能会更高效，而如果您经常需要从同一个对象访问多个字段或处理单个对象而不是一次处理多个对象， SoA 的性能会更高。

你有这个完全倒退。这是一个错字吗？foo[i].key将所有字段分组到一个foo.key[i]数组中意味着它们都打包在缓存中，因此仅访问许多对象中的一个字段意味着您正在使用您接触的每个缓存行的所有 64 字节。

你之前写的时候是对的

当仅处理来自许多“人员”记录的部分数据时，只需将这些数据加载到内存中。

（除非我认为您的意思是“从”内存（到缓存），除非您在谈论内存映射文件和从磁盘到内存的错误页面。）

索引寻址模式：

在您查看每个对象中的两个或三个字段的情况下，SoA 布局将占用更多的寄存器，这些寄存器为您循环的每个单独数组保存单独的基地址。

使用多个指针，您要么使用[reg1 + 4*reg2]x86 上的寻址模式，要么需要在循环中单独增加一堆不同的指针。索引寻址模式在英特尔 SnB 系列上可能会稍微慢一些，因为它们无法与乱序内核中的 ALU 微指令保持微融合（仅在解码器和微指令缓存中）。Skylake 可以让它们保持微融合，但需要进一步测试才能确定英特尔何时进行此更改。当 FMA 以外的三输入指令（如 CMOV 和 ADC）解码为单个 uop 时，也许使用 Broadwell，但这纯粹是猜测。需要对 Haswell 和 Broadwell 进行测试。

于 2016-10-21T05:42:47.370 回答