powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Java [игнор отключен] [закрыт для гостей] / Тормоза при использовании целочисленного деления в цикле: как обойти ?
13 сообщений из 13, страница 1 из 1
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38411035
ozzmosis
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Здравствуйте.

В цикле с большим числом итераций необходимо периодически выводить некоторую инфу (допустим, значение счетчика).
"Внезапно" обнаружилось, что при использовании деления или деления по модулю скорость работы падает в пять раз по сравнению с тем, как если бы использовались явные проверки по нескольким OR-условиям:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
class DivisionBenchMark {
  public static void main(String[] args) {
      long s0=System.currentTimeMillis();
      for(int i=0; i< 1000000000; i++) {
        if ( i % 200000000 == 0 ) { // ~25700 ms
        //if ( i/1 == 0 || i/1 == 200000000 || i/1 == 400000000 || i/1 == 600000000 || i/1 == 800000000  ) { // ~26200 ms
        //if ( i == 0 || i == 200000000 || i == 400000000 || i == 600000000 || i == 800000000  ) { // ~4800 ms
          System.out.println( "i="+i );
        }
      }
      System.out.println( "elapsed: "+( System.currentTimeMillis() - s0 ) );
  }
}

Вопрос, соб-сно, простой: как в java правильно делать такие вещи, но чтобы без тормозов ?
...
Рейтинг: 0 / 0
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38411049
cdtyjv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Во-первых, в тормозящем случае у вас, скажем так, универсальное решение, потому что оно является честным. В "нетормозящем" случае вы жульничаете, так как он у вас заточен под строго определенную ситуацию. Шаг вправо - шаг влево, и он уже не работает.
Во-вторых, написание честных бенчмарков - это очень сложная и нетривиальная задача, так как чем меньше ваша задача, тем больше на нее влияют скрытые факторы. Например, оптимизации компилятора.
В-третьих, есть такое понятие, как premature optimization. Это когда программист начинает пытаться "заоптимизировать" все, что нипопадя, не имея на то каких-либо веских оснований. Ваш случай именно таким и является. Операция % - это абсолютно нормальная и естественная операция. У нас в продукте, из которого мы пытаемся выжать все соки, мы его абсолютно спокойно ее используем, и ничего страшного в этом нет.

Так что не забивайте себе голову всякой ерундой.
...
Рейтинг: 0 / 0
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38411063
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ozzmosis,
оформите ваш бенчмарк в jmh , потом уже расскажите про тормоза в 5 раз. А так cdtyjv все верно отписал.
...
Рейтинг: 0 / 0
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38411065
avp.mk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
package divisionbenchmark;

import static java.lang.System.nanoTime;

public class DivisionBenchMark {

    public static void main(String[] args) {
        long timeStart = nanoTime();

        for (int i = 0, j = 0; i < 1_000_000_000; ++i, ++j) {
            if (j == 200_000_000) {
                j = 0;
                System.out.println("i = " + i);
            }
        }

        System.out.printf("Готово. (Время: %f сек.)\n", (nanoTime() - timeStart) / 1e9);
    }
}
...
Рейтинг: 0 / 0
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38411075
ozzmosis
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
just_vladimirоформите ваш бенчмарк в jmh , потом уже расскажите про тормоза в 5 раз. А так cdtyjv все верно отписал.avp.mk написал еще вернее, за что ему отдельное спасибо:-)
ЗЫ. Моцк у мну что-то совсем "того"... элементарно же всё было, мог бы и сам догадаться :(
...
Рейтинг: 0 / 0
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38411091
ivanra
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
ozzmosis,
а на 64-разрядной jvm проверяли тест с делением? Там должно быть быстрее
...
Рейтинг: 0 / 0
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38411260
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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 придётся включить
в факторы теста. А это путает карты.
...
Рейтинг: 0 / 0
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38411263
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ivanraozzmosis,
а на 64-разрядной jvm проверяли тест с делением? Там должно быть быстрее
В данном случае разрядность имеет отношение к модели памяти.
Будят просто снято ограничение на 1.5 - 1.8 Gb (для Win 32)
По производительности эффект может быть даже обратный.
...
Рейтинг: 0 / 0
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38411431
ivanra
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
mayton,
ну при чем в данном случае модель памяти, куча, прогрев?
Посмотрите на исходный код, приведенный автором - там вся работа на регистрах, не считая System.out.println. Самая тяжелая операция - целочисленное деление, и все остальные оптимизации JIT тут ничего существенно улучшить не смогут.
Так что на железе все сводится к делению 32 разрядных целых на 64 разрядном процессоре (угадайте, какие там регистры), работающем в long/legacy режимах. Как полагаете, в каком режиме будет быстрее?
...
Рейтинг: 0 / 0
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38411527
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ivanraи все остальные оптимизации JIT тут ничего существенно улучшить не смогут.
Еще раз. Специально для тех кто не услышал. Скорость исполнения Java кода в runtime
может плавать по независящим от алгоритма аспектам. А именно по решению когда
JVM перейдет от режима интерпретатора байткода к режиму исполнения native кода.

Поэтому любой бенчмарк java кода безсмысленен без перечисления опций запуска.

Так что на железе все сводится к делению 32 разрядных целых на 64 разрядном процессоре (угадайте, какие там регистры), работающем в long/legacy режимах. Как полагаете, в каком режиме будет быстрее?
Мы не знаем какие там регистры. Спецификация JVM не оговаривает никаких регистров.
Она работает только выполняя виртуальные операции над памятью и стеком текущего
потока.

Поэтому данный тезис наполнился бы большим смыслом если-бы мы сняли дамп памяти
ОС и увидели конкретный бинарный фрагмент кода (возм с интерпретацией в Ассемблере)
который соотвествует исходнику.

Как это сделать я не знаю поэтому предоставляю вам возможность придумать
или предложить свой вариант подтверждения тезисов.
...
Рейтинг: 0 / 0
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38412340
chabapok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это ж вам не z80, где время выполнения каждой команды документировано.
В сегодняшнем процессоре время выполнения отдельной команды тоже может зависить от большого количества факторов, максимум и минимум могут отличаться в разы.

А так можно взять плагин hsdis и посмотреть сгенерированый хотспотом код. Только по вышеобозначеной причине сравнить только по коду производительности двух почти идентичных фрагментов нереально. Этот код надо выполнить некоторое кол-во раз на реальных данных, и только тогда можно о чем-то судить. При этом еще и желательно, чтобы компиляция была на основе реальных данных.
...
Рейтинг: 0 / 0
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38412391
ivanra
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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.
public class DivisionBenchMark {
	interface ICheck {
		boolean check(int value);
	}
	static class CheckOr implements ICheck {
		public boolean check(int i) {
			return i == 0 || i == 200000000 || i == 400000000 || i == 600000000 || i == 800000000;
		}
	}
	static class CheckDiv implements ICheck {
		public boolean check(int i) {
			return i % 200000000 == 0;
		}
	}
	static class CheckCount implements ICheck {
		int count=0;
		public boolean check(int i) {
			count++;
			if (count==200000000) {
				count = 0;
				return true;
			}
			return false;
		}
	}
	private static long test(ICheck check, int count) {
		long s0=System.currentTimeMillis();
		for(int i=0; i< count; i++) {
			if (check.check(i)) {
				System.out.print('.');
			}
		}
		return System.currentTimeMillis()-s0;
	}

	static void test(ICheck check) {
		System.out.println( "method: "+check.getClass().getSimpleName());
		System.out.print("warm up: ");
		long total = 0;
		final int rounds = 7;
		final int warmup = 2;
		for (int i=0; i<rounds; i++) {
			if (i==warmup) {
				System.out.println();
				System.out.print("elapsed: ");
			}
			long elapsed = test(check,1000000000);
			System.out.print(elapsed+" ");
			if (i>=warmup)
				total = total+elapsed;
		}
		System.out.println("\n*** avg: "+total/(rounds-warmup)+"\n");
	}

	public static void main(String[] args) {
		System.out.println("java.vm.name: "+System.getProperty("java.vm.name"));
		System.out.println(ManagementFactory.getRuntimeMXBean().getInputArguments());
		System.out.println();
		test(new CheckOr());
		test(new CheckDiv());
		test(new CheckCount());
	}
}

Конечно, результирующий код стал немного сложнее, чем у автора, удельный вес деления уменьшился, но все равно видно влияние режима процессора на скорость работы. Плюс бонусом проверил оптимизацию на счетчике.
вот результаты работы на 3 разных jvm (компьютер один и тот же):
x86 client
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
java.vm.name: Java HotSpot(TM) Client VM
[-Dfile.encoding=UTF-8]

method: CheckOr
warm up: .....6119 .....5981 
elapsed: .....4964 .....4970 .....4981 .....4996 .....5011 
*** avg: 4984

method: CheckDiv
warm up: .....8958 .....8977 
elapsed: .....8987 .....8975 .....8960 .....8975 .....8990 
*** avg: 8977

method: CheckCount
warm up: .....6355 .....6307 
elapsed: .....6307 .....6324 .....6323 .....6308 .....6292 
*** avg: 6310
x86 server
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
java.vm.name: Java HotSpot(TM) Server VM
[-Dfile.encoding=UTF-8]

method: CheckOr
warm up: .....2013 .....1999 
elapsed: .....2013 .....1999 .....1999 .....2013 .....1999 
*** avg: 2004

method: CheckDiv
warm up: .....2794 .....2811 
elapsed: .....2842 .....2873 .....2857 .....2858 .....2856 
*** avg: 2857

method: CheckCount
warm up: .....3701 .....3668 
elapsed: .....3653 .....3668 .....3638 .....3886 .....3638 
*** avg: 3696
x64 jvm
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
java.vm.name: Java HotSpot(TM) 64-Bit Server VM
[-Dfile.encoding=UTF-8]

method: CheckOr
warm up: .....2029 .....2014 
elapsed: .....1998 .....2015 .....1983 .....1998 .....2014 
*** avg: 2001

method: CheckDiv
warm up: .....2326 .....2341 
elapsed: .....2030 .....2015 .....1998 .....2014 .....2014 
*** avg: 2014

method: CheckCount
warm up: .....4105 .....3981 
elapsed: .....3996 .....3996 .....4012 .....4012 .....4011 
*** avg: 4005

Впрочем, видно, что для данной постановки задачи различие быстродействия server x86-x64 такие крохи, что и задумываться не стоит
...
Рейтинг: 0 / 0
Тормоза при использовании целочисленного деления в цикле: как обойти ?
    #38413022
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Когда оптимизируют подобные методы, делают инлайнинг или убирают
накладные на call/virtual call.
...
Рейтинг: 0 / 0
13 сообщений из 13, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Тормоза при использовании целочисленного деления в цикле: как обойти ?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]