我对AoS vs SoA的理解是对吗？

Question

我最近一直在阅读AoS vs SoA结构设计和面向数据的设计.很难找到关于这两者的信息,而且我发现的东西似乎比我拥有更多的处理器功能.也就是说,我对前一个主题的理解特别导致了一些我认为应该能够理解答案的问题.

首先,为了确保我的理解不是基于错误的前提,我对AoS vs SoA的功能和利弊的理解,应用于具有'Name'和'Age'字段的'Person'记录的集合与他们相关:

阵列的结构

• 将数据存储为由多个数组组成的单个结构,例如,将People字段Names作为字符串Ages数组和整数数组作为对象.
• 信息,说,第三人的名单将通过类似给予People.Names[2]和People.Ages[2]
• 优点:
  • 当仅处理来自许多"人"记录的一些数据时,只需要从内存加载该数据.
  • 所述数据以同类方式存储,允许在大多数此类情况下通过SIMD指令更好地使用高速缓存.
• 缺点: - 当需要一次访问多个字段时,上述优点就会消失. - 访问一个或几个对象的所有数据变得效率较低. - 大多数编程语言需要更冗长,更难以读/写的代码,因为没有明确的"Person"结构.

结构数组

• 将数据存储为多个结构,每个结构都有一整套字段,它们本身存储在所有这些结构的数组中,例如对象People数组Person,它们具有Name字符串字段和Age整数字段.
• 对于第三人的信息会被像被赋予People[2].Name和People[2].Age
• 优点:
  • 代码围绕一个更简单的心理模型构建,间接被抽象掉.
  • 单个记录易于访问和使用.
  • Person结构的存在使得在大多数编程语言中编写代码变得更加简单.
• 缺点:
  • 当处理来自大量记录的一些数据时,需要将整组结构加载到包括不相关数据的存储器中.
  • 结构阵列不是均匀的,在这种情况下限制了SIMD指令可以提供的优点.

它的长短似乎是,假设为了论证,你的性能瓶颈是数据访问和编码的简易性是无关紧要的,如果你几乎完全需要一次访问大量的单个字段数据SoA可能更具性能,而如果您经常需要从同一个对象访问多个字段或处理单个对象而不是一次处理多个字段,AoS将更具性能.

也就是说,我一直在阅读的一些内容似乎让图片变得混乱.首先,多个消息来源已经声明SoA需要索引寻址,据称这是低效的.我无法理解这一点,也无法找到任何解释.在我看来,AoS和SoA需要完全相同的操作来访问任何特定的数据,尽管顺序不同,除了SoA需要一个额外的指针(可能多于一个,取决于所使用的结构类型).稍微简化一下,为了在AoS下面的上面例子中得到第五个人的年龄,你首先得到指向数组的指针,向它添加4,在数组的那个元素处获取结构指针,添加一个大小字符串指向它,因为age是第二个字段,然后访问该指针处的整数.在SoA下,您将获得指向结构的指针并向其添加字符串数组指针的大小以获取年龄列表,然后获取指向存储在那里的整数列表的指针并向其添加4,然后获取整数存储在那里.

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

最后,我已经看到SoA在遍历数据时需要更多缓存方式的说法.我不完全确定缓存方式是什么或者什么,如果有的话,特别是'遍历'数据.我最好的猜测是"缓存方式"指的是关联缓存中潜在冲突的数量或与之相关,并且它与上面提到的第二个Con相关.

Answer 1

"遍历"只意味着循环数据.

是的,你对缓存方式和冲突是正确的.64B(高速缓存行大小)存储器块彼此偏移2的大功率映射到同一组,因此相互竞争该组中的方式,而不是在不同的集合中高速缓存.(例如,英特尔的L1数据缓存是32kiB,8路关联,具有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空间游戏(无尽的天空)中,它是线段和船舶轮廓之间的所有碰撞(从精灵自动跟踪),而不是在两个多边形之间).这是原始的循环doublex,y对的向量(并使用一些(非内联!)函数作为16B SIMD向量对它们进行操作,通常使用慢速SSE3水平添加指令和类似的东西 :().

如果你不能改变数据布局,XY对上的SSE2/SSE3可能比什么都好,但是改变布局会消除并行执行4个交叉产品的所有混乱. 请参阅Insomniac Games(GDC 2015)的SIMD(SSE)简介中的幻灯片.对于之前没有使用过SIMD的人来说,它的基本内容非常基础,并详细解释了数组的结构是如何有用的.最后,它获得了中级/高级SSE技术,所以即使你已经知道一些SIMD的东西,也值得翻阅.另请参阅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;

}

然后我可以使用类似的东西来循环它(这里的真实代码:这是我正在进行的未清理的代码,尚未准备好向上游发送)

__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如果我想停止存储x[i+1]-x[i]并在运行中计算它,那么所有s连续将是一个很大的帮助.在我的布局中,我需要在向量之间进行混洗,而不是仅仅通过1个浮点数进行未对齐的偏移.

希望它还允许编译器自动向量化一些函数(例如,对于ARM,或对于具有更宽向量的AVX/AVX2).

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

如果您几乎完全需要在大量数据上一次访问一个字段,那么AoS可能会更高效,而如果您经常需要从同一个对象访问多个字段或处理单个对象而不是一次处理多个字段, SoA将更具性能.

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

你写的时候早些时候就弄错了

当仅处理来自许多"人"记录的一些数据时,只需将该数据加载到内存中.

(除了我认为你的意思是"从"内存(进入缓存),除非你在谈论内存映射文件和从磁盘到内存的错误页面.)

索引寻址模式:

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

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