Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Регистрация Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Блоги > Psycho Tiger

Оценить эту запись

Битовые сдвиги vs умножение [UPD]

Запись от Psycho Tiger размещена 12.08.2010 в 01:44
Обновил(-а) Psycho Tiger 15.08.2010 в 00:47

[UPDATE: статья почти полностью переписана, если Вам интересна эта тема рекомендую к повторному прочтению]
Нужно прочитать для понимания материала:
Битовые операции (Википедия)


На досуге провел несколько тестов, и вот результаты.
Википедия гласит:
Цитата:
Логические сдвиги влево и вправо используются для быстрого умножения и деления на 2, соответственно.
В целом, мысль понятна - мы делаем работу вместо компьютера - сами говорим ему, сколько и куда сдвинуть вместо его вычислений.
Хотя, формулировка не совсем верна: операнд справа задаёт нам степень двойки, на которую произойдёт умножение/деление. Проще говоря, 12 >> 2 поделит 12 на 2^2, т.е. на 4 и даст 3. 8 << 1 умножит 8 на 2^1, т.е. на 2. И тут встал интересный вопрос: насколько это быстрее?

Сделаем тест. Тесты подобные вообще можно проводить только по какому-нибудь событию, когда флеш плеер уже полностью загрузился и сидит, скучает. Например я проводил тест по клику, код соответственно в обработчике клика:
Код AS3:
var i:int;
var timer:Number;
var a:Number;
 
timer = getTimer();
i = 10000000;
while (i--) {
	a = 2 * 2;
}
trace("a=a*2 time: " + (getTimer() - timer));
 
timer = getTimer();
i = 10000000;
while (i--) {
	a = 2 << 1;
}
trace("2<<1 time: " + (getTimer() - timer));
Код:
a=2*2 time: 645
a<<1 time: 650
А теперь внимание: важный момент. Скорости, полученные в результате тестов очень разные, в зависимости от версии плеера, в котором это дело просматривается (ну, или отчасти от версии, в котором это дело скомпилировано). В одном из своих постов в блоге я рассказал, в чем разница и почему Debug работает медленнее. Цифры которые были получены выше - Debug компиляция, Debug плеер. Забавно, что цифры почти равны, хотя запустив в Release версии плеера "пропорция" не сохранится: результаты ниже.
Все цифры ниже будут приведены в Release версии плеера.
Код AS3:
a * 2 time: 42
a << 1 time: 95
Ничего себе!
А как это выглядит в байткоде?
Вот нормальное умножение на 2:
Код:
getlocal1 
pushbyte 2
multiply 
convert_d 
setlocal1
Вот сдвиг:
Код:
getlocal1 
pushbyte 1
lshift 
convert_d 
setlocal1
Странно, ничего ненормального нету. Неужели сдвиги, которые должны работать никак не медленнее обычного умножения работают в 2 раза медленнее?
Но нет, тут дело в другом.
Давайте заменим var a:Number на var a:int и посмотрим результаты:
Код:
a * 2 time: 31
a << 1 time: 27
4 мс на таких итерациях ничто, так что будем считать что результаты одинаковые.

Вот вам и "быстрее".
Но не отчаивайтесь: флешплеер не тормозит в сдвигах; Флешплеер летает в умножении!
О чём я говорю? О том, что код был запущен в 10 версии FP, который шел в комплекте с Flash CS4. Давайте запустим его в 9 версии, идущим в комплекте с CS3:
Код:
a * 2 time: 110
a << 1 time: 29
Интересно, правда?
Это результат при компиляции в 10 флеш плеер и открытии в девятом.
Если скомпилируем в девятом и откроем в девятом:
Код:
a * 2 time: 639
a << 1 time: 24
А если скомпилированный в девятом откроем в десятом:
Код:
a * 2 time: 30
a << 1 time: 26
Вот вам налицо оптимизации с каждым флеш плеером, которое делает Adobe.
Тесты далее будут проводиться под 10 версию флеш плеера.

Собственно, увеличим число итераций ещё в 10 раз, до 100 миллионов и попробуем сделать обратное: будем делить.
Код AS3:
var a:Number;
...
a = 2 / 2;
...
a = 2 >> 1;
Код:
a=2/2 time: 341
2>>1 time: 293
Вот и польза от сдвигов. Однако же, когда нужно поделить на 2 всегда можно умножить на 0.5 и получить почти одинаковые результаты, поэтому в рамках 10 FP битовые сдвиги пока что явно не впереди; Получать значение как степень двойки, а потом делить... В реальном проекте я слабо представляю, где такое может получится, и вообще не представляю это дело в тяжелом алгоритме;
Но не тут то было. Когда умножаются два числа, хотя бы одно из которых нецелое, вполне вероятно, что мы тоже получим нецелое. И после умножения, если нам нужно число записать в переменную нужно его конвертировать в нужный тип; Если у нас получилось число нецелое, то есть Number - самое быстрое было бы записать его в Number, что очевидно. Вспомним: a ведь в этом тесте у нас Number! Да, в прошлом тесте мы меняли тип var a:Number на var a:int, и разницы в скорости между умножением и сдвигами не заметили. Но тут у нас не 2 целых значения, так что давайте посмотрим:
Код AS3:
var a:int;
...
a = (2 * 0.5);
...
a = (2 >> 1);
Код:
a * 0.5 time: 465
a >> 1 time: 288
Хо-хо-хо, вот мы и нашли основное применение: деление на 2^n, выигрыш очевиден.

Однако, всегда помните, что помимо 10 FP есть ещё и 9, в котором помимо выигрыша в делении есть ещё и гигантский выигрыш в умножении.
Всего комментариев 30

Комментарии

Старый 13.08.2010 12:05 Волгоградец вне форума
Волгоградец
 
Аватар для Волгоградец
Хорошая статья, молодец. Только для случая с int у меня такие результаты
Код AS3:
a /= 2 time: 957
a >>= 1 time: 424
Старый 13.08.2010 14:05 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Хм, забавно. Под какой плеер тестил?
Старый 13.08.2010 14:24 Волгоградец вне форума
Волгоградец
 
Аватар для Волгоградец
Не знаю - в CS4 который.
Я как-то давно этим интересовался - по этой статье тесты делал
http://www.gamedev.net/reference/art...rticle1563.asp
Результаты были впечатляющие.
Старый 13.08.2010 14:50 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Хм, а ты запускал тест по событию (а ля клик мыши) или сразу в конструкторе базового класса?
Старый 13.08.2010 14:58 Волгоградец вне форума
Волгоградец
 
Аватар для Волгоградец
Да в кадре прям в CS4.
Старый 13.08.2010 15:10 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Это не совсем правильно: код выполняется "холодным" с ещё "загружающимся" (не знаю как правильно сказать) флеш плеером. Тесты нужно проводить, например, по клику;
Старый 13.08.2010 15:11 alexcon314 вне форума
alexcon314
Оффтоп: сишные компиляторы привели бы эти операции (*, >>,/) к битовому сдвигу и результат будет одинаков (ну, плюс-минус ерунда).
Например, (n=8)
Цитата:
;r = n*2
mov ecx,dword ptr [n]
shl ecx,1
mov dword ptr [r],ecx
;r=n>>1
mov eax,dword ptr [n]
sar eax,1
mov dword ptr [r],eax
;r = n/2
mov eax,dword ptr [n]
cdq
sub eax,edx
sar eax,1
mov dword ptr [r],eax
Дело в том, что работа идет с числами, являющимися степенью двойки.
Впрочем, уножение, скажем на 7, тоже не даст видимого эффекта. А вот деление на 7 будет сильно дольше, но это не совсем то..
Старый 13.08.2010 15:15 Волгоградец вне форума
Волгоградец
 
Аватар для Волгоградец
Да, действительно, результаты разные получились. Теперь
Код AS3:
a /= 2 time: 99
a >>= 1 time: 33
Это при i = 10000000 - как у тебя. Не поленился с mxml скомпилировал - результаты как в статье.
Старый 13.08.2010 15:38 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Ничего себе! У Flash CS4 результаты по времени отличаются с результатами mxmlc в 8 раз!
Спасибо, как появится минутка пойду смотреть байткод - очень интересно, почему так.

alexcon, объясни почему на 7 умножение не даст эффекта? По идее, разница должна быть... Я не знаток Си.
Старый 13.08.2010 16:27 alexcon314 вне форума
alexcon314
Эффект будет, но не такой сильный как при делении, плохо выразился.
При умножении на 7 вставится инструкция imod, а не сдвиг. А imod медленне.
При делении на 7 вставится idiv, а он еще медленне.
Еще оффтоп: AS3 в нативный код
AS3
function (x:int):int {
return x+10
}

.abc
getlocal 1
pushint 10
add
returnvalue

x86
mov eax,(eap+8)
mov eax,(eax+4)
add eax,10
ret

зы. это я к тому, что действительно интересно - как плеер "транслирует" арифметику в машинные коды? Неужто он такой умный, что заменяет * и / на сдвиг, когда числа кратны 2? Слабо верится.
Обновил(-а) alexcon314 13.08.2010 в 16:53
Старый 13.08.2010 16:34 -De- вне форума
-De-
 
Аватар для -De-
А вот такой код даёт в релизе превосходство << над * более, чем в 10 раз.
Я тоже не знаю, что за фигня, если чо, и интересно.
Код AS3:
var my_txt:TextField = new TextField();
			var i:int;
			var timer:Number;
			var a:uint;
 
			my_txt.text = "";
			addChild(my_txt);
 
			timer = getTimer();
			a = 1;
			i = 10000000;
			while (i--) {
				a = (a * 2) + 1;
			}
			my_txt.appendText("res1 time: " + (getTimer() - timer) + " "+ a + "\n");
 
			timer = getTimer();
			a = 1;
			i = 10000000;
			while (i--) {
				a = (a << 1) + 1;
			}
			my_txt.appendText("res2 time: " + (getTimer() - timer) + " "+ a + "\n");
UPD: да, дело в конвертации типов. a = uint(a * 2) + 1; и скорости одинаковы. И это, если чо - у флэшевого таймера точность +- 10мс.
Обновил(-а) -De- 16.08.2010 в 13:45
Старый 13.08.2010 17:06 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Хах, получил интересные результаты, но их многовато для комментария к блогу.
Сделаю новую статью, как только одобрят - прочитаете, там уже интересно.

Посвящен он будет разнице между дебаг и релиз версии.
Старый 13.08.2010 18:17 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
-De-, спасибо, тоже интересно.
Я думаю дело опять таки в конвертации типов:
При сложении int и Number как раз int приводится к Number (иначе потеряем часть после запятой) - в итоге приводим один раз перед сложением с единицей, а второй раз приводим к int, для записи в переменную. Кроме этого, Number сам по себе работает медленнее чем int, это много раз доказывалось тестами: в итоге, помимо конвертации приходится оперировать более медленным типом;

По сути, примерно об этом я написал в статье; Может быть, всё это неправда, но на данный момент я придерживаюсь именно этого мнения.
Старый 13.08.2010 19:24 NoCD вне форума
NoCD
 
Аватар для NoCD
Скажите не просвещенному, для чего эти сдвиги нужны?
Старый 14.08.2010 13:10 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Это работа с битами.
Я вроде подробно описал про один из эффектов от сдвигов и какую пользу от него можно получить.
Старый 14.08.2010 16:55 i.o. вне форума
i.o.
 
Аватар для i.o.
Цитата:
Ничего себе! У Flash CS4 результаты по времени отличаются с результатами mxmlc в 8 раз!
Спасибо, как появится минутка пойду смотреть байткод - очень интересно, почему так.
Psycho Tiger, имей ввиду (если конечно ты не в курсе), что во Flash IDE плеер всегда debug версии. А то чем ты билдишь, влияет не так сильно.
Поэтому рекоммендую тебе все тесты писать во-первых не кадре, а в отдельном классе, потому что все переменные написаные в кадре станут переменными класса. А это влечет за собой весьма странные последствия по производительности.
А во-вторых - разница в скорости работы одного и того же теста во ФлэшПлеере RELEASE и DEBUG версии (версии именно плеера, а не SWF) иногда бывает огромной.
Таким образом результаты тестов придется выводить не в трэйс, а в текстовое поле, потому что RELEASE версия плеера не записывает трэйсы в логи.
А то что ты билдишь саму SWF в debug или release версию, то толку от этого, честно говоря, мало. Само сабой дебажная SWF будет медленнее, т.к там почти через каждую строчку стоит что-то вроде debugline. Debug версия SWF нужна только для разработки и поиска багов. В конечном то счете все равно будет release версия.
Так что рекоммендую зайти сюда - http://www.adobe.com/support/flashpl...oads.html#fp10 и взять прожекторы в debug и release версии и сравнить потом результаты своих тесты.
Обновил(-а) i.o. 14.08.2010 в 17:12
Старый 14.08.2010 17:26 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
i.o, где я написал хоть слово о том, что я пишу в кадре? Последствия преобразования переменных к полям класса весьма не странные, а вполне ожидаемые, кстати.

Да, спасибо за информацию: не знал что Release версия плеера бегает быстрее Debug`овской, сейчас поправлю статью. Но то что Flash IDE билдит флешку в релиз версию - бред.
Обновил(-а) Psycho Tiger 14.08.2010 в 17:30
Старый 14.08.2010 17:32 i.o. вне форума
i.o.
 
Аватар для i.o.
Цитата:
где я написал хоть слово о том, что я пишу в кадре
Пример в топике очень похож на то, что написан в кадре. Нигде нет упоминаний как именно это было.
Цитата:
Но то что Flash IDE билдит флешку в релиз версию - бред.
Где это я такое сказал?
Цитата:
В конечном то счете все равно будет release версия.
Если вот про это, то я имел ввиду "в конечном итоге от всей работы". Т.е вы создаете например приложение, пока не считаете что она работает как задумано и без багов - билдите в debug версию и ищете недочеты / ошибки / баги. Но в финале всей работы над проектом зачем в плавание пускать дебажную версию? Это типа, а вдруг я что-то забыл и мне потом скажут что за ошибка и на какой строке вывалилась? Так вообщето и RELEASE версия в дебажном плеере отлично показывает ошибки, только без номера строк. И еще RELEASE версию нельзя профайлить. А это разве нужно финальной версии проекта? Полагаю, что нет )
Обновил(-а) i.o. 14.08.2010 в 17:42
Старый 14.08.2010 17:42 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Тьфу, запечатался.
Я хотел сказать то что FlashIDE НЕ билдит флешку в релиз версию.

UPD: Тьфу на Вас, я совсем уже запечатался.
Flash IDE билдит флешку в релиз версию.
Обновил(-а) Psycho Tiger 14.08.2010 в 17:47
Старый 14.08.2010 17:47 i.o. вне форума
i.o.
 
Аватар для i.o.
Цитата:
FlashIDE НЕ билдит флешку в релиз версию / Flash IDE билдит флешку в релиз версию.
Ну здрасьте, а на что тогда влияет птичка Publish Settings -> Flash -> "Permit debugging" ? )
Как бы с ней получается дебажная SWF, а без нее как раз release SWF.

PS: плевать на меня не нужно)
Старый 14.08.2010 17:55 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Ах ты ж!
Сколько себя помню - только сейчас эту птичку увидел. Спасибо.
Старый 14.08.2010 17:59 i.o. вне форума
i.o.
 
Аватар для i.o.
Да не за что) Просто по двум статьям про производительнось сложилось впечатление, что ты не все ньюансы знал с debug / release в SWF и плеере.
Решил помочь устранить пробелы).

Ну и совет лично от меня - не думаю, что стоит рассматривать Debug версию именно SWF. Толку как бы мало, и понятно что она тормозная. Лучше Release SWF рассматривать в Debug и Release плеере.
Обновил(-а) i.o. 14.08.2010 в 18:02
Старый 14.08.2010 19:04 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Да, спасибо, я понял.
Я переправил статьи, просмотри их пожалуйста на предмет неточностей на этот раз.
Старый 14.08.2010 23:47 i.o. вне форума
i.o.
 
Аватар для i.o.
я тебе в личку ответ отправил
Старый 18.08.2010 23:12 dimarik вне форума
dimarik
 
Аватар для dimarik
Сделай сдвиги через "C" (Carry flag) - это то, чего не хватает языку.
Старый 18.08.2010 23:44 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
dimarik, не совсем понял о чем ты. Насколько я помню Carry flag это флаг "заёма", когда число не умещается в то число бит, в которое его хотят запихать - и вот этот флаг обозначает "заём" из несуществующего бита или по другому сказать, переполнения. Вроде в AS3 такого совсем нету, к чему было предложение сделать сдвиг через него? Или я не о том думаю?
Старый 19.08.2010 00:04 dimarik вне форума
dimarik
 
Аватар для dimarik
Все верно ты понял.
Старый 19.08.2010 00:09 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Хорошо, тогда к чему было
Цитата:
Сделай сдвиги через "C" (Carry flag)
?
Старый 19.08.2010 00:10 dimarik вне форума
dimarik
 
Аватар для dimarik
Найти решение аналогичное обычному ассемблеру. Это упущено в АS.

UPD. Эта фундаментальная фича нивелирована в AS.
Старый 08.06.2011 19:04 S-ed вне форума
S-ed
 
Аватар для S-ed
Простите если повторюсь:

http://lab.polygonal.de/2007/05/10/b...-integer-math/
http://www.calypso88.com/?cat=7

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

Перый код даст обратный результат при использовании int
Код AS3:
var i:int;
var timer:Number;
var a:int; //вместо Number
 
timer = getTimer();
i = 10000000;
while (i--) {
	a = 2 * 2;
}
trace("a=a*2 time: " + (getTimer() - timer));
 
timer = getTimer();
i = 10000000;
while (i--) {
	a = 2 << 1;
}
trace("2<<1 time: " + (getTimer() - timer));
 

 


Часовой пояс GMT +4, время: 16:23.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2019, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.