Bob*_*Bob 130 c performance loops
我们的计算机科学老师曾经说过,由于某些原因,倒计时比计数更有效率.例如,如果你需要使用FOR循环并且某个地方没有使用循环索引(比如在屏幕上打印一行N*),我的意思是这样的代码:
for (i = N; i >= 0; i--)
putchar('*');
比以下更好:
for (i = 0; i < N; i++)
putchar('*');
这是真的吗？如果是这样,有谁知道为什么？
Nor*_*sey 369
这是真的吗？若有,有谁知道为什么？
在古代,当计算机仍然用手工熔化的二氧化硅芯片时,当8位微控制器在地球上漫游时,以及当你的老师年轻时(或者你老师的老师很年轻),有一种常见的机器指令称为减量和跳过如果为零(DSZ).Hotshot程序员使用此指令来实现循环.后来的机器获得了更好的指令,但是仍然有相当多的处理器,比较一些零比用其他任何东西更便宜.(甚至在某些现代RISC机器上也是如此,例如PPC或SPARC,它们保留整个寄存器始终为零.)
那么,如果您将循环设置为与零进行比较而不是N,可能会发生什么？
这些差异是否可能导致现代无序处理器上的实际程序有任何可衡量的改进？不大可能.事实上,如果你能在微基准测试中显示出可测量的改进,我会留下深刻的印象.
简介:我把你的老师抬起头来! 你不应该学习关于如何组织循环的过时的伪事实.你应该知道循环最重要的事情是确保它们终止,产生正确的答案,并且易于阅读. 我希望你的老师专注于重要的东西,而不是神话.
sig*_*fpe 29
以下是某些硬件上可能发生的情况,具体取决于编译器可以推断出您正在使用的数字范围:使用递增循环,您必须i<N每次循环测试.对于递减版本,进位标志(设置为减法的副作用)可以自动告诉您是否i>=0.这样可以节省每次循环测试的时间.
实际上,在现代流水线处理器硬件上,这种东西几乎肯定无关紧要,因为没有从指令到时钟周期的简单1-1映射.(虽然我可以想象如果你正在做一些事情,比如从微控制器生成精确定时的视频信号.但是无论如何你都会用汇编语言写.)
dth*_*rpe 27
在Intel x86指令集中,构建一个倒计数到零的循环通常可以使用比计数达到非零退出条件的循环更少的指令来完成.具体来说,ECX寄存器传统上用作x86 asm中的循环计数器,而Intel指令集有一个特殊的jcxz跳转指令,用于根据测试结果测试ECX寄存器的零和跳转.
但是,除非您的循环对时钟周期计数非常敏感,否则性能差异可以忽略不计.与向上计数相比,向下计数到零可能会在循环的每次迭代中减少4或5个时钟周期,因此它实际上比新技术更具新颖性.
此外,一个好的优化编译器现在应该能够将你的计数循环源代码转换为倒数到零的机器代码(取决于你如何使用循环索引变量)所以真的没有任何理由编写你的循环奇怪的方式只是在这里和那里挤一两个循环.
Bet*_*moo 23
是..!!
从N到0的计数稍微快一点,从硬件处理比较的意义上从0到N计数.
注意每个循环中的比较
i>=0
i<N
大多数处理器都与零指令进行比较.因此第一个处理器将转换为机器代码:
但第二个需要每次加载N形式的内存
所以这不是因为倒数或向上......而是因为你的代码将如何被翻译成机器代码..
因此从10到100的计数与从100到10的
计数相同但是从i = 100到0的计数比从i = 0到100的
计数更快- 在大多数情况下从i = N到0的计数比从i =更快0到N.
nat*_*ose 12
在C到psudo-assembly中:
for (i = 0; i < 10; i++) {
foo(i);
}
变成
clear i
top_of_loop:
call foo
increment i
compare 10, i
jump_less top_of_loop
而:
for (i = 10; i >= 0; i--) {
foo(i);
}
变成
load i, 10
top_of_loop:
call foo
decrement i
jump_not_neg top_of_loop
注意第二个psudo-assembly中没有比较.在许多体系结构中,有一些标志由算术运算(加,减,乘,除,增量,减量)设置,可用于跳转.这些通常可以为您提供基本上比较操作结果与0的免费比较.事实上,在许多架构上
x = x - 0
在语义上是相同的
compare x, 0
此外,在我的示例中与10的比较可能导致更糟糕的代码.10可能不得不住在一个寄存器中,所以如果它们供不应求,那么成本可能导致额外的代码移动或每次循环重新加载10.
编译器有时可以重新排列代码以利用这一点,但它通常很难,因为它们通常无法确定通过循环反转方向在语义上是等效的.
在这种情况下倒数更快:
for (i = someObject.getAllObjects.size(); i >= 0; i--) {…}
因为someObject.getAllObjects.size()在开始时执行一次.
当然,size()正如Peter提到的那样,可以通过调出循环来实现类似的行为:
size = someObject.getAllObjects.size();
for (i = 0; i < size; i++) {…}
比增加还是减少计数器更重要的是增加内存还是减少内存。大多数缓存都针对增加内存进行优化，而不是减少内存。由于内存访问时间是当今大多数程序面临的瓶颈，这意味着更改程序以增加内存可能会导致性能提升，即使这需要将计数器与非零值进行比较。在我的一些程序中，通过将代码更改为增加内存而不是减少内存，我发现性能有了显着提高。
持怀疑态度？只需编写一个程序来对向上/向下内存进行时间循环即可。这是我得到的输出：
Average Up Memory = 4839 mus
Average Down Memory = 5552 mus
Average Up Memory = 18638 mus
Average Down Memory = 19053 mus
（其中“mus”代表微秒）运行该程序：
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
using namespace std;
//Sum all numbers going up memory.
template<class Iterator, class T>
inline void sum_abs_up(Iterator first, Iterator one_past_last, T &total) {
T sum = 0;
auto it = first;
do {
sum += *it;
it++;
} while (it != one_past_last);
total += sum;
}
//Sum all numbers going down memory.
template<class Iterator, class T>
inline void sum_abs_down(Iterator first, Iterator one_past_last, T &total) {
T sum = 0;
auto it = one_past_last;
do {
it--;
sum += *it;
} while (it != first);
total += sum;
}
//Time how long it takes to make num_repititions identical calls to sum_abs_down().
//We will divide this time by num_repitions to get the average time.
template<class T>
chrono::nanoseconds TimeDown(vector<T> &vec, const vector<T> &vec_original,
size_t num_repititions, T &running_sum) {
chrono::nanoseconds total{0};
for (size_t i = 0; i < num_repititions; i++) {
auto start_time = chrono::high_resolution_clock::now();
sum_abs_down(vec.begin(), vec.end(), running_sum);
total += chrono::high_resolution_clock::now() - start_time;
vec = vec_original;
}
return total;
}
template<class T>
chrono::nanoseconds TimeUp(vector<T> &vec, const vector<T> &vec_original,
size_t num_repititions, T &running_sum) {
chrono::nanoseconds total{0};
for (size_t i = 0; i < num_repititions; i++) {
auto start_time = chrono::high_resolution_clock::now();
sum_abs_up(vec.begin(), vec.end(), running_sum);
total += chrono::high_resolution_clock::now() - start_time;
vec = vec_original;
}
return total;
}
template<class Iterator, typename T>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, T a, T b) {
random_device rnd_device;
mt19937 generator(rnd_device());
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) {
random_device rnd_device;
mt19937_64 generator(rnd_device());
uniform_real_distribution<double> dist(a, b);
for (auto it = start; it != one_past_end; it++)
*it = dist(generator);
return ;
}
template<class ValueType>
void TimeFunctions(size_t num_repititions, size_t vec_size = (1u << 24)) {
auto lower = numeric_limits<ValueType>::min();
auto upper = numeric_limits<ValueType>::max();
vector<ValueType> vec(vec_size);
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();
cout << "Average Up Memory = " << time_up/(num_repititions * 1000) << " mus\n";
cout << "Average Down Memory = " << time_down/(num_repititions * 1000) << " mus"
<< endl;
return ;
}
int main() {
size_t num_repititions = 1 << 10;
TimeFunctions<int>(num_repititions);
cout << '\n';
TimeFunctions<double>(num_repititions);
return 0;
}
和sum_abs_up都sum_abs_down做同样的事情（对数字向量求和），并且以相同的方式计时，唯一的区别是sum_abs_up增加内存而sum_abs_down减少内存。我什至vec通过引用传递，以便两个函数访问相同的内存位置。尽管如此，sum_abs_up始终比 快sum_abs_down。自己运行一下（我用 g++ -O3 编译了它）。
重要的是要注意我计时的循环有多紧。如果循环体很大（有很多代码），那么它的迭代器是否向上或向下内存可能并不重要，因为执行循环体所需的时间可能完全占主导地位。另外，值得一提的是，对于一些罕见的循环，减少内存有时比增加内存更快。但即使使用这样的循环，也不会出现上升内存总是比下降慢的情况（与上升内存的小型循环不同，对于后者来说，情况往往相反；事实上，对于一小部分循环，我'据统计，通过增加内存，性能提高了 40% 以上）。
根据经验，要点是，如果您可以选择，如果循环体很小，并且如果让循环向上内存而不是向下内存几乎没有什么区别，那么您应该向上内存。
仅供参考vec_original，目的是进行实验，使更改变得容易sum_abs_up，并sum_abs_down以一种使它们改变的方式vec，同时不允许这些更改影响未来的时间安排。我强烈建议尝试使用sum_abs_up和sum_abs_down并对结果进行计时。