钱德勒·卡鲁斯（Chandler Caruth）（我想-我一辈子都找不到参考文献）在几年前的cppcon演讲中说了一些话，这让我很震惊。或多或少地，95％的代码性能来自数据结构的内存布局和内存访问模式，而5％则来自明智的指令选择和指令流优化。
那是...可怕的消息！现在，指令选择几乎是完全自动化的。 LLVM进入我的代码，然后用整数除以一个愚蠢的人，很显然，您可以乘以这个随机位序列，该序列在80年代被数学家证明是等效的。和我的代码变得更快。在这方面，我不必担心。
数据结构的故事要糟糕得多。我说我想把这些字节放在这里然后编译器说“非常好先生”以一种卑鄙的英国男管家的方式。我可以感觉到也许有一些判断，并且我做出了糟糕的选择，但是编译器将按照我的指示去做。 ＆＃34;龙虾·塞米多（Lobster Thermidor）镶嵌在酷牧场多力多滋（Cool Ranch Doritos）中，非常好，先生。然后阿尔弗雷德（Alfred）走开，使我陷入了我自己设计的L2缓存未命中的情况，这使我的i-5变成了486。
我认为这是C ++的一项基本设计局限性，有一天可能会通过生成元编程来解决这一局限性（也就是说，当我们可以对C ++进行编程以编写C ++时，我们可以对其进行编程以采用笨拙的OOPy-goopy数据结构，将它们重新组织成缓存喜欢的东西），但这就是Glorious Future™。现在，本文的其余部分是关于我们今天的C ++可以做什么的。
为了更快地运行，我们必须保持CPU繁忙，这意味着不等待内存。第一步是使用vector并停止使用其他所有内容-请参阅Chandler演讲的后半部分。基本上，在我们刚刚使用的东西之后紧接着我们需要下一个东西的任何数据结构都是不好的，因为内存可能不在高速缓存中。
在前往Vulkan的港口期间，我们在X-Plane中亲身体验了这一手。从OpenGL迁移到Vulkan后，驱动程序代码中的CPU时间下降了很多-驱动程序时间减少了10倍-其余所有CPU时间都在我们自己的代码中。罪魁祸首是清除代码，该代码遍历分层的边界体积树来决定要绘制的内容。
当我在2005年编写边界卷树时，我感到非常聪明。它具有出色的O（N）属性，可让我们非常高效地丢弃大量数据。如此多的胜利！
而且，它是一棵树。节点几乎从来都不是连续的，并且每当我们跳转节点时，VTune概要文件就是大量的高速缓存未命中。它运行缓慢，因为它以主内存的速度运行。
我们将其替换为可能会导致CS 102，算法和数据结构失败的结构：
1.一堆数据被保存在一个数组中，用于风景区域的一个子部分。
就是这样。它是一棵固定设计的树，深度为2，节点数实际上是无限的。
它尖叫。它比它所替换的树快得多，因为几乎每次我们都必须遍历下一个事物时，它就在缓存中。 CPU擅长理解数组，并且在我们工作时将获得下一个缓存行。辉煌！
问题太大了，您仍然需要O（N）分析，非线性运行时间等。如果您像我一样，并且已经进行了很长时间，那么心理上的调整就是N有多大进行切换。如果N为100，则不再是很大的数字-将其放在数组中并对其进行爆炸。
到目前为止，我们所做的全部工作都是将每个STL容器替换为vector。对于新代码来说，这很容易做到，因此我想这应该是一种样式决定-默认为vector，除非您确实有，否则不要选择set / maps / lists /真的，真的是很好的理由。
但是事实证明向量也不是那么好。它可以连续排列我们的对象，但可以在整个对象上使用。如果我们有一个包含大量数据的对象，其中一些数据我们一直都在触摸，而某些数据在leap年使用一次，那么我们将在很少使用的数据上浪费缓存空间。将整个对象放到一个数组中可以使我们的缓存更小，因为它们会被填充在我们附近，因为我们不会使用它们。
游戏开发人员非常熟悉该怎么做-在C ++社区中可能更少：向量为我们提供了一系列结构-每个对象都是连续的，然后我们进入下一个对象;我们真正想要的是数组的结构-对象的每个成员都是连续的，然后我们命中下一个对象。
想象我们有一个带有位置，颜色，类型和标签的形状对象。在数组世界的结构中，我们通过存储以下内容来存储4个形状：[[（location1，location2，location3，location4），（color 1，color 2，color3，color4），（type 1，type2，type3，type 4），（标签1，标签2，标签3，标签4）]。
首先，让我们注意这对于缓存有多好。当我们去查看屏幕上是否有形状时，所有位置都挤在一起了。每当我们跳过一个形状时，下一个形状的位置就是内存中的下一个位置。我们不会在不会画的东西上浪费任何缓存或内存带宽。如果标签绘图被关闭，我们可以忽略整个内存块。如此多的胜利！
其次，让我们注意这在C ++中维护是多么悲惨。我们大约100％的用于处理对象和封装的工具都无法使用，因为我们已经将经过仔细封装的对象拿走了，切掉了它们的粘性内部并将它们散布到整个地方。如果您将此代码显示给OOP专家，他们会告诉您您丢失了弹珠。 （从粗略的角度来说，SoA不是面向对象的设计，而是面向数据的设计。对象是故意切碎的！）
因此，我已经思考了一段时间的问题是：当必须使用数组结构时，如何使它们的维护痛苦最小化？ X-Plane的用户界面对性能要求不高，因此我需要采用UI小部件的多态层次结构并将其切成小块，但是渲染引擎在很多地方都需要迁移到SoA以提高性能。
到目前为止，我提出的最差的C ++看起来像这样：
您几乎可以斜着眼睛说这是一个有五个字段的对象，而您几乎可以斜着眼睛说这是一个数组。 -两者都有！诀窍是，每个成员字段都是指向第一个对象（计数）成员字段的基本指针，而下一个字段则是连续出现的。尽管所有cull_y字段不必在内存中都跟随cull_x，但如果这样做的话，那就很好了-例如，我们宁愿不在不同的VM页面上使用它们。
我们的SoA结构既可以是一个数组（因为它拥有内存并具有基本指针），但也可以是迭代器-增量运算符会递增每个基本指针。实际上，我们可以通过增加基本指针并减少计数来轻松构建子阵列，而迭代只是将较小的子阵列切成适当的位置-这非常便宜。
事实证明这很容易管理！我们最终编写了* iter.cull_x而不是iter-＆gt; cull_x，但是我们或多或少开始按预期使用数据。
我们还有一个问题：内存是从哪里分配我们的SoA的？我们需要一个帮手-可以帮助您进行整理的东西。我们的动态内存请求，并设置指向正确位置的基本指针。此代码执行的操作符为new []。
我们的分配块帮助程序对T数组（例如任意类型）进行一堆请求，并分配一个大块，该大块连续地分配它们，并填充dest_ptr指向每个数组。当我们调用detach时，单个巨型malloc（）块将返回以由客户端代码释放。
我们可以通过一个分配块提供任意数量的SoA数组，让我们将结构数组的整个结构打包到一个连续的内存区域中。使用此工具，＆＃34; alloc＆＃34; SoA的代码很容易编写。
分配帮助程序通过在运行时动态地进行分配，从而摆脱了内存布局的麻烦。这可能很好-与从操作系统实际获取内存相比，指针数学运算的成本微不足道。
当我们进行迭代时，我们正在使用内存来查找我们的数据成员。虽然存在一些数学运算可以找到给定索引处的给定成员，但我们在迭代器中为每个成员存储一个指针，而不是总共一个指针。
通过拥有自己的内存等，可以将这些结构之一转换为看起来更像值类型的东西，但是在我们的应用程序中，我发现几个SoA倾向于组合在一起成为一个更大的＆system; ，最好让系统拥有一个块。由于我们已经打开了手动管理内存的Pandora框，因此我们不妨将已完成的事情分组并减少分配器调用，同时获得更好的局部性。
总有一天，我们将进行元编程，当我们这样做时，制作一个＆＃34; soa_vector＆＃34;在给定POD数据类型的情况下，会生成如下内容：
我之所以没有在我们的代码中进行此操作，是因为必须手动编写和维护offset-fetch宏，并且对预期的数据布局的真正含义感到困惑。我敢肯定，现在使用TMP可以做到这一点，但是治愈方法会比疾病更糟糕。但是我认为，生成元编程确实可以从相对可读的源代码中实现这一级别的优化实现。
最后一点-在我的示例中，我将剔除体积的X，Y和Z坐标拆分为它们自己的数组。这是一个好主意吗？如果它是vec3结构（带有x，y，z成员），我们应该怎么做？
答案是……取决于？在我们的实际代码中，X，Y和Z出于SIMD友好性而分开-分离坐标的一个很好的副作用是，我们可以将四个对象加载到SIMD寄存器的四个通道中，然后一次对四个对象执行数学运算。这是我们将获得的最大SIMD胜利-它具有极高的缓存效率，我们不花时间将数据按摩为SIMD格式，并且获得了100％的通道利用率。如果您有机会接受SIMD，请分开字段。
但这不一定是最好的。如果我们必须一起基于XYZ进行计算，并且我们总是一起使用它们，而又不想对它们进行SIMD，则将它们打包在一起可能是有意义的（例如，我们的数据以XYZXYZXYZXYZ的形式出现，等等。）。这意味着获取位置将只需要在内存中迈出一大步，而不需要三步。如果我们希望将它们一起存储在缓存中，则可以将它们放在一起。