Циклы

Оленевод — Sat, 13 Dec 2003 16:53:22 +0000

Оленевод:

Цитата

Такой трюк хорош в таких случаях:

vector a;

зуб даю, что вот это
for(int i = a.size(); --i>=0; )
{

}

будет работать быстрее, чем вот это:

for(int i = 0; i{

}

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

...впрочем здесь речь не об этом...

Циклы

m_fox — Sun, 16 Nov 2003 06:57:21 +0000

m_fox: Voobsche vsye zavisit ot kompilyatora i processora.
Naprimer na microkontrollere PIC for(i=0;i

Циклы

Гость Pa3k — Sun, 16 Nov 2003 00:03:00 +0000

Гость Pa3k: Вообще, на туму оптимизации, в том числе циклов, есть очень хорошая статья К. Касперского. Я впервые прочитал её в "Програмисте", а потом наткнулся в интернете. Можно поискать и найти ИСЧЕРПЫВАЮЩИЙ ответ. Как я понимаю, по большему счёту всё зависит от компилятора и того как он умеет оптимизировать код.
Я, например стараюсь по возможности использовать циклы с постусловием и с убывающим счётчиком, который явно указываю, как регистровую переменную и иногда это приносит свои плоды

Циклы

Visitor — Tue, 11 Nov 2003 20:45:25 +0000

Visitor: Я и говорю, что могут две в один такт. На PI/MMX етого не было, в смысле, два полных цикла, с декодированием, исполнением, выкидыванием результата в регистр. Как правило, ети фазы совмещались со сдвигом на 1 такт.
Но в любом случае, когда результат одной команды является аргументом другой, планировщик процессора поставит их последовательно во входной поток одного исполнительного устройства. Другое в етот момент будет простаивать, если не занимается завершением длинной команды, попавшей в него раньше

Циклы

Jin X — Tue, 11 Nov 2003 20:07:26 +0000

Jin X: Спаривание команд (когда две инструкции выполняются одновременно) было на Pentium-I и Pentium-MMX . Начиная с Pentium Pro процессор сам упорядочивает несколько смежных команд в оптимальной последовательности, каждая команда разбивается на микрооперации и они тоже могут одновременно выполняться.
В любом случае схема всех for'ов одна и та же. Только добавляются или исчезают команды, так что...

Циклы

Visitor — Tue, 11 Nov 2003 14:24:20 +0000

Visitor: Там все гораздо сложнее... Выполнение элементарных операций (аддитивные, сравнения, пересылки ...) может совмещаться (две инструкции в за один такт, или декодирование одной с выполнением другой), есть буфер предсказания переходов, конвейер. И просто так взять и посчитать количество тактов для последовательности инструкции уже достаточно сложно, несмотря на то, что ета "внутрипроцессорная" оптимизация описывается небольшим числом довольно простых правил.
Вот напрмер, время выполнения двух почти одинаковых последовательностей команд может отличаться в 1.5-2.5 (от полутора до двух с половиной) раз, в зависимости от состояния конвейера кода и данных и расположения данных в памяти:

CODE

mov eax, [var1]
add eax, edi
mov ebx, [var2]
sub ebx, esi

CODE

mov eax, [var1]
mov ebx, [var2]
add eax, edi
sub ebx, esi

...
---
если кто сильно верит в свои способности, попробуйте оптимизировать ассемблерный код, который выдает MSVC 6 при включенном /Ox (а в нем, как минимум, есть одно лишнее умножениеи вычитание), вот для такой процедуры вычисления первых 1 000 000 простых:

CODE

#define NPR 1000000
unsigned primes[NPR];
int nprimes;
void gen_primes()
{
unsigned test, i, j, q;
primes[0] = 2;
primes[1] = 3;
primes[2] = 5;
primes[3] = 7;
primes[4] = 11;
nprimes = 5;
for(test=13; nprimes < NPR; test+=2)
{
q = 1000000000;
for(j=1; q >= primes[j]; j++)
if(!(test-primes[j]*(q = test/primes[j])))
goto l_out:
primes[nprimes++] = test;
l_out:
}
}

Циклы

Jin X — Mon, 10 Nov 2003 20:47:53 +0000

Jin X:

QUOTE (=Маббус=- @ 9.11.03, 23:04)

for(int i = 0;i!=max;i++)
00411A05 mov dword ptr [i],0
00411A0C jmp main+37h (411A17h)
00411A0E mov eax,dword ptr [i]
00411A11 add eax,1
00411A14 mov dword ptr [i],eax
00411A17 mov eax,dword ptr [i]
00411A1A cmp eax,dword ptr [max]
00411A1D je main+41h (411A21h)
for(int i = max;i!=0;i--)
00411A05 mov eax,dword ptr [max]
00411A08 mov dword ptr [i],eax
00411A0B jmp main+36h (411A16h)
00411A0D mov eax,dword ptr [i]
00411A10 sub eax,1
00411A13 mov dword ptr [i],eax
00411A16 cmp dword ptr [i],0
00411A1A je main+3Eh (411A1Eh)
это не одно и тоже ? или я, что то не правильно понимаю?

На самом деле прикол в том, что при инициализации выполняется:
* в первом случае:
mov dword ptr [i],0
* во втором случае:
mov eax,dword ptr [max]
mov dword ptr [i],eax
.
Завто внутри цикла (на каждой итерации) будет:
* в первом случае:
- в начале цикла:
mov eax,dword ptr [i]
add eax,1
mov dword ptr [i],eax ; (что уже само по себе извращение, когда можно сделать inc dword ptr [i])
- в конце цикла:
mov eax,dword ptr [i] ; соптимизировать эти две инструкции нельзя,
cmp eax,dword ptr [max] ; если цикл организован именно таким образом
je main+41h
* во втором случае:
- в начале цикла:
mov eax,dword ptr [i]
sub eax,1
mov dword ptr [i],eax
- в конце:
cmp dword ptr [i],0
00411A1A je main+3Eh
.
Т.е, в первом случае приходится на 1 инструкцию больше (mov), (если отключить кэш, то разница может быть ощутима, т.к. эта инструкция обращается к памяти). Кстати, даже если включить оптимизацию, то скорее всего значение переменной будет записано в регистр. На скорость это не повлияет, но тогда будет занят на 1 регистр больше (соответственно, его нельзя будет юзать при оптимизации чего-то другого, например, второго вложенного цикла).
.
---------------------------------------------
.
Теперь по поводу того, что глаголил dimedrol...
Сравнение/присвоение нулю ничуть не быстрее сравнения/присвоения другому числу. Более того, на современных процах операции с цифрами занимают столко же времени, сколько и операции с регистрами (причём, не важно, eax это или нет). Аналогично и с inc и dec (т.е. j++ и j-- работают одинаково).
.
Здесь фокус в другом. Если включена оптимизация, то (как уже сказал rcz) в первом случае будет генериться
dec esi
cmp esi,ebx
jne loop
а во втором
dec esi
jne loop
т.е. на 1 инструкцию меньше (cmp esi,0 здесь не нужен, т.к. jne будет прыгать, если esi=0, а вот если esi=ЧтоТоДругое, то jne будет прыгать только если выполнен cmp). Надеюсь, все всё поняли
.
Важно понимать такую вещь. Делая цикл:
for(int j=SIZE;j!=0;j--)
вы присваиваете переменной j значение SIZE один раз, а далее в цикле делаете inc (или dec) и сравнение j с константой.
.
Делая же цикл:
for(int j;j!=SIZE;j++)
вы присваиваете переменной j один раз значение 0, а в цикле делаете inc (или dec) и сравнение j с SIZE. Соответственно, если SIZE - это функция, то её нужно будет вызывать на каждой итерации, следовательно, скорость снижается.
.
------------------------------------------
.
Поэтому (мораль всей басни такова) второй способ будет аналогичен первому только в двух случаях:
* если SIZE-это константа и оптимизация выключена;
* если SIZE-это константа, но мы делаем цикл не от/до нуля, а от/до другого числа.
Иначе лучше юзать первый вариант

Циклы

Visitor — Mon, 10 Nov 2003 17:57:16 +0000

Visitor: Уточню ...и если все тело цикла выполняется за мало-мало-мало микрооопераций

Циклы

rcz — Mon, 10 Nov 2003 12:52:22 +0000

rcz: Да, такой for(int j=SIZE;j!=0;j--) работает на 1 микрооперацию быстрей.

О смысле оптимизации - особенно в цикле она важна, если этот SIZE = много-много-много.

Циклы

-=Маббус=- — Mon, 10 Nov 2003 12:37:18 +0000

-=Маббус=-:

QUOTE (rcz @ 9.11.03, 23:24)

По тактам - одно и то же.
Но это ведь компиллировалось без оптимизации по скорости?
Если оптимизировать по скорости (ключ O2), то
1)for(int i = max;i!=0;i--)
сведется к
loop:
...
dec esi
jne loop
2)for(int i = 0;i!=max;i++)
если max не будет изменяться, и не будет использоваться i, то тут будет код как в 1, иначе
inc esi
cmp esi, ebx ;max
jne loop

Выходит , что первое быстрее так как там на одну комманду меньше?

Циклы

deesan — Mon, 10 Nov 2003 07:10:13 +0000

deesan: Ну тут можно вспомнить еще что ++i эффективнее чем i++.
Но вообще Страуструп писал что хороший оптимизирующий компилятор должен выдавать одинаковый код.

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

А вообще ни разу в жизни не сталкивался с ситуацией где такие изыски позволяли достичь реального увеличения производительности. Ну не писал я Real-time системы
А времен всяких там 8086 с 64кб не застал....

Циклы

rcz — Sun, 09 Nov 2003 19:24:22 +0000

rcz: По тактам - одно и то же.

Но это ведь компиллировалось без оптимизации по скорости?

Если оптимизировать по скорости (ключ O2), то
1)for(int i = max;i!=0;i--)
сведется к

loop:
...
dec esi
jne loop

2)for(int i = 0;i!=max;i++)
если max не будет изменяться, и не будет использоваться i, то тут будет код как в 1, иначе
inc esi
cmp esi, ebx ;max

jne loop

Циклы

dimedrol — Sun, 09 Nov 2003 19:16:46 +0000

dimedrol:

QUOTE

это не одно и тоже ? или я, что то не правильно понимаю?

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

CODE

00411A16 cmp dword ptr [i],0

ввиду содержаня в ней "мифического" нуля

Циклы

-=Маббус=- — Sun, 09 Nov 2003 18:04:41 +0000

-=Маббус=-: for(int i = 0;i!=max;i++)
00411A05 mov dword ptr [i],0
00411A0C jmp main+37h (411A17h)
00411A0E mov eax,dword ptr [i]
00411A11 add eax,1
00411A14 mov dword ptr [i],eax
00411A17 mov eax,dword ptr [i]
00411A1A cmp eax,dword ptr [max]
00411A1D je main+41h (411A21h)

for(int i = max;i!=0;i--)
00411A05 mov eax,dword ptr [max]
00411A08 mov dword ptr [i],eax
00411A0B jmp main+36h (411A16h)
00411A0D mov eax,dword ptr [i]
00411A10 sub eax,1
00411A13 mov dword ptr [i],eax
00411A16 cmp dword ptr [i],0
00411A1A je main+3Eh (411A1Eh)

это не одно и тоже ? или я, что то не правильно понимаю?

Циклы

AQL — Sat, 08 Nov 2003 17:19:53 +0000

AQL: Такой трюк хорош в таких случаях:

vector a;

зуб даю, что вот это
for(int i = a.size(); --i>=0; )
{

}

будет работать быстрее, чем вот это:

for(int i = 0; i{

}

Циклы

Visitor — Fri, 07 Nov 2003 23:35:59 +0000

Visitor: да не... хороший оптимизатор никаких XOR не будет делать...
будет что-то вроде

CODE

@@loc_1:
...
dec edi
<какая-то одна простая инструкция, если ее можно сюда поставить>
jnz @@loc_1

Вот на етой "одной простой инструкции" и будет выигрыш в 1 такт. Если структура выражения в цикле не позволяет ее вставить, вообще не будет выигрыша.

Циклы

Fester — Fri, 07 Nov 2003 20:35:09 +0000

Fester: Наверное все таки

CODE

for(int j=0;j!=SIZE;j++)

А вообще какая разница с чем сравнивать, если XOR дает ответ за один такт? Ну не заполняются же регистры нулем быстрее
Что касается вычитания, то тут тоже нет никакой разницы, т.к. вычитание - это тоже сложение, только в обратном/дополнительном коде. Так что скорость одна и таже.

Так что разницы быть не должно....

Циклы

Visitor — Fri, 07 Nov 2003 18:15:11 +0000

Visitor: Практически побоку... можно выиграть максимум 1 такт на процессоре старше 486. Такие циклы, чтобы ето имело значение встречаются довольно редко...

Циклы

dimedrol — Fri, 07 Nov 2003 17:33:57 +0000

dimedrol: Я слышал, что правельнее(в смысле оптимальнее) такой код

CODE

for(int j=SIZE;j!=0;j--)

чем такой

CODE

for(int j;j!=SIZE;j++)

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

Форум на Исходниках.RU

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы

Циклы