通过优秀的设计减少缓存未命中数

Question

如何在设计C++程序时减少可能的缓存未命中数？

内联函数是否每次都有帮助？或者只有当程序是CPU有界的时候（即程序是面向计算的而不是面向I/O的）才是好的？

Answer 1

以下是我在处理这类代码时需要考虑的一些事情。

• 考虑您是否想要“结构的数组”或“结构数组”。你想要使用的将取决于数据的每一部分。
• 尝试将结构保持为32个字节的倍数，以便均匀地打包缓存行。
• 在冷热元素中对数据进行分区。如果你有一组o类的对象，并且你经常一起使用ox，oy，oz，但偶尔需要访问oi，oj，那么请考虑将ox，oy和oz放在一起，然后移动i，j和k部分到平行的腋窝数据结构。
• 如果您有多维数据数组，然后使用通常的行顺序布局，则沿着首选维度扫描时访问速度会非常快，而在其他位置扫描时会非常缓慢。沿着任何维度遍历时，沿着space-fillingcurve映射它将有助于平衡访问速度。 （阻塞技术是相似的 - 它们只是具有较大基数的Z阶。）
• 如果您必须导致缓存未命中，请尝试尽可能多地使用该数据来分摊成本。
• 你在做什么多线程？注意缓存一致性协议的减速。填充标志和小计数器，以便它们位于单独的缓存行中。
• 英特尔的SSE提供了一些预取内在函数，前提是您知道提前访问的内容。

Answer 2

允许CPU有效地预取数据。例如，您可以减少按行处理多维数组的数量缓存未命中，而不是按列，展开循环等。

这种优化取决于硬件架构，因此您最好使用某种平台特定的分析器，如英特尔VTune检测缓存可能存在的问题。

Answer 3

有一个非常不错的视频由Herb萨特说提到这个话题here

对于数据绑定操作

1. 使用数组&载体在列表，地图由&套

2. 过程列上的行

Answer 4

避免在没有必要时使用动态内存。使用新的，删除，智能指针等，往往会将你的程序数据传播到内存中。这不好。如果您可以将大部分数据保存在一起（例如通过在堆栈中声明对象），缓存肯定会更好。

Answer 5

内联函数运行会危害指令缓存。如果内存没有被绑定，那么就不太可能产生太多（如果有）差异。

与往常一样，任何优化都应该通过分析而不是直觉告知。更不用说，您需要了解剖析器告诉您的内容，这意味着熟悉汇编语言以及您正在优化的plaftorm的特定特性。

现在有点老了，但迈克Abrash的“图形编程黑皮书”仍然有很多很好的一般建议。

Answer 6

另外，如果你在做C++和多线程，你需要考虑每个处理器的缓存上的虚假共享，局部性和数据的热度。这可以造成很大的差异。尤其在多线程计算中，采用LIFO方式的计算比以FIFO方式进行计算更有效，但它在单处理器体系结构中也是有效的。