Всем привет! В процессе учебы заинтересовался Android разработкой, в рамках одного из заданий необходимо провести исследование. Выбрал тему, которая давно разжигает мое любопытство, а именно производительность кода на Kotlin в сравнении с С++.
Поиск в русскоязычном интернете не дал почти ничего, всё, так или иначе сводится к перемешиванию, примитивных типов в цикле – пузырьковая сортировка и другие классические алгоритмы. В целом такие эксперименты приводят к выводу о том, что использование JNI имеет слишком высокую стоимость и Java работает быстрее.
Поиск среди научных и студенческих работ на просторах англоязычного интернета дал несколько интересных статей [1], [2],[3],[4] – обработка изображений, доступ к базе данных, быстрое преобразование Фурье и т.п. Однако в большинстве работ речь идет о устройствах с ОС Android 2.0 – 7.0.
В руководствах от Google тоже не удалось найти конкретных условий, когда нужно использовать NDK, сухое
Squeeze extra performance out of a device to achieve low latency or run
computationally intensive applications, such as games or physics simulations.Reuse your own or other developers' C or C++ libraries.
«используйте NDK, если хотите выжать максимум производительности или использовать старые библиотеки» как-то не дает четкого понимания вопроса.
В общем, было принято решение провести свой и эксперимент с blackjack и NDK.
Особенности выполнения программ
На тему устройства Android на хабре есть замечательная статья, я не претендую на истину так я джунский джун и вообще программирование всегда для меня было хобби, а более серьезно заняться я решил уже во взрослом возрасте, и так спешить все равно некуда, начал я с получения образования,но все же вкратце изложу как я понял вопрос.
Виртуальная машина – транслирует байткод java в инструкции для выполнения процессором.
В операционной системе Android до версии 5.0 использовалась виртуальная машина Dalvik, компиляция байт-кода происходила динамически во время выполнения программы (Just In Time компиляция- JIT). Dalvik был специально разработан с учетом ограниченных возможностей аппаратуры.
С выходом Android 5.0 в 2014 году, Dalvik был заменен Android Runtime (ART) – виртуальной машиной с повышенной производительностью [3]. В ART используются Ahead of Time (AOT) компиляция - приложение компилируется под конкретное устройство во время установки или в период бездействия устройства (например, когда телефон стоит на зарядке). В Android 7.0 в ART был добавлен JIT компилятор с профилированием кода, что позволило находить «узкие» места в программах и оптимизировать их выполнение.
Виртуальные машины Dalvik и ART реализованы как низкоуровневые приложения на C/C++, скомпилированные для целевой платформы.
Выполнение С++ программ
Java Native Interface (JNI) - программный интерфейс, позволяющий Java-коду, который выполняется внутри виртуальной машины Java (VM), взаимодействовать с приложениями и библиотеками, написанными на других языках программирования, таких как C, C++ . С помощью JNI можно вызывать функции на C/C++ из Java,как обычные Java-методы, передавая примитивы или объекты Java в параметрах и получая в виде возвращаемых значений. Для запуска нативного кода, Android предоставляет NativeDevelopment Kit (NDK).
Выбор алгоритма
Вооружившись знаниями про Dalvik и ART машины, JIT и Ahead of Time компиляцию, дело осталось за малым – проверить всё на реальных устройствах.
При выборе алгоритма для эксперимента я руководствовался простыми критериями:
Алгоритм должен выполняться долго – чем дольше, тем лучше, отлавливать разницу в микросекундах, когда погрешность измерения превышает время работы алгоритма, такое себе решение.
Вычисления должны выполняться процессором, без явного использования пиксельных шейдеров и графического ускорителя.
Алгоритм не должен использовать запись на диск или обращение к базе данных, так как на время работы такого алгоритма может повлиять большое число непредсказуемых факторов: работа других приложений, уровень заряда батареи, наличие свободного места на диске, фрагментация файлов базы данных etc.
В процессе выполнения алгоритма должны быть использованы пользовательские типы данных. Использование классических алгоритмов с примитивными типами (сортировка массива чисел и т.п.) может дать неожиданные результаты, так как такие алгоритмы могут быть изменены до неузнаваемости современными компиляторами в процессе компиляции.
По поводу пункта 4 необходимо добавить – моей идеей было проверить, как реально поведет себя Java машина с объектами. Java машина создает объекты на «куче» (heap) и освобождает память с помощью сборщика мусора. Что будет, если у меня нет необходимости в сортировке массива Int, а нужно обрабатывать классы, да еще и производить вычисления с плавающей точкой.
В поисках подходящего алгоритма, вспомнилось множество Мандельброта и симпатичный фрактал, в свое время писал лабораторные по OpenGL – помню, что вычисление фракталов на процессоре довольно сильно нагружало ПК, значит на мобильном телефоне точно должно отнять некоторое время. Да и комплексные числа никак уж нельзя отнести к примитивным типам данных.
Реализация приложения
Во время разработки приложения я, по мере моих сил, старался следовать рекомендациям Google:
простой интерфейс на JetPack Compose
ViewModel и StateHoder – для того чтобы смена конфигурации (поворот экрана) не становился помехой
вычисления запускаются в отдельном потоке с помощью withContext(Dispatchers.Default), так как в главной потоке работает интерфейс пользователя и запускать в нем «тяжелые» процессы нельзя
минимизирован обмен данными между JNI и JVM – никаких вызовов JNI методов в цикле, готовим все данные в С++, копируем их как массив одним вызовом JNI , дальше собираем то, что нам нужно на стороне JVM из массива
Для вычисления множества необходимо реализовать возможность производить вычисления с комплексными числами: сложение, возведение в квадрат и вычисление квадрата модуля. Для этих целей был реализован класс Complex, класс содержит: перегрузку оператора сложения,метод square - возвращает квадрат комплексного числа,метод sqr_abs – возвращает квадрат модуля комплексного числа.
Сами вычисления проиходят в методе calc класса Mandelbrot
Mandelbrot::Mandelbrot()
{
// подготовить vector так как зранее неизвестно количество точек для закрашивания
points.reserve(300000);
}
std::pair<size_t,double*> Mandelbrot::calc(const double start_x,const double end_x,const double start_y,const double end_y,unsigned int max_iter){
points.clear();
// рассчет шага
const int HD_WIDTH=1920;
const int HD_HEIGHT=1280;
double step_x=(end_x-start_x)/HD_WIDTH;
double step_y=(end_y-start_y)/HD_HEIGHT;
int iterNumb=0;
// пройти все точки с нужным шагом
for (double x=start_x;x<=end_x;x+=step_x){
for (double y=start_y;y<=end_y;y+=step_y){
Complex cn; // new complex 0
unsigned int i=0;
while (i<max_iter && sqr_abs(cn)<=4){
cn=square(cn)+Complex(x,y);
++i;
++iterNumb;
}
if (sqr_abs(cn)<=4){
points.push_back(x);
points.push_back(y);
}
}
}
__android_log_print(ANDROID_LOG_VERBOSE, "Native VS Kotlin","Iteration number %d",iterNumb);
return std::make_pair(points.size(),points.data());
}Для каждой точки (из 1920х1280) будет запущен цикл, ограниченный max_iter=200 итераций, если по окончании итераций окажется,что точка принадлежит множеству - ее координаты отправятся в вектор.
Я не старался максимально оптимизировать код, больше внимания уделял тому, чтобы реализация на Kotlin минимально отличалась от реализации на С++.
class Mandelbrot {
// подготовить vector так как зранее неизвестно количество точек для закрашивания
private var points: ArrayList<Double> = ArrayList(300000);
fun calc(
startX : Double,
endX : Double,
startY : Double,
endY : Double,
maxIter : Int
):List<Double>{
points.clear()
var iterNumb:Int=0; //total iterations
val stepX:Double
val stepY:Double
stepX= (endX-startX)/HD_WIDTH
stepY=(endY-startY)/HD_HEIGHT
// пройти все точки с нужным шагом
var x=startX
while(x<=endX){
var y=startY
while (y<=endY){
var cn=Complex() //New complex 0
var i:Int=0
while (i<maxIter && sqrAbs(cn)<4){
cn = square(cn)+Complex(x,y)
++i
++iterNumb
}
if (sqrAbs(cn)<=4){
points.add(x);
points.add(y);
}
y+=stepY
}
x+=stepX
}
Log.d("Native VS Kotlin","Kotlin iterations number =$iterNumb")
//return Pair(points.size,points)
return points
}Алгоритм на С++, после вычисления всех точек, хранит их векторе С++, Java машина не может работать с ним напрямую. Существуют способы создать объект Java прямо из нативного кода, то есть возможно в процессе итераций добавлять данные напрямую в массив Java, однако вызов любого метода JNI имеет высокую стоимость. Вызов в цикле методов JNI для каждой точки перечеркнул бы весь смысл использования нативного кода. Поэтому, после того как выполнение алгоритма окончено, будет выполнен вызов функций JNI
NewDoubleArray - создает примитивный массив Java
SetDoubleArrayRegion – копирует в массив участок памяти заданной длины. Стандарт С++ гарантирует, что данные в векторе хранятся последовательно, что дает возможность копировать их из памяти напрямую.
Таким образом, после выполнения нативного кода, Java машина получит массив Double, его преобразование к ArrayList с помощью asList() занимает минимальное (константное) время.
PNG файлы как результат вычислений
После того как данные готовы, пользователю станет доступна кнопка «Создать PNG» , после ее нажатия будет вызвана функция buildPNG (файл png.kt)
Данная функция генерирует изображения «построчно» с помощью библиотеки pngj, все точки множества будут закрашены синим цветом, остальные – белым. Готовые изображения будут сохранены на диск и отображены на экране.
Функция играет вспомогательную роль, изображения формируются для наглядного сравнения полученных множеств, поэтому время выполнения функции не учитывается.
Результаты тестов
Для измерения времени выполнения алгоритма были использованы четыре устройства.
HUAWEI Y6 2019 – ОС Android 9.0 , процессор MT6761, 2000 MHz
Realme C15 – ОС Android 11, процессор Mediatek MT6765G Helio G35, 2300 Mhz
Meizu Note 8 M822H – ОС Android 8.1, процессор Qualcomm Snapdragon 632, 1800 MHz
Realme 10 – ОС Android 13, процессор MediaTek Helio G99 2200MHz (556) 15c 1820мс
Все устройства были полностью заряжены.
Для каждого устройства были выполнены "прогревочные" запуски
Для каждого устройства было выполнено десять запусков отдельно каждого алгоритма в режиме полета и еще десять в обычном режиме
На данном этапе стало очевидно, что скорость выполнения Kotlin и С++ отличается.
Устройство | GeekBench | Kotlin, мс | C++, мс |
HUAWEI Y6 2019 | 162 | 41653 | 5604 |
Realme C15 | 174 | 50905 | 4052 |
Meizu Note 8 | 261 | 30160 | 3522 |
Realme 10 | 556 | 14550 | 1862 |
Время измерялось с помощью measureTimeMillis.
APK генерировалось в режиме Build
Во время работы алгоритма на Kotlin в Logcat можно наблюдать интересную картину:
Если я правильно понимаю, это и есть работа "сборщика мусора". В остальном Logcat ругается только на то что приложение не экономит батарею.
В целом можно с уверенностью сказать, что существуют случаи, когда производительность нативного кода колоссально превосходит производительность JVM и, несмотря на некоторое усложнение проекта, имеет смысл реализовать с помощью NDK те модули программы, которые требуют сложных вычислений, особенно если необходимо проводить вычисления не с примитивными типами, а с объектами.
Исходный код доступен на Github
UPD: По советам из комментариев - добавил ветку где С++ хранит не вектор примитивных double, а
std::vector<unique_ptr<double>>Получатся что double уже как-бы не примитив, а объект. Не особо влияет на время выполнения.
Еще добавил ветку,где Kotlin хранит координаты не в ArrayList<Double>, а DoubleArray и по окончании вычислений - оборачивает результат в List.Тоже ничего не дало.
private var points=DoubleArray(3000000);
....
return points.copyOf(index + 1).asList()UPDATE:
Как и предполагалось, узким местом в алгоритме является создание объектов Complex в каждой итерации
Я думаю все тормоза в создании объектов Complex на каждой итерации, а
куда складываются даблы в результате вычислений, уже не так и важно,
основная масса итераций это создание объектов Complex, там сильно
завышена верхняя планка по количеству операций, если ее хоть чуток
снизить, все летает. Думаю это и есть узкое место в программе, куча
созданных в куче объектов, которые потом сборщик мусора собирает, ну
собственно это я их хотел сделать)
Спасибо большое igormich88 - предложил вариант, где создание новых объектов сведено к минимуму, и все стало на свои места, работает быстрее,чем через JNI.
Kotlin Complex objetcs created =414501449
Kotlin Complex objetcs created(optimized) =1
То есть в первом случае создается больше 400 миллионов новых объектов на куче, во втором все время используется один объект.
Правда, необходимо заметить, что ту же оптимизацию можно провести и в С++, не создавать гору объектов а использовать один. Но изначально и был интерес проверить как справится ART с созданием огромного количества объектов в сравнении с таким же созданием на native.
Таким образом, проблема была не в контейнерах и как в них укладывать double, а все таки в огромном количестве создаваемых объектов Complex. Если избежать массового создания новых объектов на куче, то уже не так важно в какой массив складывать координаты точек.
Пока что оптимизация только подтверждает основной результат - автоматическое управление памятью имеет свою немалую стоимость и если в Native можно особо не заморачиваясь создать 400 млн объектов на ходу и не заметить тормозов, то в ART так пока не получается.
Как правильно заметил event1, статью правильнее было бы назвать "цена автоматического управления памятью" или что-то в этом духе.
UPDATE:
Раз мы решили оптимизировать код на Kotlin - избавиться от создания 400 млн объектов Comlex, логично провернуть тоже и в С++, как предложил placidity_master . Необходимо обратить внимание, что мы не просто вынесли объект Complex из цикла но и изменили сам класс Complex таким образом, чтобы он не конструировал новые объекты, а вел вычисления на примитивах в свои полях (метод squareSelf). OK, это еще проще делаем в С++ вычисления без создания новых Complex
Ветка master
APK с новыми кнопочками тут
Результат для Realme 10. Несмотря на потери времени на вызов JNI, С++ пока быстрее в два раза) Хотя без такой большой нагрузки на "сборщик мусора" уже разница и не такая огромная.
Предвижу предложение снова заменить ArrayList на DoubleArray, но уже в оптимизированной версии, сразу скажу - уже пробовал, не дает значительного прироста.
