|
|
|
Тормоза при использовании целочисленного деления в цикле: как обойти ?
|
|||
|---|---|---|---|
|
#18+
Здравствуйте. В цикле с большим числом итераций необходимо периодически выводить некоторую инфу (допустим, значение счетчика). "Внезапно" обнаружилось, что при использовании деления или деления по модулю скорость работы падает в пять раз по сравнению с тем, как если бы использовались явные проверки по нескольким OR-условиям: Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. Вопрос, соб-сно, простой: как в java правильно делать такие вещи, но чтобы без тормозов ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2013, 14:39:20 |
|
||
|
Тормоза при использовании целочисленного деления в цикле: как обойти ?
|
|||
|---|---|---|---|
|
#18+
Во-первых, в тормозящем случае у вас, скажем так, универсальное решение, потому что оно является честным. В "нетормозящем" случае вы жульничаете, так как он у вас заточен под строго определенную ситуацию. Шаг вправо - шаг влево, и он уже не работает. Во-вторых, написание честных бенчмарков - это очень сложная и нетривиальная задача, так как чем меньше ваша задача, тем больше на нее влияют скрытые факторы. Например, оптимизации компилятора. В-третьих, есть такое понятие, как premature optimization. Это когда программист начинает пытаться "заоптимизировать" все, что нипопадя, не имея на то каких-либо веских оснований. Ваш случай именно таким и является. Операция % - это абсолютно нормальная и естественная операция. У нас в продукте, из которого мы пытаемся выжать все соки, мы его абсолютно спокойно ее используем, и ничего страшного в этом нет. Так что не забивайте себе голову всякой ерундой. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2013, 14:56:05 |
|
||
|
Тормоза при использовании целочисленного деления в цикле: как обойти ?
|
|||
|---|---|---|---|
|
#18+
ozzmosis, оформите ваш бенчмарк в jmh , потом уже расскажите про тормоза в 5 раз. А так cdtyjv все верно отписал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2013, 15:25:03 |
|
||
|
Тормоза при использовании целочисленного деления в цикле: как обойти ?
|
|||
|---|---|---|---|
|
#18+
Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2013, 15:33:29 |
|
||
|
Тормоза при использовании целочисленного деления в цикле: как обойти ?
|
|||
|---|---|---|---|
|
#18+
just_vladimirоформите ваш бенчмарк в jmh , потом уже расскажите про тормоза в 5 раз. А так cdtyjv все верно отписал.avp.mk написал еще вернее, за что ему отдельное спасибо:-) ЗЫ. Моцк у мну что-то совсем "того"... элементарно же всё было, мог бы и сам догадаться :( ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2013, 15:48:56 |
|
||
|
Тормоза при использовании целочисленного деления в цикле: как обойти ?
|
|||
|---|---|---|---|
|
#18+
ozzmosis, а на 64-разрядной jvm проверяли тест с делением? Там должно быть быстрее ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2013, 16:19:32 |
|
||
|
Тормоза при использовании целочисленного деления в цикле: как обойти ?
|
|||
|---|---|---|---|
|
#18+
cdtyjvВо-вторых, написание честных бенчмарков - это очень сложная и нетривиальная задача, так как чем меньше ваша задача, тем больше на нее влияют скрытые факторы. Например, оптимизации компилятора. В-третьих, есть такое понятие, как premature optimization. Это когда программист начинает пытаться "заоптимизировать" все, что нипопадя, не имея на то каких-либо веских оснований. Ваш случай именно таким и является. Операция % - это абсолютно нормальная и естественная операция. У нас в продукте, из которого мы пытаемся выжать все соки, мы его абсолютно спокойно ее используем, и ничего страшного в этом нет. Я согласен. Еще добавлю несколько моментов. 1) Все любители погонять бенчмарки на Java допускают системные ошибки, касающиеся выбора модели JIT-компилляции. К примеру не учитывают факт зависимости от -client -server и -XX:CompileThreshold e.t.c. Неучёт прочих побочных эффектов "прогревания" кешей процессоров, дисков, софтверных кешей файловой системы. Неучёт "шума" и прочих влияний мультизадачной современной ОС и другое. 2) Операция % - вычисление остатка от деления является принципиально несократимой неоптимизируемой операцией. Более того, на ее свойствах основана вся современная криптография. Таймаут или некоторая вычислительная сложность которая в ней зашита стоит как бастион на пути любых методов криптоанализа. Операция % - это та самая серебрянная пуля которая позволяет нам, офисным хомякам и прочим креведам вставить шило в задницу АНБ/ФСБ с ее Призмами и Эшелонами и всё еще создать проблемы на пути к глобализации. 3) В некоторых случаях для некоторых однородных видов расчёта можно использовать мемоизацию или использование заранее расчитанных значений любой детерминистической функции (%). В старой DOS-овской игре DOOM/DOOM2 к примеру такая техника применялась для расчёта тригонометрии (синусы и косинусы хранились в целочисленных таблицах с некоторой интерполяцией). 4) Для делителя кратного степени двойки можно упростить остаток от деления % до булевых операций AND и OR на операндами. Эти операции обычно на порядки быстрее деления или умножения. И последнее. Данный тест безсмысленен по своей постановке. Непонятно ГДЕ подобное можно применять. Ну если-бы я применял то заметил-бы что код неоптимизирован. На выходе предиката i % 200000000 == 0 мы получаем строго периодическую последовательность FALSE с периодом 200000000. На этом можно сыграть если ввести второй счётчик. И операця System.out.println по степени нагрузки на систему в 10-100 кратно превышает оперецию деления по времени блокирования текущий поток (особенно когда скроллируется экран или замедляется диск при использовании перенаправления STDOUT в файл). Для данного периода в 200 млн она не имеет значения но на уменьшении периода такой пустяк как I/O придётся включить в факторы теста. А это путает карты. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2013, 23:07:51 |
|
||
|
Тормоза при использовании целочисленного деления в цикле: как обойти ?
|
|||
|---|---|---|---|
|
#18+
ivanraozzmosis, а на 64-разрядной jvm проверяли тест с делением? Там должно быть быстрее В данном случае разрядность имеет отношение к модели памяти. Будят просто снято ограничение на 1.5 - 1.8 Gb (для Win 32) По производительности эффект может быть даже обратный. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2013, 23:10:56 |
|
||
|
Тормоза при использовании целочисленного деления в цикле: как обойти ?
|
|||
|---|---|---|---|
|
#18+
mayton, ну при чем в данном случае модель памяти, куча, прогрев? Посмотрите на исходный код, приведенный автором - там вся работа на регистрах, не считая System.out.println. Самая тяжелая операция - целочисленное деление, и все остальные оптимизации JIT тут ничего существенно улучшить не смогут. Так что на железе все сводится к делению 32 разрядных целых на 64 разрядном процессоре (угадайте, какие там регистры), работающем в long/legacy режимах. Как полагаете, в каком режиме будет быстрее? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.09.2013, 10:12:38 |
|
||
|
Тормоза при использовании целочисленного деления в цикле: как обойти ?
|
|||
|---|---|---|---|
|
#18+
ivanraи все остальные оптимизации JIT тут ничего существенно улучшить не смогут. Еще раз. Специально для тех кто не услышал. Скорость исполнения Java кода в runtime может плавать по независящим от алгоритма аспектам. А именно по решению когда JVM перейдет от режима интерпретатора байткода к режиму исполнения native кода. Поэтому любой бенчмарк java кода безсмысленен без перечисления опций запуска. Так что на железе все сводится к делению 32 разрядных целых на 64 разрядном процессоре (угадайте, какие там регистры), работающем в long/legacy режимах. Как полагаете, в каком режиме будет быстрее? Мы не знаем какие там регистры. Спецификация JVM не оговаривает никаких регистров. Она работает только выполняя виртуальные операции над памятью и стеком текущего потока. Поэтому данный тезис наполнился бы большим смыслом если-бы мы сняли дамп памяти ОС и увидели конкретный бинарный фрагмент кода (возм с интерпретацией в Ассемблере) который соотвествует исходнику. Как это сделать я не знаю поэтому предоставляю вам возможность придумать или предложить свой вариант подтверждения тезисов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.09.2013, 11:27:14 |
|
||
|
Тормоза при использовании целочисленного деления в цикле: как обойти ?
|
|||
|---|---|---|---|
|
#18+
Это ж вам не z80, где время выполнения каждой команды документировано. В сегодняшнем процессоре время выполнения отдельной команды тоже может зависить от большого количества факторов, максимум и минимум могут отличаться в разы. А так можно взять плагин hsdis и посмотреть сгенерированый хотспотом код. Только по вышеобозначеной причине сравнить только по коду производительности двух почти идентичных фрагментов нереально. Этот код надо выполнить некоторое кол-во раз на реальных данных, и только тогда можно о чем-то судить. При этом еще и желательно, чтобы компиляция была на основе реальных данных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.09.2013, 20:51:36 |
|
||
|
Тормоза при использовании целочисленного деления в цикле: как обойти ?
|
|||
|---|---|---|---|
|
#18+
mayton, скорость выполнения зависит много от чего, даже от окружающей температуры, кто ж спорит. Но почему мы должны игнорировать режим работы процессора - мне непонятно. При массовых вычислениях очень даже может влиять. Я тут немного модифицировал первоначальный тест DivisionBenchMark.java Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. вот результаты работы на 3 разных jvm (компьютер один и тот же): x86 client Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. x86 server Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. x64 jvm Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. Впрочем, видно, что для данной постановки задачи различие быстродействия server x86-x64 такие крохи, что и задумываться не стоит ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.09.2013, 22:14:56 |
|
||
|
|

start [/forum/topic.php?fid=59&msg=38411075&tid=2128504]: |
0ms |
get settings: |
19ms |
get forum list: |
18ms |
check forum access: |
6ms |
check topic access: |
6ms |
track hit: |
357ms |
get topic data: |
19ms |
get forum data: |
5ms |
get page messages: |
82ms |
get tp. blocked users: |
2ms |
| others: | 311ms |
| total: | 825ms |

| 0 / 0 |
