首先,为了确保我的理解不是基于错误的前提,我对AoS vs SoA的功能和利弊的理解,适用于带有’Name’和’Age’字段的’Person’记录集合与他们相关：
数组的结构
>将数据存储为由多个数组组成的单个结构,例如,作为具有字段的People对象将Names作为字符串数组,将Ages存储为整数数组.
>例如,列表中的第三人的信息将由People.Names [2]和People.Ages [2]提供.
>优点：
>仅处理来自许多“人”记录的部分数据时,只需要从内存中加载该数据.
>所述数据以同类方式存储,允许在大多数此类情况下通过SIMD指令更好地使用高速缓存.
>缺点：
– 当需要一次访问多个字段时,上述优点就会消失.
– 访问一个或几个对象的所有数据变得效率较低.
– 大多数编程语言都需要更冗长,更难以读/写的代码,因为没有明确的“Person”结构.
结构数组
>将数据存储为多个结构,每个结构都有一整套字段,这些字段本身存储在所有此类结构的数组中,例如Person对象的Person对象,其中Name为字符串字段,Age为整数字段.
>第三人的信息将由人[2] .Name和People [2] .Age.提供
>优点：
>代码围绕一个更简单的心理模型构建,间接被抽象掉.
>单个记录易于访问和使用.
> Person结构的存在使得在大多数编程语言中编写代码变得更加简单.
>缺点：
>当处理来自大量记录的一些数据时,需要将整组结构加载到包括无关数据的内存中.
>结构阵列不是同质的,在这种情况下限制了SIMD指令可以提供的优势.
它的长短似乎是,假设为了论证,你的性能瓶颈是数据访问和编码的简易性是无关紧要的,如果你几乎完全需要一次访问大量的单个字段数据SoA可能性能更高,而如果您经常需要从同一个对象访问多个字段或处理单个对象而不是同时处理多个字段,AoS将更具性能.
也就是说,我一直在阅读的一些内容似乎让图片变得混乱.首先,多个来源已经声明SoA需要索引寻址,据称这种寻址效率低下.我无法理解这一点,也无法找到任何解释.在我看来,AoS和SoA需要完全相同的操作来访问任何特定的数据,尽管顺序不同,除了SoA需要一个额外的指针(可能多于一个,取决于所使用的结构类型).稍微简化一下,为了在AoS下面的上面例子中得到第五个人的年龄,你首先得到指向数组的指针,向它添加4,在数组的该元素处获取结构指针,添加a的大小字符串指向它,因为age是第二个字段,然后访问该指针处的整数.在SoA下,您将获得指向结构的指针并向其添加字符串数组指针的大小以获取年龄列表,然后获取指向存储在那里的整数列表的指针并向其添加4,然后获取整数存储在那里.
其次,我不清楚SoA的好处在多大程度上取决于特定的CPU架构.一方面,我对上述优点的理解并不依赖于任何特定的体系结构,除了SIMD指令在某些情况下可以提供AoS下无法提供的额外好处.另一方面,我看到声称可以根据特定SIMD架构中可用的通道数量来限制SoA的优势.同样,这似乎只会影响SIMD指令可以提供的更多通用缓存优势的额外好处.
最后,我看到SoA在遍历数据时需要更多缓存方式的说法.我不完全确定缓存方式是什么或者什么,如果有的话,具体是’遍历’数据.我最好的猜测是“缓存方式”指的是关联缓存中潜在冲突的数量或与之相关,并且它与上面提到的第二个Con相关.
“遍历”只意味着循环数据.是的,你对缓存方式和冲突是正确的. 64B(高速缓存行大小)存储器块彼此偏移2的大功率映射到同一组,因此相互竞争该组中的方式,而不是在不同的集合中高速缓存. (例如,英特尔的L1数据高速缓存为32kiB,8路关联,具有64B线.有32k / 64 = 512线分组为512/64 = 64组.
加载9个项目相互偏移4kiB(64B /行* 64集,而不是巧合的页面大小)将驱逐第一个.
L2和L3缓存是更高度关联的,如16或24方式,但仍然容易受到像这样的“混叠”,就像哈希表一样,对某些集合(桶)有很多需求而对其他集合没有需求(桶) ).对于CPU缓存,“散列函数”几乎总是使用一些地址位作为索引,并忽略其他位. (地址的高位用作标记,用于确定集合中的任何方式是否实际缓存所请求的块,低位用于选择缓存行中的字节.)
我认为SoA的好处主要来自SIMD(自动矢量化或手动),但是如果你倾向于在数据上循环只查看大多数结构中的一个或两个字段,并且只在极少数情况下访问其他字段有趣的一个基于一个成员.
对于您在一起查看的每个事物(或事物组),使用单独数组的混合方法可能是有意义的,其中每个对象的其余数据都在结构数组中.我正在想象一个线性搜索循环,其中大多数对象基于查看一个int字段而被拒绝,但是对于通过该测试的少数对象,您查看所有字段.
将大多数一起访问的字段组合在一起可以为这些访问提供空间局部性的好处,同时仍然允许检查关键字段的搜索循环遍历连续的内存(而不是大步).
我目前正在尝试在SIMD矢量大小的组中交错的布局.遍历数据的大多数代码都需要来自每个对象的所有字段,并且这样做意味着循环只需要一个指针,并且所有内存都被分配为单个块.
这是用于碰撞检测掩模(在2D空间游戏(无尽的天空)中,其中线段和船舶轮廓之间的所有碰撞(从精灵自动跟踪),而不是在两个多边形之间).这是the original,它绕过双x,y对的向量(并使用一些(非内联！)函数对它们作为16B SIMD向量进行操作,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).对于之前没有使用过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;
}
然后我可以用类似的东西循环它(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]并在运行中计算它,那么所有xs连续将是一个很大的帮助.在我的布局中,我需要在向量之间进行混洗,而不是仅仅通过1个浮点数进行未对齐的偏移.
希望它还允许编译器自动矢量化一些函数(例如,对于ARM,或对于具有更宽矢量的AVX / AVX2).
当然,手动矢量化将在这里取得胜利,因为我正在做像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.
(除了我认为你的意思是“从”内存(进入缓存),除非你在谈论内存映射文件和从磁盘到内存的错误页面.)
索引寻址模式：
在您正在查看每个对象中的两个或三个字段的情况下,
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可以使它们保持微融合,但需要进一步测试以确定英特尔何时进行此更改.也许与Broadwell在FMA之外的三输入指令(如CMOV和ADC)解码为单个uop,但这是一个纯粹的猜测.需要对Haswell和Broadwell进行测试.