大规模数组和内存不足错误
- 整个程序由数十亿个“Foos”组成的大数组组成；
首先，对于＃2，如果跨越数GB，则您可能会发现自己或用户（如果其他人运行软件）经常无法成功分配此数组。这里的一个常见错误是认为内存不足错误意味着“没有更多内存可用”，而它们实际上经常意味着操作系统找不到匹配所请求的内存大小的未使用页面的连续集。因此，人们经常感到困惑，例如他们请求分配1 GB块，尽管有30 GB物理内存可用，但它仍然失败。一旦开始分配跨度超过可用典型内存量的1％的大小的内存，通常就需要考虑避免使用一个巨大的数组来表示整个结构。
因此，也许您需要做的第一件事情是重新考虑数据结构。您可以将其分配给更小的块（聚合在一起的更小的数组），从而显著减少遇到问题的几率。例如，如果您的访问模式完全是顺序的，那么可以使用展开列表（链接在一起的数组）。如果需要随机访问，则可以使用指针数组，每个指针数组跨度为4千字节。这需要更多的工作来索引元素，但对于数十亿个元素的这种规模，通常是必要的。
访问模式
问题中未指定内存访问模式，这一部分对于指导决策至关重要。
例如，数据结构是否仅以顺序方式遍历，或者是否需要随机访问？所有这些字段（a、b、c、d）是否始终一起需要，还是可以一次或两次或三次访问它们？
让我们尝试涵盖所有可能性。在我们谈论的规模上，这样做：
struct Foo {
int a1;
int b1;
int c1;
int d1
};
这种做法可能没有太大帮助。在这种输入规模和紧密循环访问的情况下，您的时间通常会受到内存层次结构（分页和CPU缓存）上层的支配。不再需要过于关注层次结构的最低级别（寄存器和相关指令）。换句话说，在处理数十亿个元素时，您应该担心的最后一件事情是将该内存从L1缓存行移动到寄存器以及位运算指令的成本（并不是说这完全不重要，只是说它优先级较低）。
如果数据规模足够小，可以将整个热数据放入CPU缓存，并且需要进行随机访问，则此类简单表示法可以显示出性能提升，因为在层次结构的最低级别（寄存器和指令）方面有所改进，但需要比我们谈论的规模小得多。
因此，即使如此，这也可能是一个相当大的改进：
struct Foo {
char a1;
char b1;
char c1;
char d1;
};
... 这甚至更多：
struct Foo {
char a4;
char b4;
char c4;
char d4;
};
* 请注意，您可以使用位域来完成上述操作，但位域通常会有与使用的编译器相关的注意事项。由于常见的可移植性问题，我经常小心避免使用它们，尽管在您的情况下可能是不必要的。然而，当我们进入SoA和热/冷字段拆分领域时，我们将达到无法使用位域的地步。
此代码还侧重于水平逻辑，这样可以更轻松地探索一些其他优化路径（例如：将代码转换为使用SIMD），因为它已经处于微型SoA形式中。
数据“消耗”
特别是在这种规模下，即使是你的内存访问是顺序的，按照数据“消耗”（机器加载数据、进行必要的算术运算并存储结果的速度）思考也很有帮助。一个我觉得有用的简单想象图像是将计算机想象成“大嘴巴”。如果我们每次喂给它足够大的一勺数据，而不是小小的茶匙，并且将更多相关的数据紧密地打包到一勺中，它就会更快。
热/冷字段拆分
到目前为止，上述代码假设所有这些字段都是同样“热”的（经常访问），并且一起访问。您可能有一些“冷”字段或仅在成对的关键代码路径中访问的字段。假设您很少访问c和d，或者您的代码具有一个关键循环，访问a和b，另一个循环访问c和d。在这种情况下，将其拆分为两个结构可能会很有帮助：
struct Foo1 {
char a4;
char b4;
};
struct Foo2 {
char c4;
char d4;
};
如果我们向计算机“喂”数据，而我们的代码目前只对a和b字段感兴趣，那么如果我们有仅包含a和b字段的连续块，而不包含c和d字段，则可以将更多的内容打包进a和b字段的一小部分中。在这种情况下，c和d字段是计算机暂时无法处理的数据，但会混合到a和b字段之间的内存区域中。如果我们希望计算机尽可能快地消耗数据，我们应该只向其提供目前感兴趣的相关数据，因此在这些情况下拆分结构是值得的。
逐行访问的SIMD SoA
向量化并假设顺序访问，计算机能够以最快的速度消耗数据的速率通常是使用SIMD进行并行。在这种情况下，我们可能会得到这样的表示形式：
struct Foo1 {
char* a4n;
char* b4n;
};
…需要特别注意对齐和填充（对于AVX，大小/对齐应为16或32字节的倍数，甚至对于未来的AVX-512也是64字节），以便使用更快的对齐移动到XMM/YMM寄存器（将来可能使用AVX指令）。
随机/多字段访问的AoSoA
不幸的是，如果经常同时访问a和b，尤其是在随机访问模式下，上述表示法往往会失去很多潜在好处。在这种情况下，更优化的表示方法如下：
struct Foo1 {
char a4x32[32];
char b4x32[32];
};
现在我们正在聚合这个结构，使a和b字段不再相互分散，允许32个a和b字段组合成一个64字节的缓存行，并快速访问。现在，我们还可以将128或256个a或b元素装入XMM/YMM寄存器。
性能分析
通常情况下，在性能问题中我会避免给出一般性的建议，但是我注意到这个问题似乎缺少了性能分析工具提供的详细信息。如果已经在积极使用分析工具，那么请忽略这一部分，否则我会为您介绍一些基础知识。
作为一个例子，我经常能够优化比我更懂计算机体系结构的人编写的生产代码（我曾与许多来自打孔卡时代的人们共事，他们可以轻松看懂汇编代码），并常常被叫来优化他们的代码（这感觉非常奇怪）。原因很简单：我“作弊”地使用了分析工具（VTune），而我的同事们经常不用（他们对此过敏，并认为他们了解热点问题就像分析工具一样，并且认为使用分析工具是浪费时间）。
当然，最理想的情况是找到既有计算机体系结构专业知识又懂得如何使用分析工具的人，但是如果缺乏其中之一，分析工具可以给我们带来更大的优势。优化仍然需要基于最有效的优先级排序的生产力思维模式，而最有效的优先级排序是优化那些真正最重要的部分。分析工具可以详细地解析花费了多少时间以及在哪里花费的时间，还可以提供有用的指标，如缓存未命中和分支预测错误。即使是最高级别的人通常也无法像分析工具一样准确地预测这些指标。此外，性能分析往往是发现计算机体系结构如何更快地运行的关键，通过追踪热点并研究它们为什么存在，加快了对计算机体系结构的理解。对我来说，性能分析是更好地理解计算机体系结构实际工作方式的终极入口，而不是我想象的工作方式。只有这样，像Mysticial这样经验丰富的人的写作才会变得越来越清晰明了。
接口设计
这里可能开始显现出许多优化的可能性。这种问题的答案将是关于策略而不是绝对方法的。在试用某些方法并在需要时迭代向更优解决方案的过程中，还有许多东西需要后来者去发现和改进。
在复杂的代码库中，一个困难就是要为接口留出足够的空间来进行实验和尝试不同的优化技术，以便不断迭代向更快的解决方案。如果接口留出了这些优化的空间，则即使有试错心态，我们也可以整天进行优化，并通过正确的测量手段获得
通常，在实现中留出足够的空间来尝试和探索更快的技术，往往需要接口设计能够批量接收数据。特别是当接口涉及间接函数调用（例如通过dylib或函数指针）时，内联不再是有效的可能性。在这种情况下，为了避免接口断裂，留出优化空间通常意味着设计远离接收简单标量参数的思维模式，而是选择传递整个数据块的指针（如果存在各种交错可能性，则可能带有步幅）。因此，虽然这涉及到一个相当广泛的领域，但在优化方面的许多重点都将归结为留出足够的空间来优化实现，而不会在整个代码库中引起级联更改，并随时准备好使用分析器指导您正确的方向。
总之，这些策略中的一些应该有助于指导您正确的方向。这里没有绝对的东西，只有指南和要尝试的事情，并且最好在手头拥有分析器的情况下完成。然而，当处理如此巨大规模的数据时，始终值得记住饥饿的怪物形象，以及如何以最有效的方式向其提供适当大小和包装的相关数据。
a的一次遍历，或者只关心一半结构体中的d的一次遍历？ - rob mayoff