优化循环与复制代码：哪个更好？

Question

我的问题是如何最好地处理可以接受参数的长重循环。考虑以下方法：

void HeavyLoop(byte* startingAddress, bool secondaryModification)
{
    for (int i = 0; i < 10000000; i++)
    {
        byte* b = startingAddress + i;
        *b+= 1;
        if (secondaryModification) *b+= 2;
    }
}

这种方法可以实现我想要的功能，但是在循环中使用了10000000个不必要的if语句。

如果我像这样编写相同的方法：

void HeavyLoop(byte* startingAddress, bool secondaryModification)
{
    if (secondaryModification)
    {
        for (int i = 0; i < 10000000; i++)
        {
            byte* b = startingAddress + i;
            *b+= 1;
            *b+= 2;
        }
    }
    else
    {
        for (int i = 0; i < 10000000; i++)
        {
            byte* b = startingAddress + i;
            *b+= 1;         
        }
    }   
}

我将得到相同的结果，但我的整个循环代码必须被复制。如果我们只讨论一个参数，这并不是什么大问题，但当你有4个独立的参数时，我必须编写16个不同版本的循环。

在这种情况下，“正确”的解决方案是什么？如果这是像Python这样的语言，我可以动态构建一个函数来处理循环。C++中是否有类似的东西？

不用说，代码只是一个例子，而不是实际情况。请不要给出与 *b+=1 有关的解决方案。如果有语法错误，请原谅我，因为我现在没有编译器。

编辑：问题是处理不能在循环外预先计算的语句。

- Rotem

---

我认为你需要提供一个稍微复杂一些的例子，否则像Kerrek提供的简单解决方案将会被发布。 - duedl0r

你是否已经证明了编译器本身不会进行这种优化？将不变量提升出循环是一项长期以来的标准优化，而且实现起来也很容易。 - user395760

@delnan：即使不将循环提升，CPU 的动态分支预测也应该能够很好地处理这个问题。因此，尽管我同意如果编译器已经进行了优化，那么进行这种优化是毫无意义的，但请注意，即使编译器没有进行优化，进行这种优化也可能是毫无意义的。 - Steve Jessop

@Steve：CPython不会，它是一个解释器。另一方面，PyPy具有跟踪JIT编译器。消除条件跳转和内联调用是跟踪JIT所做的最少事情。并且由于它的构造方式，它根本不在乎代码是手动编写还是动态创建的。还有循环不变式代码移位，因此它应该将任何可能留在循环外的“guard”提升出来，而不管变量来自哪里。 - user395760

@KerrekSB - 我主要想知道如何在长循环中消除不必要的 if 检查，我认为这个问题并不严重依赖于实际语句，对吗？ - Rotem

Answer 1

你可以将循环实现为一个模板；模板参数是编译时常量，因此优化器应该在其为假时删除不需要的代码。然后你需要一个包装器，在运行时根据特定值调用正确的特化。

template <bool secondaryModification>
void HeavyLoop(byte* startingAddress)
{
    for (int i = 0; i < 10000000; i++)
    {
        byte* b = startingAddress + i;
        *b+= 1;
        if (secondaryModification) *b+= 2;
    }
}

void HeavyLoop(byte* startingAddress, bool secondaryModification)
{
    if (secondaryModification) {
        HeavyLoop<true>(startingAddress);
    } else {
        HeavyLoop<false>(startingAddress);
    }
}

在编译时，两个版本的模板都将被实例化（一个包含*b+=2;，另一个不包含，并且都不对参数进行运行时测试）；然后它们应该被内联到包装函数中，以生成与第二个示例完全相同的代码 - 但不需要复制任何源代码。

- Mike Seymour

---

这看起来很有趣，我对C++中的模板函数不熟悉。我不确定你所说的“模板参数是编译时常量”的意思是什么。编译器是否静态地创建了两个单独的函数（每个可能的secondaryModification值一个），还是在调用HeavyLoop<true>(startingAddress)之前在运行时创建函数？ - Rotem

@Rotem：在编译时生成两个函数；通常，如果需要，模板特化始终会在编译时生成。 - Mike Seymour

哦，我明白了。所以如果代码中没有调用过 HeavyLoop<false>(startingAddress)，编译器就不会静态生成这个特化版本了？ - Rotem

@Rotem：没错。只有在需要时或者你显式实例化它（即 template void HeavyLoop<false>(byte*);）时，模板特化才会被实例化。 - Mike Seymour

@MikeSeymour，现在看看你干了什么：https://dev59.com/W3fZa4cB1Zd3GeqPUq5g - doctorlove

Answer 2

编辑：为更好地满足原帖作者的需求并消除冗余信息，本贴已经进行了全面修改。

当然，我会假设你已经对此进行了性能分析，并且已经确定这是个热点……对吧？

事实上，我敢打赌你没有这样做。而且你可能严重低估了你的编译器。

例如，以下是使用LLVM编译的你的代码：

void f1(char*);
void f2(char*);

void loop(char* c, int n, int sm) {
  for (int i = 0; i < n; ++i) {
    if (sm) f1(c);
    else f2(c);
  }
}

这将产生：

define void @loop(i8* %c, i32 %n, i32 %sm) nounwind uwtable {
  %1 = icmp sgt i32 %n, 0
  br i1 %1, label %.lr.ph, label %._crit_edge

.lr.ph:                                           ; preds = %0
  %2 = icmp eq i32 %sm, 0
  br i1 %2, label %3, label %5

; <label>:3                                       ; preds = %3, %.lr.ph
  %i.01.us = phi i32 [ %4, %3 ], [ 0, %.lr.ph ]
  tail call void @f2(i8* %c) nounwind
  %4 = add nsw i32 %i.01.us, 1
  %exitcond = icmp eq i32 %4, %n
  br i1 %exitcond, label %._crit_edge, label %3

; <label>:5                                       ; preds = %5, %.lr.ph
  %i.01 = phi i32 [ %6, %5 ], [ 0, %.lr.ph ]
  tail call void @f1(i8* %c) nounwind
  %6 = add nsw i32 %i.01, 1
  %exitcond2 = icmp eq i32 %6, %n
  br i1 %exitcond2, label %._crit_edge, label %5

._crit_edge:                                      ; preds = %5, %3, %0
  ret void
}

即使您不了解LLVM IR，只需关注"sm"变量即可：

.lr.ph:                                           ; preds = %0
  %2 = icmp eq i32 %sm, 0
  br i1 %2, label %3, label %5

编译器生成了两个不同的循环（分别从 <label>:3 和 <label>:5 开始），并且最终选择一次性在函数开头执行循环。

这是一个相当常见的编译器技巧：循环不变式代码移动（和衍生技术），所以为什么要手动去做呢？如果编译器认为值得，它会这样做！

- Matthieu M.

---

+1 是为了向我展示一些我不知道的酷东西，但我的问题是如何处理循环外无法预先确定的值。如果从问题中没有表达清楚，我深感抱歉。 - Rotem

@Rotem：我完全改变了答案，以更好地展示您所寻找的行为（使用纯声明，使编译器无法看穿各种操作）。看看它是如何简单地复制循环代码，专门针对 sm == true（标签5）或 sm == false（标签3）进行优化，并将比较提升出循环呢 :) ? - Matthieu M.

这非常有趣，验证了其他人在这个问题中所说的声明。谢谢你抽出时间来。 - Rotem

太遗憾了，我不能给出比+1更多的评分 - 这是唯一合理的答案。为什么要用模板混淆代码，去做任何一个半好的编译器都会做的事情呢？（如果它不这样做，你就有比这更大的性能问题）手动优化最好的效果是避免一个分支（至少我真的看不出任何给出的带有模板等的答案，除了将不变量提出循环之外还做了什么）。 - Voo

@Matthieu：我已经测试了这种方法（没有手动优化）和Mike建议的模板函数。测试函数需要5个布尔参数。当所有参数都传递为true，或者换句话说，当不需要丢弃任何代码分支时，性能没有区别。但是，当它们都是false时，性能会有约35％的差异。然而，由于缺乏经验，我可能只是没有正确设置某些编译器开关。 - Rotem

@Rotem：如果有许多不同的开关，编译器可能无法将所有不变量提升出循环。在这种情况下，您可以尝试使用模板解决方案。 - Matthieu M.

Answer 3

解决这类问题的一种技术，适用于C和C ++，是使用内联函数。对于仅限于C ++ 的情况，您可以使用模板函数（实质上是相同的解决方案，但略微更加优雅）。

以下是C / C ++的内联解决方案：

inline void HeavyLoop_inline(byte* startingAddress, bool secondaryModification)
{
    for (int i = 0; i < 10000000; i++)
    {
        byte* b = startingAddress+ i;
        *b+= 1;
        if (secondaryModification) *b+= 2;
    }
}

void HeavyLoop(byte* startingAddress, bool secondaryModification)
{
    if (secondaryModification)
    {
        HeavyLoop_inline(startingAddress, TRUE);
    }
    else
    {
        HeavyLoop_inline(startingAddress, FALSE);
    }
}

这种方法能够运行（并且高效）的原因是传递给内联函数的secondaryModification的值是编译时常量，因此编译器可以优化掉每次调用时的任何无用代码。这样就会给您两个“专门”的函数版本。

---

注

根据您使用的编译器，您可能需要采取其他步骤以确保内联函数实际上被内联。例如，对于gcc，您可以添加__attribute__ ((always_inline))。

还要注意，一些编译器将执行这种类型的循环重构优化而无需任何干预，因此在尝试超越编译器之前，请先检查生成的代码。

- Paul R

---

它将在相同的问题中内联代码。 "if" 总是存在，不是吗？ - Roee Gavirel

只要函数被真正内联，这应该会产生预期的效果；标志是一个编译时常量，因此优化器应该能够删除死代码。我可能会使用模板参数，以确保编译器将其视为编译时常量（就像我在回答中所做的那样，之后我才看到这个答案）。 - Mike Seymour

编译器应该能够判断参数是否已知，因此可以在编译时包含或排除 *b += 2。 - Mike Dunlavey

+1，那些不理解这个的人可能需要使用适当的优化进行编译和反汇编。内联允许优化器静态地预测分支if (secondaryModification)，因此在FALSE情况下它将被完全消除，在true情况下条件测试将被消除并保留*b+=2。然后希望与*b+=1结合起来。 - Steve Jessop

由于您所说的C++似乎更优雅，因此我会使用模板函数。 - Rotem

Answer 4

为什么不这样做：

void HeavyLoop(byte * startingAddress, bool secondaryModification)
{
    int const incr = secondaryModification ? 3 : 1;

    for (byte * b = startingAddress, * const end = startingAddress + 10000000;
         b != end; ++b)
    {
        *b += incr;
    }
}

当然，您可以在incr的定义中放置任何您喜欢的内容。

疯狂的人甚至可能会在循环增量器中写入*(b++) += incr。对于喜欢奥妙C语法的人来说，更好的方法是：

byte * b = startingAddress, * const end = startingAddress + 10000000;
while (b != end) { *(b++) += incr; }

- Kerrek SB

---

我认为OP说：“不用说，代码只是一个例子，而不是实际情况。请不要提供与*b+=1本身有关的解决方案。”而你的解决方案仅适用于给定的情况。对于更复杂的解决方案，使用函数指针可能会起作用，但由于函数调用的开销（与简单分支相比），可能并不真正提高性能。 - Matthieu M.

@MatthieuM.：我认为问题就在于不清楚 OP 想要什么。当然，你可以用任何更复杂的条件组合来替换 incr 的初始化。如果整个循环体需要灵活处理，那我们需要其他方法（确实不清楚通过函数指针间接访问是否比条件语句更好），但这点从问题中并不清晰。因此，我给 OP 打负分。 - Kerrek SB

Answer 5

编辑：鉴于原帖中的新文本“问题是处理循环外无法预计算的语句。”

如果语句无法在循环外预计算，那么根据定义，它必须在循环内计算，在循环内使用除了检查原始代码的其他任何东西都只会使代码模糊不清。我假设由于你正在问这个问题，所以仍有另一个细节你没有向我们展示。

原始答案：

首先，按照明显的方式编写代码，直到分析表明它太慢为止。但在这种情况下，您可以提前计算该术语：

void HeavyLoop(byte* startingAddress, bool secondaryModification)
{
    const int val = 1 + (secondaryModification ? 2 : 0);

    for (int i = 0; i < 10000000; i++)
    {
        byte* b = startingAddress + i;
        *b += val;
    }
}

- Mark B

---

我在我的问题中强调了*b+=1和*b+=2只是例子，不相关，对于任何的混淆我表示抱歉。 - Rotem