Быстрее ли подсчитывать, чем подсчитывать?

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

for (i = N; i >= 0; i--)  
  putchar('*');

лучше, чем:

for (i = 0; i < N; i++)  
  putchar('*');

Это правда? И если да, то кто-нибудь знает, почему?

Ответы

Ответ 1

Это правда? и если так кто-нибудь знает, почему?

В древние времена, когда компьютеры все еще были выбиты из плавленого кремнезема вручную, когда 8-битные микроконтроллеры бродили по Земле, а когда ваш учитель был молод (или учитель учитель был молод), была обычная машинная инструкция, называемая декремент и пропустить, если нуль (DSZ). Программисты сборки Hotshot использовали эту инструкцию для реализации циклов. Позже машины получили более увлекательные инструкции, но было еще немало процессоров, на которых было дешевле сравнивать что-то с нулем, чем сравнивать с чем-либо еще. (Это правда даже на некоторых современных машинах RISC, таких как PPC или SPARC, которые сохраняют полный регистр всегда равным нулю.)

Итак, если вы устанавливаете свои циклы для сравнения с нулем вместо N, что может произойти?

  • Вы можете сохранить регистр
  • Вы можете получить инструкцию сравнения с меньшей двоичной кодировкой
  • Если предыдущая команда устанавливает флаг (вероятно, только на семейных машинах x86), вам может даже не понадобиться явная команда сравнения

Являются ли эти различия, вероятно, результатом какого-либо измеримого улучшения реальных программ на современном процессоре без рецепта? Очень вряд ли. Фактически, я был бы впечатлен, если бы вы могли показать измеримое улучшение даже на микрообъекте.

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

Ответ 2

Вот что может случиться на каком-то оборудовании в зависимости от того, что компилятор может вывести из диапазона чисел, которые вы используете: с циклом инкремента вы должны тестировать i<N каждый раз за цикл. Для декрементирующей версии флаг переноса (заданный как побочный эффект вычитания) может автоматически сообщать вам, если i>=0. Это сохраняет тест за время цикла.

В действительности, на современном конвейерном процессорном оборудовании этот материал почти наверняка не имеет значения, поскольку нет простого сопоставления 1-1 от инструкций до тактовых циклов. (Хотя я мог представить, что это произойдет, если вы делаете такие вещи, как генерация точно синхронизированных видеосигналов от микроконтроллера. Но тогда вы все равно напишите на ассемблере.)

Ответ 3

В наборе инструкций Intel x86 построение цикла для обратного отсчета до нуля обычно может выполняться с меньшим количеством команд, чем цикл, который учитывает ненулевое условие выхода. В частности, регистр ECX традиционно используется как счетчик циклов в x86 asm, а набор инструкций Intel имеет специальную инструкцию jcxz jump, которая проверяет регистр ECX на нуль и переходы на основе результата теста.

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

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

Ответ 4

Да..!!

Подсчет от N до 0 немного быстрее, чем подсчет от 0 до N в смысле того, как аппаратное обеспечение будет обрабатывать сравнение.

Обратите внимание на сравнение в каждом цикле 

i>=0
i<N

Большинство процессоров имеют сравнение с нулевой инструкцией. Первый из них будет переведен в машинный код как:

  • Загрузить i
  • Сравнить и прыгать, если меньше или равно нулю

Но второй нужно загружать N-форму памяти каждый раз

  • загрузить i
  • загрузить N
  • Sub я и N
  • Сравнить и прыгать, если меньше или равно нулю

Значит, это не из-за подсчета или вверх. Но из-за того, как ваш код будет переведен в машинный код.

Таким образом, подсчет от 10 до 100 - это то же самое, что и счетная форма от 100 до 10
Но подсчет от я = 100 до 0 быстрее, чем от я = 0 до 100 - в большинстве случаев
И подсчет от я = N до 0 быстрее, чем от я = 0 до N

  • Обратите внимание, что в наши дни компиляторы могут сделать эту оптимизацию для вас (если она достаточно умна)
  • Обратите внимание, что конвейер может вызвать Belady anomaly-like effect (не может быть уверен, что будет лучше)
  • Наконец: обратите внимание, что 2 цикла, которые вы представили, не эквивалентны. первый отпечаток еще один *....

по теме: Почему n ++ выполняется быстрее, чем n = n + 1?

Ответ 5

В 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-сборке. На многих архитектурах есть флаги, которые устанавливаются арифметическими операциями (добавление, вычитание, умножение, деление, приращение, декремент), которые вы можете использовать для прыжков. Они часто дают вам то, что по сути является сравнением результата операции с 0 бесплатно. Фактически на многих архитектурах

x = x - 0

семантически совпадает с

compare x, 0

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

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

Ответ 6

Считайте быстрее в случае:

for (i = someObject.getAllObjects.size(); i >= 0; i--) {…}

потому что someObject.getAllObjects.size() выполняется один раз в начале.

Конечно, подобное поведение может быть достигнуто путем вызова size() из цикла, как отметил Питер:

size = someObject.getAllObjects.size();
for (i = 0; i < size; i++) {…}

Ответ 7

Быстрее ли подсчитывать, чем вверх?

Может быть. Но гораздо больше, чем 99% времени, это не имеет значения, поэтому вы должны использовать самый "разумный" тест для завершения цикла, и разумным я имею в виду, что читателю требуется наименьшее количество мыслить, чтобы выяснить что делает цикл (включая то, что заставляет его остановиться). Сделайте свой код совместимым с умственной (или документированной) моделью того, что делает код.

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

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

Немного больше о "возможно" в ответе:

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

С другой стороны, если вы отсчитываете от нуля и используете счетчик в качестве индекса массива, например, вы можете найти код, работающий против архитектуры памяти системы - чтение в памяти часто приводит к тому, что кэш "загляните вперёд" в несколько мест памяти за прошлым в ожидании последовательного чтения. Если вы работаете в обратном направлении через память, система кэширования может не ожидать считывания местоположения памяти по более низкому адресу памяти. В этом случае возможно, что цикл "назад" может повредить производительность. Тем не менее, я бы все же, вероятно, закодировал цикл таким образом (пока производительность не стала проблемой), потому что правильность имеет первостепенное значение, а соответствие кода модели является отличным способом обеспечения правильности. Некорректный код так же неоптимизирован, как вы можете получить.

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

Ответ 8

На некоторых старых процессорах есть/были такие команды, как DJNZ == "декремент и прыжок, если не ноль". Это позволило использовать эффективные циклы, в которые вы загрузили начальное значение счета в регистр, а затем вы могли бы эффективно управлять циклом декременции с одной инструкцией. Мы говорим здесь о ISA 1980-х годов: ваш учитель серьезно оторван, если считает, что это "эмпирическое правило" по-прежнему применяется к современным процессорам.

Ответ 9

Боб,

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

В вашем примере цикла есть четыре вопроса:

for (i=N; 
 i>=0;             //thing 1
 i--)             //thing 2
{
  putchar('*');   //thing 3
}
  • Сравнение

Сравнение (как указывали другие) относится к конкретным архитектурам процессоров. Существует больше типов процессоров, чем процессоры Windows. В частности, может быть инструкция, которая упрощает и ускоряет сравнение с 0.

  • Настройка

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

  • Тело петли

Вы получаете доступ к syscall с putchar. Это происходит медленно. Кроме того, вы оказываетесь на экране (косвенно). Это еще медленнее. Подумайте о соотношении 1000: 1 или больше. В этой ситуации тело петли полностью и полностью перевешивает стоимость коррекции/сравнения петли.

  • Кэширование

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

Ответ 10

Это интересный вопрос, но, как практический вопрос, я не считаю его важным и не делает ни одной петли лучше, чем другой.

В соответствии с этой страницей wikipedia: Leap second, "... солнечный день увеличивается на 1,7 мс каждый столетие из-за главным образом приливного трения". Но если вы считаете дни до вашего дня рождения, вы действительно заботитесь о этой крошечной разнице во времени?

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

Я бы пообещал, что большинство программистов читают (i = 0; я < N; я ++) и сразу понимают, что это петли N раз. Петля (i = 1; я <= N; я ++), для меня в любом случае, немного менее ясна, и с (i = N; i > 0; i--) я должен думать об этом для момент. Лучше всего, если цель кода идет прямо в мозг, не требуя никакого мышления.

Ответ 11

Странно, похоже, что есть разница. По крайней мере, в PHP. Рассмотрим следующий критерий:

<?php

print "<br>".PHP_VERSION;
$iter = 100000000;
$i=$t1=$t2=0;

$t1 = microtime(true);
for($i=0;$i<$iter;$i++){}
$t2 = microtime(true);
print '<br>$i++ : '.($t2-$t1);

$t1 = microtime(true);
for($i=$iter;$i>0;$i--){}
$t2 = microtime(true);
print '<br>$i-- : '.($t2-$t1);

$t1 = microtime(true);
for($i=0;$i<$iter;++$i){}
$t2 = microtime(true);
print '<br>++$i : '.($t2-$t1);

$t1 = microtime(true);
for($i=$iter;$i>0;--$i){}
$t2 = microtime(true);
print '<br>--$i : '.($t2-$t1);

Интересны результаты:

PHP 5.2.13
$i++ : 8.8842368125916
$i-- : 8.1797409057617
++$i : 8.0271911621094
--$i : 7.1027431488037


PHP 5.3.1
$i++ : 8.9625310897827
$i-- : 8.5790238380432
++$i : 5.9647901058197
--$i : 5.4021768569946

Если кто-то знает, почему, было бы хорошо знать:)

EDIT. Результаты совпадают, даже если вы начинаете считать не с 0, а на другое произвольное значение. Таким образом, существует, вероятно, не только сравнение с нолем, которое имеет значение?

Ответ 12

Он может быть быстрее.

На процессоре NIOS II, с которым я сейчас работаю, традиционный для цикла

for(i=0;i<100;i++)

создает сборку:

ldw r2,-3340(fp) %load i to r2
addi r2,r2,1     %increase i by 1
stw r2,-3340(fp) %save value of i
ldw r2,-3340(fp) %load value again (???)
cmplti r2,r2,100 %compare if less than equal 100
bne r2,zero,0xa018 %jump

Если мы обратим внимание на

for(i=100;i--;)

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

ldw r2,-3340(fp)
addi r3,r2,-1
stw r3,-3340(fp)
bne r2,zero,0xa01c

Если у нас есть вложенные циклы, где внутренний цикл выполняется много, мы можем иметь измеримую разницу:

int i,j,a=0;
for(i=100;i--;){
    for(j=10000;j--;){
        a = j+1;
    }
}

Если внутренний цикл написан так, как указано выше, время выполнения: 0.12199999999999999734 секунд. Если внутренний цикл написан традиционным способом, время выполнения: 0.17199999999999998623 секунды. Таким образом, счетчик циклов быстрее 30%.

Но: этот тест был сделан при выключенной оптимизации GCC. Если мы включим их, компилятор на самом деле умнее этой удобной оптимизации и даже сохранит значение в регистре в течение всего цикла, и мы получим сборку вроде

addi r2,r2,-1
bne r2,zero,0xa01c

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

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

register int i;
for(i=10000;i--;)
{ ... }

Конечно, это работает только, если не имеет значения, что цикл выполняется в обратном порядке, и, как сказал Betamoo, , только если вы считаете до нуля.

Ответ 13

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

for(int i=myCollection.size(); i >= 0; i--)
{
   ...
}

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

Ответ 14

независимо от направления, всегда используйте форму префикса (++ я вместо я ++)!

for (i=N; i>=0; --i)

или

for (i=0; i<N; ++i)

Объяснение: http://www.eskimo.com/~scs/cclass/notes/sx7b.html

Кроме того, вы можете написать

for (i=N; i; --i)

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

Ответ 15

Дело в том, что при подсчете вам не нужно проверять i >= 0 отдельно на уменьшение i. Обратите внимание:

for (i = 5; i--;) {
  alert(i);  // alert boxes showing 4, 3, 2, 1, 0
}

Оба сравнения и декрементации i могут быть выполнены в одном выражении.

См. другие ответы, почему это сводится к меньшему количеству инструкций x86.

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

Ответ 16

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

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

Ave. Up Memory   = 4839 mus
Ave. Down Memory = 5552 mus

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 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;
}

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;
}

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;
}


template<class ValueType>
void TimeFunctions(std::size_t num_repititions, std::size_t vec_size = (1u << 24)) {
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::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();
  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 ;
}

int main() {
  std::size_t num_repititions = 1 << 10;
  TimeFunctions<int>(num_repititions);
  std::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).

FYI vec_original существует для экспериментов, чтобы было легко изменить sum_abs_up и sum_abs_down таким образом, чтобы они меняли vec, не позволяя этим изменениям влиять на будущие тайминги.

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

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

Ответ 17

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

Не останавливаясь на этом, без необходимости использовать счетчик циклов и т.д. - то, что имеет значение ниже, - это просто скорость и количество циклов (ноль).

Вот как большинство людей реализует цикл с 10 итерациями:

int i;
for (i = 0; i < 10; i++)
{
    //something here
}

В 99% случаев это все, что вам может понадобиться, но вместе с PHP, PYTHON, JavaScript есть целый мир критически важного программного обеспечения (обычно встроенный, ОС, игры и т.д.), где действительно важны клещи ЦП, поэтому кратко посмотрите на сборку код:

int i;
for (i = 0; i < 10; i++)
{
    //something here
}

после компиляции (без оптимизации) скомпилированная версия может выглядеть так (VS2015):

-------- C7 45 B0 00 00 00 00  mov         dword ptr [i],0  
-------- EB 09                 jmp         labelB 
labelA   8B 45 B0              mov         eax,dword ptr [i]  
-------- 83 C0 01              add         eax,1  
-------- 89 45 B0              mov         dword ptr [i],eax  
labelB   83 7D B0 0A           cmp         dword ptr [i],0Ah  
-------- 7D 02                 jge         out1 
-------- EB EF                 jmp         labelA  
out1:

Весь цикл - 8 инструкций (26 байтов). В нем - на самом деле есть 6 инструкций (17 байт) с двумя ветвями. Да, я знаю, что это можно сделать лучше (это просто пример).

Теперь рассмотрим эту частую конструкцию, которую вы часто найдете написанной встроенным разработчиком:

i = 10;
do
{
    //something here
} while (--i);

Он также выполняет итерацию 10 раз (да, я знаю, что значение я отличается от показанного для цикла, но здесь мы ищем счетчик итераций). Это может быть скомпилировано следующим образом:

00074EBC C7 45 B0 01 00 00 00 mov         dword ptr [i],1  
00074EC3 8B 45 B0             mov         eax,dword ptr [i]  
00074EC6 83 E8 01             sub         eax,1  
00074EC9 89 45 B0             mov         dword ptr [i],eax  
00074ECC 75 F5                jne         main+0C3h (074EC3h)

5 инструкций (18 байт) и только одна ветвь. На самом деле в цикле есть 4 команды (11 байтов).

Лучше всего, что некоторые процессоры (включая совместимость с x86/x64) имеют инструкцию, которая может уменьшить регистр, а затем сравнить результат с нулем и выполнить ветвь, если результат отличается от нуля. Практически ВСЕ ПК cpus реализуют эту инструкцию. Используя его, цикл на самом деле является только одной (даной) 2-байтной инструкцией:

00144ECE B9 0A 00 00 00       mov         ecx,0Ah  
label:
                          // something here
00144ED3 E2 FE                loop        label (0144ED3h)  // decrement ecx and jump to label if not zero

Должен ли я объяснять, что быстрее?

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

Итак, независимо от некоторых случаев, которые вы можете указать в качестве комментария, почему я ошибаюсь и т.д. и т.д. Я ЕСМЬ НАСТОЯЩИМ - ДА, ПОЛУЧЕННО ПОТЕРЯТЬ ВНИЗ, если вы знаете, как, почему и когда.

PS. Да, я знаю, что мудрый компилятор (с соответствующим уровнем оптимизации) перепишет для цикла (с восходящим счетчиком циклов) в do..while эквивалент для постоянных итераций цикла... (или разворачивает его)...

Ответ 18

Теперь, я думаю, у вас было достаточно собраний лекций:) Я хотел бы представить вам еще одну причину подхода top- > down.

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

Посмотрите на эту небольшую часть кода Java (язык не имеет значения, я думаю по этой причине):

    System.out.println("top->down");
    int n = 999;
    for (int i = n; i >= 0; i--) {
        n++;
        System.out.println("i = " + i + "\t n = " + n);
    }
    System.out.println("bottom->up");
    n = 1;
    for (int i = 0; i < n; i++) {
        n++;
        System.out.println("i = " + i + "\t n = " + n);
    }

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

Ответ 19

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

Это еще более верно, когда число итераций не является константой, а переменной.

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