Битовые сдвиги vs умножение [UPD]
[UPDATE: статья почти полностью переписана, если Вам интересна эта тема рекомендую к повторному прочтению]
Нужно прочитать для понимания материала:
Битовые операции (Википедия)
На досуге провел несколько тестов, и вот результаты.
Википедия гласит:
Цитата:
Логические сдвиги влево и вправо используются для быстрого умножения и деления на 2, соответственно.
Хотя, формулировка не совсем верна: операнд справа задаёт нам степень двойки, на которую произойдёт умножение/деление. Проще говоря, 12 >> 2 поделит 12 на 2^2, т.е. на 4 и даст 3. 8 << 1 умножит 8 на 2^1, т.е. на 2. И тут встал интересный вопрос: насколько это быстрее?
Сделаем тест. Тесты подобные вообще можно проводить только по какому-нибудь событию, когда флеш плеер уже полностью загрузился и сидит, скучает. Например я проводил тест по клику, код соответственно в обработчике клика:
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
Все цифры ниже будут приведены в Release версии плеера.
Ничего себе!
А как это выглядит в байткоде?
Вот нормальное умножение на 2:
Код:
getlocal1 pushbyte 2 multiply convert_d setlocal1
Код:
getlocal1 pushbyte 1 lshift convert_d setlocal1
Но нет, тут дело в другом.
Давайте заменим var a:Number на var a:int и посмотрим результаты:
Код:
a * 2 time: 31 a << 1 time: 27
Вот вам и "быстрее".
Но не отчаивайтесь: флешплеер не тормозит в сдвигах; Флешплеер летает в умножении!
О чём я говорю? О том, что код был запущен в 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
Тесты далее будут проводиться под 10 версию флеш плеера.
Собственно, увеличим число итераций ещё в 10 раз, до 100 миллионов и попробуем сделать обратное: будем делить.
Код:
a=2/2 time: 341 2>>1 time: 293
Но не тут то было. Когда умножаются два числа, хотя бы одно из которых нецелое, вполне вероятно, что мы тоже получим нецелое. И после умножения, если нам нужно число записать в переменную нужно его конвертировать в нужный тип; Если у нас получилось число нецелое, то есть Number - самое быстрое было бы записать его в Number, что очевидно. Вспомним: a ведь в этом тесте у нас Number! Да, в прошлом тесте мы меняли тип var a:Number на var a:int, и разницы в скорости между умножением и сдвигами не заметили. Но тут у нас не 2 целых значения, так что давайте посмотрим:
Код:
a * 0.5 time: 465 a >> 1 time: 288
Однако, всегда помните, что помимо 10 FP есть ещё и 9, в котором помимо выигрыша в делении есть ещё и гигантский выигрыш в умножении.
Всего комментариев 30
Комментарии
13.08.2010 12:05 | |
13.08.2010 14:05 | |
Хм, забавно. Под какой плеер тестил?
|
13.08.2010 14:24 | |
Не знаю - в CS4 который.
Я как-то давно этим интересовался - по этой статье тесты делал http://www.gamedev.net/reference/art...rticle1563.asp Результаты были впечатляющие. |
13.08.2010 14:50 | |
Хм, а ты запускал тест по событию (а ля клик мыши) или сразу в конструкторе базового класса?
|
13.08.2010 14:58 | |
Да в кадре прям в CS4.
|
13.08.2010 15:10 | |
Это не совсем правильно: код выполняется "холодным" с ещё "загружающимся" (не знаю как правильно сказать) флеш плеером. Тесты нужно проводить, например, по клику;
|
13.08.2010 15:15 | |
13.08.2010 16:27 | |
Эффект будет, но не такой сильный как при делении, плохо выразился.
При умножении на 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 | |
А вот такой код даёт в релизе превосходство << над * более, чем в 10 раз.
Я тоже не знаю, что за фигня, если чо, и интересно. 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"); |
|
Обновил(-а) -De- 16.08.2010 в 13:45
|
13.08.2010 19:24 | |
Скажите не просвещенному, для чего эти сдвиги нужны?
|
14.08.2010 13:10 | |
Это работа с битами.
Я вроде подробно описал про один из эффектов от сдвигов и какую пользу от него можно получить. |
14.08.2010 16:55 | |
Цитата:
Ничего себе! У Flash CS4 результаты по времени отличаются с результатами mxmlc в 8 раз!
Спасибо, как появится минутка пойду смотреть байткод - очень интересно, почему так. Поэтому рекоммендую тебе все тесты писать во-первых не кадре, а в отдельном классе, потому что все переменные написаные в кадре станут переменными класса. А это влечет за собой весьма странные последствия по производительности. А во-вторых - разница в скорости работы одного и того же теста во ФлэшПлеере 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 | |
i.o, где я написал хоть слово о том, что я пишу в кадре? Последствия преобразования переменных к полям класса весьма не странные, а вполне ожидаемые, кстати.
Да, спасибо за информацию: не знал что Release версия плеера бегает быстрее Debug`овской, сейчас поправлю статью. Но то что Flash IDE билдит флешку в релиз версию - бред. |
|
Обновил(-а) Psycho Tiger 14.08.2010 в 17:30
|
14.08.2010 17:32 | |
Цитата:
где я написал хоть слово о том, что я пишу в кадре
Цитата:
Но то что Flash IDE билдит флешку в релиз версию - бред.
Цитата:
В конечном то счете все равно будет release версия.
|
|
Обновил(-а) i.o. 14.08.2010 в 17:42
|
14.08.2010 17:42 | |
Тьфу, запечатался.
Я хотел сказать то что FlashIDE НЕ билдит флешку в релиз версию. UPD: Тьфу на Вас, я совсем уже запечатался. Flash IDE билдит флешку в релиз версию. |
|
Обновил(-а) Psycho Tiger 14.08.2010 в 17:47
|
14.08.2010 17:55 | |
Ах ты ж!
Сколько себя помню - только сейчас эту птичку увидел. Спасибо. |
14.08.2010 17:59 | |
Да не за что) Просто по двум статьям про производительнось сложилось впечатление, что ты не все ньюансы знал с debug / release в SWF и плеере.
Решил помочь устранить пробелы). Ну и совет лично от меня - не думаю, что стоит рассматривать Debug версию именно SWF. Толку как бы мало, и понятно что она тормозная. Лучше Release SWF рассматривать в Debug и Release плеере. |
|
Обновил(-а) i.o. 14.08.2010 в 18:02
|
14.08.2010 19:04 | |
Да, спасибо, я понял.
Я переправил статьи, просмотри их пожалуйста на предмет неточностей на этот раз. |
14.08.2010 23:47 | |
я тебе в личку ответ отправил
|
18.08.2010 23:12 | |
Сделай сдвиги через "C" (Carry flag) - это то, чего не хватает языку.
|
19.08.2010 00:04 | |
Все верно ты понял.
|
19.08.2010 00:09 | |
Хорошо, тогда к чему было
Цитата:
Сделай сдвиги через "C" (Carry flag)
|
19.08.2010 00:10 | |
Найти решение аналогичное обычному ассемблеру. Это упущено в АS.
UPD. Эта фундаментальная фича нивелирована в AS. |
08.06.2011 19:04 | |
Простите если повторюсь:
http://lab.polygonal.de/2007/05/10/b...-integer-math/ http://www.calypso88.com/?cat=7 От себя хочу добавить, что такой метод оценки не учитывает неравномерную нагрузку на процессор. Его надо прокручивать около сотни раз, с интервалом в несколько минут. Перый код даст обратный результат при использовании int |
Последние записи от Psycho Tiger
- Тонкости и трюки ActionScript`а, которые... бесполезны (10.05.2011)
- Vkontakte: как пользоваться wall.post, нужен ли теперь wall.savePost? (05.03.2011)
- А пятый контер-страйк хорош. (19.01.2011)
- Пацаны, гоу Вконтакте? (21.12.2010)
- Давайте начистоту (18.12.2010)