2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Java и быстродействие
Сообщение10.01.2021, 00:25 
Аватара пользователя


26/05/12
1534
приходит весна?
Вздумалось чего-то мне потестить, как в Java различные модификации кода влияют на быстродействие. Для начала написал такую вот тестирующую программку:

код: [ скачать ] [ спрятать ]
Используется синтаксис Java
import java.util.*;

public class Simple_Performance_Test_Function {
   
    private static final long seed = System .currentTimeMillis ();
    private static final Random rng = new Random (seed);
   
    private static final int size = 30000000;
    private static final byte [] values = new byte [size];
   
    private static final int iterNumber = 50;
    private static final double [] times1 = new double [iterNumber];
    private static final double [] times2 = new double [iterNumber];
   
    public static void main(String[] args) {
        int k, res1, res2;
        long startTime, stopTime;
        double time1, time2;
        double [] stats1, stats2;
       
        generateTest ();
       
        for (k = 0; iterNumber > k; ++k) {
            startTime = System .nanoTime ();
            res1 = simpleTest ();
            stopTime  = System .nanoTime ();
            time1 = 1e-6 * (stopTime - startTime);
           
            startTime = System .nanoTime ();
            res2 = functionTest ();
            stopTime  = System .nanoTime ();
            time2 = 1e-6 * (stopTime - startTime);
           
            times1 [k] = time1;
            times2 [k] = time2;
           
            System .out .println (String .format (Locale .UK, "%9.3f%9.3f%12d%12d", time1, time2, res1, res2));
        }
       
        stats1 = calculateStats (times1);
        stats2 = calculateStats (times2);
        System .out .println ();
        System .out .println (String .format (Locale .UK, "%9.3f%9.3f", stats1 [0], stats2 [0]));
        System .out .println (String .format (Locale .UK, "%9.3f%9.3f", stats1 [1], stats2 [1]));
    }
   
    private static void generateTest () {
        int k;
       
        for (k = 0; size > k; ++k) {
            values [k] = (byte) rng .nextInt (42);
        }
    }
   
    private static double [] calculateStats (double [] times) {
        int k, limit;
        double value, sum, sum2;
        double [] result;
       
        Arrays .sort (times);
        value = times [(iterNumber - 1) / 2];
        limit = Arrays .binarySearch (times, 2 * value - times [2]);
        if (0 > limit) {
            limit = -limit - 1;
        }
        sum = 0;
        sum2 = 0;
        for (k = 2; limit > k; ++k) {
            value = times [k];
            sum += value;
            sum2 += value * value;
        }
        limit -= 2;
        result = new double [2];
        result [0] = sum / limit;
        result [1] = Math .sqrt ((sum2 - sum * sum / limit) / (limit - 1));
       
        return result;
    }
   
    private static int simpleTest () {
        int k, result = 0;
       
        for (k = 0; size > k; ++k) {
            result += values [k];
        }
        return result;
    }
   
    private static int functionTest () {
        int k, result = 0;
       
        for (k = 0; size > k; ++k) {
            result += testFunction (k);
        }
        return result;
    }
   
    private static byte testFunction (int index) {
       
        return values [index];
    }
}
 

Объектом тестирования в ней являются функции simpleTest () и functionTest (). Каждая из них суммирует элементы заранее сгенерированного массива values случайных чисел. Разница лишь в том, что первая процедура суммирует значения сразу, а вторая для получения очередного значения из массива вызывает вложенную функцию testFunction (int index). Идея теста заключается в том, чтобы проверить как много времени требуется, чтобы организовать вызов функции.

К моему удивлению время работы функций simpleTest () и functionTest () оказалось одинаковым и равным
Код:
   14.739   14.666
    0.176    0.153

Видимо, JIT-компилятор сообразил, что вложенную функцию во втором цикле можно заинлайнить.

Дальше я сделал такую модификацию:
код: [ скачать ] [ спрятать ]
Используется синтаксис Java
    private static int simpleTest () {
        int k, result = 0;
       
        for (k = 0; size > k; ++k) {
            if (0 == (values [k] & 1)) {
                result += values [k];
            }
        }
        return result;
    }
   
    private static int functionTest () {
        int k, result = 0;
       
        for (k = 0; size > k; ++k) {
            result += testFunction (k);
        }
        return result;
    }
   
    private static byte testFunction (int index) {
       
        if (0 == (values [index] & 1)) {
            return values [index];
        }
        return 0;
    }
 

Добавилось условие на необходимость добавления очередной величины к результату. Время работы разумеется возросло, причём больше, чем я ожидал: проверка условия (по идее) делается порядка времени сложения, а сложение теперь происходит в среднем в два раза реже (так как величины в массиве values — случайные). Ожидаемый рост времени работы не более чем в полтора раза (ведь там же ещё есть обслуживание цикла и чтение массива). Время же выросло более чем в два раза, и процедура functionTest () оказалась хуже:
Код:
   36.488   40.319
    0.305    0.317


Поэкспериментировав я заметил, что если в первой функции simpleTest () равенство в условии заменить не неравенство: if (0 != (values [k] & 1)), то время работы стабильно вырастает на 2 миллисекунды и становится:
Код:
   38.392   39.974
    0.244    0.154

На время работы второй функции такая же замена почему-то не влияет. В любом случае, разница во времени работы не на столько велика, чтобы сделать заключение, что компилятор перестал инлайнить вложенную функцию второй процедуры. Однако сложение в ней однозначно производится на каждой итерации цикла. Компилятор не сообразил, что его можно не делать, когда условие выбора не выполняется.

Дальше я сделал такой апгрейд:
код: [ скачать ] [ спрятать ]
Используется синтаксис Java
    private static int simpleTest () {
        int k, result = 0;
        byte value;
       
        for (k = 0; size > k; ++k) {
            value = values [k];
            if (0 == (value & 1)) {
                result += value;
            }
        }
        return result;
    }
   
    private static int functionTest () {
        int k, result = 0;
       
        for (k = 0; size > k; ++k) {
            result += testFunction (k);
        }
        return result;
    }
   
    private static byte testFunction (int index) {
        byte value = values [index];
        if (0 == (value & 1)) {
            return value;
        }
        return 0;
    }
 

Его идея заключается в том, чтобы проверить, умеет ли компилятор замечать подряд идущие обращения к одному и тому же элементу массива. Оказалось, что не умеет: время выполнения резко упало. Это объясняет, почему во второй модификации при добавлении проверки время выполнения возросло. Однако! Для процедуры functionTest () время упало слишком резко! Она стала работать почти в два раза быстрее:
Код:
   31.675   21.743
    0.193    0.107

Вроде бы процедуры делают одно и то же, причём первая делает это чуть-чуть оптимальнее: она не всегда производит суммирование. Но нет! Практика показывает, что вторая процедура почти в полтора раза эффективнее.

В этих казалось бы элементарных тестах я получил совершенно невероятные на мой неискушённый взгляд результаты. В связи с этим, у меня естественным образом возникает вопрос: а почему происходит то, что происходит? Можно ли хоть как-то объяснить подобное поведение времени работы?

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 08:16 
Заслуженный участник


02/08/11
6874
Проверка условия, зависящего от случайного числа \(\Rightarrow\) предсказатель переходов в половине случаев ошибается \(\Rightarrow\) спекулятивное исполнение стопорится в среднем после каждого второго цикла.

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 16:53 
Аватара пользователя


26/05/12
1534
приходит весна?
warlock66613, спасибо за направление, в котором следует изучать вопрос! По запросу "предсказатель переходов" нашёл интересную статью на Хабре. Забавно, но краткий краш-курс по тому, что такое предсказатель переходов, внеочередное и спекулятивное исполнение нашёл во вступлении в статье об уязвимости "Spectre". Тем не менее, не могли бы вы по-развёрнутей объяснить, почему в третьем эксперименте вариант со вложенной функцией работает в полтора раза быстрее? И почему во втором эксперименте смена проверки равенства на неравенство ведёт к росту времени выполнения первой функции, но не ведёт у второй?

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 18:25 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
B@R5uk, а есть какая-то возможность посмотреть, какой в итоге ассемблер получается? Очевидная гипотеза - в каком-то варианте компилятор лучше генерирует SIMD инструкции.
Варианты с равенством/неравенством и вложенной функцией на C++ работают все одинаково, без условия вообще - на 15% быстрее.

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 18:41 
Заслуженный участник


09/05/12
25179
mihaild в сообщении #1500102 писал(а):
Очевидная гипотеза - в каком-то варианте компилятор лучше генерирует SIMD инструкции.
Вообще-то это Java, так что почти наверняка до процессорного кода дело просто не доходит, и результат определяется не реальной машинной архитектурой, а устройством виртуальной Java-машины.

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 19:09 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero

(Оффтоп)

B@R5uk в сообщении #1499994 писал(а):
в Java ... быстродействие

:mrgreen:

Простите, не сдержался.

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 19:20 
Заслуженный участник


09/05/12
25179
Хотя, возможно, аппаратные различия тоже сказываются. Интереса ради погонял ваши тесты на трех "железно" разных машинах с одной и той же версией Java. Результаты, соответствующие вашим 1-му, 2-му и 4-му (3-ю небольшую модификацию отдельно делать не стал) выглядят так.

Первая машина:
Код:
   10.201   10.149
    0.116    0.152

  107.264   21.669
    0.410    0.103

   22.474   17.430
    0.188    0.114

Вторая машина:
Код:
   12.285   11.890
    0.165    0.013

   99.140   23.910
    0.203    0.008

   25.583   19.095
    0.211    0.010

Третья машина:
Код:
   11.124   10.970
    0.091    0.031

   88.101   24.509
    0.137    0.017

   26.363   20.930
    0.059    0.020

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

-- 10.01.2021, 19:22 --

StaticZero в сообщении #1500112 писал(а):
Простите, не сдержался.
Ну сравнительное... хотя, конечно, при потребности в быстродействии это все гонки на черепахах. :-)

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 19:53 
Аватара пользователя


26/05/12
1534
приходит весна?
mihaild в сообщении #1500102 писал(а):
а есть какая-то возможность посмотреть, какой в итоге ассемблер получается?
Если и есть какая-то, то я слыхом не слыхивал. Если честно, я даже профайлером пользоваться не умею. Говорят на Java он есть встроенный.

Pphantom в сообщении #1500106 писал(а):
Вообще-то это Java, так что почти наверняка до процессорного кода дело просто не доходит
Это зависит от кода и того, как долго выполняется конкретный цикл. Я не знаю конкретные цифры, но после нескольких секунд в цикле, можно быть на 100% уверенным, что он сджитился. Более того, посмотрите на время: 15 мс в первом примере на 30 миллионов итераций. Мой процессор имеет частоту 3 ГГц, это означает, что на одну итерацию цикла в среднем уходит $15\cdot 10^{-3}\;\text{сек}\times 3\cdot 10^9\;\text{Гц}\;/\;30\cdot 10^6=1.5$ такта процессора. Это никак не может быть интепретируемым кодом. И, если честно, что-то слишком быстро эта Java работает... Вот, даже не знал на что жалуюсь.

Pphantom в сообщении #1500116 писал(а):
Интересно, что первый и второй процессоры - более близкие родственники, чем второй и третий.
Так самое главное здесь — это какие у них частоты. Они одинаковые?

-- 10.01.2021, 19:57 --

mihaild в сообщении #1500102 писал(а):
Варианты с равенством/неравенством и вложенной функцией на C++ работают все одинаково, без условия вообще - на 15% быстрее.
То есть компилятор оптимизирует код на столько, что во всех случаях итерации циклов выполняются за 1,5-2 такта процессора? Какое у вас получилось время и на процессоре какой частоты? Может я что-то не правильно считаю?

-- 10.01.2021, 20:03 --

Pphantom в сообщении #1500116 писал(а):
Интереса ради погонял ваши тесты на трех "железно" разных машинах
Только сейчас заметил, что во втором результате у вас стабильно время лучше. У меня — только в последнем тесте. Какие у вас процессоры? У меня: DualCore AMD Athlon 64 X2, 3000 MHz (15 x 200) 6000+. Версия JVM тоже, наверное, играет роль. У меня
Код:
C:\Users\Operator>java -version
java version "1.8.0_271"
Java(TM) SE Runtime Environment (build 1.8.0_271-b09)
Java HotSpot(TM) 64-Bit Server VM (build 25.271-b09, mixed mode)

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 20:16 
Аватара пользователя


23/05/20
336
Беларусь
B@R5uk в сообщении #1500121 писал(а):
Мой процессор имеет частоту 3 ГГц, это означает, что на одну итерацию цикла в среднем уходит $15\cdot 10^{-3}\;\text{сек}\times 3\cdot 10^9\;\text{Гц}\;/\;30\cdot 10^6=1.5$ такта процессора. Это никак не может быть интепретируемым кодом.



Из этого факта можно сделать простой, но близкий каждому физику вывод. У вас время квантуется, а вы этого не заметили, потому что программа выполнялась в "матрице".

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 20:26 
Заслуженный участник


09/05/12
25179
B@R5uk в сообщении #1500121 писал(а):
Так самое главное здесь — это какие у них частоты. Они одинаковые?
Нет.

Все три - AMD. Первый FX-6350 (3.9 GHz), второй FX-8120 (3.1 GHz) , третий Phenom II X6 1090T (3.2 GHz). От частот, как видите, зависимость по меньшей мере неочевидна.

Версия JVM, использовавшаяся во всех трех случаях:
Код:
$ java -version
openjdk version "11.0.9" 2020-10-20
OpenJDK Runtime Environment (build 11.0.9+11-suse-lp152.2.6.2-x8664)
OpenJDK 64-Bit Server VM (build 11.0.9+11-suse-lp152.2.6.2-x8664, mixed mode)


-- 10.01.2021, 20:31 --

B@R5uk в сообщении #1500121 писал(а):
DualCore AMD Athlon 64 X2, 3000 MHz (15 x 200) 6000+.
Такой, кстати, тоже есть под руками. Для него те же три результата
Код:
   12.455   12.433
    0.035    0.026

  108.665   28.923
    0.032    0.012

   31.060   24.326
    0.036    0.010

Версия JVM та же, что и в других моих случаях.

Вот тут, пожалуй, уже точно видно, что от JVM зависит куда больше, чем от процессора. :-)

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 20:38 
Аватара пользователя


26/05/12
1534
приходит весна?
Pphantom в сообщении #1500128 писал(а):
От частот, как видите, зависимость по меньшей мере неочевидна.
Ну почему же? В самом простейшем первом эксперименте везде выходит для всех машин одно и то же: порядка 1.3 такта на итерацию цикла в среднем в пределах погрешности. Параллелизм операций ещё лучше, чем у меня (если там вообще не одной инструкцией всё делается).

StepV, я, если честно, не понял вашего комментария. Это был какой-то упрёк? Можно тогда по-подробнее?

-- 10.01.2021, 20:40 --

Pphantom в сообщении #1500128 писал(а):
Вот тут, пожалуй, уже точно видно, что от JVM зависит куда больше, чем от процессора.
Пожалуй... :D А может дело в том, на сколько быстрая оперативка (во всяком случае, для первого теста). 30 миллионов байтов — это чуть меньше 29 МБ, явно в процессорный кэш не лезет.

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 21:17 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Pphantom в сообщении #1500106 писал(а):
Вообще-то это Java, так что почти наверняка до процессорного кода дело просто не доходит, и результат определяется не реальной машинной архитектурой, а устройством виртуальной Java-машины
Не вижу связи. JIT во многих машинах умеет в векторизацию.
B@R5uk в сообщении #1500121 писал(а):
Мой процессор имеет частоту 3 ГГц, это означает, что на одну итерацию цикла в среднем уходит $15\cdot 10^{-3}\;\text{сек}\times 3\cdot 10^9\;\text{Гц}\;/\;30\cdot 10^6=1.5$ такта процессора.
Зависит от архитектуры, но, вообще говоря, это очень медленно. На моем i7-6600U получается 4-5 итераций за такт.
B@R5uk в сообщении #1500121 писал(а):
Какое у вас получилось время и на процессоре какой частоты?
Код https://github.com/mihaild/dxdy/blob/ma ... l/main.cpp. Результаты
Код:
-------------------------------------------------------------------------------
Benchmark                                     Time             CPU   Iterations
-------------------------------------------------------------------------------
BM_test<with_all>/30000000_mean         1824488 ns      1817164 ns            5
BM_test<with_all>/30000000_median       1824990 ns      1819090 ns            5
BM_test<with_all>/30000000_stddev         16607 ns        14608 ns            5
BM_test<with_neq>/30000000_mean         2008712 ns      2001068 ns            5
BM_test<with_neq>/30000000_median       2007173 ns      2000837 ns            5
BM_test<with_neq>/30000000_stddev         37414 ns        34785 ns            5
BM_test<with_eq>/30000000_mean          1943092 ns      1936122 ns            5
BM_test<with_eq>/30000000_median        1939502 ns      1933531 ns            5
BM_test<with_eq>/30000000_stddev          36582 ns        33718 ns            5
BM_test<with_nested>/30000000_mean      1943595 ns      1937270 ns            5
BM_test<with_nested>/30000000_median    1947702 ns      1939957 ns            5
BM_test<with_nested>/30000000_stddev      26719 ns        25643 ns            5

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 21:20 
Аватара пользователя


23/05/20
336
Беларусь
B@R5uk в сообщении #1500129 писал(а):
я, если честно, не понял вашего комментария. Это был какой-то упрёк? Можно тогда по-подробнее?


Нет. Это был прямой намек, что данные теста не совсем правильно вами воспринимаются. Основное архитектурное решение для ява-машины: все программы испольняются внутри нее, т.е в адресах VM, результаты работы процессора иммитируются для программ. Т.е если для реально работающей OS время выполнения куска вашей программы составило 10 мс, то вы, считав регистры виртуального процессора, делаете вывод, что уложились, к примеру, в 100 микросекунд.
Поэтому выводы об ускорении той или иной конфигурации кода в яве делать можно, но, так сказать, в условных цифрах.
Дополнение. Скажем в тех значениях времени, которые вы считываете с виртуальных регистров, только не надо считать, что это реальные мс или мкс.

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 21:28 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Да, для сравнения, первый тест из стартового топика на моем CPU -
Код:
   10.785   10.479
    0.185    0.180

Т.е. пошустрее, но как-то совсем печально по сравнению с плюсами.

Как
StepV в сообщении #1500138 писал(а):
Т.е если для реально работающей OS время выполнения куска вашей программы составило 10 мс, то вы, считав регистры виртуального процессора, делаете вывод, что уложились, к примеру, в 100 микросекунд
следует из
StepV в сообщении #1500138 писал(а):
все программы испольняются внутри нее, т.е в адресах VM
?
System.nanoTime возвращает время в наносекундах, прошедшее с какой-то фиксированной временной точки. Разность при двух вызовах, соответственно, равна времени в наносекундах между этими вызовами. Как это связано с JVM - непонятно.

 Профиль  
                  
 
 Re: Java и быстродействие
Сообщение10.01.2021, 21:30 
Заслуженный участник


09/05/12
25179
mihaild в сообщении #1500136 писал(а):
Не вижу связи. JIT во многих машинах умеет в векторизацию.
Аналогично. :-) Да, умеет, но как это будет организовано (и даже будет ли), зависит от JVM. Это все-таки не совсем прозрачная "прослойка" между программой и процессором.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 44 ]  На страницу 1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group