倒计在循环

Question

我相信(从一些研究，阅读)，倒计在循环是实际上的更有效和更快的运行时间。我完全码软件是用C++

我现在有这样的：

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

我的'我'是无符号resgister int， 还域'是unsigned int

在对环我是用于通过一系列的，例如

array[i] = do stuff

换这个数下来弄乱了预期的/正确的输出的我的程序。

我可以想象的答案是相当微不足道，但我不能让我的头轮。

更新：做的东西'并不取决于先前或以后的迭代。计算内为环是独立于那次迭代。(我希望，使人感)。

更新：实现一个运行时加速与我对环，我倒计，如果因此删除的未签名的一部分，当delcaring我int或其他什么方法？

请帮助。

Answer 1

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

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

在这种情况下，因为 i 是无符号，所以始终大于或等于零。当您递减一个等于零的无符号变量时，它将回绕到一个非常大的数字。解决方案是使 i 签名，或者更改for循环中的条件，如下所示：

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

或从 domain 计算到 1 ，而不是从 domain - 1 到 0 ：

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

Answer 2

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

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

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

我知道非常不明显。

Answer 3

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

这种优化完全不相关，应留给编译器（如果完成的话）。

您是否已分析过您的程序以检查您的for循环是否为瓶颈？如果没有，那么你不需要花时间担心这一点。更重要的是，拥有“我”。作为“注册”在你写的时候，从性能的角度来看，int没有任何意义。

即使不知道您的问题域，我也可以向您保证反向循环技术和“注册”技术。 int counter会对程序的性能产生可忽略的影响。请记住，“过早优化是所有邪恶的根源”。

也就是说，优化时间更长的是考虑整体计划结构，使用的数据结构和算法，资源利用率等。

Answer 4

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

在x86上：

dec eax
jnz Foo

而不是：

inc eax
cmp eax, 15
jl Foo

Answer 5

如果你有一个不错的编译器，它将优化“向上计数”和“倒计时”一样有效。只需尝试一些基准，你就会看到。

Answer 6

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

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

Answer 7

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

Answer 8

它与计算 up 或 down 无关。更快的是将计为零。 迈克尔的回答显示了为什么＆＃8212; 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 时，调试器可能会显示

这个想法是，即使使用额外的 Inc 或 Dec 指令，在运行时间方面，它仍然是一个净胜利，而不是进行显式比较。 您是否可以注意这种差异可供辩论。

但请注意，转换是编译器自动自动的转换，基于它是否认为转换是有价值的。 编译器通常比优化代码更好，所以不要花太多精力与它竞争。

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

没有什么能阻止你自己编写循环：

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

执行可能会使代码运行得更快。就像我之前说过的那样，你可能不会注意到。通过手动安排循环来支付的更高成本是您的代码不再遵循既定惯用语。你的循环是一个完全普通的“for”。循环，但它不再看起来像一个＆＃8212;它有两个变量，它们以相反的方向计数，其中一个甚至没有在循环体中使用＆＃8212;所以任何人都在阅读你的代码（包括你，一周，一个月或一年后，当你忘记了你希望实现的“优化”）时，需要花费额外的努力向自己证明循环确实是一个伪装的普通循环。

（您是否注意到我上面的代码使用了无符号变量而没有绕零的危险？使用两个单独的变量允许这样做。）

从这一切中拿走三件事：

1. 让优化器完成它的工作;总的来说，它比你更好。
2. 使普通代码看起来很普通，这样特殊代码就不必竞争以获得人们审核，调试或维护它的注意力。
3. 在测试和分析显示必要之前，不要以性能的名义做任何事情。

Answer 9

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

#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 

Answer 10

很难说有给出的信息，但......反转你的阵列，并倒计时？

Answer 11

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

此形式利用了算术运算后某些处理器上设置的条件标志 - 在某些体系结构上，分支条件的减量和测试可以组合成单个指令。请注意，使用预先减少（ - i ）是关键 - 使用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（*指针））。

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

Answer 12

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

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

我很惊讶这篇文章在真正的问题上被选为-1。

Answer 13

这里的每个人都专注于表现。实际上有一个逻辑上的原因是迭代到零可以产生更清晰的代码。

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

进一步解释......

如果：

1. 您可以通过交换数组的一端并更改数组边界来排除坏元素，从而删除不良元素。

然后很明显：

1. 您将与一个好元素交换，即在此迭代中已经过测试的元素。

所以这意味着：

1. 如果我们从变量bound迭代，那么变量bound和当前迭代指针之间的元素已被证明是好的。迭代指针是否获得++或 - 并不重要。重要的是我们正在迭代变量边界，所以我们知道与它相邻的元素是好的。

最后：

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

Answer 14

什么事情比你是否增加或减少你的反的是你是否正在上升的存储器或下来的记忆。最高速缓存优化上升的存储器，不存储器。由于存取时间是瓶颈，大多数程序今天面，这意味着改变你的计划所以你去了存储器可能导致性能的提升，甚至如果这种需要比你的计算器非零值。在我的一些程序，我看到了显着改善性能通过改变我的代码去了存储器而不是下来。

持怀疑态度？这里的输出，我得到了：

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.给它自己跑(I编制与克++-O3)。

FYI vec_original 有没有用于实验，可以很容易对我来说改变 sum_abs_up 和 sum_abs_down 在一种方式，使他们改变 vec 同时不允许这些变化的影响未来的时间安排。

重要的是要注意如何严密的循环，我时刻进行。如果一个循环的身体是大然后它可能不会不管是否为其迭代上升或下来的记忆由于时间来执行的循环体将可能完全占据主导地位。此外，重要的是要提到，有一些罕见的循环下去的记忆有时快过去了。但即使有这样的循环，这是很少的情况，会上总是低于在下降(同的循环，走上去记忆，它们常常总是快于相当于下存储器中循环；一小撮的时候他们甚至40+％的速度).

这一点是，作为一项规则的拇指,如果你有的选择，如果循环的身体是很小的，如果有一点差异之间具有你的循环，走上存储器而不是下来，然后你应该去的记忆。