2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Java и быстродействие
Сообщение11.01.2021, 14:24 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
StepV в сообщении #1500241 писал(а):
Или вы останавливали и запускали саму ява-машину, а процесс чувствовал это время останова через $nanoTime$?
Саму машину. Просто pkill -STOP java.

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


26/05/12
1534
приходит весна?
Судя по всему, чтобы посмотреть ассемблер, выдаваемый JIT-компилятором, придётся сначала скомпилировать всю JVM заново, внеся нужные изменения. :facepalm: Слишком много разбираться, бросаю пока это дело.

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


23/05/20
336
Беларусь
mihaild в сообщении #1500253 писал(а):
Саму машину. Просто pkill -STOP java.


Замечательно. Тогда вопрос снимается. Спасибо за информацию, все совершенствуется, скорректировал свои знания. в этой части.

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


26/05/12
1534
приходит весна?
StepV в сообщении #1500230 писал(а):
Поэтому замеры с помощью утилит, типа nanoTime, дают вроде бы согласованное время, но оно не учитывает времени, на которое были остановки виртуальной машины.
Выделенное жирным в ваших словах я не понял. Вы имели в виду, что временная дельта, полученное по разности двух вызовов System .nanoTime (), включает в себя только время затрачиваемое виртуальной машиной, но не время, тратящееся процессором на выполнение других задач (в том числе системных процессов)? Это утверждение не верно. Или же вы понимаете, что это просто разность двух моментов времени, между которыми процессор выполнял как JVM, так и другие задачи, и недовольны этим фактом?

StepV в сообщении #1500230 писал(а):
Поэтому при повышенной загрузке компьютера у вас будут совсем другие цифры задержек, т.к. системная часть времени обслуживания увеличивается.
Тут проблема гораздо глубже, чем вы себе представляете. Если система слишком загружена, и процесс с тестируемым на быстродействие алгоритмом часто прерывается для выполнения каких-либо других процессов (не важно, системных или же пользовательских), то тестируемый алгоритм получает задержки не только в связи временем выполнения прерывающих процессов, но так же задержки, связанные с необходимостью заново подгружать кэш памяти, используемой алгоритмом, так как эти области памяти будут вытеснены из кэша другими процессами. Поэтому подобная ситуация напрочь сломает все попытки оптимизировать использование алгоритмом кэша процессора.

Логично, что тестирование быстродействия надо производить на системе без других активных программ и с минимумом фоновых служб. Логично так же, использовать как минимум двухядерный процессор: одно ядро для системый нужд, другое — для исследуемого алгоритма, но процессор с как минимум двумя ядрами давно стал дэфолтным вариантом в ПК.

Разумеется, надо набирать временную статистику по-больше и критически отсеивать как завышенные времена работы, так и заниженные. Последнее, например, может случиться, если алгоритм выделяет и освобождает память, но на каком-то тестовом проходе свободной памяти JVM хватило, чтобы ни разу не вызывать сборщик мусора. Выделение/освобождение памяти в Java и работа сборщика мусора является частью алгоритма, хоть последнее и не присутствует явно в коде программы, поэтому это время мы просто обязаны учитывать при оценке временной сложности конкретного алгоритма.

Если вы внимательно присмотритесь к моей функции calculateStats ( ... ), то заметите, что там используется весьма изощрённый подход к расчёту среднего времени работы. Мне давно стоило его пояснить. Сначала функция сортирует собранную статистику в порядке возрастания. Это нужно для удобства отсеивания слишком малых и слишком больших времён работы, которые окажутся, соответственно, в начале и в конце массива с экспериментальными данными. Затем процедура берёт центральную ячейку массива, которая теперь содержит медиану набранной статистики и вычисляет границы отрезка с центром в этой медиане, на котором будет производится вычисление среднего и стандартного отклонения. Для левой (меньшей) границы берётся третье по счёту значение в отсортированном массиве, для правой — величина, не превышающая зеркально симметричное значение левой границы относительно центра. Надо заметить, что после проделанных "обрезаний" медиана является центром искомого отрезка по величине, но не по количеству экспериментальных величин: превышающих медиану величин как правило будет меньше, чем величин, меньших медианы. Этот подход ломается, если заниженных значений больше двух, но это случается очень редко (в простых алгоритмах без динамической работы с памятью — никогда); или если завышенных значений оказывается больше половины и сама медиана оказывается завышенной. В последнем случае надо задуматься над тем, чем же таким загружена система.

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


23/05/20
336
Беларусь
B@R5uk в сообщении #1500265 писал(а):
Вы имели в виду, что временная дельта, полученное по разности двух вызовов System .nanoTime (), включает в себя только время затрачиваемое виртуальной машиной, но не время, тратящееся процессором на выполнение других задач (в том числе системных процессов)? Это утверждение не верно.


Да. Вот это неверное утверждение я имел ввиду. Даже вам нашел подтверждение своих слов в интернете. Но вроде mihaild в сообщении https://dxdy.ru/post1500253.html#p1500253 разубедил меня в этом факте. Все совершенствуется. Как я понимаю, разработчики теперь сделали так, что при каждой установке VM на CP, ее регистры восстанавливаются по регистрам основной машины.

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


26/05/12
1534
приходит весна?
StepV, когда я искал чем замерять время работы программы я надеялся, что будет именно так, как вы думали, а не так как это на самом деле. К сожалению, временные функции предназначены немного для другого: для засекания точных абсолютных временных промежутков. Это нужно для вывода анимации, в динамических играх или в других интерактивных программах. А для замера быстродействия грамотнее будет использовать всевозможные профайлеры. Я, правда, пока такими средствами разработки не владею, хотя говорят, у джавы есть встроенный профайлер.

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


20/08/14
11070
Россия, Москва
mihaild в сообщении #1500136 писал(а):
Странно медленно, по идее код мог бы скомпилиться примерно в такой:
Используется синтаксис ASM
;                                                       Порты      Latency/Throughput
.next:          vmovdqa         ymm0,[RSI]              ;23     3/0.5   Чтение памяти
                vpand           ymm1,ymm0,ymm7          ;015    1/0.33  Выделение младшего бита
                vpcmpeqb        ymm1,ymm1,ymm6          ;01     1/0.5   Преобразование в маску байтов
                vpand           ymm1,ymm1,ymm0          ;015    1/0.33  Обнуление лишних байтов
                vpaddb          ymm5,ymm5,ymm1          ;015    1/0.33  Сложение нужных байтов с накопителем
                add     RSI,32                          ;0156   1/0.25
                sub     RCX,32                          ;0156   1/0.25
                jnz     .next                           ;06     1/0.5
Что для Вашего процессора даёт 2.2 такта на 32 итерации или примерно 15 итераций на такт. Вычисления происходят в портах 015, счётчик с указателем и переход используют порт 6. Почему не укладывается в 2 такта (или даже чуть меньше) мне не слишком понятно, похоже не хватает потока микрокоманд. Развернув цикл вдвое получается 20 итераций на такт, а разворот вчетверо даёт 23 итерации на такт, дальше разворачивать смысла нет.
Данные не реального прогона, а Intel® Architecture Code Analyzer.
Реальный прогон на Haswell i5-4690@3.7ГГц (в плане скорости на такт от вашего не отличается) даёт 17 итераций на такт без разворота, 21 итерацию на такт при развороте вдвое, 23 итерации на такт при развороте вчетверо (дальнейший разворот ускоряет в пределах одной итерации на такт). Данные читались исключительно из кэша L1, чтение реальной памяти не проверялось (лень, понятно что будем мерить её скорость, а не вычислений, см. далее).

У Вас же скорость падает до 4-5 итераций на такт видимо из-за одноканальной памяти, 2мс на 30МБ это 15ГБ/с или почти ровно половина от максимально возможных 34ГБ/с. Проверить это можно уменьшив объём до 3МБ (и возможно увеличив количество повторов) чтобы влезло в кэш.

-- 11.01.2021, 16:25 --

B@R5uk в сообщении #1500265 писал(а):
но так же задержки, связанные с необходимостью заново подгружать кэш памяти, используемой алгоритмом, так как эти области памяти будут вытеснены из кэша другими процессами.
Раньше я тоже этого боялся, но когда реально посчитал сколько это занимает времени, оказалось что это менее 0.1% (ну грубо 256КБ L2 загрузить из памяти 30ГБ/с это менее 10мкс, при тике переключения задач в 18мс или порядка 1/2000 или 0.05%). Так что не бойтесь перезагрузки кэшей при плановом переключении вычислительных задач (в других случаях может чаще переключаться контекст и потому там вопрос отдельный).

-- 11.01.2021, 16:37 --

Dmitriy40 в сообщении #1500280 писал(а):
по идее код мог бы скомпилиться примерно в такой:
Тут я конечно немного смухлевал, вместо второй vpand надо использовать vpblendvb, но она сильно медленнее (2/1 вместо 1/0.33), потому скорость ещё снизится. Зато можно будет сложение делать заранее и потом лишь отбирать нужный вариант в результат, правда на скорость это не влияет, влияет лишь на глубину просмотра планировщика в процессоре.

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


26/05/12
1534
приходит весна?
Dmitriy40, спасибо за объяснение!

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


16/07/14
8355
Цюрих
Dmitriy40 в сообщении #1500280 писал(а):
Проверить это можно уменьшив объём до 3МБ (и возможно увеличив количество повторов) чтобы влезло в кэш.
Правдоподобно, но, видимо, что-то еще влияет. На 3мб получается 10 итераций на такт, на 300кб - 15.
Ассемблерный код получается https://godbolt.org/z/G5jEjW. Цикл разворачивается в 8 раз, отличается от вашего невыровненными чтениями и вроде бы больше ничем важным.

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


20/08/14
11070
Россия, Москва
mihaild
Команды выровненного и невыровненного чтения сами по себе по скорости не отличаются (для наших и более современных процессоров), разница будет только если данные реально не выровнены.
Лишний переход вроде бы должен корректно предсказываться и на скорость заметно не влиять.
У меня разворот цикла с 4 до 8 раз меняет скорость с 22.6 до 23.1 итерации на такт, а это меньше погрешности моих измерений, потому я и округлял до целых.
Да, я тоже существенных отличий кода не вижу.
15 итераций на такт это уже правдоподобно, снова почему-то в полтора раза медленнее возможных ... Может всё же данные не выровнены и потому штраф независимо от уровня кэша? Но почему полтора вместо двух, это странно ... Или я не помню какой именно штраф за невыровненность данных. Тут моих познаний не хватает.

-- 11.01.2021, 17:29 --

Dmitriy40 в сообщении #1500280 писал(а):
Раньше я тоже этого боялся, но когда реально посчитал сколько это занимает времени, оказалось что это менее 0.1% (ну грубо 256КБ L2 загрузить из памяти 30ГБ/с это менее 10мкс, при тике переключения задач в 18мс или порядка 1/2000 или 0.05%).
На самом деле это несколько идеализированный случай, но даже в минимуме скорость подкачки кэша из памяти не будет падать ниже чем примерно 20нс (полное время цикла случайной выборки) на строку кэша 64 байта или 3ГБ/с или около 0.5% от времени вычислений. Считаю что и этим тоже можно смело пренебречь.

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


16/07/14
8355
Цюрих
На третий день Зоркий Глаз заметил, что в комнате не хватает стены, а CPU работает не на полной частоте. На 16кб получается как раз 21.4 циклов на такт, на 32кб - уже 17.4. На 1мб - 12.6, на 4мб (размер L3) - 6.2.
Выравнивание (ожидаемо при таких результатах) ни на что не влияет.

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


20/08/14
11070
Россия, Москва
На удивление у меня тоже время зависит от размера массива:
2КБ (L1): 22.2 итерации на такт;
20КБ (L1): 21.6 итерации на такт;
200КБ (L2): 16.6 итерации на такт;
2МБ (L3): 11.7 итерации на такт;
4МБ (L3): 11.0 итерации на такт;
20МБ (RAM): 4.9 итерации на такт или примерно 18ГБ/с (память 25ГБ/с).
Откуда такая зависимость мне непонятно, ведь все кэши должны успевать поставлять данные со скоростью как минимум 32 байта на такт (хотя бы L2 и L1), т.е. тормозить не должны. А выборка данных строго последовательная и должна процессором хорошо предсказываться.
Проверил добавку команды предвыборки prefetcht0 [RSI+1024] в развёрнутом вчетверо цикле, скорость чуточку подросла:
20КБ (L1): 20 итераций на такт — замедление!
200КБ (L2): 17.7 итераций на такт;
2МБ (L3): 13.8 итераций на такт;
20МБ (RAM): 4.9 итерации на такт или примерно 18ГБ/с (память 25ГБ/с).
Я проверял только выровненные данные.

mihaild
Кстати, в вашем процессоре нижние кэши больше (128К/512К/4М против 32К/256К/6М у меня). Так что 32К тоже попадает в L1 и подтормаживать от 16К вовсе не должно, как и 4М от 1М, у меня же 2КБ и 20КБ и 2М и 4М практически одинаковы.

В общем наверное можно тему ассемблера/С++ закрыть, с ними понятно всё, они на порядок-полтора быстрее Java. И С++ код компилится хороший, возможно даже достигающий пиковой производительности. А неясности остались уже в работе процессора, а не компилятора, что в этой теме скорее офтопик (хоть я сам его и начал).

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


26/05/12
1534
приходит весна?
Dmitriy40 в сообщении #1500325 писал(а):
А выборка данных строго последовательная и должна процессором хорошо предсказываться.

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

-- 11.01.2021, 20:54 --

Dmitriy40 в сообщении #1500325 писал(а):
с ними понятно всё, они на порядок-полтора быстрее Java
Это случай простого цикла суммирования где всё векторизуется, а если какой-нибудь алгоритм по-сложнее, какое у них преимущество будет?

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


16/07/14
8355
Цюрих
Dmitriy40 в сообщении #1500325 писал(а):
Кстати, в вашем процессоре нижние кэши больше (128К/512К/4М против 32К/256К/6М у меня)
У меня 32K/256K/4M.
B@R5uk в сообщении #1500349 писал(а):
А профайлером не пробовали?
Переходы предсказываются правильно (0.05% ошибок), что логично - условие остается только в завершении цикла. Промахов да, сильно больше - 23% на 4мб, 9% на 16кб.
B@R5uk в сообщении #1500349 писал(а):
Это случай простого цикла суммирования где всё векторизуется, а если какой-нибудь алгоритм по-сложнее, какое у них преимущество будет?
Сильно зависит от задачи и еще кучи условий. Если мы скажем в основном по деревьям бегаем - джава может и почти не отставать (а при плохой работе с памятью в плюсах - и выиграть). Если матрицы перемножаем - то будет такой же отрыв.

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

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



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

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


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

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