数组的结构和结构体的数组 - 性能差异

Question

数组的结构和结构体的数组 - 性能差异

13

我有一个类似这样的类：

//Array of Structures
class Unit
{
  public:
    float v;
    float u;
    //And similarly many other variables of float type, upto 10-12 of them.
    void update()
    {
       v+=u;
       v=v*i*t;
       //And many other equations
    }
};

我创建了一个Unit类型的对象数组，并对它们调用了update方法。

int NUM_UNITS = 10000;
void ProcessUpdate()
{
  Unit *units = new Unit[NUM_UNITS];
  for(int i = 0; i < NUM_UNITS; i++)
  {
    units[i].update();
  }
}

为了提高速度，可能还可以自动向量化循环，我将AoS转换为数组结构。

//Structure of Arrays:
class Unit
{
  public:
  Unit(int NUM_UNITS)
  {
    v = new float[NUM_UNITS];
  }
  float *v;
  float *u;
  //Mnay other variables
  void update()
  {
    for(int i = 0; i < NUM_UNITS; i++)
    {
      v[i]+=u[i];
      //Many other equations
    }
  }
};

当循环无法自动向量化时，结构数组的性能非常差。对于50个单位，SoA（结构化数组）的更新稍微比AoS（数组的结构化）快一些。但是从100个单位开始，SoA比AoS慢。在300个单位处，SoA几乎是AoS的两倍糟糕。在十万个单位处，SoA比AoS慢4倍。虽然缓存可能会影响SoA，但我没有预料到性能差异会这么大。在cachegrind上进行分析显示，两种方法的缺失数量相似。一个单位对象的大小为48个字节。L1缓存为256K，L2为1MB，L3为8MB。我错过了什么？这真的是一个缓存问题吗？

编辑：我正在使用gcc 4.5.2。编译器选项是-o3-msse4-ftree-vectorize。

我在SoA中进行了另一个实验。我不是在动态分配数组，而是在编译时分配“v”和“u”。当有10万个单位时，这会带来比动态分配数组的SoA快10倍的性能。这是怎么回事？为什么静态分配内存和动态分配内存之间有如此大的性能差异？

- excray

你用什么编译器选项来构建这个程序？ - Sergey K.

不确定这是否有所不同，但是 std::valarray 可能会（或可能不会）有所帮助。它专为在整个数组上执行数学运算而设计（具有更清晰的语法），但我猜测实现者可能会有特殊的重载来尝试优化这些操作并进行智能分配等。它可能根本没有帮助，但值得一看。 - pstrjds

1

在运行基准测试之前将数据集清零会发生什么？未初始化的浮点数很有可能会成为非规格化数。您不希望这会破坏您的基准测试。 - Mysticial

4个回答

1

预取对于那些大部分时间都在等待数据出现的代码至关重要。现代前端总线具有足够的带宽，只要程序没有超越当前加载集合过远，预取应该是安全的。

由于各种原因，在C++中，结构体和类可能会导致许多性能问题，并且可能需要更多的调整才能获得可接受的性能水平。当代码很大时，请使用面向对象编程。当数据很大（并且性能很重要）时，请勿使用。

float v[N];
float u[N];
    //And similarly many other variables of float type, up to 10-12 of them.
//Either using an inlined function or just adding this text in main()
       v[j] += u[j];
       v[j] = v[j] * i[j] * t[j];

- Max

2

我认为OOP不应该与使用AoS混淆。在OOP中，标量场可以被视为一个对象，就像在数学中一样，但是如果您使用多个标量场表示空间区域，则使用SoA方式与OOP一致。这归结于您在OOP中如何看待对象。 - 16807

1

好观点。我应该提到运行时多态性、构造函数开销等。面向对象的语言倾向于提供许多易于使用的功能，但必须包含大量的多余代码和开销，导致二进制文件变慢。面向对象的代码不一定很慢，C++已经证明了模板和类有时可以提供更高级别的抽象，使编译器延迟优化并获得稍微更好的性能。 - Max

1

有两件事情你需要注意，它们可能会有很大的差别，这取决于你的CPU：

对齐
缓存行别名

由于你正在使用SSE4，使用一个专门的内存分配函数来返回一个在16字节边界对齐的地址，而不是使用new，可能会给你带来提升，因为你或编译器将能够使用对齐的加载和存储。我没有注意到在新的CPU上有太大的区别，但在旧的CPU上使用非对齐的加载和存储可能会慢一点。

至于缓存行别名，英特尔在其参考手册中明确提到了它（搜索“Intel® 64 and IA-32 Architectures Optimization Reference Manual”）。英特尔表示这是你需要注意的问题，特别是在使用SoA时。所以，你可以尝试填充数组，使它们的低6位地址不同。这样做的想法是避免它们争夺同一个缓存行。

- user1593842

0

当然，如果您没有实现向量化，那么进行SoA转换的动力就不是很大。

除了__RESTRICT的广泛实际接受，gcc 4.9还采用了#pragma GCC ivdep来打破假定的别名依赖关系。

至于使用显式预取，如果有用的话，当然您可能需要更多的预取来处理SoA。主要的重点可能是通过提前获取页面来加速DTLB缺失解决，因此您的算法可能会变得更加缓存饥饿。

我认为，在没有更多细节（包括有关您的操作系统的具体信息）的情况下，无法对所谓的“编译时”分配进行智能评论。毫无疑问，高级别分配和重复使用分配的传统非常重要。

- tim18

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergey K. · Accepted Answer

在这种情况下，数组的结构不够友好，无法充分利用缓存。

你同时使用了u和v，但是如果它们分别存在两个不同的数组中，它们将不能同时被加载到一个缓存行中，因此缓存未命中将会导致巨大的性能损失。

_mm_prefetch可以用于使AoS表示方法更快。