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

Question

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

У меня сейчас есть это:

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

my 'i' - это неподписанный регистр int, также «домен» не подписан int

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

array[i] = do stuff

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

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

ОБНОВЛЕНИЕ: «делать вещи» не зависит от предыдущей или более поздней итерации. Расчеты внутри цикла for не зависят от этой итерации i. (Надеюсь, это имеет смысл).

ОБНОВЛЕНИЕ: Чтобы добиться ускорения во время выполнения с моим циклом for, нужно ли вести обратный отсчет и, если это так, удалять неподписанную часть при удалении из моего int или каким-либо другим методом?

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

Answer 1

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

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

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

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

Answer 2

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

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 3

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

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

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

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

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

Answer 4

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

На x86:

dec eax
jnz Foo

Вместо:

inc eax
cmp eax, 15
jl Foo

Answer 5

Это не имеет ничего общего с подсчетом вверх или вниз . Что может быть быстрее, так это счет к нулю . Ответ Михаэля показывает, почему - 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. Циклы «for» в C ++ не так легко применить эту оптимизацию, как в циклах «for» в Pascal, потому что границы циклов Pascal всегда полностью вычисляются перед выполнением цикла, тогда как циклы C ++ иногда зависят от условия остановки и цикла содержание. Компиляторам C ++ необходимо провести некоторый статический анализ, чтобы определить, может ли какой-либо конкретный цикл соответствовать требованиям для того типа преобразования, для которого циклы Паскаля квалифицируются безоговорочно. Если компилятор C ++ выполняет анализ, он может выполнить аналогичное преобразование.

Ничто не мешает вам писать свои циклы таким образом:

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

Выполнение этого может заставить ваш код работать быстрее. Как я уже говорил, вы, вероятно, не заметите. Большая плата, которую вы платите за ручную организацию таких циклов, состоит в том, что ваш код больше не следует установленным идиомам. Ваш цикл является совершенно обычным циклом «for», но он больше не выглядит как один - он имеет две переменные, они считают в противоположных направлениях, и одна из них даже не используется в цикле тело - так что любой, кто читает ваш код (включая вас, неделю, месяц или год, когда вы забыли «оптимизацию», на которую вы надеялись), должен будет приложить дополнительные усилия, чтобы доказать себе, что петля действительно замаскированная обычная петля.

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

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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

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

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

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

Для дальнейшего объяснения ...

Если:

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

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

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

Итак, это подразумевает:

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

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

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