Что важнее, чем увеличение или уменьшение счетчика, так это увеличение или уменьшение памяти. Большинство кэшей оптимизировано для увеличения объема памяти, а не для ее уменьшения. Поскольку время доступа к памяти является узким местом, с которым сталкивается большинство программ сегодня, это означает, что изменение вашей программы с целью увеличения объема памяти может привести к увеличению производительности, даже если для этого необходимо сравнить счетчик с ненулевым значением. В некоторых из моих программ я увидел значительное улучшение производительности, изменив код для увеличения объема памяти вместо уменьшения.
Скептически? Вот вывод, который я получил:
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).
FYI vec_original предназначен для экспериментов, чтобы мне было легко изменить sum_abs_up и sum_abs_down таким образом, чтобы они изменили vec, не допуская, чтобы эти изменения повлияли на будущие сроки.
Важно отметить, насколько тугая петля, на которую я рассчитываю. Если тело цикла большое, то, вероятно, не будет иметь значения, будет ли его итератор увеличивать или уменьшать объем памяти, поскольку время, необходимое для выполнения тела цикла, вероятно, будет полностью доминировать. Также важно отметить, что при некоторых редких циклах уменьшение памяти иногда происходит быстрее, чем увеличение. Но даже с такими циклами редко случается, что повышение всегда было медленнее, чем снижение (в отличие от циклов, которые увеличивают объем памяти, которые очень часто всегда быстрее, чем эквивалентные циклы нехватки памяти; небольшое количество раз они были даже 40 +% быстрее).
Дело в том, что, как правило, если у вас есть возможность, если тело цикла маленькое, и если есть небольшая разница между тем, чтобы ваш цикл увеличивал память, а не уменьшал ее, то вы должны увеличивать память.