优化该函数（C++中）

Question

我有一个消耗 cpu 的代码，其中一些带有循环的函数被执行很多次。该循环中的每一次优化都会带来显着的性能提升。问题：你将如何优化这个循环（虽然没有太多需要优化的地方......）？

void theloop(int64_t in[], int64_t out[], size_t N)
{
    for(uint32_t i = 0; i < N; i++) {
        int64_t v = in[i];
        max += v;
        if (v > max) max = v;
        out[i] = max;
    }
}

我尝试了一些事情，例如，我用在每个循环中递增的指针替换数组，但是（令人惊讶的是）我失去了一些性能而不是获得...

编辑：

• 更改了一个变量的名称（>itsMaximums，错误）
• 该函数是一个类的方法，
• in 和 put 都是 int64_t ，因此负数和正数
• `(v > max) 可以 评估为真：考虑实际最大值为负数时的情况
• 代码在32位PC（开发）和64位（生产）上运行
• N在编译时未知
• 我尝试了一些SIMD，但未能提高性能...（将变量移动到 _m128i、执行和存储回来的开销高于 SSE 速度增益。但我不是 SSE 专家，所以也许我的代码很差

） ：

我添加了一些循环展开， 和 Alex 帖子中的一个不错的技巧。下面我粘贴一些结果：

1. 原始：14.0s
2. 展开循环（4 次迭代）：10.44s
3. Alex 的技巧：10.89s
4. 2) 和 3) 一次：11.71s

stage，4) 不比 3) 和 4) 快。 4）的代码如下：

for(size_t i = 1; i < N; i+=CHUNK) {
    int64_t t_in0 = in[i+0];
    int64_t t_in1 = in[i+1];
    int64_t t_in2 = in[i+2];
    int64_t t_in3 = in[i+3];


    max &= -max >> 63;
    max += t_in0;
    out[i+0] = max;

    max &= -max >> 63;
    max += t_in1;
    out[i+1] = max;

    max &= -max >> 63;
    max += t_in2;
    out[i+2] = max;

    max &= -max >> 63;
    max += t_in3;
    out[i+3] = max;

}

Answer 1

首先，您需要查看生成的程序集。否则，您无法知道执行此循环时实际上发生了什么。

现在：这段代码在 64 位机器上运行吗？如果没有，那些 64 位的附加功能可能会有点伤害。

该循环似乎是使用 SIMD 指令的明显候选者。 SSE2 支持许多用于整数算术的 SIMD 指令，包括一些处理两个 64 位值的指令。

除此之外，查看编译器是否正确展开循环，如果没有，请自行展开。展开循环的几次迭代，然后重新排序。将所有内存加载放在循环的顶部，以便可以尽早启动它们。

对于 if 行，检查编译器是否生成条件移动，而不是分支。

最后，查看您的编译器是否支持 restrict/__restrict 关键字。它不是 C++ 中的标准，但它对于向编译器指示 in 和 out 不指向相同的地址非常有用。

大小 (N) 在编译时已知吗？ ，请将其设为模板参数（然后尝试将 in 和 out 作为对适当大小的数组的引用传递，因为这也可能有助于编译器进行别名分析）

如果是这样 我的脑海中浮现出一些想法。但再次，研究反汇编。您需要知道编译器为您做什么，尤其是它不为您做什么。

编辑

您的编辑：

max &= -max >> 63;
max += t_in0;
out[i+0] = max;

令我印象深刻的是您添加了一个巨大依赖链。
在计算结果之前，必须对 max 求反，必须对结果进行移位，that 的结果必须与其原始值进行和运算，并且结果的 必须添加到另一个变量中。

换句话说，所有这些操作都必须串行化。在前一个任务完成之前，您无法启动其中一个任务。这不一定是加速。现代流水线乱序 CPU 喜欢并行执行许多事情。将其与一长串依赖指令捆绑在一起是您可以做的最严重的事情之一。 （当然，如果它可以与其他迭代交错，它可能会效果更好。但我的直觉是简单的条件移动指令会更好）

Answer 2

<sub>> #**Announcement** see [chat](https://chat.stackoverflow.com/rooms/5056/discussion-between-sehe-and-jakub-m)
> > _Hi Jakub, what would you say if I have found a version that uses a heuristic optimization that, for random data distributed uniformly will result in ~3.2x speed increase for `int64_t` (10.56x effective using `float`s)?_
>
I have yet to find the time to update the post, but the explanation and code can be found through the chat.
> I used the same test-bed code (below) to verify that the results are correct and exactly match the original implementation from your OP</sub>
   **Edit**: ironically... that testbed had a fatal flaw, which rendered the results invalid: the heuristic version was in fact skipping parts of the input, but because existing output wasn't being cleared, it appeared to have the correct output... (still editing...)

---

好的，我已经根据您的代码版本发布了一个基准测试，以及我建议使用 partial_sum 的基准。

在此处查找所有代码 https://gist.github .com/1368992#file_test.cpp

功能

对于默认配置，

#define MAGNITUDE     20
#define ITERATIONS    1024
#define VERIFICATION  1
#define VERBOSE       0

#define LIMITED_RANGE 0    // hide difference in output due to absense of overflows
#define USE_FLOATS    0

它将（参见输出片段此处）：

• 运行 100 x 1024 次迭代（即100 个不同的随机种子）
• ，数据长度为 1048576 (2^20)。
• 随机输入数据在整个元素数据类型 (int64_t) 上均匀分布）
• 通过生成输出的哈希摘要来验证输出数组并将其与 OP 中的参考实现进行比较。

结果

有许多（令人惊讶或不足为奇）的结果：

0. 任何算法之间没有显着性能差异（对于整数数据），前提是您正在启用优化的情况下进行编译。 （参见 Makefile；我的架构是 64 位，Intel Core Q9550 和 gcc-4.6.1）< /p>

1. < p>这些算法不相同（您会看到哈希值不同）：特别是 Alex 提出的位小提琴并没有以完全相同的方式处理整数溢出（这可以隐藏定义

   <前><代码>#define LIMITED_RANGE 1

   限制输入数据，因此不会发生溢出；请注意，partial_sum_in Correct 版本显示了等效的 C++ 非按位算术运算，它们产生相同的不同结果：

   返回 max<0 ? v : 最大值 + v; 
   

   也许，这适合您的目的？）

2. 令人惊讶同时计算最大值算法的两个定义并不更昂贵。您可以看到这是在 partial_sum_ Correct 中完成的：它在同一循环中计算 max 的两个“公式”；这实际上只不过是一个琐事，因为这两种方法都没有明显更快......

3. 更令人惊讶的是，当您能够使用时，可以实现巨大的性能提升 >float 而不是 int64_t。可以将快速而肮脏的黑客应用于基准测试

   <前><代码>#define USE_FLOATS 0

   表明，当使用 float 而不是 int64_t 时，基于 STL 的算法 (partial_sum_in Correct) 的运行速度大约快 2.5 倍 >（！！！）。
   注意：

   • partial_sum_in Correct 的命名仅与整数溢出有关，不适用于浮点数；这可以从哈希值匹配的事实看出，所以实际上它是 partial_sum_float_ Correct :)
   • 当前的 partial_sum_ Correct 实现正在做双重工作，导致其在浮点模式下表现不佳。请参阅项目符号 3。

4. （我之前提到的 OP 中的循环展开版本中存在 1 倍误差的错误）

部分求和

出于您的兴趣，部分求和应用程序在 C++11 中如下所示：

std::partial_sum(data.begin(), data.end(), output.begin(), 
        [](int64_t max, int64_t v) -> int64_t
        { 
            max += v;
            if (v > max) max = v;
            return max;
        });

Answer 3

有时，你需要退后一步，重新审视。第一个问题显然是，你需要这个吗？是否有一种替代算法可以表现得更好？

话虽这么说，假设为了这个问题您已经选择了这个算法，我们可以尝试推理我们实际拥有的内容。

免责声明：我描述的方法受到 Tim Peters 用于改进传统 introsort 实现的成功方法的启发，导致 TimSort< /a>.所以请耐心等待；）

1。提取属性

我看到的主要问题是迭代之间的依赖性，这将阻止许多可能的优化并阻止许多并行化尝试。

int64_t v = in[i];
max += v;
if (v > max) max = v;
out[i] = max;

让我们以功能性的方式重新编写这段代码：

max = calc(in[i], max);
out[i] = max;

哪里：

int64_t calc(int64_t const in, int64_t const max) {
  int64_t const bumped = max + in;
  return in > bumped ? in : bumped;
}

或者更确切地说，一个简化的版本（由于未定义而没有溢出）：

int64_t calc(int64_t const in, int64_t const max) {
  return 0 > max ? in : max + in;
}

你注意到提示点了吗？行为的变化取决于 ill-named(*) max 是正数还是负数。

这个临界点使得更仔细地观察 in 中的值变得有趣，特别是根据它们可能对 max 产生的影响：

• max max in 0 和 in[i] 0 然后 out[i] = in[i] 0
• 最大< 0 和 in[i]> 0 然后 out[i] = in[i] > 0
• 最大> 0 和 in[i] 0 然后 out[i] = (max + in[i]) ?? 0
• 最大> 0 和 in[i]> 0 则 out[i] = (max + in[i]) > 0

(*) 名字不好，因为它也是一个累加器，但名称隐藏了它。不过我也没有更好的建议。

2.优化操作

这使我们发现了有趣的情况：

• 如果我们有一个仅包含负值的数组切片[i, j)（我们称之为负切片），那么我们可以这样做a std::copy(in + i, in + j, out + i) 和 max = out[j-1]
• 如果我们有一个切片 [ i, j) 只包含正值的数组，然后它是一个纯粹的累积代码（可以很容易地展开）
• 一旦 in[i] 为正数，max 就会变为正数

因此，它可能很有趣（但也许不是，我不作任何承诺）在实际使用输入之前建立输入的配置文件。请注意，对于大输入，可以逐块制作配置文件，例如根据缓存行大小调整块大小。

作为参考，这 3 个例程：

void copy(int64_t const in[], int64_t out[],
          size_t const begin, size_t const end)
{
  std::copy(in + begin, in + end, out + begin);
} // copy

void accumulate(int64_t const in[], int64_t out[],
                size_t const begin, size_t const end)
{
  assert(begin != 0);

  int64_t max = out[begin-1];

  for (size_t i = begin; i != end; ++i) {
    max += in[i];
    out[i] = max;
  }
} // accumulate

void regular(int64_t const in[], int64_t out[],
             size_t const begin, size_t const end)
{
  assert(begin != 0);

  int64_t max = out[begin - 1];

  for (size_t i = begin; i != end; ++i)
  {
    max = 0 > max ? in[i] : max + in[i];
    out[i] = max;
  }
}

现在，假设我们可以使用简单的结构以某种方式表征输入：

struct Slice {
  enum class Type { Negative, Neutral, Positive };
  Type type;
  size_t begin;
  size_t end;
};

typedef void (*Func)(int64_t const[], int64_t[], size_t, size_t);

Func select(Type t) {
  switch(t) {
  case Type::Negative: return ©
  case Type::Neutral: return ®ular;
  case Type::Positive: return &accumulate;
  }
}

void theLoop(std::vector<Slice> const& slices, int64_t const in[], int64_t out[]) {
  for (Slice const& slice: slices) {
    Func const f = select(slice.type);
    (*f)(in, out, slice.begin, slice.end);
  }
}

现在，除非 introsort 循环中的工作很少，所以计算特征可能成本太高......但是它会导致本身就可以并行化。

3.简单并行化

请注意，表征是输入的纯函数。因此，假设您以每个块的方式工作，则可以并行地拥有：

• Slice Producer：一个表征器线程，用于计算 Slice::Type 值
• Slice Consumer：一个工作线程线程，实际执行代码

即使输入本质上是随机的，只要块足够小（例如，CPU L1 缓存行），也可能有它可以工作的块。两个线程之间的同步可以通过简单的 Slice 线程安全队列（生产者/消费者）并添加 bool last 属性来停止消费或通过创建 Slice 来完成。 code>Slice 具有 Unknown 类型的向量，并让消费者阻塞直到它已知（使用原子）。

注意：因为人物塑造是纯粹的，所以它是令人尴尬的平行。

4.更多并行化：推测性工作

请记住这句天真的言论：只要 in[i] 为正值，max 就会变为正值。

假设我们可以（可靠地）猜测 Slice[j-1] 将产生一个负的 max 值，那么对 Slice[j] 的计算 与之前的内容无关，我们现在就可以开始工作！

当然，这是一个猜测，所以我们可能是错的......但是一旦我们完全表征了所有切片，我们就有了闲置的核心，所以我们不妨将它们用于推测性工作！如果我们错了呢？好吧，消费者线程将简单地删除我们的错误并用正确的值替换它。

推测性计算 Slice 的启发式应该很简单，并且必须进行调整。它也可能具有适应性......但这可能更困难！

结论

分析您的数据集并尝试查找是否可以打破依赖关系。如果是的话，即使不使用多线程，您也可以利用它。

Answer 4

如果 max 和 in[] 的值远离 64 位最小值/最大值（例如，它们始终在 -2⁶¹ 和+2⁶¹），您可以尝试没有条件分支的循环，这可能会导致一些性能下降：

for(uint32_t i = 1; i < N; i++) {
    max &= -max >> 63; // assuming >> would do arithmetic shift with sign extension
    max += in[i];
    out[i] = max;
}

理论上编译器也可能会执行类似的技巧，但如果没有看到反汇编，则很难来判断它是否做到了。

Answer 5

代码看起来已经相当快了。根据 in 数组的性质，您可以尝试特殊的大小写，例如，如果您碰巧知道在特定调用中所有输入数字均为正数，则 out[i] 将等于累积和，而无需一个 if 分支。

Answer 6

确保方法不是虚拟、内联、_属性_((always_inline))和 -funroll-loops 似乎是值得探索的不错选择。

只有通过对它们进行基准测试，我们才能确定它们是否值得在您的大型程序中进行优化。

Answer 7

唯一想到的可能有一点帮助的是在循环中使用指针而不是数组索引，类似于

void theloop(int64_t in[], int64_t out[], size_t N)
{
    int64_t max = in[0];
    out[0] = max;
    int64_t *ip = in + 1,*op = out+1;

    for(uint32_t i = 1; i < N; i++) {
        int64_t v = *ip; 
        ip++;
        max += v;
        if (v > max) max = v;
        *op = max;
        op++
    }
}

这里的想法是数组的索引很容易编译为数组的基地址，将元素的大小乘以索引，然后将结果相加以获得元素地址。保持运行指针可以避免这种情况。我猜一个好的优化编译器已经可以做到这一点，所以您需要研究当前的汇编器输出。

Answer 8

int64_t max = 0, i;

for(i=N-1; i > 0; --i) /* Comparing with 0 is faster */  
{  
    max = in[i] > 0 ? max+in[i] : in[i];
    out[i] = max;

    --i;  /* Will reduce checking of i>=0 by N/2 times */  

    max = in[i] > 0 ? max+in[i] : in[i]; /* Reduce operations v=in[i], max+=v by N times */  
    out[i] = max;         
}

if(0 == i) /* When N is odd */
{ 
    max = in[i] > 0 ? max+in[i] : in[i]; 
    out[i] = max;
}