Re[3]: Что быстрее IF или +
От: TK Лес кывт.рф
Дата: 04.12.06 11:20
Оценка: 1 (1) +1
Hello, "_d_m_"
>
> S>public static Matrix ScalarMultiply(Matrix m, float a)
> S>{
> S> if (a == 0)
> S> return ZeroMatrix;
> S> if (a == 1)
> S> return m;
> S> return m*a; // честное умножение
> S>}
> S>[/c#]
> S>6. Особенно если 0 и 1 встречаются чаще, чем другие значения параметра.

Наглядная демонстрация того, что ранняя оптимизация — зло
Posted via RSDN NNTP Server 2.0
Если у Вас нет паранойи, то это еще не значит, что они за Вами не следят.
Re: Что быстрее IF или +
От: Sinclair Россия https://github.com/evilguest/
Дата: 04.12.06 10:49
Оценка: +2
Здравствуйте, Alexander_fx, Вы писали:

A_>Что быстрее и правильнее

1. Нормальный язык высокого уровня должен позволять не заботиться о таких вещах. Это настолько зависит от конкретного контекста исполнения, что заморачивать программиста — бред.
2. Если компилятор вашего языка совсем не умеет оптимизировать, то нужно экспериментировать. Только профайлер даст точную информацию.
3. Обычно сравнение целых чисел выполняется через вычитание и проверку соответствующего флага. Поэтому для одного или двух сложений городить if смысла не имеет.
4. Но если предполагается выполнить много арифметических вычислений с участием параметра, то имеет смысл все же проверить самые частые случаи.
5. Например, если речь идет о матрицах, то скорее всего стоит таки задуматься о построении кода типа такого:
public static Matrix ScalarMultiply(Matrix m, float a)
{
    if (a == 0)
        return ZeroMatrix;
    if (a == 0)
        return m;
    return m*a; // честное умножение
}

6. Особенно если 0 и 1 встречаются чаще, чем другие значения параметра.
1.2.0 alpha rev. 655
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: Что быстрее IF или +
От: Sinclair Россия https://github.com/evilguest/
Дата: 07.12.06 09:47
Оценка: 18 (1)
Здравствуйте, Morpheus_, Вы писали:

S>>Ты не мог бы поделиться со мной пояснением, как именно CPU предсказывает переходы? А то мое представление о "сложности" этой операции явно расходится с твоим.


M_>честно говоря непонятен твой смех в данном вопросе,

Это трудно объяснить. Логика обработки условных переходов в процессорах довольно-таки тривиальна. За последние десять лет все изменения в ней сводятся к расширению таблицы переходов. Никакой "сложности" в этом нет, тормознутости тоже. Ключ к успеху — правильное предсказание перехода. Причем стоимость ошибки может быть разной. В тривиальном случае — просто сброс конвеера. В условиях начальной задачи сказано, что в 80% случаев условие выполняется. Значит, предсказывалка будет ошибаться не более чем в 20% случаев.

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

Ты разобрался и получил? Или не разобрался, но рискуешь давать советы? Это все из области рисунков на карте типа "здесь драконы".
1.2.0 alpha rev. 655
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[2]: Что быстрее IF или +
От: _d_m_  
Дата: 04.12.06 11:01
Оценка: +1
Здравствуйте, Sinclair, Вы писали:

S>public static Matrix ScalarMultiply(Matrix m, float a)

S>{
S> if (a == 0)
S> return ZeroMatrix;
S> if (a == 1)
S> return m;
S> return m*a; // честное умножение
S>}
S>[/c#]
S>6. Особенно если 0 и 1 встречаются чаще, чем другие значения параметра.
Re[6]: Что быстрее IF или +
От: Sinclair Россия https://github.com/evilguest/
Дата: 06.12.06 13:29
Оценка: +1
Здравствуйте, Morpheus_, Вы писали:
M_>Есть информация что C#/JIT скомпилят их не в условный jmp и add соответственно?
Ну естественно. Не зная типа аргументов, рассуждать о том, кто во что скомпилит — бессмысленно.

M_>Я не специалист по кэшам современных процессоров

Я так и подозревал. Зачем тогда брать на себя смелость утверждать что-либо о сравнительной производительности низкоуровневых операций?
M_>Думаю как минимум DBTB, BHT, T-cache и кэшей более высокого уровня
И что, все эти кэши кэшируют переходы?
M_>размер кода в исходном посте не оговаривался, поэтому рассматриваем общий случай

S>>Мне довольно сложно представить внутренний цикл, который содержит более тысячи различных переходов.


M_>
M_>    for(int i=0; i < 100; i++)
M_>    {
M_>        DoDifficultTask();
M_>    }
M_>


M_>

Я смею полагать, что если DoDifficultTask переполнит DBTB, то общее время ее исполнения будет значительно больше, чем стоимость ошибки предсказания перехода в for.
1.2.0 alpha rev. 655
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[8]: Что быстрее IF или +
От: fddima  
Дата: 06.12.06 18:32
Оценка: +1
Здравствуйте, Morpheus_, Вы писали:

S>>Я смею полагать, что если DoDifficultTask переполнит DBTB, то общее время ее исполнения будет значительно больше, чем стоимость ошибки предсказания перехода в for.


M_>совершенно верно, если DoDifficultTask переполнит DBTB, то время выполнения этого кода будет значительно больше чем если DoDifficultTask не переполнит DBTB

M_>а сравнение в for будет усугублять ситуацию
Sinclair, как я понял, имел ввиду, что если DoDifficultTask переполнит DBTB или не переполнит DBTB а просто сделает Sleep(1000) — то нам будет абсолютно фиолетово будет ли ошибка предсказания в for или нет, так как общее время выполнения кода будет неощутимо одинаковым.

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

Действительно сложнее — возможно a у нас в регистре и проверка ничего не стоит. а b и c — даже не в кеше, и если a=0 — достаточно частый случай, а b и c упорно вылазят из кеша — то будешь не прав ты.
Ну и наконец a у нас int, а b и c — float (или что-то более изощренное? ), так что подозреваю нужно будет привести a к float да и float-ы складываются уже не так как int-ы.
Хотя есть сценарий что b и c — это property и по set выполняется sleep(rnd()) для разнообразия.

А в целом — компилятор может это оптимизировать сам если посчитает нужным. А программисту в крайнем случае следует заиметь любимый профайлер.
Re[9]: Что быстрее IF или +
От: fddima  
Дата: 07.12.06 11:09
Оценка: +1
Здравствуйте, Morpheus_, Вы писали:

M_>предсказываются они не совсем легко и только если они инфа о них уже лежит в кэше, но в любом случае сама операция перехода довольно длительная (20-50 тактов, а у сложения 1), конечно если переход только что уже выполнялся то он выполнится быстрее чем если это переход на новый адрес, но всеравно в несколько десятков раз медленнее чем сложение

Откуда такие выводы?
Далеко не факт что будет
add ebx, eax
.
Весьма вероятно, что
add dword ptr [esp-124], eax
, а это не совсем так любимый тобою 1 такт.
Так или иначе всё это выглядит бездоказательным, и голословным. Есть реальный компилятор, реальная программа (у автора поста), реальная платформа и реальный JIT, и тока анализируя это всё можно вообще говорить о тактах.

И опять не могу понять, почему ты так уверен что это int?!
Что быстрее IF или +
От: Alexander_fx  
Дата: 02.12.06 21:39
Оценка:
Что быстрее и правильнее

if a<>0 then b=b+5

или

b=b+5


просто есть параметр — который в 80% не используется
вот я и думаю — что проще и быстрее — просто прибавлять его ВСЕГДА или проверять наличие и прибавлять только когда он есть

Понимаю что по разница небольшая — так что вопрос наверное академический.
Re: Что быстрее IF или +
От: Аноним  
Дата: 02.12.06 21:44
Оценка:
Здравствуйте, Alexander_fx, Вы писали:

A_>Что быстрее и правильнее

A_>if a<>0 then b=b+5
A_>или
A_>b=b+5

А сэр вообще о каком языке говорит? Что-то Паскаль навевает с этим then

A_>просто есть параметр — который в 80% не используется


не используется а, и прибавляется в... логика где?

A_>вот я и думаю — что проще и быстрее — просто прибавлять его ВСЕГДА или проверять наличие и прибавлять только когда он есть


A_>Понимаю что по разница небольшая — так что вопрос наверное академический.


А не быстрей сделать b+=5? и ВСЕГДА?
Re[2]: Что быстрее IF или +
От: Alexander_fx  
Дата: 02.12.06 21:50
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Alexander_fx, Вы писали:


A_>>Что быстрее и правильнее

A_>>if a<>0 then b=b+5
A_>>или
A_>>b=b+5

А>А сэр вообще о каком языке говорит? Что-то Паскаль навевает с этим then


A_>>просто есть параметр — который в 80% не используется


А>не используется а, и прибавляется в... логика где?


A_>>вот я и думаю — что проще и быстрее — просто прибавлять его ВСЕГДА или проверять наличие и прибавлять только когда он есть


A_>>Понимаю что по разница небольшая — так что вопрос наверное академический.


А>А не быстрей сделать b+=5? и ВСЕГДА?



сорри -читать так
If a<>0 then
b=b+a
c=c+a


или

b=b+a
c=c+a


т.е. стоит ли 1 сравнение двум сложениям

Язык — VB NET
Re[3]: Что быстрее IF или +
От: Аноним  
Дата: 03.12.06 02:40
Оценка:
Здравствуйте, Alexander_fx, Вы писали:

A_>Здравствуйте, Аноним, Вы писали:


А>>Здравствуйте, Alexander_fx, Вы писали:


A_>сорри -читать так

A_>If a<>0 then
A_>b=b+a
A_>c=c+a


A_>или


A_>b=b+a

A_>c=c+a


A_>т.е. стоит ли 1 сравнение двум сложениям


A_>Язык — VB NET



Одно сложение по любому быстрее.
Re[3]: Что быстрее IF или +
От: Аноним  
Дата: 03.12.06 10:02
Оценка:
Быстрее в каком плане?
В плане производительности, скорости разработки, отдавливания багов?
Думаю намек понятен.
С/у Дмитрий.


данное сообщение получено с www.gotdotnet.ru
ссылка на оригинальное сообщение
Re: Что быстрее IF или +
От: WinterMute Россия http://yarrr.ru
Дата: 03.12.06 10:32
Оценка:
Здравствуйте, Alexander_fx, Вы писали:

A_>Что быстрее и правильнее


A_>if a<>0 then b=b+5


A_>или


A_>b=b+5



A_>просто есть параметр — который в 80% не используется

A_>вот я и думаю — что проще и быстрее — просто прибавлять его ВСЕГДА или проверять наличие и прибавлять только когда он есть

A_>Понимаю что по разница небольшая — так что вопрос наверное академический.


Обычно сравнение достаточно дорогая операция, я бы не постоветовал так "оптимизировать".
Re[2]: Что быстрее IF или +
От: _d_m_  
Дата: 03.12.06 12:48
Оценка:
Здравствуйте, WinterMute, Вы писали:

WM>Обычно сравнение достаточно дорогая операция, я бы не постоветовал так "оптимизировать".


а я еще со времен ассемблера 8086 считал, что сравнение целых чисел одна из дешевых операций
Re: Что быстрее IF или +
От: _d_m_  
Дата: 03.12.06 12:57
Оценка:
Здравствуйте, Alexander_fx, Вы писали:

A_>Что быстрее и правильнее


A_>if a<>0 then b=b+5


A_>или


A_>b=b+5



A_>просто есть параметр — который в 80% не используется

A_>вот я и думаю — что проще и быстрее — просто прибавлять его ВСЕГДА или проверять наличие и прибавлять только когда он есть

A_>Понимаю что по разница небольшая — так что вопрос наверное академический.


Сравнение и сложение суть операции равновесные — так было всегда начиная от Asm/C/C++. Не думаю что кардинально что-то изменилось в .Net. Так что смысла нет в if — просто складывай и все.

PS: На уровне процессора сравнение целых чисел осуществляется вычитанием одного операнда из другого. Сравнение на равенство/неравенство нулю осуществляется операцией "исключающее или" — XOR
Re[3]: Что быстрее IF или +
От: Алексей П Россия  
Дата: 03.12.06 13:23
Оценка:
Здравствуйте, _d_m_, Вы писали:

___> а я еще со времен ассемблера 8086 считал, что сравнение целых чисел одна из дешевых операций


Вообще-то не дешевая. То есть сравнить-то их просто, за такт в идеале, а вот jnz потом может тормозить хорошо в условиях длинного конвеера.
... << RSDN@Home 1.2.0 alpha rev. 668>>
Re[4]: Что быстрее IF или +
От: _d_m_  
Дата: 04.12.06 02:03
Оценка:
Здравствуйте, Алексей П, Вы писали:

АП>Здравствуйте, _d_m_, Вы писали:


___>> а я еще со времен ассемблера 8086 считал, что сравнение целых чисел одна из дешевых операций


АП>Вообще-то не дешевая. То есть сравнить-то их просто, за такт в идеале, а вот jnz потом может тормозить хорошо в условиях длинного конвеера.


Ну тогда пользуйте процессоры фирмы AMD — в этом случае они как раз выигрывают
Что быстрее IF или +
От: Аноним  
Дата: 04.12.06 02:32
Оценка:
Сложение с 0 происходит быстро, лучше делай сложение без условий, в других ситуациях где *, ^, \, тогда условие конечно будет экономить.
--------------
Любое удобство идет за счет мегагерцеф! : {<b>1</b>, <b>2</b>, <b>3</b>, 4}


данное сообщение получено с www.gotdotnet.ru
ссылка на оригинальное сообщение
Re[3]: Что быстрее IF или +
От: Аноним  
Дата: 05.12.06 02:33
Оценка:
чем тебе не понравилась данная оптимизация?
--------------
Любое удобство идет за счет мегагерцеф! : {<b>1</b>, <b>2</b>, <b>3</b>, 4}


данное сообщение получено с www.gotdotnet.ru
ссылка на оригинальное сообщение
Re[4]: Что быстрее IF или +
От: _d_m_  
Дата: 05.12.06 04:03
Оценка:
Здравствуйте, Nimnul, Вы писали:

N>чем тебе не понравилась данная оптимизация?


Вероятно тем, что в примере была ошибка — 0 вместо 1
Re[5]: Что быстрее IF или +
От: TK Лес кывт.рф
Дата: 05.12.06 05:11
Оценка:
Hello, "_d_m_"
>
> N>чем тебе не понравилась данная оптимизация?
> Вероятно тем, что в примере была ошибка — 0 вместо 1

На понравилось следующее:
1. Ошибка 0 вместо 1
2. Сравнение на равенство вещественных чисел

ИХМО, внесение потенциальных проблемем с каждой второй сторчкой кода это серьезный повод задуматься о полезности такой оптимизации.
Posted via RSDN NNTP Server 2.0
Если у Вас нет паранойи, то это еще не значит, что они за Вами не следят.
Re: Что быстрее IF или +
От: Morpheus_  
Дата: 05.12.06 13:08
Оценка:
Здравствуйте, Alexander_fx, Вы писали:

A_>Что быстрее и правильнее

A_>if a<>0 then b=b+5
A_>или
A_>b=b+5
A_>просто есть параметр — который в 80% не используется
A_>вот я и думаю — что проще и быстрее — просто прибавлять его ВСЕГДА или проверять наличие и прибавлять только когда он есть
A_>Понимаю что по разница небольшая — так что вопрос наверное академический.

IF будет выполняться значительно дольше чем + (относительно времени выполнения +), кроме того IF будет снижать производительность остального кода за счет того что блок предсказания перехода в процессоре сохранит какуюто инфу об этом условном переходе заняв место для информации о другом более важном условном переходе и процессор будет вынужден выполнять лишние операции которых можно было избежать используя +...
Впрочем замедление для одного if'а очень мало, т.к. разница эта будет порядка сотен наносекунд-единиц микросекунд, но злоупотреблять числом if'ов не стоит, при большом количестве if'ов внутри длительного цикла производительность снизится чрезмерно значительно

Операция + имеет максимальную скорость, IF (для процессора это условный jmp) это самая тяжелая и тормозящая операция, т.к. процессору сложно предсказать по какому пути пойдет исполнение до того как не выполнятся все операции до этого условного jmp и корректно подгрузить следующую порцию кода. Более того, время выполнения IF сложнопредсказуемо, зависит от текущего состояния процессора и может при определенных условия приводить к резкому скачкообразному замедлению производительности в тысячи раз
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re: Что быстрее IF или +
От: Morpheus_  
Дата: 05.12.06 13:14
Оценка:
Здравствуйте, Nimnul, Вы писали:

N>Сложение с 0 происходит быстро, лучше делай сложение без условий, в других ситуациях где *, ^, \, тогда условие конечно будет экономить.


условие никогда не будет быстрее чем операция сложения! насколько я знаю на всех архитектруах процессоров (и на RISC в том числе) условный переход (а именно в эту инструкцию компилируется IF) занимает в 2-3 раза больше времени чем выполнение операции сложения. В процессорах x86 операция условного перехода будет еще более медленной, в том числе за счет задействования блока предсказания переходов, поэтому в некоторых особо неудачных случаях IF будет выполнятся в тысячи раз медленнее чем +, в других случаях будет как минимум в 5-10 раз медленее чем +
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[2]: Спасибо
От: Alexander_fx  
Дата: 05.12.06 15:58
Оценка:
Здравствуйте, Morpheus_, Вы писали:

M_>Здравствуйте, Nimnul, Вы писали:


N>>Сложение с 0 происходит быстро, лучше делай сложение без условий, в других ситуациях где *, ^, \, тогда условие конечно будет экономить.


M_>условие никогда не будет быстрее чем операция сложения! насколько я знаю на всех архитектруах процессоров (и на RISC в том числе) условный переход (а именно в эту инструкцию компилируется IF) занимает в 2-3 раза больше времени чем выполнение операции сложения. В процессорах x86 операция условного перехода будет еще более медленной, в том числе за счет задействования блока предсказания переходов, поэтому в некоторых особо неудачных случаях IF будет выполнятся в тысячи раз медленнее чем +, в других случаях будет как минимум в 5-10 раз медленее чем +
Re[2]: Что быстрее IF или +
От: Sinclair Россия https://github.com/evilguest/
Дата: 06.12.06 10:01
Оценка:
Здравствуйте, Morpheus_, Вы писали:
льше чем +[/b] (относительно времени выполнения +), кроме того IF будет снижать производительность остального кода за счет того что блок предсказания перехода в процессоре сохранит какуюто инфу об этом условном переходе заняв место для информации о другом более важном условном переходе и процессор будет вынужден выполнять лишние операции которых можно было избежать используя +...
Гм. А почему ты думаешь, что предсказывалка переходов не поможет в следующий раз?
M_>Впрочем замедление для одного if'а очень мало, т.к. разница эта будет порядка сотен наносекунд-единиц микросекунд, но злоупотреблять числом if'ов не стоит, при большом количестве if'ов внутри длительного цикла производительность снизится чрезмерно значительно

M_>Операция + имеет максимальную скорость, IF (для процессора это условный jmp) это самая тяжелая и тормозящая операция, т.к. процессору сложно предсказать по какому пути пойдет исполнение до того как не выполнятся все операции до этого условного jmp и корректно подгрузить следующую порцию кода.


Ты не мог бы поделиться со мной пояснением, как именно CPU предсказывает переходы? А то мое представление о "сложности" этой операции явно расходится с твоим.
M_>Более того, время выполнения IF сложнопредсказуемо, зависит от текущего состояния процессора и может при определенных условия приводить к резкому скачкообразному замедлению производительности в тысячи раз
Почему?
1.2.0 alpha rev. 655
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[3]: Что быстрее IF или +
От: Morpheus_  
Дата: 06.12.06 11:20
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Morpheus_, Вы писали:

S>льше чем +[/b] (относительно времени выполнения +), кроме того IF будет снижать производительность остального кода за счет того что блок предсказания перехода в процессоре сохранит какуюто инфу об этом условном переходе заняв место для информации о другом более важном условном переходе и процессор будет вынужден выполнять лишние операции которых можно было избежать используя +...
S>Гм. А почему ты думаешь, что предсказывалка переходов не поможет в следующий раз?

например здесь

При формировании трассы предсказание целевого адреса и направления перехода необходимо для того, чтобы размещать МОПы в трассе в соответствии с предполагаемым динамическим порядком их последующего исполнения. Предсказание производится по адресу исходной x86-инструкции перехода. Этой цели служит так называемая динамическая таблица адресов переходов (Dynamic Branch Target Buffer, DBTB) и связанная с ней таблица истории переходов (Branch History Table, BHT). Таблица DBTB по своей структуре напоминает кэш-память и состоит из 4096 элементов, организованных в виде 1024 наборов по 4 элемента.


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


M_>>Впрочем замедление для одного if'а очень мало, т.к. разница эта будет порядка сотен наносекунд-единиц микросекунд, но злоупотреблять числом if'ов не стоит, при большом количестве if'ов внутри длительного цикла производительность снизится чрезмерно значительно


M_>>Операция + имеет максимальную скорость, IF (для процессора это условный jmp) это самая тяжелая и тормозящая операция, т.к. процессору сложно предсказать по какому пути пойдет исполнение до того как не выполнятся все операции до этого условного jmp и корректно подгрузить следующую порцию кода.

S>
S>Ты не мог бы поделиться со мной пояснением, как именно CPU предсказывает переходы? А то мое представление о "сложности" этой операции явно расходится с твоим.

если интересны глубинные детали, то лучше найти специалиста по реализации кэшей и блоков предсказания переходов в современных процессорах, инфа эта вроде как доступна в инете, можешь например порыться в документации по реализации кэшей в P4, ну и как говориться см. google...
Коротко из того что google вывалил первой ссылкой: Мистический и загадочный Trace-кэш:

На самом деле механизм отображения адресов x86-инструкций в адреса МОПов необходим не для каждой инструкции, а только для тех, на которые производится переход — то есть для первой (микро)инструкции в каждой трассе.
....
При неправильном предсказании перехода: сначала выполняются действия 1, 2 или 3 — в соответствии с предсказанным направлением. В тот момент, когда выяснится, что направление предсказано неверно, исполнение всех стартовавших инструкций (начиная с инструкции перехода) прекращается, результаты их работы аннулируются, и производится поиск трассы по другому (правильному) адресу. Далее начинается исполнение найденной трассы либо формирование новой. Неправильно предсказанный переход при нахождении адресата в Т-кэше занимает около 20 тактов для процессора P4 и около 30 тактов для процессора P4E. Если адресата нет в Т-кэше, то требуется ещё около 20 тактов (по грубым оценкам).


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


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

S>Почему?

Например потому что если число переходов в цикле превысит размер одного из кэшей, то процессор будет вынужден на каждую итерацию цикла обращаться к внешней памяти или делать другую крайне медленную операцию, процессор же в это время будет тупо простаивать теряя драгоценное время.
На этом основаны принципы измерения размеров кэш памяти — вызывается процедура со все большими требованиями к кэш памяти и как только происходит резкое замедление в десятки раз, значит достигнут предел кэш памяти и можно подсчитать его размер. См. например утилиты определяющие размеры кэш памяти процессора.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[4]: Что быстрее IF или +
От: Morpheus_  
Дата: 06.12.06 11:27
Оценка:
Здравствуйте, Sinclair, Вы писали:

M_>>Операция + имеет максимальную скорость, IF (для процессора это условный jmp) это самая тяжелая и тормозящая операция, т.к. процессору сложно предсказать по какому пути пойдет исполнение до того как не выполнятся все операции до этого условного jmp и корректно подгрузить следующую порцию кода.

S>
S>Ты не мог бы поделиться со мной пояснением, как именно CPU предсказывает переходы? А то мое представление о "сложности" этой операции явно расходится с твоим.

честно говоря непонятен твой смех в данном вопросе, выполнение операции перехода внутри современных процессоров это очень не тривиальная задача, человек решивший разобраться во всех деталях выполнения данной операции рискует получить рак моска...
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[5]: Что быстрее IF или +
От: Morpheus_  
Дата: 06.12.06 11:29
Оценка:
M_>честно говоря непонятен твой смех в данном вопросе, выполнение операции перехода внутри современных процессоров это очень не тривиальная задача, человек решивший разобраться во всех деталях выполнения данной операции рискует получить рак моска...

речь разумеется идет не о том как использовать операцию перехода в программе, а о том как она обрабатывается процессором
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[4]: Что быстрее IF или +
От: Sinclair Россия https://github.com/evilguest/
Дата: 06.12.06 11:59
Оценка:
Здравствуйте, Morpheus_, Вы писали:


M_>>>Операция + имеет максимальную скорость, IF (для процессора это условный jmp) это самая тяжелая и тормозящая операция, т.к. процессору сложно предсказать по какому пути пойдет исполнение до того как не выполнятся все операции до этого условного jmp и корректно подгрузить следующую порцию кода.

S>>
S>>Ты не мог бы поделиться со мной пояснением, как именно CPU предсказывает переходы? А то мое представление о "сложности" этой операции явно расходится с твоим.
Ок. Поясняю: процессору предскзать, по какому пути пойдет исполнение, не стоит ровно ничего. Стоимость связана только с ошибкой предсказания, которая приведет к сбросу конвеера и прочим прелестям.

M_>операция-же сложения выполнится за 1 такт

Это не вполне верно. Она может выполниться за 1 такт, если оба аргумента уже лежат в регистрах. Это далеко не всегда факт: загрузка операнда может привести к чему угодно, вплоть до cache miss. Заметь, автор начального вопроса не спрашивал, что дешевле — add или jmp; он привел пример кода на языке высокого уровня. Делать столь категоричные утверждения, как "IF будет выполняться значительно дольше чем +" я лично бы не стал, т.к. не вполне понятно, как именно реализуется if и как +.

M_>Например потому что если число переходов в цикле превысит размер одного из кэшей,

Какого именно?
У меня возникает подозрение, что ты сваливаешь в одну кучу размер кода процедуры, разброс данных, и количество переходов. Из твоей же цитаты следует, что размер таблицы переходов для P4 равен 1024. Мне довольно сложно представить внутренний цикл, который содержит более тысячи различных переходов.
1.2.0 alpha rev. 655
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: Что быстрее IF или +
От: Morpheus_  
Дата: 06.12.06 12:57
Оценка:
Здравствуйте, Sinclair, Вы писали:

M_>>операция-же сложения выполнится за 1 такт

S>Это не вполне верно. Она может выполниться за 1 такт, если оба аргумента уже лежат в регистрах. Это далеко не всегда факт: загрузка операнда может привести к чему угодно, вплоть до cache miss. Заметь, автор начального вопроса не спрашивал, что дешевле — add или jmp; он привел пример кода на языке высокого уровня. Делать столь категоричные утверждения, как "IF будет выполняться значительно дольше чем +" я лично бы не стал, т.к. не вполне понятно, как именно реализуется if и как +.

Есть информация что C#/JIT скомпилят их не в условный jmp и add соответственно?

M_>>Например потому что если число переходов в цикле превысит размер одного из кэшей,

S>Какого именно?

Я не специалист по кэшам современных процессоров
Думаю как минимум DBTB, BHT, T-cache и кэшей более высокого уровня

S>У меня возникает подозрение, что ты сваливаешь в одну кучу размер кода процедуры, разброс данных, и количество переходов. Из твоей же цитаты следует, что размер таблицы переходов для P4 равен 1024.


размер кода в исходном посте не оговаривался, поэтому рассматриваем общий случай

S>Мне довольно сложно представить внутренний цикл, который содержит более тысячи различных переходов.


    for(int i=0; i < 100; i++)
    {
        DoDifficultTask();
    }


... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re: В тему ,что быстрее IF или Virtual Call
От: chudo19  
Дата: 06.12.06 13:06
Оценка:
Вот меня интересовал всегда более сложный вариант
что быстрее много IF или замена на виртуальный метод.
И где находится та граница в кол-ве IF которые будут тормознее виртуального вызова
(Про не правильный ООП дизайн просьба не постить )
Re[7]: Что быстрее IF или +
От: Morpheus_  
Дата: 06.12.06 17:54
Оценка:
Здравствуйте, Sinclair, Вы писали:

M_>>Я не специалист по кэшам современных процессоров

S>Я так и подозревал. Зачем тогда брать на себя смелость утверждать что-либо о сравнительной производительности низкоуровневых операций?

по твоему никто вообще не должен брать на себя смелось утверждать что-либо?

M_>>Думаю как минимум DBTB, BHT, T-cache и кэшей более высокого уровня

S>И что, все эти кэши кэшируют переходы?

именно

M_>>размер кода в исходном посте не оговаривался, поэтому рассматриваем общий случай


S>>>Мне довольно сложно представить внутренний цикл, который содержит более тысячи различных переходов.


M_>>
M_>>    for(int i=0; i < 100; i++)
M_>>    {
M_>>        DoDifficultTask();
M_>>    }
M_>>


M_>>

S>Я смею полагать, что если DoDifficultTask переполнит DBTB, то общее время ее исполнения будет значительно больше, чем стоимость ошибки предсказания перехода в for.

совершенно верно, если DoDifficultTask переполнит DBTB, то время выполнения этого кода будет значительно больше чем если DoDifficultTask не переполнит DBTB
а сравнение в for будет усугублять ситуацию

На деле все еще сложнее так как кэш не один, короче операция сложения многократно легковеснее и быстрее чем операция перехода, особенно условного, думаю этого достаточно
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[7]: Что быстрее IF или +
От: Аноним  
Дата: 07.12.06 01:38
Оценка:
я почему то всегда думал, что короткие переходы работают быстро, т.к. адреса переходов относительны и легко предсказываются планировщиком кеша.
--------------
Любое удобство идет за счет мегагерцеф! : {<b>1</b>, <b>2</b>, <b>3</b>, 4}


данное сообщение получено с www.gotdotnet.ru
ссылка на оригинальное сообщение
Re[8]: Что быстрее IF или +
От: Morpheus_  
Дата: 07.12.06 10:59
Оценка:
Здравствуйте, Nimnul, Вы писали:

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


N>
данное сообщение получено с www.gotdotnet.ru

N>ссылка на оригинальное сообщение


предсказываются они не совсем легко и только если они инфа о них уже лежит в кэше, но в любом случае сама операция перехода довольно длительная (20-50 тактов, а у сложения 1), конечно если переход только что уже выполнялся то он выполнится быстрее чем если это переход на новый адрес, но всеравно в несколько десятков раз медленнее чем сложение
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[6]: Что быстрее IF или +
От: Morpheus_  
Дата: 07.12.06 11:01
Оценка:
Здравствуйте, Sinclair, Вы писали:


S>рисунков на карте типа "здесь драконы".


... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[10]: Что быстрее IF или +
От: Morpheus_  
Дата: 07.12.06 13:07
Оценка:
Здравствуйте, fddima, Вы писали:

M_>>предсказываются они не совсем легко и только если они инфа о них уже лежит в кэше, но в любом случае сама операция перехода довольно длительная (20-50 тактов, а у сложения 1), конечно если переход только что уже выполнялся то он выполнится быстрее чем если это переход на новый адрес, но всеравно в несколько десятков раз медленнее чем сложение

F> Откуда такие выводы?
F> Далеко не факт что будет
add ebx, eax
.

F> Весьма вероятно, что
add dword ptr [esp-124], eax
, а это не совсем так любимый тобою 1 такт.

F>Так или иначе всё это выглядит бездоказательным, и голословным. Есть реальный компилятор, реальная программа (у автора поста), реальная платформа и реальный JIT, и тока анализируя это всё можно вообще говорить о тактах.

в таком случае мы рассматриваем что будет быстрее:
+:
    add    dword ptr [esp+4],5


или if:
    cmp    dword ptr [esp+4],0 
    je    00000016 
    add    dword ptr [esp+4],5


как ни крути а + будет быстрее
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[11]: Что быстрее IF или +
От: fddima  
Дата: 07.12.06 13:20
Оценка:
Здравствуйте, Morpheus_, Вы писали:

F>>Так или иначе всё это выглядит бездоказательным, и голословным. Есть реальный компилятор, реальная программа (у автора поста), реальная платформа и реальный JIT, и тока анализируя это всё можно вообще говорить о тактах.


M_>в таком случае мы рассматриваем что будет быстрее:

M_>или if:
M_>
M_>    cmp    dword ptr [esp+4],0 
M_>    je    00000016 
M_>    add    dword ptr [esp+4],5 
M_>

Ой, а откуда 5? у нас a была переменной.
Затем в оригинале было: if(a==0){b+=a;c+=a;}
А у тебя получилось if(a==0){a=5;}

И разве это реально сгенерированный код? Кажется нет, стоит ли его обсуждать.

ESP+XXX это тоже хорошо, но я больше показал для демонстрации того что b и c у нас не в регистрах. А где-то в памяти... которая не всегда в кеше.

M_>как ни крути а + будет быстрее

Ты развёл разговор о предсказаниях переходов, а я говорю о том, что это врядли будет имеет значение. У тебя как минимум непростая виртуальная машина + непростая ОС. Предсказатель работает так как он работает, но точить код под него совершенно не стоит. Наш код прерывают тысячи раз, а мы этого не замечаем, и почему-то не думаем об этом.

Я бы вставлял проверки, если они соответствует алгоритму. Но не в целях оптимизации. Опять таки, как насчёт того что b и c это float?
Re[12]: Что быстрее IF или +
От: Morpheus_  
Дата: 07.12.06 14:02
Оценка:
Здравствуйте, fddima, Вы писали:

F>Здравствуйте, Morpheus_, Вы писали:


F>>>Так или иначе всё это выглядит бездоказательным, и голословным. Есть реальный компилятор, реальная программа (у автора поста), реальная платформа и реальный JIT, и тока анализируя это всё можно вообще говорить о тактах.


M_>>в таком случае мы рассматриваем что будет быстрее:

M_>>или if:
M_>>
M_>>    cmp    dword ptr [esp+4],0 
M_>>    je    00000016 
M_>>    add    dword ptr [esp+4],5 
M_>>

F> Ой, а откуда 5? у нас a была переменной.

в оригинале было:
b=b+5


операция
add dword ptr [esp+4],5


это не a=5, это a=a+5

F> Затем в оригинале было: if(a==0){b+=a;c+=a;}

F> А у тебя получилось if(a==0){a=5;}

неправильно, на самом деле получилось if(a!=0) a=a+5;

F> И разве это реально сгенерированный код? Кажется нет, стоит ли его обсуждать.


именно так, это реально сгенерированный код C#/JIT v1.1.4322
исходник был таков:
using System;

class Program
{
   static void Main()
   {
      int a=0;

      if(a!=0)
         a+=5;
   
      Console.WriteLine("{0}", a.ToString());        // предотвращаем оптимизацию выкидывающую код связанный с переменной a
   }
}


F> ESP+XXX это тоже хорошо, но я больше показал для демонстрации того что b и c у нас не в регистрах. А где-то в памяти... которая не всегда в кеше.


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

M_>>как ни крути а + будет быстрее

F> Ты развёл разговор о предсказаниях переходов, а я говорю о том, что это врядли будет имеет значение. У тебя как минимум непростая виртуальная машина + непростая ОС. Предсказатель работает так как он работает, но точить код под него совершенно не стоит. Наш код прерывают тысячи раз, а мы этого не замечаем, и почему-то не думаем об этом.

F> Я бы вставлял проверки, если они соответствует алгоритму. Но не в целях оптимизации. Опять таки, как насчёт того что b и c это float?


float +:
    fld         qword ptr ds:[06D300A8h] 
    fadd        dword ptr [esp] 
    fstp        dword ptr [esp]


float if:
    fld         dword ptr [esp] 
    fld         qword ptr ds:[06D300B8h] 
    fcomip      st,st(1) 
    fstp        st(0) 
    jp          00000019 
    je          00000025 
00000019    fld         qword ptr ds:[06D300C0h] 
    fadd        dword ptr [esp] 
    fstp        dword ptr [esp] 
00000025




Упорным сторонникам того что if вместе с + будут быстрее чем просто + приведу еще пару доводов

1. if скомпилится не только в тяжелую операцию перехода, но также и в операцию проверки которая сводится к операции вычитания, которая в свою очередь сводится к операции сложения, таким образом имеем:
a) просто +
b) +,jmp,еще одна операция + которая будет выполнятся не всегда
другими словами мы ничего не выигрываем, а только проигрываем, причем значительно, как с точки зрения читабельности кода, так и с точки зрения производительности

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

исходный код:
    for(int i=0; i < 10; i++)
        someWork();


оптимизированный код:
    someWork();
    someWork();
    someWork();
    someWork();
    someWork();
    someWork();
    someWork();
    someWork();
    someWork();
    someWork();


суть этого метода в избавлении от операции перехода на каждой итерации цикла
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[13]: Что быстрее IF или +
От: Morpheus_  
Дата: 07.12.06 14:13
Оценка:
времена нынче другие, скорость работы программ никого не итересует, память сейчас не ресурс, но когда начинают "оптимизировать" с помощью добавления лишних тяжелых операций становится не посебе
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[13]: Что быстрее IF или +
От: fddima  
Дата: 07.12.06 14:53
Оценка:
Здравствуйте, Morpheus_, Вы писали:

M_>в оригинале было:

M_>
M_>b=b+5
M_>

Автор оригинала исправился тут
Автор: Alexander_fx
Дата: 03.12.06
.

M_>операция

M_>
M_>add dword ptr [esp+4],5 
M_>

M_>это не a=5, это a=a+5
если a = 0, то a=a+5 -> a=5;
получилась непонятка. Говорим о разных оригиналах поста.


F>> И разве это реально сгенерированный код? Кажется нет, стоит ли его обсуждать.


M_>именно так, это реально сгенерированный код C#/JIT v1.1.4322

M_>исходник был таков:
А теперь смотрим на всё таки исходный пример (тоже 1.1.4322):
using System;

class Program
{
    static void Main()
    {
        int a = 0;
        int b = 2; 
        int c = 3;

        if(a==0) 
        {
            b+=a;
            c+=a;
        }

        Console.WriteLine("{0}", a.ToString()+b.ToString()+c.ToString());        // предотвращаем оптимизацию выкидывающую код связанный с переменной a
    }
}


А теперь получаем:
        int b = 2; 
0000001b  mov         dword ptr [ebp-8],2 
       int c = 3;
00000022  mov         dword ptr [ebp-0Ch],3 
       if(a==0) 
00000029  cmp         dword ptr [ebp-4],0 
0000002d  jne         0000003B 
           b+=a;
0000002f  mov         eax,dword ptr [ebp-4] 
00000032  add         dword ptr [ebp-8],eax 
           c+=a;
00000035  mov         eax,dword ptr [ebp-4] 
00000038  add         dword ptr [ebp-0Ch],eax


Грустно... пойду напьюсь...
Или я как-то не так смотрю...


F>> ESP+XXX это тоже хорошо, но я больше показал для демонстрации того что b и c у нас не в регистрах. А где-то в памяти... которая не всегда в кеше.

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

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

M_>float +:

M_>
M_>    fld         qword ptr ds:[06D300A8h] 
M_>    fadd        dword ptr [esp] 
M_>    fstp        dword ptr [esp] 
M_>


M_>float if:

M_>
M_>    fld         dword ptr [esp] 
M_>    fld         qword ptr ds:[06D300B8h] 
M_>    fcomip      st,st(1) 
M_>    fstp        st(0) 
M_>    jp          00000019 
M_>    je          00000025 
M_>00000019    fld         qword ptr ds:[06D300C0h] 
M_>    fadd        dword ptr [esp] 
M_>    fstp        dword ptr [esp] 
M_>00000025
M_>

для тела условия уже всё подготовлено. Я говорил только про то что b и c — float?


M_>Упорным сторонникам того что if вместе с + будут быстрее чем просто + приведу еще пару доводов

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

M_>1. if скомпилится не только в тяжелую операцию перехода, но также и в операцию проверки которая сводится к операции вычитания, которая в свою очередь сводится к операции сложения, таким образом имеем:

Что и как делает cmp — нас не должно волновать собственно... каждая из команд вполне адекватно описана, сколько она занимает тактов и туды-сюды.

M_>2. С древних времен известен такой метод оптимизации как раскрутка цикла, смысл его сводится к тому чтобы избавится от инструкций переходов, значительно повысив таким образом производительность (в ущерб размеру кода разумеется), например:

На спектруме разворачивали люди процедуру вывода символов 6x8 (организация экрана 1 бит — одна точка) и килобайта в 4, и там это было очень ощутимо. (Ну уж ооочень удачно сделан был экран).

M_>исходный код:

M_>
M_>    for(int i=0; i < 10; i++)
M_>        someWork();
M_>


M_>оптимизированный код:

[skip]
а someWork — это DoDifficultTask — и в таком случае толку 0. Но об этом может заботиться только jit/компилятор. Об этом уже говорили...
Re[14]: Что быстрее IF или +
От: fddima  
Дата: 07.12.06 14:55
Оценка:
Здравствуйте, Morpheus_, Вы писали:

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

Да, сейчас люди этим деньги зарабатывают, и когда оптимизируют — берутся для начала за разного рода профайлеры.
Re[12]: Что быстрее IF или +
От: Аноним  
Дата: 08.12.06 02:06
Оценка:
2. С древних времен известен такой метод оптимизации как раскрутка цикла, смысл его сводится к тому чтобы избавится от инструкций переходов, значительно повысив таким образом производительность (в ущерб размеру кода разумеется), например:

исходный код:





for(int i=0; i < 10; i++)
someWork();

оптимизированный код:





someWork();
someWork();
someWork();
someWork();
someWork();
someWork();
someWork();
someWork();
someWork();
someWork();

суть этого метода в избавлении от операции перехода на каждой итерации цикла
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

такая оптимизация доступна при двух условиях:
1. Количество итераций статично.
2. Количество статичных итераций не слишком велико.
Любое удобство идет за счет мегагерцеф! : {<b>1</b>, <b>2</b>, <b>3</b>, 4, 5}


данное сообщение получено с www.gotdotnet.ru
ссылка на оригинальное сообщение
Re[8]: Что быстрее IF или +
От: Аноним  
Дата: 08.12.06 02:09
Оценка:
Morpheus_:

но в любом случае сама операция перехода довольно длительная (20-50 тактов, а у сложения 1


Давай будем объективными? код теста в студию.
Любое удобство идет за счет мегагерцеф! : {<b>1</b>, <b>2</b>, <b>3</b>, 4, 5}


данное сообщение получено с www.gotdotnet.ru
ссылка на оригинальное сообщение
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.