Комментарии 52
for (int i=0; i<size; i++) {
array[i] = i;
for (int j=0; j<size; j++) {
sum += array[i] * array[j];
sum -= sum / 3;
}
}
Возможно java работает быстрее, т.к. делает оптимизацию для попадания в кеш процессора.
Те. преобразовывает цикл
sum += array[i] * array[j];
В нормальный вид. Когда умножаемое и множитель, расположены рядом друг с другом в памяти (а точнее в L1 кеше процессора).
Цикл разбивается на два независимых цикла.
Т.е. сначала заполняется полностью массив array (т.к. после присвоения, над array[i] нет действий с присваиванием)
Далее уже отдельный внутренний цикл, производит последовательное перемножение элементов.
В этом случае, не будет скачков по ОЗУ и будет максимально использоваться кеш процессора. Т.к. будут перемножаться элементы массива, которые находятся в памяти рядом друг с другом. (что позволит им, попадать в «страницу кеша процессора», и далее обрабатывать их без обращения к памяти)
Современные компиляторы уже достаточно развиты, чтобы оптимизировать такие простые циклы. Корректнее было бы сравнить полноценную программу на Java (чтобы хотя бы несколько сот классов было) и аналогичный нативный. Я уверен, что картина была бы совсем другая.
Поскольку в этом тесте запуск самой JVM и её инициализация вынесены за скобки,
вполне вероятно, что в конечном итоге процессором будет выполнен примерно одинаковый код. Плюс ещё сюда кэш, как уже говорилось. Плюс ещё сюда особенности работы эмулятора (если использовался эмулятор).
Кроме того входной тестовый поток достаточно небольшой, что можно часть времени считать погрешностью и переключением контекстов ОС.
Замеры времени производятся внутри контекста JVM, поэтому не совсем ясно насколько эффективно машина распределяет время между таймерами и полезной нагрузкой в процессе работы.
Вполне очевидно, что полноценный код с кучей Java классов будет медленнее аналогичного нативного. И тут не нужно никаких сравнений. Это аксиома. Просто потому что у нативный код не зависит от рантайма JVM.
Что касается более новых устройств, с Android версии выше 7.0 (где используется среда выполнения ART)
ART используется начиная с Android 5.0, а появился он (как эксперимент) в Android 4.4...
Изначально сделал тесты на Kotlin и в среднем получались такие результаты:
VM:2.1.0
C/C++: 6325939ns
Kotlin: 69608705ns
Kotlin to C/C++ ratio 11.00369526168368Телефон Google Pixel 4 Android 11
Потом сделал на Java и результаты получились примерно такие же
Немного не сходиться с вашей теорией
Может быть вы дадите исходники проекта, что бы люди могли просо запускать и проверять?
Такое может быть ещё из-за того, что алиасинг и отсутствие понимания крестами того, с чем они работают не давать применять полноценные оптимизации. У Java-то глубокое понимание того, что за объект и как используется, поэтому Java для своих родных объектов может гарантировать оптимизации без UB. Но это скорей всего это частный случай этого примера. В C# тоже P/Invoke не даёт преимуществ, если вызывать нативный код часто или со сложными структурами из-за оверхеда managed-to-native transitions и отсутствию штук вроде whole program optimization или инлайнинга.
int* array = new int[size];
Грубая ошибка для C++. Много где встречал, что это является плохим тоном. Для базовых числовых типов не желательно использовать массив из указателей и использовать new, если переменная локальная! Основная проблема, что при указателях C++ может разместит массив в куче, а не в кэше(на стеке), отсюда алгоритм может потерять в скорости. Но посмотрел плюс минус скорость одинаковая при размере 100000, и видимо компилятор все же оптимизировал код, но с указателями примерно на 0.2с медленее(не смотрел почему, но некоторые компиляторы все же добавляют разименовывание указателя). Правильно для локальных массивов делать:
int array[size]stackoverflow.com/questions/2305770/efficiency-arrays-vs-pointers
Третья причина при выходе из функции массив автоматически удалится.
1 Это не массив из указателей
Может, я спросонья вижу то, чего нет, но комментарий вызывает поднятие бровей
(ноль) Постить комментарии с телефона на хабр невозможно :( И ни удалить, ни отредактировать теперь не могу
Так вот, правильная версия:
- это не массив указателей
- никаких "может разместить" — слово new прямо говорит о выделении памяти в куче
- "Сделайте правильно" int array[size] когда size не константа?
- по вашей ссылке немножко не то, что вы утверждаете, там люди играются опциями оптимизации, и утверждается, что при их включении отличия несущественны. Кроме того, изначальный посыл вообще противоположен вашему.
И вот теперь постскриптум, да:
Может, я спросонья вижу то, чего нет, но комментарий вызывает поднятие бровей
2. Компилятор может как угодно оптимизировать код, тут никто не знает. Сейчас компиляторы значительно умные, и там может быть что угодно, зависит от реализации. Все правильно new изначально размещал всегда в куче. Если указатель далее никуда не передается, то компилятор вполне может предсказать поведение. Предлагаю вам взять несколько современных компиляторов и разобрать ассемблерный код на выходе.
3. Когда даже не константа, если размер стека нам позволяет, то мы можем выделить нужный размер и сместить указатель на вершину стека.
4. Все то, только поведение зависит от компилятора и ключей оптимизации. Что на выходе будет предсказать сложно, новые компиляторы оптимизируют агрессивнее.
Можете привести пример, когда new не выделяет память в куче? Как это должно работать с технической точки зрения?
Компилятор может как угодно оптимизировать код, тут никто не знает.Могу предположить, что может использоваться inline для new. Это лишь предположения, что вполне возможно такое поведение с современными компиляторами, не давно с людьми смотрели как GCC развернул циклы и как LLVM, люди с опытом, которые занимаются написанием компиляторов не могли понять, что делает GCC и как оптимизировал код. LLVM посчитал цикл бесконечным и не смог развернуть, GCC его развернул и выплюнул очень длинный ассемблерный код. Как итог GCC был значительно быстрее и это с дефолтными настройками.
Вот смотрите, стандарт нам говорит, что время жизни объектов, выделенных при помощи new, не заканчивается при выходе из скоупа. Как этого добиться, не выделяя память в куче? Про разворачивание циклов и другие интересные трюки я в курсе, это не то.
В свете вашего первоначального комментария и моего ответа - это неважно. Есть вещи, которые компиляторы могут делать, а есть вещи, которые не могут. Разницу знать полезно.
Я прошу прощения, меня стриггерило ваше "Х - грубая ошибка", за которым следуют несколько сомнительных утверждений. Слишком безапелляционно.
2. Компилятор может как угодно оптимизировать код, тут никто не знает.
Не как угодно. Это определяется стандартами и спецификацией компилятора. Люди, программирующие на C знают, что будет делать компилятор при применении определенных флагов.
«Сделайте правильно» int array[size] когда size не константа?
В C это возможно начиная с C99, а в C++ начиная с C++14. Последние версии clang имплементируют стандарт C++14 в полном виде (так заявлено в документации).
Ссылки:
isocpp.org/files/papers/N3690.pdf — страница 185
clang.llvm.org/docs/LanguageExtensions.html#c-14-runtime-sized-arrays
clang.llvm.org/compatibility.html#vla
Мне нужно было добиться максимальной схожести логики на Java и C. Специально использовал new, а не локальные аллокацию (на стеке), чтобы сравнение было справедливым. Ведь, на сколько мне известно, Java все равно будет брать память в куче. По этой же причине осознанно закомментил delete[] для теста.
Грубая ошибка для C++. Много где встречал, что это является плохим тоном. Для базовых числовых типов не желательно использовать массив из указателей и использовать new, если переменная локальная!
Самое обычное выделение памяти под динамический массив в C++. Объявляется указатель на участок памяти, где будет располагаться массив не указателей, а целочисленных значений. В данном случае, конечно, new использовать было совсем не обязательно, т.к. размер необходимого массива нам заранее известен (в данном случае ваш пример с кодом приведен корректно). Но это никак не зависит от того глобальная переменная или локальная. Зависит от того, известна нам размерность или нет.
Основная проблема, что при указателях C++ может разместит массив в куче, а не в кэше(на стеке)
new говорит о выделении динамической памяти, а это всегда только куча, если не применены оптимизации компилятора. Указатели тут не при чем.
Кэш != стек. Помещение данных в стек не гарантирует его кэширование процессором.
Вторая причина компилятор может векторизовать циклы при работе с массивом, а с указателями нет.
В данном случае векторизовывать нечего, т.к. представленный в тесте цикл не параллелится.
2. Все правильно. Про кеш тоже согласен. Плюс еще есть предсказатель переходов и т.д., факторов много влияет на скорость. Тема сложная и мало кто в ней хорошо плавает. Просто изначально всегда обучали и делали акцент на стеке, что это кэш память, а куча более медленная. Плюс у нас все же несколько видов кеша в процессорах.
3. Так и есть. Написал выше «может», поведение зависит от контекста, поэтому использовать просто массив выгоднее чем указатель на массив.
Может я ошибаюсь, но, насколько я помню, new[] в Java гарантирует корректное зануление массива, а вот в плюсах там может быть что угодно. Так что плюсовый вариант будет с неинициализированным массивом, По факту UB. Это раз.
Два - итоговый sum нигде не используется, и достаточно ушлые компиляторы технически могли бы вырезать весь бенчмарк с концами. Так как цикл работает только с массивом, счётчиками и переменной - их можно пристрелить без side-effect’ов.
Наконец, недавно была статья о том, что какие-то компиляторы умеют преобразовывать циклы в простые математические конструкции. Даже я тут вижу несколько очевидных оптимизаций, которые мгновенно снижают сложность с O(n^2) до O(n), а при помощи менее очевидных - до O(1).
Так что тут битва не столько Java/JNI, сколько компиляторов…
Вы правы. Я осознанно не занулял отдельно массив, чтобы сравнение произошло более менее справедливо (вдруг Android Runtime это делает отдельно). Отсутствие зануления влияет лишь на результат расчетов, а не снижает скорость C функции.
Может я ошибаюсь, но, насколько я помню, new[] в Java гарантирует корректное зануление массива, а вот в плюсах там может быть что угодно. Так что плюсовый вариант будет с неинициализированным массивом, По факту UB. Это раз.
В контексте статьи не имеет значения. В C++ там просто будет какой-то мусор размерностью int. Поэтому UB тут вполне defined.
Два — итоговый sum нигде не используется, и достаточно ушлые компиляторы технически могли бы вырезать весь бенчмарк с концами.
Так и будет. Clang при применении оптимизации O2 и O3 даже не вызовет эту функцию. Это полностью компрометирует предложенные результаты и всю статью целиком.
микроскопической длительности?
Там одно изменение частоты процессора запросто даст различие на порядок.
Вы правы. Поэтому вначале и написал disclaimer, что это очень тупой и простой бенчмарк. По идее много чего не учтено. К этому короткому исследовантю я пришел тогда, когда решил переписать с Java на C++ свой рендер (sprite batching). Когда увидел, что это мало что дало на новых устройствах (на старых дало). Решил провести такой вот простой бенч. Никаких амбиций по поводу высокой точности. Но множество итераций было проведено, чтобы более менее среднее посчитать.
Думаю, мой вопрос скорее не о сравнении языков Java vs C/C++ (пишу на обоих и у каждого свои сильные стороны), а о компиляторах (Android Runtime vs Clang). Если есть способы безусловно на всех устройствах получить преимущество в производительности на C/C++, то напишу важные части движка на нём. Если нет, тогда оставлю на Java. Поэтому и советуюсь с сообществом.
Выведите результат, переключитесь в релиз и увидите совсем другие цифры
Вы походу дебаг билдите, вот оптимизации и не выкидывают неиспользуемый код,
По-умолчанию отладочные символы не включаются компилятором в сборку (что в Java, что в C++). Для этого используется отдельный флаг -g. Автор его явно не использовал (было бы странно). Ассертов тут нет. А для того, чтобы применить оптимизацию в C++, необходимо передать соответствующие флаги (можно использовать специальные флаги, которые включают в себя группы оптимизаций: O1, O2, O3), в противном случае компилятор не производит существенных изменений в исходный код.
Для того, чтобы выкинуть неиспользуемый код необходимо задать флаг O2 и выше. Автор это сделал в части тестов, однако не учёл каким образом оптимизировался код.
Выведите результат, переключитесь в релиз и увидите совсем другие цифры
Если судить по написанному, то автор явно не использовал сборщики, а передавал флаги напрямую. Понятие дебаг/релиз применимо только к сборщикам (Make, Gradle, CMake и т.д.). Так что переключаться никуда не получится.
Так себе тест, хоть результат и интересен.
А попробуй реализовать тест с бес знаковой переменной и там и там. Что ни будь вроде свертки с где есть опасность переполнения...
Производительность Android Runtime vs NDK