Есть один аспект, когда компилятор хуже: отладка. Отладчик байткода пишется довольно легко (я даже думаю, не написать ли об этом следующую статью). Но если мы компилируем, да еще и применяем оптимизации, то сложность отладчика резко возрастает и это перестает быть "проектом выходного дня".
Я бы оставил printf() считая его частью задачи. Редко мы используем интерпретаторы общего назначения исключительно для числодробилок без i/o. Для того чтобы нивелировать случайные эффекты, лучше запускать бенчмарк 5 раз, как это сделано у @Atakua. С увеличением задачи согласен, все стало уже слишком быстрым
Я работаю над этим сейчас, пока результаты спорные: - с одной стороны больше кода - бранч-предиктору легче (но возможно это проявляется лишь на коротких программах как представленная @Atakua - с другой стороны, больше кода - больше кэш-миссов - с третьей вообще все очень сильно зависит от нюансов ассемблерной реализации и сочетания с другими способами оптимизации. Для такого тюнинга уже хочется иметь какой-то решатель, который выбирает способ оптимизации в зависимости от внешних условий. Но это уже круто отличается от подхода "давайте возьмем интерпретатор, напишем его возможно более оптимально, и нам не потребуется писать сложный jit" - т.к. такой селектор оптимизаций будет приближаться по сложности к jit.
Моя статья своей задачи достигла: интерпретатор с малой сложностью показывает достаточно высокую производительность (даже выше чем ожидалось) путем применения небольшого количества приемов. Можно применить больше приемов и выжать еще немного.
Дальше есть два пути: 1. попробовать включить два приема, предложенных в комментариях: - отказ о указателя на таблицу сервисных процедур (все процедуры будут одного размера) - зависимость набора процедур от состояния стека (его глубины и порядка элементов в нем, возможно что-то еще) 2. двигаться в сторону суперинструкций, объединяя в одну инструкцию идущие подряд. Строго говоря, это уже немного jit (я считаю что граница проходит там, где мы начинаем создавать машинный код на который передаем управление)
Оба этих подхода интересные, но увеличивают сложность и становятся ненадежными с точки зрения выигрыша: первый зависит попадания процедур в кэш, второй требует нахождения компромисса между затратами на предобработку и ускорением обработанного байткода. Вывод будет неочевидным - если затюнить параметры иначе можно получить радикально отличающиеся бенчмарки. (Это было бы хорошо если бы мне платили за развязывание споров.) В моей статье этой неочевидности нет - ассемблерный оптимизированный интерпретатор реально быстрый и очевидно по каким причинам.
Да, конечно, забыл, но в оправдание могу сказать, что я просто хотел чтобы ось Y начиналась от нуля, а то это получается "лгать при помощи графиков".
Сейчас я пытаюсь проверить, как распределение кода влияет на промахи кэша. Выше уже предложили (а я немного адаптировал идею), что если оставлять в начале сервисной процедуры только 16-32 байт кода, а до остального прыгать jump-ом то может быть это сможет дать лучшее попадание в кэш для тех процедур, которые не превышают эти 16-32 байта и не такую большую просадку из-за jump-а потому что он будет хорошо предсказываться.
Убирать нельзя, т.к. в исходной статье измерения проводятся вместе с printf. С другой стороны она не оказывает серьезного влияния на общий бенчмарк, т.к. вызывается всего лишь 9592 раз.
Решение, на мой взгляд, есть - переход от общего взвешивания к индивидуальному. Я бы хотел чтобы у каждой статьи или комментария плюс человека, которому я доверяю весил во много раз больше, чем плюс нонейма. Таким образом будет формироваться мой, индивидуализированный рейтинг статьи, а не общехабровский рейтинг "миллиона мух"
0000000000000016 a size_of_Add
0000000000000016 a size_of_And
000000000000000f a size_of_Break
0000000000000016 a size_of_Dec
0000000000000024 a size_of_Drop
0000000000000024 a size_of_Dup
000000000000000f a size_of_Halt
0000000000000019 a size_of_Inc
000000000000004a a size_of_Je
0000000000000017 a size_of_Jne
000000000000001d a size_of_Jump
000000000000003e a size_of_Mod
0000000000000016 a size_of_Mul
0000000000000016 a size_of_Nop
0000000000000016 a size_of_Or
0000000000000022 a size_of_Over
0000000000000016 a size_of_Pic
0000000000000051 a size_of_Print
0000000000000028 a size_of_Push
0000000000000016 a size_of_Rand
0000000000000016 a size_of_Rot
0000000000000016 a size_of_SHL
0000000000000016 a size_of_SHR
0000000000000016 a size_of_SQRT
0000000000000024 a size_of_Sub
0000000000000018 a size_of_Swap
0000000000000016 a size_of_Xor
Поэтому я выровнял их все на 0x100 байт и расположил в порядке, соответсвующем байткоду, избавившись от таблицы service_routines. Теперь в routines лежит адрес первой процедуры.
Макрос DISPATCH стал вот таким:
.macro DISPATCH
# jmp *(routines, opcode64, 8)
shl $8, opcode64 # Умножить номер функции на 0x100
lea (routines, opcode64), opcode64 # Добавить базовый адрес первой функции
jmp *opcode64 # Перейти по адресу, хранящемуся в opcode64
.endm
В результате бенчмарка я получил следующий результат (нас интересует столбец asmexp):
Возможно, увеличение размера кода ухудшило попадание в кэш кода или, что более вероятно, профит от исчезновения коссвенности сьели добавленные в DISPATCH команды. Может быть есть и другие предположения? Или есть способ написать ассемблерный код оптимальнее?
>> прежде хорошо изучите устройство и принципы работы таких интерпретаторов, как интерпретатора байт-кода в OpenJDK.
Давайте перейдем в более конструктивную плоскость. В этой статье были изложены принципы оптимизации интерпретаторов, которые дают измеримый эффект для производительности. Я бы хотел узнать, какие принципы могут еще улучшить перформанс (неважно откуда они будут - из OpenJDK или других источников). Можете поделиться?
public class Main {
public static void main(String[] args) {
for (int i = 2; i < 100000; i++) {
boolean isPrime = true;
for (int divisor = 2; divisor < i; divisor++) {
if (i % divisor == 0) {
isPrime = false;
break;
}
}
if (isPrime)
System.out.printf("[%d]\n", i);
}
}
}
запустил без jit-компиляции:
time java -Xint Main
и получил время 3.945s (сравните с 3.228s при исполнении алгоритма в виртуальной машине, со всеми включенными проверками границ, счетчиками шагов и счетчиками вызова сервисных функций)
Вывод: Java-код не в состоянии обогнать оптимизированный интерпретатор байткода.
Мне больше нравится обобщенное решение, т.к. я не уверен в своей способности не внести каких-нибудь багов по невнимательности. Особенно когда мы делаем несколько вариантов одной и той же реализации ВМ под разные процессоры: x86_64, ARM, RISC-V...
Спасибо за ссылку, там интересные идеи. Я думаю стоит написать генератор, который смог бы для каждого варианта стека из обычного набора сервисных процедур сгенерировать несколько стекозависимых. Это было бы интересно обсудить
Это еще один хороший пример "общего мнения", которое легко опровергнуть - прожорливость нативных тредов в современных операционных системах связана с тем, что для того чтобы создать/остановить/продолжить/завершить их - требуется обращение к ядру, а значит переключение контекста.
Если все нативные треды созданы в начале программы и завершены в конце, а в процессе работы у них нет или мало "точек рандеву" - то они будут быстрее чем зеленые треды, потому что среда выполнения (интерпретатор) не обслуживает диспетчер тредов и эти точки рандеву.
Это огромный класс задач: например у вас может быть IDE, в которой один поток занимается подсветкой синтаксиса, другой - пользовательским интерфейсом, третий - чем то еще.
Прожорливость зеленых тредов становится видна если их создавать и уничтожать на каждый чих: тогда накладные расходы становятся дороже чем полезная нагрузка.
Но, даже если мы делаем зеленые треды, можно посмотреть, что будет занимать время при их переключении в среде выполнения. В текущем варианте ВМ все они будут разделять общий код и данные, но стек у каждого зеленого треда будет свой, это значит что весь контекст выполнения который нужно переключить - это: - указатель стека - кэшированные два элемента стека - program counter
Все остальное - глобальное в регистрах.
Переключение (создание/уничтожение) будет требовать всего нескольких ассемблерных команд - и значит будет очень быстрым
Я хотел бы поучаствовать в этом совместном проекте. У меня давно зреет идея о FPGA-компьютере в формате клавиатуры, способном подключаться к экранам через HDMI и содержащем внутри себя Forth-машину, которую можно было бы разрабатывать и на обычном GNU/Linux/FreeBSD компьютере. Я запускал Plan9 очень давно и было бы интересно потестить Inferno и 9p-протокол снова
Есть один аспект, когда компилятор хуже: отладка. Отладчик байткода пишется довольно легко (я даже думаю, не написать ли об этом следующую статью). Но если мы компилируем, да еще и применяем оптимизации, то сложность отладчика резко возрастает и это перестает быть "проектом выходного дня".
Я бы оставил printf() считая его частью задачи. Редко мы используем интерпретаторы общего назначения исключительно для числодробилок без i/o. Для того чтобы нивелировать случайные эффекты, лучше запускать бенчмарк 5 раз, как это сделано у @Atakua. С увеличением задачи согласен, все стало уже слишком быстрым
Я работаю над этим сейчас, пока результаты спорные:
- с одной стороны больше кода - бранч-предиктору легче (но возможно это проявляется лишь на коротких программах как представленная @Atakua
- с другой стороны, больше кода - больше кэш-миссов
- с третьей вообще все очень сильно зависит от нюансов ассемблерной реализации и сочетания с другими способами оптимизации. Для такого тюнинга уже хочется иметь какой-то решатель, который выбирает способ оптимизации в зависимости от внешних условий. Но это уже круто отличается от подхода "давайте возьмем интерпретатор, напишем его возможно более оптимально, и нам не потребуется писать сложный jit" - т.к. такой селектор оптимизаций будет приближаться по сложности к jit.
Моя статья своей задачи достигла: интерпретатор с малой сложностью показывает достаточно высокую производительность (даже выше чем ожидалось) путем применения небольшого количества приемов. Можно применить больше приемов и выжать еще немного.
Дальше есть два пути:
1. попробовать включить два приема, предложенных в комментариях:
- отказ о указателя на таблицу сервисных процедур (все процедуры будут одного размера)
- зависимость набора процедур от состояния стека (его глубины и порядка элементов в нем, возможно что-то еще)
2. двигаться в сторону суперинструкций, объединяя в одну инструкцию идущие подряд. Строго говоря, это уже немного jit (я считаю что граница проходит там, где мы начинаем создавать машинный код на который передаем управление)
Оба этих подхода интересные, но увеличивают сложность и становятся ненадежными с точки зрения выигрыша: первый зависит попадания процедур в кэш, второй требует нахождения компромисса между затратами на предобработку и ускорением обработанного байткода. Вывод будет неочевидным - если затюнить параметры иначе можно получить радикально отличающиеся бенчмарки. (Это было бы хорошо если бы мне платили за развязывание споров.) В моей статье этой неочевидности нет - ассемблерный оптимизированный интерпретатор реально быстрый и очевидно по каким причинам.
Я в чем-то неправ?
Экспериментирую тут https://github.com/rigidus/interpreters-comparison/tree/checkpoint (можно на ты, так как-то привычнее - я родом из интернета до роскомнадзора)
Думаю о комбинации этих идей: https://habr.com/ru/articles/856480/comments/#comment_27534590
Да, конечно, забыл, но в оправдание могу сказать, что я просто хотел чтобы ось Y начиналась от нуля, а то это получается "лгать при помощи графиков".
Сейчас я пытаюсь проверить, как распределение кода влияет на промахи кэша. Выше уже предложили (а я немного адаптировал идею), что если оставлять в начале сервисной процедуры только 16-32 байт кода, а до остального прыгать jump-ом то может быть это сможет дать лучшее попадание в кэш для тех процедур, которые не превышают эти 16-32 байта и не такую большую просадку из-за jump-а потому что он будет хорошо предсказываться.
Кажется что разница значительная, но на самом деле картинка вводит в заблуждение. Добавление native варианта позволяет сопоставить в масштабе
У меня вот такие результаты.
Можно ли ссылку на форк с изменениями?
Убирать нельзя, т.к. в исходной статье измерения проводятся вместе с printf. С другой стороны она не оказывает серьезного влияния на общий бенчмарк, т.к. вызывается всего лишь
9592раз.Решение, на мой взгляд, есть - переход от общего взвешивания к индивидуальному. Я бы хотел чтобы у каждой статьи или комментария плюс человека, которому я доверяю весил во много раз больше, чем плюс нонейма. Таким образом будет формироваться мой, индивидуализированный рейтинг статьи, а не общехабровский рейтинг "миллиона мух"
попробуешь провести экперимент? там в Makefile чтобы запустить бенчмарк достаточно
Я измерил размеры всех сервисных процедур:
Поэтому я выровнял их все на 0x100 байт и расположил в порядке, соответсвующем байткоду, избавившись от таблицы service_routines. Теперь в routines лежит адрес первой процедуры.
Макрос DISPATCH стал вот таким:
В результате бенчмарка я получил следующий результат (нас интересует столбец asmexp):
Возможно, увеличение размера кода ухудшило попадание в кэш кода или, что более вероятно, профит от исчезновения коссвенности сьели добавленные в DISPATCH команды. Может быть есть и другие предположения? Или есть способ написать ассемблерный код оптимальнее?
Код в отдельной ветке: https://github.com/rigidus/interpreters-comparison/tree/asmexp
>> прежде хорошо изучите устройство и принципы работы таких интерпретаторов, как интерпретатора байт-кода в OpenJDK.
Давайте перейдем в более конструктивную плоскость. В этой статье были изложены принципы оптимизации интерпретаторов, которые дают измеримый эффект для производительности. Я бы хотел узнать, какие принципы могут еще улучшить перформанс (неважно откуда они будут - из OpenJDK или других источников). Можете поделиться?
В этой статье мы сравниваем не интерпретируемую джаву с компилируемой а разные способы создавать интерпретаторы байткода.
Подождите следующей статьи :)
Я взял код из native.c и переписал его на Java
запустил без jit-компиляции:
и получил время 3.945s (сравните с 3.228s при исполнении алгоритма в виртуальной машине, со всеми включенными проверками границ, счетчиками шагов и счетчиками вызова сервисных функций)
Вывод: Java-код не в состоянии обогнать оптимизированный интерпретатор байткода.
Вы всерьез ожидали иного результата?
Мне больше нравится обобщенное решение, т.к. я не уверен в своей способности не внести каких-нибудь багов по невнимательности. Особенно когда мы делаем несколько вариантов одной и той же реализации ВМ под разные процессоры: x86_64, ARM, RISC-V...
Спасибо за ссылку, там интересные идеи. Я думаю стоит написать генератор, который смог бы для каждого варианта стека из обычного набора сервисных процедур сгенерировать несколько стекозависимых. Это было бы интересно обсудить
Это еще один хороший пример "общего мнения", которое легко опровергнуть - прожорливость нативных тредов в современных операционных системах связана с тем, что для того чтобы создать/остановить/продолжить/завершить их - требуется обращение к ядру, а значит переключение контекста.
Если все нативные треды созданы в начале программы и завершены в конце, а в процессе работы у них нет или мало "точек рандеву" - то они будут быстрее чем зеленые треды, потому что среда выполнения (интерпретатор) не обслуживает диспетчер тредов и эти точки рандеву.
Это огромный класс задач: например у вас может быть IDE, в которой один поток занимается подсветкой синтаксиса, другой - пользовательским интерфейсом, третий - чем то еще.
Прожорливость зеленых тредов становится видна если их создавать и уничтожать на каждый чих: тогда накладные расходы становятся дороже чем полезная нагрузка.
Но, даже если мы делаем зеленые треды, можно посмотреть, что будет занимать время при их переключении в среде выполнения. В текущем варианте ВМ все они будут разделять общий код и данные, но стек у каждого зеленого треда будет свой, это значит что весь контекст выполнения который нужно переключить - это:
- указатель стека
- кэшированные два элемента стека
- program counter
Все остальное - глобальное в регистрах.
Переключение (создание/уничтожение) будет требовать всего нескольких ассемблерных команд - и значит будет очень быстрым
Я хотел бы поучаствовать в этом совместном проекте. У меня давно зреет идея о FPGA-компьютере в формате клавиатуры, способном подключаться к экранам через HDMI и содержащем внутри себя Forth-машину, которую можно было бы разрабатывать и на обычном GNU/Linux/FreeBSD компьютере. Я запускал Plan9 очень давно и было бы интересно потестить Inferno и 9p-протокол снова