将循环变成算术以加速函数

Question

您好，我正在优化一个函数，该函数应该给我 "next" 的东西。到目前为止我得到的是

  int fun(int a){
    const int k = ...;
    for(;test_value(a++) != k;);
    return a;
   }

这是测试我的算法是否有效的一种快速而肮脏的方法，但现在我担心循环会在每次迭代时对分支进行测试（如果不是，编译器非常擅长在幕后处理它？）。让我们说任何 a 完成测试的机会最多是 1/5，最坏的情况是百万分之一，但 test_value 只是一个或两个时钟周期。有没有一些系统的方法可以帮助我的编译器用算术交换所有分支以更好地利用 CPU 管道？

Answer 1

你可以 "unroll" 你的循环有点像：

int nomatch = 1;
while( nomatch ){
    nomatch   = (test_value(a++) != k);
    nomatch &&= (test_value(a++) != k);
    nomatch &&= (test_value(a++) != k);
    nomatch &&= (test_value(a++) != k);
    nomatch &&= (test_value(a++) != k);
}

这会产生更少的迭代，一旦找到匹配，短路会阻止 test_value 的评估。

与您的原始代码一样，这假设会在某个时候找到匹配项。

将循环变成算术以加速函数

Turning loop into arithmetics to speed up function

c

optimization

pipeline

branch-prediction