基于Rust的面向数据设计导论

面向数据的设计是一种通过仔细考虑数据结构的内存布局及其对自动向量化和CPU高速缓存使用的影响来优化程序的方法。如果您还没有看过Mike Acton的“面向数据的设计和C++”演讲，我强烈推荐您去看一下。

数组结构与结构数组是指组织要操作的实体数据的两种截然不同的方式。

例如，假设我们正在编写一个视频游戏，并且我们希望拥有一个具有以下字段的Player结构：

Pub struct player{名称：字符串，健康：F64，位置：(F64，F64)，速度：(F64，F64)，加速度：(F64，F64)，}。

然后在每一帧，我们想要更新所有播放器的位置和速度。我们可以这样写：

Pub FN run_oop(Player：&；mut Vec<；Player>；){对于Player.iter_mut(){Player.Location=(Player.Location.。0+玩家.速度。0，玩家。位置。1+玩家.速度。1，)；玩家速度=(玩家速度。0+玩家.加速。0，玩家.速度。1+玩家.加速。1，)；}}。

这将是解决此问题的常用面向对象方法。这里的问题是，结构按如下方式存储在内存中(假设没有字段重新排序，即#[repr(C)])，在64位体系结构上，每个字段将为64位(8字节，因此每个播放器为64字节)：

--vec<；播放器名称(指向堆的指针)--播放器1运行状况位置0(为清楚起见，拆分元组)location1velocity0velocity1acceleration0acceleration1name(指向堆的指针)--播放器2location0 location1velocity0velocity1acceleration0acceleration1...

请注意，我们要操作的部分(位置、速度和加速度)不能跨不同的播放器连续存储。这阻止了我们使用矢量操作一次对多个播放器进行操作(因为它们不能加载到相同的CPU缓存线中，通常为~64字节)。

相反，面向数据的方法是围绕这一限制进行设计，并针对自动矢量化进行优化。现在，我们不再对每个玩家使用astruct，而是对所有玩家使用一个结构，并且每个玩家的值都存储在各自的属性矢量中的索引处：

Pub struct DOPlayer{名称：VEC<；String>；，运行状况：VEC<；(F64，F64>；，位置：VEC<；(F64，F64)>；，速度：VEC<；(F64，F64)>；，加速度：VEC<；(F64，F64)>；，}。

Pub fn run_dop(world：&；mut DOPlayer){for(pos，(vel，acc))in world.locations.iter_mut().zip(world.veloities.iter_mut().zip(world.acceleration.iter(){*pos=(pos.。0+vel.。0，位置。1+vel.。1)；*vel=(vel.。0+访问。0，韦尔。1+Acc。1)；}}。

相关字段现在连续存储。考虑到每个位置元组将是16字节，我们现在可以可行地将4个位置元组加载到同一高速缓存线上，以便使用SIMD指令同时对它们进行操作。

以下是上述代码的标准基准测试结果(完整代码和基准代码可在Github repo中找到)：

总体而言，我们看到面向数据的方法完成的时间减半。这似乎是由于面向数据的用例同时在两个播放器上操作-我们可以通过查看编译后的程序集来确认这一点。

//相关的OOP循环。LBB0_2：movupd xmm0，xmmword PTR[rax+rdx+32]movupd xmm1，xmmword PTR[rax+rdx+48]movupd xmm2，xmmword ptr[rax+rdx+64]addpd xmm0，xmm1 movupd xmmword PTR[rax+rdx+32]，xmm0 addpd xmm2，x1 mmupd xmmword PTR[rax+rdx+48]，xmm2 add RDX，80 CMP RCX，RDX j.LB0_2//...//相关DOP loop.LBB1_7：movupd mm0，xmmpd xmr[rax+rdx-16]，xmm0 addpd xmmword PTR[rax+rdx+48]，xmm2 add RDX，80 CMP RCX，RDX j.LB0_2//...//相关DOP loop.LBB1_7：movupd x0，xmmpd xmmword[rax+rdx-16]movupd xmm2，x1 mmupd xmmword PTR[rax+rdx+48]。Xmmword ptr[rax+rdx-16]addpd xmm1，xmm0 movupd xmmword ptr[rcx+rdx-16]，xmm1 movupd xmm0，xmmword ptr[r9+rdx-16]movupd xmm1，xmmword ptr[rax+rdx-16]addpd xmm1，x1 mmvupd mmvupd xmm0，xmmword PTR[rax+rdx-16]，xmm1 add rdi，2 movupd xmm1，xmmword ptr[RCX+RDX]addpd mmx1，xmm0 movupd xmmword ptR[RCX+RDX]，xmmupd xmmword PTR[rax+rdx]addpd mmx1，xmm0 movupd xmmword PTR[RCX+RDX]addpd mmx1，xmm0 movupd xmmword ptr[RCX+RDX]addpd mmx1，xmm0 movupd xmmword PTR[RX+RDX]addpd mmx1，xmmword ptr[RX+RDX]addpd mmx1，xmm0 movupd xmmword PTR[RCX+RDX]addpd mmx1。Xmm0 movupd xmmword PTR[RAX+RDX]，xmm1添加RDX，32 CMP RSI，RDI jne.LBB1_7测试r8，r8 je.LBB1_5

我们可以看到，在面向数据的情况下，循环被展开以同时对两个元素进行操作-导致总体速度提高了50%！

附录：正如Reddiit上的/u/five9a2所指出的，上面的输出是专门针对默认目标的，这具有误导性，因为Cargo bench默认使用本机目标(即您的CPU上所有可能的功能)，所以我们的基准测试没有使用上面的汇编代码。

通过将编译器标志设置为-C target-cpu=skylake-avx512以启用Skylake功能，我们将获得以下输出：

//oop loop.LBB0_2：vmovupd ymm0，ymmword ptr[rax+rdx+32]vaddpd ymm0，ymm0，ymmword PTR[rax+rdx+48]vmovupd ymmword PTR[rax+rdx+32]，ymm0 add RDX，80 CMP RCX，RDX jne.LBB0_2...//DOP loop.LBB1_19：vmovupd zmm0，zmmword PTR[RSI+4*rax-64]vpd PTzmm0，zmm0，zaddvupd zmmword[RSI+4*rax-64]，z0 vvmoupd zmmword[RSI+4*rax-64]，z0 vvmoupd zmmword[RSI+4*rax-64]，zbb1_19：vmovupd zmm0，zmmword PTR[RSI+4*rax-64]vmovupd zmmwor[RSI+4*rax-64]，zmovupd zmmword[RSI+4*rax-64]，z0 vvmoupd zmmword[RSI+4*rax-64]。Zmmword PTR[RCX+4*rax-64]vaddpd zmm0，zmm0，zmmword PTR[R10+4*rax-64]vmovupd zmmword PTR[RCX+4*rax-64]，zmm0 vmovupd zmm0，zmmword PTR[RSI+4*rax]vaddpd zmm0，zmm0，zmmword PTR[RCX+4*rax]，vmovupd zmmword PTR[RSI+4*rax]，zmm0 vmovupd zmz0，zmmword pz0，zmm0，zmmword PTR[R10+4*rax]，zmm0，zmmword PTR[RCX+4*rax]，zmovupd zmmword PTR[RSI+4*rax]，zmm0 vmovupd mmz0，zmmword ptR[R10+4*rax]，zmm0，zmmword PTR[RCX+4*rax]，zmovupd zmmword PTR[RSI+4*rax]，zmm0 vmovupd mmz0，zmmword PTR[R10+4*rax]，zmm0，zmmword PTR[RCX+4*rax]，zmm0 add 11，add 8，add 32。2 jne.LBB1_19测试R9，R9 je.LBB1_22。

在这里，我们看到OOP循环使用256位的YMM寄存器用于位置元组和速度元组，另一个寄存器用于速度元组和加速度元组。这是可能的，因为它们在内存中相邻(由于字段的排序)。在DOP环路中，使用512位ZMM寄存器。

性能差异似乎来自缓存级别之间的带宽，因为小示例的性能是相同的。这可以通过从结构中删除额外的字段来进一步演示-在这种情况下，我们只看到25%的性能差异(Good Boltlink)，这对应于播放器结构现在是384位(因此，512位读/写的1/4是未使用的)。在这种情况下，我们可以看到只有25%的性能差异(Good Boltlink)，这对应于播放器结构现在是384位(因此，512位读/写的1/4是未使用的)。

这强调了考虑您的部署目标是多么重要，如果部署性能敏感的代码，考虑明确设置目标CPU以从其所有功能中获益。

它还演示了字段的排序对性能是如何重要的。默认情况下，Rust将自动重新排序字段，但您可以设置#[repr(C)]来禁用此功能(例如，对于C互操作性是必需的)。

这个例子说明了当目标是性能代码和自动向量化时，考虑内存布局的重要性。

请注意，当使用结构数组时，同样的逻辑也适用-使结构更小将允许您在同一缓存行上加载更多元素，并可能导致自动向量化。这是一个板条箱(在Rust Subreddit上共享)的例子，它通过这样做实现了40%的性能改进。

这种特殊的重组与数据库设计有直接的相似之处。针对事务性(OLTP)工作负载的数据库和针对分析(OLAP)工作负载的数据库之间的主要区别在于，后者倾向于使用基于列的存储。与上面的情况一样，这意味着对一列的操作可以利用连续存储并使用向量操作，这往往是分析工作负载的主要访问模式(例如，计算所有行的平均购买大小，而不是更新和检索整个特定行)。

在分析数据库的情况下，这实际上是一个双赢，因为它也适用于数据到磁盘的串行化，现在可以沿着列应用压缩(其中保证数据是相同类型的)，从而产生更好的压缩比。

如果您正在处理一个可能受益于数组结构方法的问题，并且想要运行一个快速基准测试，那么您可能会对允许您从struct派生数组结构的SOA派生速率感兴趣。

另一种优化策略是避免在代码的任何“热门”部分(即任何将被多次执行的部分)中分支。

分支可能以微妙的方式出现，通常是通过尝试将一个结构用于许多不同的情况。例如，我们可以定义一些常规节点类型，如下所示：

当我们有一个包含数万个元素的VEC<；Node>；时，问题就来了，我们可能需要在每一帧上操作这些元素。通过使用node.node_type来决定要使用的逻辑，我们需要检查每个元素(因为在VEC<；Node>；中的node_type的顺序是未知的)。

这种比较不仅意味着我们必须对每个元素执行额外的操作，而且还会阻碍自动向量化，因为我们的相关节点(属于相同的node_type)可能不是连续存储的。

面向数据的方法是按node_type拆分这些节点，理想情况下为每个节点类型创建一个单独的结构，或者至少在热循环之前将它们分隔在单独的向量中。这意味着我们不需要检查热循环中的node_type，我们可以利用这样一个事实，即我们操作的节点将存储不连续的内存。

#[派生(复制，克隆)]pub struct foo{x：i32，calc_type：CalcType，}#[派生(复制，克隆)]pub枚举CalcType{Identity，Square，Cube，}//...。Pub FN RUN_MIXED(x：&；[foo])->；Vec<；I32>；{x.into_iter().map(|x|Match x.calc_type{CalcType：：Identity=>；x，CalcType：：Square=>；x.x*x.x，CalcType：：Cube=>；X.x*x.x*x.x，}).Collect()}pub FN run_Separate(x：&；[foo]，y：&；[foo]，z：&；[foo])->；(Vec<；I32&>；，Vec<；I32>；，Vec<；I32>；){设x=x.into_iter().map(|x|x.x).Collect()；设y=y.into_iter().map(|x|x.x*x*.x).Collect()；设z=z.into_iter().map(|x|x.x*x.x*x.x).Collect()；(x，y，z)}。

比较foos的混合向量和按calc_type拆分的foos的单独向量的情况。

总体而言，我们看到面向数据的方法大约在四分之一的时间内完成。

这次关于Godbolt的输出不太清楚，但是我们可以看到，在这些单独的情况下似乎有一些展开，这在混合情况下是不可能的，因为在这种情况下需要检查calc_type。

您应该熟悉将任何指令移出热循环的概念，但这个示例也演示了它是如何影响向量化的。

在本例中，我们将比较遍历(双重)链接的listv的迭代。一个矢量。这个案例在Rust的LinkedList文档、Rust的STD：：Collection文档和Learn Rust with All Too More Linked List的公共服务公告中都有提及，后者的公共服务公告涵盖了很多常用的链接列表的情况，所以如果您还没有阅读，我建议您阅读一下。尽管如此，证据就在布丁中，所以我认为直接查看基准是有用的。

链表间接存储元素，也就是说，它存储一个元素和指向下一个元素的指针。这意味着链表中的连续元素不会存储在连续的内存位置中。

链表的元素可以存储在任意相隔很远的地方，因此我们不能仅将一块内存加载到CPU高速缓存以同时对它们进行操作。

例如，我们可以将i32的向量存储在堆上，如下所示(在堆栈上持有指向向量开始、向量容量和向量长度的指针)：

这些值是连续存储的，而对于(单个)链表，我们可能会遇到以下情况。

在这里，值没有存储在连续的内存中(或者甚至没有必要按照它们的指针在列表中维护的顺序)。

在本例中，基准非常简单，只需将链表和向量的所有元素平方即可：

Pub fn run_list(list：&；mut LinkedList<；I32>；){list.iter_mut().for_each(|x|{*x=*x**x；})；}pub fn run_vec(list：&；mut Vec<；I32>；){list.iter_mut().for_each(|x|{*x=*x**x；})；}。

在Godbolt上的输出显示了在VEC案例中的展开，这在LinkedList案例中是不可能的。

这个案例是众所周知的，并且展示了所有基准中最大的不同之处。请注意，这里我们只关注迭代，而不是其他可以被认为在某种程度上有利于LinkedList的操作，如插入，在这些操作中，它避免了矢量调整大小的(摊余)成本，然而，正如在学习包含太多链接的列表中所讨论的那样，这在矢量中也可以避免。

希望这将成为常识，我们将看到更少的面试问题和基于链表和间接性的实践问题，只考虑大O的复杂性，而不是真实的世界性能。

在编写泛型函数时(即，对于实现某些Trait的任何类型)，我们可以在动态分派和单形化之间进行选择。

动态调度允许我们使用混合的特征对象集合，即我们可以拥有一个Vec<；Box<；dyn MyTrait>；，它可以包含对全部实现MyTrait的不同类型的引用。特征对象包含一个指向struct自身实例的指针(实现MyTrait)和一个指向结构的虚拟方法表(或vtable，指向MyTrait的每个方法的实现的查找表)的指针。然后，当我们在其中一个特征对象上调用方法时，在运行时，我们通过查阅vtable来确定要使用该方法的哪个实现。

请注意，这意味着间接的。我们的向量必须是指向结构实例本身的指针(因为实现MyTrait的不同结构在大小和字段上可能不同)，我们还必须引用vtable中的指针来找出要调用哪个实现。

另一方面，单形化为每个可能的类型创建了泛型函数的单独实现。例如，下面的代码实际上会为Foo和Bar类型的run_vecs_square()创建两个单独的函数：

Pub struct foo{id：usize，}pub struct Bar{id：usize，}pub特征MyTrait{fn square_id(&；mut self)；}为foo实施MyTrait{fn square_id(&；mut self){sel.id=sel.id*sel.id；}}为bar实施myTrait{fn square_id(&；mut self){sel.id=sel.id*sel.id*self.id；}}pub FN run_vecs_square<；T：MyTrait>；(x：&；mut Vec<；T>；){x.iter_mut().for_each(|x|x.square_id())}。

这增加了二进制大小，但为我们提供了一种为不同类型生成函数的多个实现的简单方法，并允许用户避免间接(即注意，我们可以使用Vec<；T>；，而不需要使用Vec<；Box<；T>；>；)。

而在下面的代码中，我们使用动态分派。Run_dyn_square只有一个实现，但是它应该调用Square_id()的确切实现是在运行时通过参考特征对象的vtable来确定的。

这会更方便，因为我们可以创建包含对不同类型的引用的向量，而不必担心实际类型是什么(只是它们实现了MyTrait)，并且我们不会夸大二进制大小。然而，我们被迫使用间接，因为底层类型可能有不同的大小，正如我们在LinkedList示例中看到的那样，这可能会对自动向量化产生重大影响。

总体而言，我们看到单形化示例完成的时间大约是动态分派示例的四分之一。具有间接性的单形化情况(VEC<；Box；T>；>；)仅比动态分派情况略快，这意味着大部分性能差距是由于添加的间接阻碍矢量化造成的，而vtable查找本身只增加了很小的恒定开销。

不幸的是，在这种情况下，Godbolt在生成的输出中不包括目标函数。

该基准测试表明，由于引入了必要的间接性，动态分派的主要成本是阻碍向量化，并且在vtable本身中查找的成本相对较小。

这意味着，如果您的方法执行的操作(如上面的数学操作)将极大地受益于向量化，那么您绝对应该考虑设计表单非形式化。另一方面，如果它们执行的是未向量化的操作(例如，构造字符串)，则动态调度的总体成本可能可以忽略不计。

在本文中，我们看到了四种考虑内存中数据布局的情况，CPU缓存的现实和限制导致了显著的性能改进。

这只触及了面向数据的设计和优化的皮毛。例如，结构包装、填充和对齐未包括在内。Richard Fabian的“面向数据的设计”一书还涵盖了一些额外的主题。

重要的是要注意，在我们的所有示例中，我们没有修改我们使用的算法。每种情况下的所有实现都具有相同的大O复杂度，但在实践中性能可能差异很大，仅通过优化矢量化和现代CPU的其他功能，就可以实现2倍-10倍的加速。

支持使用较少/没有间接性和连续内存的数据结构(使用借用检查器也会更容易！)。

如果部署性能敏感代码，请考虑将目标计算机的CPU功能作为目标(即使用RUSTFLAGS)。