Как стать автором
Обновить

Глобально оптимальный, восьмой и наиболее быстрый вид интерпретаторов байткода

Уровень сложностиСложный
Время на прочтение15 мин
Количество просмотров12K
Всего голосов 101: ↑98 и ↓3+120
Комментарии104

Комментарии 104

vjft - интересно. А грамматика GL-ля уже есть?

Правильно ли я понимаю, что раз мы много чего делаем глобальным, многопоточным это не сделать? А в случае кооперативной многозадачности (типа фиберы, корутины) надо будет добавлять код по сохранению/восстановлению глобальных значений в некий контекст выполнения?

Не совсем. Нам никто не мешает запустить несколько потоков в каждом из которых будет своя виртуальная машина - это будет классическая многопоточность, где у каждой ВМ есть свой стек, но при этом могут быть общие области памяти (и критические секции)

Можно. Но нативные треды прожорливее, чем зеленые треды (корутины и прочее).
Жаль это убивать на корню.

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

Если все нативные треды созданы в начале программы и завершены в конце, а в процессе работы у них нет или мало "точек рандеву" - то они будут быстрее чем зеленые треды, потому что среда выполнения (интерпретатор) не обслуживает диспетчер тредов и эти точки рандеву.

Это огромный класс задач: например у вас может быть IDE, в которой один поток занимается подсветкой синтаксиса, другой - пользовательским интерфейсом, третий - чем то еще.

Прожорливость зеленых тредов становится видна если их создавать и уничтожать на каждый чих: тогда накладные расходы становятся дороже чем полезная нагрузка.

Но, даже если мы делаем зеленые треды, можно посмотреть, что будет занимать время при их переключении в среде выполнения. В текущем варианте ВМ все они будут разделять общий код и данные, но стек у каждого зеленого треда будет свой, это значит что весь контекст выполнения который нужно переключить - это:
- указатель стека
- кэшированные два элемента стека
- program counter

Все остальное - глобальное в регистрах.

Переключение (создание/уничтожение) будет требовать всего нескольких ассемблерных команд - и значит будет очень быстрым

Почему говоря о производительности вы не упоминаете память?

И по моему сложно не согласиться, что в любом случае нативные треды дороже. Всё, что вы написали - это попытки уменьшить их стоимость.

Я не говорю, что нативные треды это зло. Просто упомянул, что иметь возможность работы с зелёными стредами это большой плюс.

Их нельзя сравнивать в лоб. Это разные инструменты для разных задач. Зелёные предназначены чтобы обслуживать по 10к клиентов, при этом процессор в основном ждёт данные с сокетов, с БД или ждёт запись в файлы логов. А числодробилки на "зелёных" делать неэффективно - там нет точек await, когда треду нужно ожидание, а процессор можно передать другому треду.

Согласен! Просто мне показалось, что ваше решение для многозадачности не поддерживает зеленые треды.

Не тот уровень абстракции. Компилятор, генерирующий байт-код, должен уметь async-функцию компилить в конечный автомат, т.е. 1 вызов фунции = 1 шаг автомата между точками await. Интерпретатор байт-кода может и не знать, что он выполняет не обычную функцию, а зелёную.

Обычно для этого функции определенным образом помечают (async как ключевое слово перед определением функци). Поэтому, скорее всего, интерпретатор тоже может владеть такой информацией и понимать, что он исполняет зеленую функцию. Нет?

Можно, конечно, async вынести на уровень интерпретатора, и сделать поддержку в специальных опкодах. Но по классике, чтобы было оптимально, компилятор в байт-код генерирует код с поддержкой кооператива, чтобы не нагружать этим интерпретатор байт-кода.

В компилируемых языках процессор не знает, выполняет он "зелёную" функцию или обычную. Он молотит все опкоды подряд, которые ему подсунут. Никто пока не предложил инструкции процессора под async. Было бы выгодно - сделали бы.

Меня в заблуждение ввела фраза "Для начала можно сделать все данные состояния интерпретатора глобальными переменными.". Только посмотрев код тщательнее, я понял, что "глобальными переменными" вы имеете ввиду не в рамках программы-хоста, а в рамках виртуальной машины. Ну и потом эти "глобальные переменные" прибиваете к регистрам. То есть перед началом выполнения кода ВМ заполняем регистры хоста из контекста выполнения, в случае прерывания выполнения кода ВМ сохраняем регистры хоста обратно в контекст выполнения, чтобы потом можно было возобновить выполнение. Тогда можно и несколько ВМ запускать в одном потоке поочерёдно.

В коде не вижу ничего особо глобального, во все функции передаётся контекст cpu_t *

А вообще, через кодогенерацию/макросы можно сделать до 16 копий (или сколько нужно) кода интерпретатора, и запускать эти копии на разных тредах.

Или через пре-процессор

namespace cpu1 {
#include "cpu_impl.cpp"
}
namespace cpu2 {
#include "cpu_impl.cpp"
}
namespace cpu3 {
#include "cpu_impl.cpp"
}
...

Эм я правильно понимаю что эта VM способна выполнять только свои опкоды и не может вызвать например библиотечную ф-ю через POSIX ABI, тк для этого придётся потерять контроль над регистрами и стеком?

Нет, неправильно. Более того она делает именно это в своей процедуре Print которая вызывает обычный такой библиотечно-POSIX-вый printf(), просто сохраняя/восстанавливая несколько регистров, которые в любом случае пришлось бы сохранять по ABI.

Мы можем добавить еще опкодов которые будут делать любые сисколлы или библиотечные вызовы или даже один опкод который сможет делать любой сискол по номеру - ограничений нет

Не пробовали ли Вы избавитьcя от вызова cервисной функции по указателю из таблицы (routines) ? Что если сделать указатель сервисной функции просто вычислимым ? Скажем, разместить код сервисных функций в памяти с равным интервалом кратным степени 2 и вычислять адрес путем сдвига опкода и прибавления смещения. На мой взгляд это должно еще немного увеличить производительность, так как процессору не нужно будет постоянно заглядывать в свой кэш для получения указателя.

Я думаю, это блестящая идея! Стоит попробовать!

На самом деле, есть еще несколько интересных оптимизаций, которые можно было бы испробовать - одна из них - иметь два комплекта сервисных процедур: один для стека (top, subtop) а второй - для обратного ему (subtop, top).

Тогда процедура SWAP может не делать ничего кроме переключения с одного комплекта на другой. OVER тоже будет оптимизирован лучше в результате. Мы можем даже использовать "флаг направления (DF)" в процессоре для отслеживания какой комплект работает в данный момент.

Я предолагаю, что из-за этого предсказатель переходов будет предсказывать лучше, т.к. у него будет больше переходов и информационная нагрузка на один переход уменьшится. Приглашаю это проверить вместе.

Попробуйте пожалуйста, мне очень интересно каков будет эффект. :)

Я измерил размеры всех сервисных процедур:

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 команды. Может быть есть и другие предположения? Или есть способ написать ассемблерный код оптимальнее?

Код в отдельной ветке: https://github.com/rigidus/interpreters-comparison/tree/asmexp

Можно выровнять на 0x80, или даже на 0x40, если большие функции, типа Print, разбить на функции поменьше и основное их тело вынести в другое место.

Ну, или как вариант, сделать таблицу трамплинов

.align 8
jumps:
        jmp Opcode_Add
.align 8
        jmp Opcode_And
...
        // rcx = next opcode
        lea rax, [jumps + rcx*8]
        jmp rax

Двойной прыжок, но второй не косвенный, а прямой - конвеер должен понимать, какой код будет сразу после прыжка и начинать его выполнять

попробуешь провести экперимент? там в Makefile чтобы запустить бенчмарк достаточно

make measure

Я нашел время проверить, насколько трамплины замедляют выполнение, сделал таблицу трамплинов:

trampoline_table:
    jmp srv_Break
    .byte 0x90, 0x90, 0x90
    jmp srv_Nop
    .byte 0x90, 0x90, 0x90
    jmp srv_Halt
    .byte 0x90, 0x90, 0x90
    <....>
    jmp sr_Pick
    .byte 0x90, 0x90, 0x90

на старте ее адрес загружается в %rdi

dispatch теперь стал таким:

.macro DISPATCH
    lea    (%rdi, opcode64, 8), opcode64
    jmp    *opcode64
.endm

Вот результаты бенчмарка с размером задачи 100000 (как в оригинале). Интересующий нас столбец - asmtrm

В результате мы экономим пространство за счет времени исполнения (в asmexp все функции выровнены на 0x80, а в asmtrm - на 0x10). На моей машине L1 кэш инструкций составляет 704 килобайта, поэтому имеет смысл использовать трамплины для того чтобы иметь несколько наборов кода - пока мы попадаем в кэш.

Можно попробовать оценить, сколько можно иметь кодовых наборов. За образец можно взять виртуальную машину WASM, у нее однобайтовый опкод, на текущий момент занято где-то 200 команд, но можно брать по максимуму - 255.

Даже если кешировать три элемента стека (а не два, как сейчас) и мы хотим варианты наборов процедур для всех перестановок, нам нужно 6 вариантов. Тогда мы попадаем в этот кэш при среднем размере процедуры в 471 байт (что довольно много).

На практике не все опкоды из этих 255 работают со стеком, так что можно чувствовать себя еще свободнее. Но на машине @checkpoint c 32 килобайтами средний размер процедуры будет только 21 байт, что уже несколько стесняет, даже если мы будем расширять большие процедуры за счет тех что меньше среднего размера.

На этих бенчмарках вызов printf() не удалялся

На этих бенчмарках вызов printf() не удалялся

Таким образом Вы опять измеряете производительность операционной системы, а не своего алгоритма.

Хочу видеть результат без printf(). :-)

c 32 килобайтами средний размер процедуры будет только 21 байт, что уже несколько стесняет, даже если мы будем расширять большие процедуры за счет тех что меньше среднего размера.

Не понял, откуда такие цифры ? 32768 / 128 = 256 сервисных функций по 128 байт. Помоему это овердохрена. Сервисные функции длиной более 128 байт поделить на четыре отдельных опкода, но таких функций быть вообще-то не должно!

Вариант без printf() несложно получить, но я упорствую в своем глупом мнении, что printf() это правильная, реальная нагрузка, которая в числе прочего вымывает из кэша полезные для производительности линии.

(32*1024) / (255*6)
32килобайтный кэш / 6 вариантов всех 255 инструкций

Проблема с printf в том, что она не выполняется за константное время. Поэтому и результаты замера получаются смазанными.

Если вы хотите чтобы кэш процессора "вымывался", то стоит вызывать что-то другое, не работающее с I/O.

Еще одно замечения по методике измерения. Для чистоты эксперимента нужно убрать вызов Printf, иначе Вы замеряете производительность очень медленной библиотечной функции vfprintf, а также системного вызова write и кучу сопутствующего всякого разного.

Убирать нельзя, т.к. в исходной статье измерения проводятся вместе с printf. С другой стороны она не оказывает серьезного влияния на общий бенчмарк, т.к. вызывается всего лишь 9592 раз.

Очень даже оказывает.

Короче, я закоментировал вызов printf() в ассемблерном коде и увеличил задачу до 200000 чисел. Вот результат:

rz@butterfly:~/interpreters-comparison % time ./asmexp > /dev/null
26.451u 0.000s 0:26.45 100.0%	853+2895k 0+8io 0pf+0w

rz@butterfly:~/interpreters-comparison % time ./asmopt > /dev/null
32.203u 0.000s 0:32.20 100.0%	843+2896k 0+8io 0pf+0w

На моей машине (AMD Ryzen 5 5600H) вычислимый адрес сервисной функции дает прирост производительности почти на 23% по сравнению с косвенным вызовом. Проверьте пожалуйста самостоятельно, может быть я где-то напортачил.

Также рекомендую прогнать все остальные алгоритмы без вызова printf() и сравнить результаты.

Update:

Я немного поэкспериментировал с выравниванием сервисных функций по 0x80 и по 0x1000 байт (в Вашем коде 0x100 байт). При .align 0x80 время исполнения задания еще немного уменьшилось, до 24 сек. А вот при .align 0x1000 существенно возросло до 45 сек. Моё предположение было в том, что функции выравненные по границе страниц могут выполнятся быстрее, но это предположение оказалось ложным.

Можно ли ссылку на форк с изменениями?

Вот патч:

Патч для убирания вызова printf()
diff --git a/asmexpll.S b/asmexpll.S
index 968f140..f80b83c 100644
--- a/asmexpll.S
+++ b/asmexpll.S
@@ -106,7 +106,9 @@ handle_state_is_not_running:
 
 .macro DISPATCH
     # jmp     *(routines, opcode64, 8)
-    shl    $8, opcode64      # Умножить номер функции на 0x100
+    //shl    $8, opcode64      # Умножить номер функции на 0x100
+    shl    $7, opcode64      # Умножить номер функции на 0x80
+    //shl    $12, opcode64      # Умножить номер функции на 0x1000
     lea    (routines, opcode64), opcode64  # Добавить базовый адрес первой функции
     jmp    *opcode64         # Перейти по адресу, хранящемуся в %rdx
 .endm
@@ -306,7 +308,9 @@ sz_stack_underflow:
 .macro RTN name
     .global srv_\name
     .type srv_\name, @function
-    .align 0x100
+    .align 0x80 # This gives best result on AMD Ryzen 5
+    //.align 0x100
+    //.align 0x1000
 srv_\name:
     .if DBGCNT
     incq    cnt_\name(%rip)
@@ -372,6 +376,7 @@ end_of_\name:
       POP_IMM acc
     .endif
     BAIL_ON_ERROR
+/*
     push    %rdi
     push    %rsi
     push    %rcx
@@ -392,6 +397,7 @@ end_of_\name:
     pop     %rcx
     pop     %rsi
     pop     %rdi
+*/
     NEXT 1
     .section .data
 sz_fmt_str:
diff --git a/asmoptll.S b/asmoptll.S
index 8dd925d..2a43458 100644
--- a/asmoptll.S
+++ b/asmoptll.S
@@ -587,6 +587,7 @@ sz_divide_zero:
       POP_IMM acc
     .endif
     BAIL_ON_ERROR
+/*
     push    %rdi
     push    %rsi
     push    %rcx
@@ -607,6 +608,7 @@ sz_divide_zero:
     pop     %rcx
     pop     %rsi
     pop     %rdi
+*/
     ADVANCE_PC 1
     FETCH_DECODE
     DISPATCH
diff --git a/common.c b/common.c
index 85d4d50..9a8f931 100644
--- a/common.c
+++ b/common.c
@@ -37,7 +37,7 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
 
 /* Program to print all prime numbers < 10000 */
 const Instr_t Primes[PROGRAM_SIZE] = {
-    Instr_Push, 100000, // nmax (maximal number to test)
+    Instr_Push, 300000, // nmax (maximal number to test)
     Instr_Push, 2,      // nmax, c (minimal number to test)
     /* back: */
     Instr_Over,         // nmax, c, nmax

У меня вот такие результаты.

Не густо, но тоже результат. :)

Дайте мне свой код, я прогоню его на моей машине.

Прогнал этот вариант без внесения каких либо изменений. На моей машине результат прежний:

rz@butterfly:~/rigidus/interpreters-comparison % time ./asmexp > /dev/null
24.809u 0.000s 0:24.81 99.9%	848+2896k 0+8io 0pf+0w

rz@butterfly:~/rigidus/interpreters-comparison % time ./asmopt > /dev/null
36.961u 0.015s 0:36.97 100.0%	843+2896k 0+8io 0pf+0w

Это выборка из нескольких прогонов, с минимальным значением.

Моя машина - ноут Lenovo Ideapad Gaming:

Кажется что разница значительная, но на самом деле картинка вводит в заблуждение. Добавление native варианта позволяет сопоставить в масштабе

Вы задачу у native увеличить не забыли ? У меня native выполняется на этой задаче более 5 сек.

Да, volatile для всех переменных в цикле native тоже не забудьте. Иначе компилятор сожмет его до пустого цикла. :-)

Да, конечно, забыл, но в оправдание могу сказать, что я просто хотел чтобы ось Y начиналась от нуля, а то это получается "лгать при помощи графиков".

Сейчас я пытаюсь проверить, как распределение кода влияет на промахи кэша. Выше уже предложили (а я немного адаптировал идею), что если оставлять в начале сервисной процедуры только 16-32 байт кода, а до остального прыгать jump-ом то может быть это сможет дать лучшее попадание в кэш для тех процедур, которые не превышают эти 16-32 байта и не такую большую просадку из-за jump-а потому что он будет хорошо предсказываться.

Что-то получилось с трамплинами ?

Мне почему-то кажется, что лишний jump испортит картину.

Предлагаю проверить. Я немного занят рабочей задачей прямо сейчас, смогу вернуться к интерпретатору после ее решения

native без pintf() на этой же увеличенной задаче на моей машине дает 5.26 сек.

На самом деле, есть еще несколько интересных оптимизаций, которые можно было бы испробовать - одна из них - иметь два комплекта сервисных процедур: один для стека (top, subtop) а второй - для обратного ему (subtop, top)

Эта оптимизация скорее важна для Forth машин, для той же Жабы она скорее всего бесполезна.

Приглашаю это проверить вместе.

Я сейчас увлечен немного другой темой. Но тема VM тоже интересна как вариант минималистичной ОС для синтезируемой ЭВМ.

Я как раз читаю эту статью, принципы из ее начала резонируют с моим ощущением "как правильно". Я бы был заинтересован в изготовлении тестового стенда для опробования всего этого в железе и экспериментов

У меня в голове крутится идея сделать VM поверх получившейся синтезируемой ЭВМ, с примитивами для работы с периферией (клавиатурой, отображения на VGA монитор и тд). Forth не плохо подходит под эту тему. Еще мне нравится Inferno - это тоже байт-кодовая VM. Далее использовать её для всяких экспериментов в пром автоматизации, а также как персональную ЭВМ независимую от глобального стека ПО. Если Вам интересно позаниматься этой темой я могу выслать платку "Карно", их есть у меня. :)

Я хотел бы поучаствовать в этом совместном проекте. У меня давно зреет идея о FPGA-компьютере в формате клавиатуры, способном подключаться к экранам через HDMI и содержащем внутри себя Forth-машину, которую можно было бы разрабатывать и на обычном GNU/Linux/FreeBSD компьютере. Я запускал Plan9 очень давно и было бы интересно потестить Inferno и 9p-протокол снова

Я пробовал Plan9 и Inferno в конце 90-х. Да, с тех пор запало в душу. Короче, присылайте свой адрес в личку. :)

Несколько месяцев назад в комментариях прорабатывали версию кеширования верхушки стека в регистрах, но так, чтобы на каждую глубину стека, загруженную в регистры, был свой вариант обработчиков байт-кода. Тогда DROP - это просто NO-OP (переход на ветку с меньшей глубиной стека в регистрах), какой-нибудь ADD - это add rax, rbx с переходом на другую ветку. Получается довольно интересно по скорости, но с большим гемором в реализации интерпретатора, кучу дублирующегося кода надо писать руками.

Спасибо за ссылку, там интересные идеи. Я думаю стоит написать генератор, который смог бы для каждого варианта стека из обычного набора сервисных процедур сгенерировать несколько стекозависимых. Это было бы интересно обсудить

Мне кажется все варианты всех опкодов на все возможные глубины стека быстрее написать руками, чем пытаться создавать обобщённый генератор.

Мне больше нравится обобщенное решение, т.к. я не уверен в своей способности не внести каких-нибудь багов по невнимательности. Особенно когда мы делаем несколько вариантов одной и той же реализации ВМ под разные процессоры: x86_64, ARM, RISC-V...

Было бы интересно играться размером вершины стека, которая лежит в регистрах, а также стратегией передвижения окна. Например, если все регистры заняты, вытеснить в память только 1, а все остальные сдвинуть, или вытеснить половину, чтобы вытеснения были пореже. А может, выгодно вытеснять сразу 3/4? Аналогично с обратным процессом - если кеш опустел, подгружать по 1 регистру, или сразу 6, чтобы пореже на это отвлекаться.

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

Попробуйте сравнить скорость самогобыстрого интерпретатора со скоростью интерпретатора в OpenJDK. Многие гениальные идеи отпадут сами собой.

Я взял код из native.c и переписал его на Java

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-код не в состоянии обогнать оптимизированный интерпретатор байткода.

Вы всерьез ожидали иного результата?

Вы посчитали еще подьем, инициализацию JVM. А она очень толстая.

Запуск java-машины очень дорогой процесс. Сравните время "gcc --version" и "java --version". При старте java-машины выполняется инициализация контекста. Как-то делал замер, и у меня получилось что-то вроде ~20 млн. байт-код инструкций - это только инициализация. Обработка "--version" потребует все несколько десятков инструкций. Причем много функций исполняется 1-2 раза. Однако jit-компилятор пытается многие из них оптимизировать. В итоге время компиляции не окупается, так как нативная версия функции может вообще не исполнится ни разу. Поэтому действительно "java --version" работает медленнее, чем "java --version -Xint". Но это классическая проблема любой jit-системы, выигрыш от исполнения оптимизированной версии должен перевесить время, затраченное на компиляцию. А это бывает не всегда. Для любой jit-системы можно найти анти-патерн.

Вывод - учите матчасть.

java запускалась без jit-компиляции. В обоих случаях измеряется полное время программы, с любой подготовкой контекста, запуском и остальными приготовлениями.

Ок, было сказано, что

> Java-код не в состоянии обогнать оптимизированный интерпретатор байткода

А где сказано, что количество байт-код инструкций при обоих сравнениях одинаковое, и где обоснования, что семантика байткод инструкций идентичная?

Как без этого можно утверждать, что один интерпретатор быстрее, и Вы всерьез полагаете, что в OpenJDK не оптимизированный интерпретатор?

Просто абсолютное общее время работы не говорит само по себе ни о чем.

Я пожалуй воздержусь от спора. Иначе тут будет затратное мероприятие по отводу аргументов лернейской гидры - с одним справился, тут тебя еще десятью закидают :) Специалист извлечет для себя методы и подходы из статьи, баталии в комментариях - это непродуктивный спор с теми, кто, к сожалению, не сможет улучить время в бенчмарке.

Полностью с Вами согласен. Нужно любые утверждения из всех научных статей принимать сугубо на веру. В заголовке же написано про наиболее быстрый интерпретатор среди всех возможных, значит так оно и есть! Вопросы - да зачем? А всех этих дармоедов из OpenJDK, CoreNET и V8/Chrome надо разогнать к чертям собачьим.

Ну вообще написано про быстрейший из рассмотренных, а "среди всех возможных" -- это вы сами выдумали. Хотите опровергнуть -- ну так напишите 9-й, быстрейшей из этих 9. Или хотя бы укажите на неоптимальности в этом. По мне, так прекрасная статья, показывающая, как правильно подходить к оптимизации, написанная легким для чтения языком (как и предыдущая, которую она дополняет).

Я так понимаю, вы разбираетесь с том, какие техники оптимизации применены в интерпретаторе JVM, ну так может напишите статью об этом? А если сохраните тот же легкий стиль изложения, как у вышеупомянутых авторов, цены ей не будет.

Не являюсь разработчиком JVM, хотя действительно в свое время не мало просидел в отладчике gdb и над кодом генерации кода интерпретатора, и над уже сгенерированном в памяти кодом самого интерпретатора. Не меньше, если не больше времени просидел в отладчике gdb над кодом генератора Baseline транслятора в Firefox. Медитировал над исходными кодами. Что было, то было :). Разработал даже как-то интерпретатор одного регистрового байткода целиком на ассемблере для одного процессора со статическим планированием :)). С производительностью близкой уже к шаблонному транслятору. И это тоже было.

Теперь, что касается данной статьи и моих начальных "оценок". Тут я с "оценками", мдя, но не буду о грустном :). Все что автор рассказал про свой интерпретатор, все классно. Технологии им примененные и достигнутый результат (для одной конкретной стековой машины) достойны серьезных похвал. Кстати, как и достижения разработчиков JVM. И разработчиков V8.

Но вот когда в конце статьи целиком и полностью посвященной одному конкретному интерпретатору, пусть и наиболее быстрому, делается вывод о JIT-компиляции. Хм. А где в статье разбор jit-компиляции-то, чтобы выводы о ней делать? Поскольку интерпретатор наиболее быстрый, то jit-компиляция ... А что собственно jit-компиляция-то?

Не будь таких выводов о jit/aot - и это была статья с совсем другим посылом.

Но ведь в статье каких-то выводов о JIT/AOT нет, лишь замечание о том, что усилия по их написанию могут оказаться неадекватными полученному ускорению, в некоторых случаях может оказаться быстрее написать правильно оптимизированный интерпретатор, чем правильно оптимизированный JIT/AOT. Ведь в оригинальной статье последним рассматривался примитивный JIT.

Вот под вашим комментарием автор действительно не учел, что старт JVM тоже какое-то время занял и он померял не только алгоритм.

Как рассказывали знающие люди, еще в самом начале пути, разработчики java-машины были уверены, что им достаточно сделать только интерпретатор. Это сейчас говорим java-машина, а подразумеваем jit-компилятор. Но так было не всегда. Однако, очень быстро разработчики убедились, что jit-компилятор делать придется. И да, производительности много не бывает. Поэтому разработчики java-машины (лет 40 назад?) уже наступили на эти грабли. И нет, сколь угодно быстрого интерпретатора недостаточно.

Можно сказать, ну всегда найдутся ниши там где производительность не важна. Ну во-первых что это за ниши такие и кому это будет интересно? А во-вторых, а зачем тогда быстрый интерпретатор, производительность-то не важна? Да и дело в экосистеме. Кого, как, куда и кто пересадит на совершенно новую ВМ? И Зачем?

блин, арифметика, конечно "лет 30 назад"

От специалиста который провел не одну ночь в gdb я хотел бы услышать более аргументированное обьяснение того, почему JIT выигрывает над "до предела заоптимизированной" JVM. Делательно, с примерами машинного кода, что во что компилируется, и сопоставить это с тем как реализовано в JVM. Короче, с Вас ответная статья. :)

Вам не очевидно, что любой интерпретатор будет проигрывать native? Хотя бы потому что, процессору приходится выполнять в разы больше инструкций для выполнения одного и того же действия.

Нет, не очевидно, так как не понято в какой именно набор инструкций компилирует JIT. Так как нативная платформа существенно отличается по "архитектуре" от виртуальной, то преобразование одной в другую сожрет существенную часть производительности.

Предполагается, что jit хороший, долгий проект, где все очевидные оптимизации сделаны. И интерпретатор байт-кода такой же хороший, оптимизированный.

преобразование одной в другую сожрет существенную часть производительности

Только jit будет нести расходы на несоответстие vm и архитектуры в compile-time, а интерпретатор - в run-time.

Но время работы компилятора тоже не бесплатное.

Кроме того, существуют языковые конструкции, которые по самой своей природе не поддаются компиляции (например, когда программа меняет синтаксис или семантику своего собственного языка в ходе исполнения). И это не абстрактная казуистическая возможность, хотя и не имеет прямого отношения к теме обсуждения.

Могу предложить контр-аргумент: есть конструкции, которые не могут быть эффективно выражены в байт-коде (из-за его фиксированного набора опкодов), но для которых есть инструкции на целевой архитектуре, и компилятор может использовать их, распознав некоторый знакомый паттерн. Наиболее частый пример - авто-векторизация.

Я вовсе не пытаюсь сказать, что компилятор вообще бесполезен. Я говорю только о том, что сравнительная эффективность компиляции и интерпретации может быть разной в зависимости от конкретного обрабатываемого кода.

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

Скорее наоборот, нативный код является предельным частным случаем интерпретатора, когда байт-код + интерпретатор кладут в чёрный ящик и объявляют "нативной реализацией". Поэтому "нативная реализация" всегда будет как минимум не хуже интерпретатора.

Нативный код – да, но мы же сравниваем эффективность выполнения данной нам программы на входном языке (или байткоде), а не эффективность уже полученного из неё машинного кода в сравнении с интерпретацией ещё не обработанного байткода. Чтобы получить нативный код, сначала должен отработать компилятор, что составляет весьма значительные начальные затраты.

Компилятор можно крутить в разные стороны: дольше компилировать / быстрее выполнять, а то и вообще стартовать на интерпретаторе и в фоне компилировать. У интерпретатора нет такой гибкости.

Ну я и говорю, что интерпретатор - это выкрученный в ноль компилятор.

Элементарно есть масштабируемость по количеству итераций цикла? Когда внутренний цикл погружаем во внешний, чтобы исключить постоянные накладные расходы на раскрутку.

При старте java-машины происходит инициализация стандартной java-библиотеки. Java-библиотека написана на java ("ДБ." Лавров.) И это дорогой процесс. А только потом "пролетает" код собственно примера.

ДОПОЛНЕНИЕ. Хотя не-а, похоже я сильно ошибся, насчет сложности старта java-машины. Либо в примере должны быть import'ы или new Object.

Увеличил счетчик в цикле в 2 раза (i < 2*100000)

$ time java Main > /dev/null

real 0m6,139s


$ time java -Xint Main > /dev/null

real 0m22,493s


Нативный код из-под java-компилятора быстрее java-интерпретатора. Вы ожидали иного результата?

В этой статье мы сравниваем не интерпретируемую джаву с компилируемой а разные способы создавать интерпретаторы байткода.

Подождите следующей статьи :)

Михаил, конечно большинство моих комментариев были идиотскими (впрочем может как и этот), но и они отчасти есть следствие очень неаккуратных формулировок

> Является ли JIT (или AOT) - нашей последней надеждой на производительность? Думаю, я смог ответить на этот вопрос.

> Вывод: Java-код не в состоянии обогнать оптимизированный интерпретатор байткода.

В x86-процессоре есть предсказатель переходов. Но если код интерпретатора фиксирован, и исполняется не только маленький цикл интерпретируемой программы, то и такой планировщик не панацея.

Шаблонный транслятор tier-1 раскручивает байткод в прямые последовательности в пределах одного линейного блока. Это идеальная ситуация для аппаратного планировщика. И даже на переходах из байткода ситуация на порядок станет лучше.

Кроме того, jit-компиляторы уровня tier-2 в jit-языках, на мой взгляд, чаще занимаются не столько архитектурными оптимизациями, сколько оптимизациями этих самых языков. (Особенно это наглядно для языков с динамической типизацией.) Но и архитектурными оптимизациями тоже. Так tier-2 компиляторы преобразуют стековый байткод в регистровое промежуточное представление (в пределах линейного блока). Ну про инлайн и не вспоминаем (его и на байткоде делать можно). А нативный код, полученный из регистрового представления лучше планируется и быстрее исполняется из-за аппаратных особенностей.

$ time java Main > /dev/null

real 0m6,139s

$ time java -Xint Main > /dev/null

real 0m22,493s

Эти результаты, кстати, очень хорошо перекликаются с тем, что выдают варианты native и asmexp. Попробуйте запустить тест native, asmopt и asmexp из моего репозитория (ветка noprintf), интересно какие будут абсолютные цифры на Вашей машине. Сравним их JVM и JIT.

В статье приведен другой репозиторий. В чем отличие? Чем asmoptll.S отличается от asmexpll.S? Что должны демонстрировать тесты native, asmopt и asmexp?

Почитайте выше мою переписку с автором. В asmexp реализован вычислимый способ получения адреса сервисной процедуры, без заглядывания в таблицу. На моей машине (ноутбук с AMD Ryzen5) этот метод на 23% быстрее чем asmopt. У автора почему-то этот результат куда более скромный. Интересно какой будет у Вас. Ну и сравним его с JIT и JVM.

В моём репозитории для способов native, asmopt и asmexp отключен вызов printf, а задача увеличена до 300000 числе. Это делает эксперимент более точным.

В репозитории из статьи взял ветку asmexp:

$ time ./asmopt > /dev/null
real 0m7,739s

$ time ./asmexp > /dev/null
real 0m8,787s

$ time ./native > /dev/null
real 0m1,253s

Попробуйте пожалуйста ветку noprintf. Там задача 300000 чисел и отключен вызов printf.

Update:

На моей машне Java без printf на задаче в 300000 чисел дает такой результат:

rz@butterfly:~/interpreters-comparison % time java -Xint Main
31.386u 0.055s 0:31.43 100.0%	5+167k 0+4io 0pf+0w

rz@butterfly:~/interpreters-comparison % time java Main
5.340u 0.031s 0:05.36 100.1%	17+171k 0+4io 0pf+0w

JIT вариант ожидаемо дает результат близкий к native, а вот JVM существенно проигрывает asmexp (22s) и близок к asmopt (32s). Хочу увидеть эти же тесты на других машинах. Есть основания полагать, что вариант предложенный автором + моя идея с вычислимым адресом, несколько более эффективен. Но результат сильно зависит от конкретной модели микропроцессора.

Возможно не совсем корректно убирать печать. Я еще не проверял, но могу продположить что Java-вариант должен оптимизировать

if (isPrime) System.out.printf("[%d]\n", i);

убирая соответствующие байткоды, а в отключенном asmexp убирается только сам вызов функции, судя по патчу, накладные расходы остаются

Разумеется тупо закоментировать printf() ни к чему хорошему не приведет - компилятор соптимизирует цикл. Я ввел переменную в которую суммирую результат, этого оказалось достаточно.

Java код без printf()
public class Main {
    public static void main(String[] args) {
	int res = 0;
        for (int i = 2; i < 300000; i++) {
            boolean isPrime = true;
            for (int divisor = 2; divisor < i; divisor++) {
                if (i % divisor == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
                res = res + i; //System.out.printf("[%d]\n", i);
        }
    }
}

В asmexp убран вызов библиотечной функции, сам опкод для печати остается, но он ничего не делает. Это равносильно суммированию в Java коде.

Возможно res стоит возвращать: я не знаю насколько умный компилятор Java но он может соптимизировать цикл т.к. res нигде не применяется

Я проверил - c res не оптимизирует, а без неё - да. :)

Судя по ассемблерному коду который привел пользователь @e2k_sid в своей ответной статье, явовскому JIT компилятору (и JVM) до оптимума еще как до Китая пешим драпом. Честно говоря я был неприятно удивлен.

$ time java Main > /dev/null
real 0m1,786s

$ time java -Xint Main > /dev/null
real 0m6,686s

model name : Intel(R) Xeon(R) CPU E5-2690 v2 @ 3.00GHz
openjdk 11.0.6 2020-01-14

Кстати, 6.7 s на openjdk - это меньше, чем 7.7 s на asmopt.

Кроме того мой комментарий был про то, что прежде чем в очередной раз изобретать велосипед, то есть придумывать самыйбыстрый интерпретатор байт-кода стекового представления, прежде хорошо изучите устройство и принципы работы таких интерпретаторов, как интерпретатора байт-кода в OpenJDK.

Хотя должен также предупредить, что в виде C++ или даже asm-кода его в исходных кодах проекта Вы не найдете :), там есть только C++-код генерации кода интерпретатора :))). Но когда это останавливало нас, профеcсионалов :))?

И хотя Baseline в Firefox - это по сути шаблонный транслятор, включающий при этом паттерны динамической детипизации (JS - ужасный язык), но в плане работы со стековым байткодом, Baseline как брат-близнец похож на генератор интерпретатора в OpenJDK. Предполагаю, что и в CoreNET и V8/Chrome принципы быстрой интерпретации стекового представления схожи. Коммуниздят идеи друг у друга и не краснеют :).

Если исходить из научного дискурса, поиска знаний.

То было у меня такое исследование - сделать интерпретатор регистрового представления. В компилятор javac (из OpenJDK) сделал патч, в рамках которого из Java-AST вместо стандартного байткода стандартной стековой машины создавался регистровый байткод самопальной виртуальной машины. Утверждать о корректности сравнения конечно не могу, кроме просто интерпретации кода есть еще семантика стандарта исходного языка. Но в первом приближении, можно предполагать, что удалось достичь паритета между стековым интерпретатором из OpenJDK и регистровым интерпретатором из самопальной ВМ. При этом интерпретация одной регистровой инструкции конечно занимает больше времени, но в среднем регистровых инструкций меньше. Вот и вышел баш на баш.

При написании регистрового интерпретатора пришлось долго "воевать" с компилятором gcc, чтобы заработали jump'ы из asm-вставок и ручное распределение части указателей на регистры (gcc все норовил сделать ряд оптимизаций).

Поэтому с научной точки зрения, опираясь на очень косвенные данные, можно осторожно предположить, что для x86, то есть out-of-order процессора (arm/mips сюда же видимо), производительности стекового и регистрового интерпретаторов в общем и целом равны, если каждый из интерпретаторов достаточно оптимизирован. Но это как отправная точка для исследования.

В этом смысле, разработчики OpenJDK/Firefox/CoreNET/Chrome вложили очень много сил и времени в разработку быстрых интерпретаторов стековых машин. И с наскоку их обойти, ну наверное, не то чтобы не получится, но затруднительно. Хотя может и получится. Но нужны корректные сравнения и легко читаемые "проценты".

>> прежде хорошо изучите устройство и принципы работы таких интерпретаторов, как интерпретатора байт-кода в OpenJDK.

Давайте перейдем в более конструктивную плоскость. В этой статье были изложены принципы оптимизации интерпретаторов, которые дают измеримый эффект для производительности. Я бы хотел узнать, какие принципы могут еще улучшить перформанс (неважно откуда они будут - из OpenJDK или других источников). Можете поделиться?

Михаил, если говорить про реализацию интерпретатора конкретно для вашего стекового байткода, то наверное, действительно ваша реализация будет самой эффективной. Особенно при условии что берутся маленькие циклы на байткоде. И скорее всего вы действительно достигли эффективности шаблонного транслятора, и в этом достижение серьёзное. Однако на более разнообразном байткоде шаблонный транслятор за счёт аппаратного планировщика скорее всего даст лучший результат.

Что касается сравнений. Если была бы речь про то, что ваша реализация, например, java-машины как системы целиком быстрее, то тогда понятно. Берем одинаковые Java программы и сравниваем общее время для двух машин. Но при этом гарантируем для программистов идентичную семантику java-программ. Но все равно это про системы целиком. И тогда могут сравниваться подходы в целом.

В общем, подобное надо сравнивать с подобным. Если сравниваются два интерпретатора, то у них должны быть одинаковые байт-код программы на входе. Ну и по-хорошему идентичная семантика. Иначе это сравнение в непонятных попугаях. Тогда некорректно говорить, что один быстрее другого. У них контекст разный. Именно как интерпретаторов а не VM.

При этом в целом возможно ваши подходы в чем-то и эффективней подходов из openjdk. А может они сопоставимы по эффективности. А может у OpenJDK чуть эффективней.

Однако в любом случаи, когда вы, Михаил, в конце статьи переходите к обобщающему выводу относительно jit-компиляторов доводов не хватает. Собственно вот что "зацепило" именно меня :). И это безотносительно ваших реальных достижений по созданию очень быстрого интерпретатора для конкретного стекового представления.

«А мне тут вообще всё не нравится».

Это про меня. :)

Очень интересное исследование получилось! Мой оригинальный проект был нацелен на то, чтобы быть иллюстрацией методов интерпретации для студентов, а также как упражнение для них по изменению некоторых аспектов работы интерпретаторов. Мне тогда не пришло в голову давать кому-то задачу по дальнейшей профилировке и ускорению.

У меня есть один комментарий по поводу следующего утверждения из статьи:

Рекомендация компилятору привязать одну глобальную переменную к регистру - это только рекомендация, и компилятор может ее проигнорировать.

В случае с GCC и расширения asm("reg-name") это не так. Компилятор действительно перестаёт использовать указанный регистр для своих целей. Фактически, за модификации в ABI после этого отвечает сам программист.
Можно даже поставить компилятор в тупик и заставить его отказаться от компиляции кода, в котором важные для ABI регистры были у него "забраны". Например, если прибить RBP на x86-64, то компиляция с --coverage становится невозможной. GCC хочет использовать RBP для stack frame, который необходим для инструментации покрытия кода.

Пример, хотя конкретно здесь я не смог --coverage сломаться. Но в реальном проекте с более хитрыми ограничениями на хостовые регистры эта проблема всплывает.

atakua@localhost:~$ cat no-stack-frame.c 

register long long a asm("%rbp");
int main() {
    return (int)a;
};

atakua@localhost:~$ gcc no-stack-frame.c 
no-stack-frame.c: In function ‘main’:
no-stack-frame.c:4:5: error: frame pointer required, but reserved
    4 | int main() {
      |     ^~~~
no-stack-frame.c:1:20: note: for ‘a’
    1 | register long long a asm("%rbp");
      |                    ^

atakua@localhost:~$ gcc -fomit-frame-pointer no-stack-frame.c 
# OK

Спасибо за уточнение и, конечно, за оригинальную статью, она вдохновляет.

Мне кажется в этой теме еще довольно много пространства для работы студентов: не только оптимизация, но и, например:
- написание отладчика байткода,
- сэмплирующего профайлера,
- инструмента для определения целей для Instr_Jump, Instr_Je и Instr_Jne, чтобы правильно собирать суперинструкции,
- сама сборка суперинструкций,
- и наконец, jit-компилятор, опирающийся на профилировку времени исполнения.

Уже хватит на несколько курсовых, ну или семестровых работ - я не знаю актуальный уровень студентов. У меня ушло где-то две недели по вечерам на написание ассемблерного интерпретатора, допускаю что среднему студенту потребуется больше времени.

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

Что-то из этого (или даже все) я бы с удовольствием прочел на хабре.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории