Быстрее считать, чем считать?

Question

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

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

лучше чем:

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

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

Answer 1

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

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

Вот как большинство людей реализуют цикл с 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 байт) с 2 ветками. Да, да, я знаю, что это можно сделать лучше (это всего лишь пример).

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

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-совместимые) имеют инструкцию, которая может уменьшить регистр, затем сравнить результат с нулем и выполнить ветвление, если результат отличается от нуля. Практически ВСЕ процессоры ПК реализуют эту инструкцию. Используя его, цикл фактически представляет собой одну (да, одну) 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..в то же время эквивалентно для итераций постоянного цикла ... (или развернуть его) ...

Answer 2

Странно, похоже, что есть разница. По крайней мере, в 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

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

РЕДАКТИРОВАТЬ : Результаты такие же, даже если вы начинаете считать не с 0, а с другим произвольным значением. Так что, вероятно, есть не только сравнение с нулем, которое имеет значение?

Answer 3

Это может быть быстрее.

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

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--;)
{ ... }

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

Answer 4

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

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

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

Могу поспорить, что большинство программистов читают (i = 0; i 0; i--) я должен подумать об этом на мгновение , Лучше всего, если намерение кода попадет прямо в мозг без каких-либо размышлений.

Answer 5

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

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

И сравнение, и уменьшение i могут быть выполнены в одном выражении.

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

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

Answer 6

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

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)  

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

Answer 7

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

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

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

Answer 8

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

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

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

Answer 9

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

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

Посмотрите на эту небольшую часть кода 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);
    }

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