c++ - 在 for 循环中倒计时

Question

我相信（从一些研究阅读中）在 for 循环中倒计时实际上在运行时更有效和更快。我的完整软件代码是 C++

我目前有这个：

for (i=0; i<domain; ++i) {

我的“我”是未签名的注册整数，“域”也是未签名的整数

在 for 循环中 i 用于遍历数组，例如

array[i] = do stuff

将其转换为倒计时会打乱我例程的预期/正确输出。

我可以想象答案是微不足道的，但我无法理解它。

更新：“做事”不依赖于之前或之后的迭代。for 循环中的计算与 i 的迭代无关。（我希望这是有道理的）。

更新：为了使用我的 for 循环实现运行时加速，我是否要倒计时，如果是这样，在删除我的 int 时删除无符号部分，或者其他什么方法？

请帮忙。

score 39 · Accepted Answer

只有一种使用无符号计数器向后循环的正确方法：

for( i = n; i-- > 0; )
{
    // Use i as normal here
}

这里有一个技巧，对于最后一次循环迭代，你将在循环顶部有 i = 1，i--> 0 通过，因为 1 > 0，然后 i = 0 在循环体中。在下一次迭代中 i-- > 0 失败，因为 i == 0，所以后缀减量在计数器上滚动并不重要。

我知道非常不明显。

score 29 · Accepted Answer

我猜你的向后 for 循环看起来像这样：

for (i = domain - 1; i >= 0; --i) {

在这种情况下，因为i是unsigned，它总是大于或等于零。当你减少一个等于零的无符号变量时，它会环绕到一个非常大的数字。解决方案是进行i签名或更改 for 循环中的条件，如下所示：

for (i = domain - 1; i >= 0 && i < domain; --i) {

domain或从to1而不是 from domain - 1to计数0：

for (i = domain; i >= 1; --i) {
    array[i - 1] = ...; // notice you have to subtract 1 from i inside the loop now
}

score 12 · Accepted Answer

这不是您问题的答案，因为您似乎没有问题。

这种优化完全无关紧要，应该留给编译器（如果有的话）。

您是否分析过您的程序以检查您的 for 循环是否是瓶颈？如果没有，那么您无需花时间担心这一点。更重要的是，从性能的角度来看，将“i”作为“寄存器”int，就像你写的那样，没有真正的意义。

即使不知道您的问题域，我也可以向您保证，反向循环技术和“注册”int 计数器对您的程序性能的影响可以忽略不计。请记住，“过早的优化是万恶之源”。

也就是说，更好的优化时间应该是考虑整体程序结构、使用的数据结构和算法、资源利用率等。

score 10 · Accepted Answer

检查一个数字是否为零可能比比较更快或更有效。但这是你真正不应该担心的那种微优化——几个时钟周期将与几乎任何其他性能问题相形见绌。

在 x86 上：

dec eax
jnz Foo

代替：

inc eax
cmp eax, 15
jl Foo

score 4 · Accepted Answer

它与向上或向下计数无关。可以更快的是向零计数。Michael 的回答说明了原因——x86 为您提供了与零的比较，这是许多指令的隐含副作用，因此在调整计数器后，您只需根据结果进行分支，而不是进行显式比较。（也许其他架构也这样做；我不知道。）

Borland 的 Pascal 编译器因执行该优化而臭名昭著。编译器转换此代码：

for i := x to y do
  foo(i);

变成更类似于这样的内部表示：

tmp := Succ(y - x);
i := x;
while tmp > 0 do begin
  foo(i);
  Inc(i);
  Dec(tmp);
end;

（我说臭名昭著不是因为优化影响循环的结果，而是因为调试器错误地显示了计数器变量。当程序员检查i时，调试器可能会显示的值tmp相反，给那些认为他们的循环正在向后运行。）

这个想法是，即使有额外的Inc或Dec指令，在运行时间方面，它仍然是一个净胜，超过了明确的比较。你是否真的能注意到这种差异还有待商榷。

但请注意，转换是编译器会自动执行的操作，具体取决于它是否认为转换值得。编译器通常比你更擅长优化代码，所以不要花太多精力与它竞争。

无论如何，你问的是 C++，而不是 Pascal。C++“for”循环不像Pascal“for”循环那样容易应用优化，因为Pascal循环的边界总是在循环运行之前完全计算，而C++循环有时取决于停止条件和循环内容。C++ 编译器需要做一些静态分析来确定任何给定的循环是否可以满足 Pascal 循环无条件适用的转换类型的要求。如果 C++ 编译器进行分析，那么它可以进行类似的转换。

没有什么能阻止您以自己的方式编写循环：

for (unsigned i = 0, tmp = domain; tmp > 0; ++i, --tmp)
  array[i] = do stuff

这样做可能会使您的代码运行得更快。不过，就像我之前说的，你可能不会注意到。像这样手动安排循环所付出的更大代价是你的代码不再遵循既定的习惯用法。你的循环是一个非常普通的“for”循环，但它不再像一个循环——它有两个变量，它们以相反的方向计数，其中一个甚至没有在循环体中使用——所以任何阅读你的人代码（包括你，一个星期，一个月或一年后你忘记了你希望实现的“优化”）将需要花费额外的努力向自己证明循环确实是一个普通的循环变相。

（你有没有注意到我上面的代码使用了无符号变量，没有回零的危险？使用两个单独的变量可以做到这一点。）

从这一切中带走三件事：

让优化器完成它的工作；总的来说，它比你更擅长。
让普通代码看起来很普通，这样特殊代码就不必为了获得审查、调试或维护它的人的注意而竞争。
在测试和分析表明它是必要的之前，不要以性能的名义做任何花哨的事情。

score 3 · Accepted Answer

如果你有一个体面的编译器，它会优化“向上计数”，就像“向下计数”一样有效。只需尝试一些基准测试，您就会看到。

score 3 · Accepted Answer

所以你“读到”计算下来更有效率？除非您向我展示一些分析器结果和代码，否则我很难相信这一点。我可以在某些情况下购买它，但在一般情况下，不能。在我看来，这是一个过早优化的经典案例。

您对“register int i”的评论也很有说服力。如今，编译器总是比你更清楚如何分配寄存器。除非您已经对代码进行了概要分析，否则不要使用 register 关键字。

score 3 · Accepted Answer

当您循环访问任何类型的数据结构时，缓存未命中的影响远大于您前进的方向。关注内存布局和算法结构的大局，而不是琐碎的微优化。

score 2 · Accepted Answer

您可以尝试以下方法，哪个编译器将非常有效地优化：

#define for_range(_type, _param, _A1, _B1) \
    for (_type _param = _A1, _finish = _B1,\
    _step = static_cast<_type>(2*(((int)_finish)>(int)_param)-1),\
    _stop = static_cast<_type>(((int)_finish)+(int)_step); _param != _stop; \
_param = static_cast<_type>(((int)_param)+(int)_step))

现在你可以使用它了：

for_range (unsigned, i, 10,0)
{
    cout << "backwards i: " << i << endl;
}

for_range (char, c, 'z','a')
{
    cout << c << endl;
}

enum Count { zero, one, two, three }; 

for_range (Count, c, three, zero)
{
    cout << "backwards: " << c << endl;
}

您可以向任何方向迭代：

for_range (Count, c, zero, three)
{
    cout << "forward: " << c << endl;
}

循环

for_range (unsigned,i,b,a)
{
   // body of the loop
}

将产生以下代码：

 mov esi,b
L1:
;    body of the loop
   dec esi
   cmp esi,a-1
   jne L1

score 1 · Accepted Answer

1

给出的信息很难说，但是......反转你的数组，倒计时？

于 2009-04-29T23:39:23.883 回答

score 1 · Accepted Answer

Jeremy Ruten 正确地指出，使用无符号循环计数器是危险的。据我所知，这也是不必要的。

其他人也指出过早优化的危险。他们是绝对正确的。

话虽如此，这是我多年前在嵌入式系统编程时使用的一种风格，当时每个字节和每个周期都有意义。这些表格在我使用的特定 CPU 和编译器上对我很有用，但你的情况可能会有所不同。

// Start out pointing to the last elem in array
pointer_to_array_elem_type p = array + (domain - 1);
for (int i = domain - 1; --i >= 0 ; ) {
     *p-- = (... whatever ...)
}

这种形式利用了在算术运算之后在某些处理器上设置的条件标志——在某些架构上，分支条件的递减和测试可以组合成一条指令。请注意，使用--ipredecrement ( ) 是这里的关键 - 使用 postdecrement ( i--) 不会很好。

或者，

// Start out pointing *beyond* the last elem in array
pointer_to_array_elem_type p = array + domain;
for (pointer_to_array_type p = array + domain; p - domain > 0 ; ) {
     *(--p) = (... whatever ...)
}

第二种形式利用了指针（地址）算法。这些天我很少看到这种形式(pointer - int)（有充分的理由），但是语言保证当你从指针中减去一个 int 时，指针会减少(int * sizeof (*pointer)).

我将再次强调，这些形式是否适合您取决于您使用的 CPU 和编译器。他们在摩托罗拉 6809 和 68000 架构上为我提供了很好的服务。

score 1 · Accepted Answer

在一些后来的 arm 内核中，递减和比较只需要一条指令。这使得递减循环比递增循环更有效。

我不知道为什么也没有增量比较指令。

我很惊讶这篇文章在它是一个真正的问题时被投票为-1。

score 1 · Accepted Answer

这里的每个人都专注于性能。实际上有一个合乎逻辑的理由向零迭代，这可以产生更清晰的代码。

当您通过与数组末尾交换来删除无效元素时，首先迭代最后一个元素很方便。对于不相邻的坏元素，我们可以交换到结束位置，减少数组的结束边界，并继续迭代。如果您要迭代到最后，那么与结尾交换可能会导致交换坏为坏。通过将 end 迭代为 0，我们知道数组末尾的元素已经被证明对这次迭代有效。

如需进一步解释...

如果：

通过与数组的一端交换并更改数组边界以排除坏元素来删除坏元素。

然后很明显：

您将换用一个好的元素，即已经在本次迭代中测试过的元素。

所以这意味着：

如果我们从变量边界迭代，那么变量边界和当前迭代指针之间的元素就被证明是好的。迭代指针是 ++ 还是 -- 无关紧要。重要的是我们正在远离变量边界进行迭代，因此我们知道与其相邻的元素是好的。

所以最后：

向 0 迭代允许我们仅使用一个变量来表示数组边界。这是否重要是您和您的编译器之间的个人决定。

score 1 · Accepted Answer

比你增加或减少计数器更重要的是你是增加内存还是减少内存。大多数缓存都针对增加内存而不是减少内存进行了优化。由于内存访问时间是当今大多数程序面临的瓶颈，这意味着更改程序以增加内存可以提高性能，即使这需要将计数器与非零值进行比较。在我的一些程序中，通过将代码更改为增加内存而不是减少内存，我看到了性能的显着提高。

持怀疑态度？这是我得到的输出：

sum up   = 705046256
sum down = 705046256
Ave. Up Memory   = 4839 mus
Ave. Down Memory =  5552 mus
sum up   = inf
sum down = inf
Ave. Up Memory   = 18638 mus
Ave. Down Memory =  19053 mus

从运行这个程序：

#include <chrono>
#include <iostream>
#include <random>
#include <vector>

template<class Iterator, typename T>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, T a, T b) {
  std::random_device rnd_device;
  std::mt19937 generator(rnd_device());
  std::uniform_int_distribution<T> dist(a, b);
  for (auto it = start; it != one_past_end; it++)
    *it = dist(generator);
  return ;
}

template<class Iterator>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, double a, double b) {
  std::random_device rnd_device;
  std::mt19937_64 generator(rnd_device());
  std::uniform_real_distribution<double> dist(a, b);
  for (auto it = start; it != one_past_end; it++)
    *it = dist(generator);
  return ;
}

template<class RAI, class T>
inline void sum_abs_up(RAI first, RAI one_past_last, T &total) {
  T sum = 0;
  auto it = first;
  do {
    sum += *it;
    it++;
  } while (it != one_past_last);
  total += sum;
}

template<class RAI, class T>
inline void sum_abs_down(RAI first, RAI one_past_last, T &total) {
  T sum = 0;
  auto it = one_past_last;
  do {
    it--;
    sum += *it;
  } while (it != first);
  total += sum;
}

template<class T> std::chrono::nanoseconds TimeDown(
                      std::vector<T> &vec, const std::vector<T> &vec_original,
                      std::size_t num_repititions, T &running_sum) {
  std::chrono::nanoseconds total{0};
  for (std::size_t i = 0; i < num_repititions; i++) {
    auto start_time = std::chrono::high_resolution_clock::now();
    sum_abs_down(vec.begin(), vec.end(), running_sum);
    total += std::chrono::high_resolution_clock::now() - start_time;
    vec = vec_original;
  }
  return total;
}

template<class T> std::chrono::nanoseconds TimeUp(
                      std::vector<T> &vec, const std::vector<T> &vec_original,
                      std::size_t num_repititions, T &running_sum) {
  std::chrono::nanoseconds total{0};
  for (std::size_t i = 0; i < num_repititions; i++) {
    auto start_time = std::chrono::high_resolution_clock::now();
    sum_abs_up(vec.begin(), vec.end(), running_sum);
    total += std::chrono::high_resolution_clock::now() - start_time;
    vec = vec_original;
  }
  return total;
}

int main() {
  std::size_t num_repititions = 1 << 10;
  {
  typedef int ValueType;
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(1 << 24);

  FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper);
  const auto vec_original = vec;
  ValueType sum_up = 0, sum_down = 0;

  auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count();
  auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count();
  std::cout << "sum up   = " << sum_up   << '\n';
  std::cout << "sum down = " << sum_down << '\n';
  std::cout << "Ave. Up Memory   = " << time_up/(num_repititions * 1000) << " mus\n";
  std::cout << "Ave. Down Memory =  "<< time_down/(num_repititions * 1000) << " mus"
            << std::endl;
  }
  {
  typedef double ValueType;
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(1 << 24);

  FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper);
  const auto vec_original = vec;
  ValueType sum_up = 0, sum_down = 0;

  auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count();
  auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count();
  std::cout << "sum up   = " << sum_up   << '\n';
  std::cout << "sum down = " << sum_down << '\n';
  std::cout << "Ave. Up Memory   = " << time_up/(num_repititions * 1000) << " mus\n";
  std::cout << "Ave. Down Memory =  "<< time_down/(num_repititions * 1000) << " mus"
            << std::endl;
  }
  return 0;
}

两者都sum_abs_up做sum_abs_down同样的事情，并且以相同的方式计时，唯一的区别是sum_abs_up内存增加而sum_abs_down内存减少。我什至通过vec引用传递，以便两个函数访问相同的内存位置。然而，sum_abs_up始终比sum_abs_down. 自己运行一下（我用 g++ -O3 编译它）。

FYIvec_original在那里进行实验，让我更容易改变sum_abs_up，并sum_abs_down以一种使它们改变的方式，vec同时不允许这些改变影响未来的时间安排。

重要的是要注意我计时的循环有多紧。如果一个循环的主体很大，那么它的迭代器是否会增加或减少内存可能并不重要，因为执行循环主体所需的时间可能会完全占主导地位。此外，重要的是要提到，对于一些罕见的循环，下降内存有时比上升内存要快。但即使有这样的循环，上升总是比下降慢的情况很少发生（不像上升内存的循环，它通常总是比等效的内存下降循环快；少数几次甚至是 40 +% 更快）。

关键是，根据经验，如果你有选择，如果循环的主体很小，如果让你的循环增加内存而不是减少内存之间没有什么区别，那么你应该增加内存。

c++ - 在 for 循环中倒计时

14 回答 14

Related

Reference