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-протокол снова
Я как раз читаю эту статью, принципы из ее начала резонируют с моим ощущением "как правильно". Я бы был заинтересован в изготовлении тестового стенда для опробования всего этого в железе и экспериментов
На самом деле, есть еще несколько интересных оптимизаций, которые можно было бы испробовать - одна из них - иметь два комплекта сервисных процедур: один для стека (top, subtop) а второй - для обратного ему (subtop, top).
Тогда процедура SWAP может не делать ничего кроме переключения с одного комплекта на другой. OVER тоже будет оптимизирован лучше в результате. Мы можем даже использовать "флаг направления (DF)" в процессоре для отслеживания какой комплект работает в данный момент.
Я предолагаю, что из-за этого предсказатель переходов будет предсказывать лучше, т.к. у него будет больше переходов и информационная нагрузка на один переход уменьшится. Приглашаю это проверить вместе.
Нет, неправильно. Более того она делает именно это в своей процедуре Print которая вызывает обычный такой библиотечно-POSIX-вый printf(), просто сохраняя/восстанавливая несколько регистров, которые в любом случае пришлось бы сохранять по ABI.
Мы можем добавить еще опкодов которые будут делать любые сисколлы или библиотечные вызовы или даже один опкод который сможет делать любой сискол по номеру - ограничений нет
К слову сказать, я бы не отказался прочесть статью о том, как в emacs реализовано undo потому что на мой взгляд это лучшая реализация из мне известных. Возможно автор обратит внимание на тему для статьи..
Думаю, минусуют карму ему за проскальзывающую в комментариях манеру учить других и категоричность в суждениях (которая кстати часто встречается у матерых системщиков). А вот за хорошие статьи плюсуют реже чем за плохие комментарии. Я плюсанул.
Очень интересное решение, спасибо, я думал о разработке чего-то подобного, рад что теперь можно адаптировать этот подход. Интересно, работает ли внутри емакса, который внутри termux сложные штуки такие как emacs-jabber или erc или этот подход годится только для org-заметок?
Возможно, вы сейчас имеете дело с куда более качественными компонентами, а избыточность схемы была нужна для компенсации температурного дрейфа характеристик
Хотя в последнем утверждении я может погорячился, иначе не было бы статей https://habr.com/ru/articles/767342/ "Геймдев на Lisp. Часть 1: ECS и металингвистическая абстракция"
Лисп - это мудрый и эксцентричный дядя (настолко эксцентричный что редко покидает свой замок в Трансильвании), который живет в своем мире и мыслит иногда настолько нестандартно, что тебе приходится выбросить из головы не только "все чему учили в школе", но и "best practices" индустрии.
В отличии от Rust он не пытается тебя ограничивать "как бы чего не вышло", в отличии от С++ - не бьет по рукам кувалдой, вместо этого он просто позволяет творческому процесу не создавать проблем - тебе не нужен Rc<RefCell<T>> потому что в языке уже есть быстрый GC, но если ты хочешь - ты можешь придумать что-нибудь свое - и это будет удобно сосуществовать с тем что уже придумано до тебя - без необходимости переписывать мир, потому что в Lisp типизируются не переменные а значения. И это позволяет лепить прототип так как ты захочешь, а перед релизом вдруг обнаружить что он написан на каком-то своем диалекте Лиспа, который включает все необходимое для конкретной этой игры. И если ты вдруг хочешь большей строгости - то твой дядя поможет написать тебе минимальный компилятор этого [твоего суб-диалекта] с разнообразными проверками статическими и динамическими.
Но будем честными, если тебя покусал этот твой дядя, то разработка игр становится уже куда менее интересной чем разработка новых Lisp-ов..
Я измерил размеры всех сервисных процедур:
Поэтому я выровнял их все на 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-протокол снова
Я как раз читаю эту статью, принципы из ее начала резонируют с моим ощущением "как правильно". Я бы был заинтересован в изготовлении тестового стенда для опробования всего этого в железе и экспериментов
Я думаю, это блестящая идея! Стоит попробовать!
На самом деле, есть еще несколько интересных оптимизаций, которые можно было бы испробовать - одна из них - иметь два комплекта сервисных процедур: один для стека (top, subtop) а второй - для обратного ему (subtop, top).
Тогда процедура SWAP может не делать ничего кроме переключения с одного комплекта на другой. OVER тоже будет оптимизирован лучше в результате. Мы можем даже использовать "флаг направления (DF)" в процессоре для отслеживания какой комплект работает в данный момент.
Я предолагаю, что из-за этого предсказатель переходов будет предсказывать лучше, т.к. у него будет больше переходов и информационная нагрузка на один переход уменьшится. Приглашаю это проверить вместе.
Нет, неправильно. Более того она делает именно это в своей процедуре Print которая вызывает обычный такой библиотечно-POSIX-вый printf(), просто сохраняя/восстанавливая несколько регистров, которые в любом случае пришлось бы сохранять по ABI.
Мы можем добавить еще опкодов которые будут делать любые сисколлы или библиотечные вызовы или даже один опкод который сможет делать любой сискол по номеру - ограничений нет
Тогда возможно понравится исследование, насколько он может быть быстр (спойлер: очень быстр) https://habr.com/ru/articles/856480/
К слову сказать, я бы не отказался прочесть статью о том, как в emacs реализовано undo потому что на мой взгляд это лучшая реализация из мне известных. Возможно автор обратит внимание на тему для статьи..
Думаю, минусуют карму ему за проскальзывающую в комментариях манеру учить других и категоричность в суждениях (которая кстати часто встречается у матерых системщиков). А вот за хорошие статьи плюсуют реже чем за плохие комментарии. Я плюсанул.
Очень интересное решение, спасибо, я думал о разработке чего-то подобного, рад что теперь можно адаптировать этот подход. Интересно, работает ли внутри емакса, который внутри termux сложные штуки такие как emacs-jabber или erc или этот подход годится только для org-заметок?
Возможно, вы сейчас имеете дело с куда более качественными компонентами, а избыточность схемы была нужна для компенсации температурного дрейфа характеристик
О, я бы не отказался от ссылок на гайд по обоим асмам..
Хотя в последнем утверждении я может погорячился, иначе не было бы статей https://habr.com/ru/articles/767342/ "Геймдев на Lisp. Часть 1: ECS и металингвистическая абстракция"
Лисп - это мудрый и эксцентричный дядя (настолко эксцентричный что редко покидает свой замок в Трансильвании), который живет в своем мире и мыслит иногда настолько нестандартно, что тебе приходится выбросить из головы не только "все чему учили в школе", но и "best practices" индустрии.
В отличии от Rust он не пытается тебя ограничивать "как бы чего не вышло", в отличии от С++ - не бьет по рукам кувалдой, вместо этого он просто позволяет творческому процесу не создавать проблем - тебе не нужен Rc<RefCell<T>> потому что в языке уже есть быстрый GC, но если ты хочешь - ты можешь придумать что-нибудь свое - и это будет удобно сосуществовать с тем что уже придумано до тебя - без необходимости переписывать мир, потому что в Lisp типизируются не переменные а значения. И это позволяет лепить прототип так как ты захочешь, а перед релизом вдруг обнаружить что он написан на каком-то своем диалекте Лиспа, который включает все необходимое для конкретной этой игры. И если ты вдруг хочешь большей строгости - то твой дядя поможет написать тебе минимальный компилятор этого [твоего суб-диалекта] с разнообразными проверками статическими и динамическими.
Но будем честными, если тебя покусал этот твой дядя, то разработка игр становится уже куда менее интересной чем разработка новых Lisp-ов..
"То ли нужно менять слуховой аппарат, то ли менять окрестность..." (c) БГ
Мне кажется надо идти на собесы к тем кто спрашивает по сикп и книге дракона - у них и денег больше и работать интереснее