优化循环与代码复制

Question

我的困境是如何最好地处理可以接受参数的长重循环.请考虑以下方法:

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

这个方法会做我想要的,但是我if在循环中使用了10000000个不必要的s.

我是否写过这样的方法:

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本身有关的解决方案. 我是C++新手,请原谅我,如果有一个我不知道的简单解决方案.如果有语法错误,请原谅我,目前我还没有编译器.

编辑:问题是处理无法在循环外预先计算的语句.

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;一个版本,一个不包含,并且不对参数执行运行时测试); 然后应该在包装函数中内联它们以生成与第二个示例完全相同的代码 - 但不需要复制任何源代码.

Answer 2

编辑:为了更好地瞄准OP想要的东西,仍然删除了这个帖子,这篇文章已经过彻底的编辑.

当然,我会假设您已对此进行了描述,这显示为热点......对吗？

事实上,我打赌你没有.并且你严重低估了你的编译器.

例如,这是使用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,并选择一次,并且所有循环在fonction开始时执行).

这是一个众所周知的编译器技巧:循环不变代码运动(并衍生),所以为什么还要手动做呢？如果它值得,编译器就会这样做!

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)).

另请注意,某些编译器将在不进行任何干预的情况下执行此类循环重构因子优化,因此请在尝试优于编译器之前先检查生成的代码.