Обратный отсчет в циклах for

StackOverflow https://stackoverflow.com/questions/804777

  •  03-07-2019
  •  | 
  •  

Вопрос

Я полагаю (исходя из некоторых исследований), что обратный отсчет в циклах for на самом деле более эффективен и быстр во время выполнения.Мой полный программный код - C ++

В настоящее время у меня есть это:

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

мой 'i' - это unsigned resgister int, также 'domain' - это unsigned int

в цикле for i используется для прохождения по массиву, например

array[i] = do stuff

преобразование этого в обратный отсчет портит ожидаемый / правильный результат моей процедуры.

Я могу представить, что ответ довольно тривиален, но у меня никак не укладывается это в голове.

Обновить:"делать материал" не зависит от предыдущей или более поздней итерации.Вычисления внутри цикла for независимы для этой итерации i.(Я надеюсь, что в этом есть смысл).

Обновить:Чтобы ускорить выполнение с помощью моего for-цикла, должен ли я отсчитывать время и, если да, удалять неподписанную часть при удалении моего int или каким другим методом?

Пожалуйста, помогите.

Это было полезно?

Решение

Я предполагаю, что ваш обратный цикл for выглядит примерно так:

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
}

Другие советы

Существует только один правильный метод обратного цикла с использованием беззнакового счетчика:

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

Здесь есть хитрость, для последней итерации цикла у вас будет i = 1 в верхней части цикла, i-- > 0 проходит, потому что 1 > 0, тогда i = 0 в теле цикла.На следующей итерации i-- > 0 завершается с ошибкой, потому что i == 0, поэтому не имеет значения, что постфиксное уменьшение превысило счетчик.

Очень неочевидно, я знаю.

Это не ответ на вашу проблему, потому что, похоже, у вас нет проблемы.

Такого рода оптимизация совершенно неуместна и должна быть оставлена на усмотрение компилятора (если вообще выполняется).

Вы профилировали свою программу, чтобы проверить, является ли ваш цикл for узким местом?Если нет, то вам не нужно тратить время на беспокойство по этому поводу.Более того, наличие "i" в качестве "register" int, как вы пишете, не имеет реального смысла с точки зрения производительности.

Даже не зная вашей проблемной области, я могу гарантировать вам, что как метод обратного цикла, так и счетчик int "register" будут иметь незначительный влияние на производительность вашей программы.Помните, "Преждевременная оптимизация - это корень всего зла".

Тем не менее, лучше потратить время на оптимизацию, подумав об общей структуре программы, используемых структурах данных и алгоритмах, использовании ресурсов и т.д.

Проверка того, равно ли число нулю, может быть быстрее и эффективнее, чем сравнение.Но это тот вид микрооптимизации, о котором вам действительно не стоит беспокоиться - несколько тактов будут значительно затмевать практически любую другую проблему с производительностью.

На x86:

dec eax
jnz Foo

Вместо того, чтобы:

inc eax
cmp eax, 15
jl Foo

Если у вас есть приличный компилятор, он оптимизирует "обратный отсчет" так же эффективно, как и "обратный отсчет".Просто попробуйте несколько тестов, и вы увидите.

Итак, вы "прочитали", что снижение курса более эффективно?Мне очень трудно в это поверить, пока вы не покажете мне некоторые результаты профилировщика и код.Я могу купить это при некоторых обстоятельствах, но в общем случае - нет.Мне кажется, что это классический случай преждевременной оптимизации.

Ваш комментарий по поводу "register int i" также очень красноречив.В настоящее время компилятор всегда лучше вас знает, как распределять регистры.Не утруждайте себя использованием ключевого слова using register, если вы не профилировали свой код.

Когда вы перебираете структуры данных любого рода, промахи в кэше оказывают гораздо большее влияние, чем направление, в котором вы движетесь.Займитесь более широкой картиной расположения памяти и структуры алгоритма, а не тривиальными микрооптимизациями.

Это не имеет никакого отношения к подсчету вверх или вниз.Что может быть быстрее, так это подсчет к нулю. Ответ Майкла показывает, почему — 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;

(Я говорю "пресловутый" не потому, что оптимизация влияет на результат цикла, а потому, что отладчик неправильно отображает переменную counter.Когда программист проверяет 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", но он больше не выглядит как и one - у него есть две переменные, они ведут отсчет в противоположных направлениях, и одна из них даже не используется в теле цикла — так что любому, кто читает ваш код (включая вас, через неделю, месяц или год, когда вы забудете об "оптимизации", которой надеялись достичь), придется потратить дополнительные усилия, доказывая самому себе, что цикл действительно является обычным замаскированным циклом.

(Вы заметили, что в моем приведенном выше коде использовались переменные без знака, без опасности обтекания нулем?Использование двух отдельных переменных позволяет это сделать.)

Три вещи, которые нужно вынести из всего этого:

  1. Позвольте оптимизатору выполнять свою работу;в целом у него это получается лучше, чем у вас.
  2. Сделайте обычный код обычным, чтобы специальному коду не приходилось конкурировать за привлечение внимания со стороны людей, просматривающих, отлаживающих или поддерживающих его.
  3. Не делайте ничего необычного во имя производительности, пока тестирование и профилирование не покажут, что это необходимо.

Вы можете попробовать следующее, какой компилятор будет оптимизировать очень эффективно:

#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

Трудно сказать, учитывая предоставленную информацию, но...переверните свой массив и ведите обратный отсчет?

Джереми Рутен справедливо отметил, что использование счетчика циклов без знака опасно.Насколько я могу судить, в этом тоже нет необходимости.

Другие также указывали на опасность преждевременной оптимизации.Они абсолютно правы.

С учетом сказанного, вот стиль, который я использовал при программировании встроенных систем много лет назад, когда каждый байт и каждый цикл действительно что-то значили.Эти формы были полезно для меня на конкретных процессорах и компиляторах, которые я использовал, но ваш пробег может отличаться.

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

Эта форма использует флаг условия, который установлен на некоторые процессоры после выполнения арифметических операций - на некоторых архитектурах уменьшение и тестирование условия ветвления могут быть объединены в одну инструкцию.Обратите внимание, что использование predecrement (--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 (*pointer)).

Я еще раз подчеркну, что будут ли эти формы выигрышными для вас, зависит от используемого вами процессора и компилятора.Они хорошо послужили мне на архитектурах Motorola 6809 и 68000.

В некоторых более поздних ядрах arm для уменьшения и сравнения требуется только одна команда.Это делает уменьшающиеся циклы более эффективными, чем увеличивающиеся.

Я не знаю, почему также нет инструкции по увеличению-сравнению.

Я удивлен, что за этот пост проголосовали "-1", хотя это настоящая проблема.

Все здесь сосредоточены на производительности.На самом деле существует логическая причина для итерации к нулю, которая может привести к получению более чистого кода.

Сначала выполнить итерацию по последнему элементу удобно, когда вы удаляете недопустимые элементы путем замены их местами с концом массива.Для плохих элементов, не смежных с концом, мы можем поменять местами конечную позицию, уменьшить конечную границу массива и продолжить итерацию.Если бы вы выполняли итерацию до конца, то замена на end могла бы привести к замене плохого на плохое.Повторяя end до 0, мы знаем, что элемент в конце массива уже доказал свою допустимость для этой итерации.

Для получения дальнейших разъяснений...

Если:

  1. Вы удаляете плохие элементы, меняя местами один конец массива и изменяя границы массива, чтобы исключить плохие элементы.

Тогда очевидно:

  1. Вы бы поменялись местами с хорошим элементом, т.е.тот, который уже был протестирован в этой итерации.

Таким образом, это подразумевает:

  1. Если мы выполняем итерацию в стороне от границы переменной, то элементы между границей переменной и указателем текущей итерации оказались хорошими.Получает ли указатель итерации значение ++ или --, не имеет значения.Важно то, что мы отступаем от границы переменной, поэтому мы знаем, что соседние с ней элементы хороши.

Итак, наконец-то:

  1. Итерация к 0 позволяет нам использовать только одну переменную для представления границ массива.Имеет ли это значение - личное решение между вами и вашим компилятором.

Что имеет гораздо большее значение, чем то, увеличиваете вы или уменьшаете свой счетчик, так это то, увеличиваете вы объем памяти или уменьшаете его.Большинство кэшей оптимизированы для увеличения объема памяти, а не для уменьшения объема.Поскольку время доступа к памяти является узким местом, с которым сегодня сталкивается большинство программ, это означает, что изменение вашей программы таким образом, чтобы увеличить объем памяти, может привести к повышению производительности, даже если для этого потребуется сравнить ваш счетчик с ненулевым значением.В некоторых моих программах я увидел значительное улучшение производительности за счет изменения моего кода таким образом, чтобы увеличить объем памяти, а не уменьшить ее.

Скептически настроен?Вот результат, который я получил:

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

К ТВОЕМУ сведению vec_original есть ли здесь место для экспериментов, чтобы мне было легко измениться sum_abs_up и sum_abs_down таким образом, который заставляет их меняться vec при этом не допуская, чтобы эти изменения повлияли на будущие тайминги.

Важно отметить, насколько плотен цикл, который я рассчитываю.Если тело цикла велико, то, вероятно, не будет иметь значения, увеличивается или уменьшается объем памяти в его итераторе, поскольку время, необходимое для выполнения тела цикла, скорее всего, будет полностью доминировать.Кроме того, важно упомянуть, что при некоторых редких циклах уменьшение объема памяти иногда происходит быстрее, чем ее увеличение.Но даже с такими циклами редко бывает так, чтобы подъем всегда был медленнее, чем спад (в отличие от циклов, которые увеличивают объем памяти, которые очень часто всегда быстрее, чем эквивалентные циклы с пониженной памятью;в небольшой горстке раз они были даже на 40 +% быстрее).

Дело в том, что, как правило, если у вас есть возможность, если тело цикла невелико, и если есть небольшая разница между тем, чтобы ваш цикл увеличивал объем памяти, а не уменьшал ее, то вам следует увеличить объем памяти.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top