数据布局问题

数据布局问题是一大类相关问题，起源于程序员或编译器如何组织程序在内存中使用的变量和对象。这受数据结构和数据类型的选择以及此类结构中对象的排序的影响。

所有数据布局问题的共同属性是经常使用的数据与很少或从不使用的数据混合在同一个缓存行中。发生这种情况的原因有很多。

糟糕的数据布局会受到两次惩罚：

糟糕的数据布局会增加保存常用数据所需的缓存行数，从而增加缓存未命中和缓存行提取的次数。

例如，假设应用程序的一部分经常需要按顺序遍历大量 8 字节的值，并且处理器使用 64 字节的高速缓存行。如果数据以最佳方式打包，则每个缓存行中可以存储其中的 8 个值，但如果它与其他 8 字节值交错，则每个缓存行中只能存储 4 个值。对于打包不良的数据，在遍历值时需要访问两倍的行，并且在相同的未命中率下，它会导致两倍的缓存未命中。

糟糕的数据布局也会通过减少有效缓存大小 来增加缓存未命中率，也就是说，如果数据打包不当，则不太有用的数据将适合一定大小的缓存。这种糟糕的数据布局会增加缓存未命中率。

例如，在上面的示例中，与交错情况相比，最佳打包情况下缓存中频繁访问的值的数量是其两倍。

由于糟糕的数据布局增加了缓存行获取的数量，它也增加了应用程序的内存带宽需求。对于受可用内存带宽限制的应用程序，这可能会严重影响性能。

部分使用的结构

数据布局不佳的一个常见原因是仅部分使用的结构。现代编程范式要求人们在结构或对象中收集相关数据。但是，这通常对缓存性能有害。

考虑以下示例。这里我们有一个结构，我们有四个字段a，b，c 和d。所有字段都可以在应用程序的某处使用，但a和b仅在性能最关键的循环中使用。

尽管如此，将未使用的字段从内存中带入缓存，使缓存行读取次数增加一倍并占用缓存空间的一半。

如果可以重写此代码，以便将很少使用的字段移动到单独的结构中：

性能关键循环现在只会将实际使用的字段加载到缓存中。

这种优化应该只在实际需要时使用。大多数程序员会发现修改后的代码丑陋且难以阅读，而且这种变化与所有关于编程的教导背道而驰。但是，如果谨慎使用，这种优化可以带来非常大的性能改进。

数据类型太大

与拥有未使用的字段非常相似的一个问题是使用比必要的更大的数据类型。效果是一样的。更少的字段适合每个缓存行，导致更多的缓存行提取和更高的缓存未命中率。

例如，如果在 16 位数据类型就足够的地方使用 64 位数据类型，则只有四分之一的元素适合缓存行。

不幸的是，Freja 无法确定数据类型是否大于所需的数量。因此生成的报告不会警告此类问题，你必须手动检查代码。

对齐问题

许多现代处理器需要对对齐地址进行内存访问。一些处理器支持未对齐访问，但对齐内存访问的性能通常更好。

大多数处理器需要自然对齐。这意味着字段必须存储在其大小的倍数的地址，例如，4 字节的字段必须存储在 4 的倍数的地址，而 8 字节的字段必须是存储在 8 的倍数的地址中。

编译器知道这一点，并在变量和字段之间插入填充，以确保每个字段的起始地址与其特定数据类型正确对齐。这种填充会消耗高速缓存空间，并且通常可以通过对结构成员进行仔细排序来避免或最大限度地减少这种浪费。考虑这个例子：

假设 char 是 1 字节数据类型，int 是 4 字节数据类型。然后，编译器将在字段a和b之间布置三个字节的填充数据 ，并确保b存储在 4 的倍数的偏移量处。

如果把字段a放在b后，无需填充即可满足所有字段的对齐要求。

你当然可以自己计算结构中的偏移量并确保所有字段在没有任何填充的情况下正确对齐，但是确保没有不必要的填充的更简单方法是根据对齐要求简单地对字段进行排序。从对齐要求最高的字段开始，然后以对齐要求递减顺序继续处理字段。

如果你的结构太大以至于它使用了多个缓存行，你可能希望确保最常用的字段靠在一起，这样你就可以避免混合使用频繁的字段和很少使用的字段。

我们现在已经消除了结构中的内部对齐填充。但是，对整个结构也有对齐要求。考虑这个创建结构数组的例子：

例如，该结构可能需要 8 字节对齐。由于该结构有 6 个字节大，编译器必须在数组中的每个结构之间插入 2 个字节的填充以确保对齐。

像这样的外部对齐比内部对齐更难避免。一种方法是拆分不常用的字段。

如果处理器不严格要求对齐，而只是为了更好的性能而更喜欢它，例如 x86 处理器，编译器可能会提供 pragma，你可以使用它来告诉它不要插入任何填充。减少高速缓存未命中带来的性能提升可能超过未对齐内存访问的成本。

然而，使用这样的未对齐结构可能会导致其他问题，例如，使用此类编译指示编译的共享库可能与使用其他编译器编译的代码不兼容。

动态内存分配

标准内存分配器的许多实现都保留了与每块已分配内存相邻的额外内务处理数据。此数据通常仅在分配和取消分配区域时使用，并且不会用于应用程序执行的大部分。

如果许多小的内存分配是由应用程序完成的，那么缓存行的很大一部分可能会被这些内务处理数据占用。考虑一个分配 32 字节结构的应用程序，其内存分配器分配 16 字节的数据用于内务处理：

这个问题可以通过避免分配许多单独的对象来避免。如果需要分配 1000 个对象，请分配一个包含 1000 个对象的数组，而不是分配 1000 个单独的对象。

你甚至可能想要考虑实施您自己的自定义内存管理。它可以分配一个相当大的内存块，然后在这个块内分发内存区域。这样开销就保持在最低限度。

还有一些可用的替代内存分配包，可以将它们的内务处理数据分配到与分配内存不同的内存区域，以避免此类问题。

动态内存分配也可能将分配的内存区域分布在堆上，从而导致随机访问模式。