Совершать невозможное и раздавать пинки здравому смыслу — в этом и состоит жизнь членов Гуррен-Дана! (C) Камина
Эта статья вступает в техническую полемику со статьей 2015 года за авторством Atakua, подходы из которой я и атакую. Atakua исследует 7 видов интерпретаторов байткода, но делает это без уважения - быстрейшей оказывается двоичная трансляция, которая, по сути, уже не интерпретатор байткода, а форма Ahead-Of-Time компилятора. Эта двоичная трансляция транслирует байткод в машинный код, представляющий собой цепочку вызовов скомпилированных сервисных процедур. Тех самых, что в интерпретаторе байткода отвечают за выполнение каждого опкода.
Но Atakua не выжал из интерпретаторов байткода всю скорость которая возможна. Так что эта статья - туториал: как написать интерпретатор байткода, который может обгонять JIT/AOT-компиляцию по скорости. Интересно? Читайте дальше!
Бенчмарк прилагается. Будет немного хардкора и ни одной сгенерированной нейросетью картинки!
Для затравки посмотрим на гистограмму. Я использую бенчмарк Atakua, добавив в него свои результаты. Самый правый, он же самый маленький синий столбец (native) - это нативный код, данный Atakua в качестве оценки пределов оптимизации. Он не вполне корректен для оценки, потому что в нем нет проверок на количество шагов, границ стека, счетчиков вызываемых процедур и прочих атрибутов виртуальной машины - просто демонстрация минимального предела времени для выбранного алгоритма нахождения простых чисел.
Мои результаты отмечены красным цветом. Да, я смог обогнать двоичную трансляцию. Втрое.
Почему это важно и кому это нужно?
Потому что интерпретатор байткода - это один из лучших способов реализовать среду выполнения "на месте". Это позволяет решать много проблем элегантным способом. Например?
чтобы добавить в свой продукт скриптовый язык для автоматизации действий пользователя,
для разработки варианта регулярных выражений для анализа не текста, а последовательностей событий, которые приходят из телеметрии мобильного приложения - с миллионов устройств и в реалтайме,
для портирования abandonware на современную архитектуру (эмуляторы),
создания безопасных "песочниц" для исполнения и эвристического анализа недоверенного кода,
разработки системы плагинов для вашего нового браузера,
вы делаете кросплатформенное приложение, и ищете способ писать минимум архитектурно-зависимого кода,
вы пытаетесь заставить работать смартконтракты Ethereum в не предназначенном для них блокчейне Solana,
пишете утилиту инструментирования кода, программный монитор или эмулирующий отладчик для свежеиспеченного System-On-Chip,
избавляете человечество от головной боли поиска драйверов,
пишете свой Форт для собственного удовольствия.
Почти серебряная пуля, судя по широте применений!
Все это требует понимания, насколько быстрым может быть интерпретатор байткода. И знание методов, как его сделать быстрым. Особенно, если вы не готовы применять тяжелую артиллерию вроде JIT-компиляции и хочется обойтись "малой кровью".
Эта статья поможет вам понять, как написать, возможно, самый быстрый интерпретатор байткода.
Давайте немного восстановим контекст. Вот картинка из статьи Atakua, которая все объясняет (если нет - то стоит освежить в памяти его статью)
Его tailrecursive-вариант хорош: он демонстрирует лучшую скорость среди его интерпретаторов. Почему? Потому что в конце каждой сервисной процедуры находится то, что фортеры называют "NEXT": инлайненный код трех операций: ADVANCE_PC, FETCH_DECODE, и, наконец, DISPATCH. Этот последний DISPATCH и выполняет хвостовой вызов.
Почему этот способ быстрейший? Процессорный предсказатель ветвлений ассоциирует с каждым переходом историю. История улучшает предсказания. В последовательности команд байткода есть логика: например, за процедурой сравнения обычно выполняется процедура условного перехода. Таким образом, у каждого хвостового DISPATCH появляются предположения о том, куда ему нужно будет прыгнуть. Эти предположения известны еще до того как этот прыжок начнет выполняться. Поэтому процессор начинает выполнять следующую команду заранее, ну а если не угадал - можно просто отбросить результаты выполнения.
Atakua проделал отличную работу, подведя нас к реализации tailrecursive виртуальной машины, для чего, конечно же, надо было рассмотреть все предыдущие варианты (они тоже интересные). И теперь мы можем продвинуться дальше.
Попытаемся глобально оптимизировать всю программу: наша задача хорошо подходит для этого, потому что сама программа, т.е. интерпретатор байткода - компактна.
Для начала можно сделать все данные состояния интерпретатора глобальными переменными. Это позволит сэкономить на передаче параметров функций, их прологах и эпилогах, сохранении и восстановлении регистров. Хвостовым вызовам не нужны адреса возврата, поэтому нам не нужны call/ret, а все вызовы внутри сервисных процедур и так встраиваются (inline).
Тут мы как раз и можем побить компилятор, оптимизации которого локальны. Глобальный анализ любой программы потребовал бы от компилятора анализировать слишком много путей выполнения. Но, в отличии от компилятора, мы точно знаем, что в tailrecursive все пути выполнения имеют общий паттерн - сервисные процедуры прыгают одна в другую до тех пор, пока не достигнут Halt или Break. Тут мы умнее, или, лучше сказать, более информированы, чем компилятор, который вынужден действовать в ограничениях наиболее общего сценария.
Посмотрим на структуры данных, которые управляют состоянием виртуального процессора и виртуальной машиной в целом:
typedef uint32_t Instr_t;
typedef enum {
Cpu_Running = 0,
Cpu_Halted,
Cpu_Break
} cpu_state_t;
/* Simulated processor state */
typedef struct {
int32_t sp; /* Stack Pointer */
uint64_t steps; /* Statistics - total number of instructions */
uint32_t stack[STACK_CAPACITY]; /* Data Stack */
uint32_t pc; /* Program Counter */
const Instr_t *pmem; /* Program Memory */
cpu_state_t state;
} cpu_t;
/* A struct to store information about a decoded instruction */
typedef struct {
Instr_t opcode;
int length; /* size of instruction (1 or 2 for our bytecode) */
int32_t immediate; /* argument of opcode if exists */
} decode_t;О, Atakua написал очень минималистичную виртуальную машину! Что если мы перенесем все это в регистры? Тогда наша виртуальная машина в процессе своей работы сможет вообще не трогать память (кроме стека):
#define sp %rsp
#define steps %r8
#define pc %r9
#define prog_mem %rsi
#define state %r15
#define opcode64 %rdx
#define opcode32 %edx
#define immed64 %r14
#define immed32 %r14dВ оригинальной виртуальной машине Atakua стек 32-разрядный и может содержать до 32 значений. Это то, с чем приходится жить: если сделать иначе, то сравнительный бенчмарк станет нерелевантным. Но при реализации такого стека "в лоб" нужно иметь дело с массивом, доступ к которому будет выполняться с помощью комбинации базового адреса стека и смещения ячейки стека. Это менее оптимально, чем использовать 64-разрядный стек хозяйской машины. Поэтому ради оптимизации, можно поменять способ работы со стеком:
использовать 64-разрядные элементы стека вместо 32-разрядных, оставляя верхние биты нулевыми,
в качестве смещения использовать указатель стека в регистре %RSP (смещения станут кратными размеру элемента стека)
Таким образом, мы убираем код, который вручную пересчитывает указатель стека, используя вместо него инструкции процессора, которые одновременно помещают/удаляют элемент стека и изменяют %RSP. Так мы упрощаем адресацию и выигрываем в скорости в самом "горячем" коде стековой машины - работе со стеком.
Все эти части интерпретатора работают вместе, улучшение производительности в одном аспекте открывает возможности для улучшения в другом. При этом, оптимизируя интерпретатор, мы ничего не меняем в самой виртуальной машине. Для устранения неоднозначности приведу тут объяснение от ruv:
Следует разделять понятия "машины" (или "виртуальной машины") и "среды исполнения" ("исполняющей среды") для этой машины.
Понятие "стековая машина" (или, "виртуальная стековая машина") подразумевает, что инструкции этой машины берут параметры со стека и кладут результаты на стек. Стек — часть виртуальной машины. Разные стековые машины имеют разный формат "исполняемого" кода.
Код "исполняемый" в кавычках, потому что есть вопрос в том, кто/что его исполняет. Если его исполняет реальный CPU напрямую, то это действительно исполняемый код. Иначе, этот код исполняется другой программой. В Форт-терминологии эта программа называется "адресный интерпретатор", для байткода она будет называться "интерпретатор байткода".
Интерпретатор — часть среды исполнения. Сервисные процедуры, которые реализуют инструкции машины — тоже часть среды исполнения. Детали реализации разных частей среды исполнения завязаны друг с другом — т.е., если изменить реализацию адресного интерпретатора, может понадобиться изменить и сервисные процедуры.
Для одной и той же виртуальной машины (и формата кода) могут быть сделаны разные исполняющие среды.
Формат кода (шитый код, подпрограммный код, байткод, и т.п.) характеризует виртуальную машину, а не исполняющую среду.
Детали реализации адресного интерпретатора (если он есть) — характеризуют исполняющую среду, а не виртуальную машину.
Если адресный интерпретатор использует стек — то, формально, это другой стек, не стек стековой машины. В некоторых случаях сам адресный интерпретатор (или интерпретатор байткода) может быть конечным автоматом и вообще не использовать стек.
В нашем случае сам интерпретатор не использует стек, поскольку он построен на хвостовых вызовах и не нуждается в стеке для вызова следующей сервисной инструкции. Только одна сервисная процедура (Print) использует стек классическим способом - для вызова printf(), остальные используют стек для манипулирования данными, с которыми работает байткод виртуальной машины.
Есть еще одна важная вещь для стека - его границы. Поскольку они проверяются при каждой операции со стеком, мы тем более должны положить их в регистры. Значения границ должны быть вычислены при старте виртуальной машины, перед началом исполнения байткода.
/* Удобно запомнить, если воспринимать "b" в имени регистра как "border" */
#define stack_max %rbp
#define stack_min %rbxЧто еще (часто используемого) можно положить в регистры, чтобы интерпретатор работал быстрее? Остались две вещи: первая - это ограничение на количество шагов которое может сделать интерпретатор, а вторая - это базовый адрес массива указателей на процедуры. Каждая из этих процедур обслуживает свой опкод виртуальной машины.
#define steplimit %rcx
#define routines %rdiОтлично! Мы разместили все переменные в регистрах и у нас даже остались лишние регистры. Два из них можно занять под часто используемые константы:
# 1 = Cpu_Halted
#define one %r11
# 2 = Cpu_Break
#define two %r12И еще остается два регистра, которые можно использовать чтобы кэшировать два верхних элемента стека. Это используется при реализации форт-машин и помогает улучшить производительность часто выполняемых SWAP и OVER. Ниже я покажу эту технику в деталях.
#define top %rax
#define subtop %r10Обратите внимания на выбор %RAX в качестве регистра, который кэширует вершину стека (top). Некоторые машинные команды, такие как DIV, используют регистр %RAX в качестве неявного операнда. И если мы уже имеем операнд на вершине стека, его не придется загружать, что сэкономит нам одну команду ассемблера в реализации сервисной процедуры MOD далее.
Итак, мы заняли все регистры, кроме одного. Назовем его "аккумулятор" и будем использовать в случае необходимости:
# define acc %r13
И на третий день Бог создал "Ремингтон" со скользящим затвором, чтобы человек стрелял в динозавров и прикладных программистов... Аминь! (с)
"Но подождите!" - скажет человек с компилятором, - "Разве мы можем вручную распределить все регистры, не оставив ни одного компилятору? Даже Atakua в своей двоичной трансляции прибил только одну переменную к регистру %r15!"
Рекомендация компилятору привязать одну глобальную переменную к регистру - это только рекомендация, и компилятор может ее проигнорировать. Но вот прибить все регистры - это уже троллинг. Поэтому, пощадим чувства компилятора и расчехлим ассемблер. Какой ассемблер использовать? Конечно мы будем использовать ассемблер, предназначенный служить бэкендом GCC, а не для того чтобы на нем писал человек. Ассемблер с вывернутым наизнанку порядком операндов, настолько взрывоопасный, что это даже отражено в его названии: GAS.
Итак, каждая сервисная процедура у Atakua заканчивается следующей последовательностью:
ADVANCE_PC();
*pdecoded = fetch_decode(pcpu);
DISPATCH();..и этот код повторяется чуть менее чем везде и представляет собой отличного кандидата для оптимизации. Что же в нем происходит?
#define DISPATCH() service_routines[pdecoded->opcode](pcpu, pdecoded);
#define ADVANCE_PC() do { \
pcpu->pc += pdecoded->length; \
pcpu->steps++; \
if (pcpu->state != Cpu_Running \
|| pcpu->steps >= steplimit) \
return; \
} while(0);
static inline decode_t fetch_decode(cpu_t *pcpu) {
return decode(fetch_checked(pcpu), pcpu);
}Decode помещает текущую инструкцию в переменную opcode и вычисляет её длину. Если инструкция имеет непосредственный операнд, который следует за ней, то он помещается в переменную immediate. fetch_checked проверят не вышел ли program_counter за пределы байткода программы:
static inline Instr_t fetch_checked(cpu_t *pcpu) {
if (!(pcpu->pc < PROGRAM_SIZE)) {
printf("PC out of bounds\n");
pcpu->state = Cpu_Break;
return Instr_Break;
}
return fetch(pcpu);
}Пожалуй я лучше не буду показывать вам, во что превращает этот код компилятор (нас могут читать дети!): даже на высоких уровнях оптимизации на это без слез не взглянешь. Многие сейчас говорят, что компиляторы теперь гораздо лучше в оптимизации, чем человек. Но я подозреваю, что это потому, что пока средний компилятор умнел, тот человек, с которым он соревновался, занимался неизвестно чем. Что и говорить, если в наши дни некоторые разработчики виртуальных машин даже позволяют себе иметь семью!
Итак, мы будем следовать пути, который проложил Atakua: использование макросов ассемблера заменит нам inline для целей встраивания кода. Для быстрого визуального распознавания я буду именовать их большими буквами.
.macro FETCH_DECODE
FETCH_CHECKED
DECODE
.endmЭти двое: FETCH_CHECKED и DECODE - всегда ходят парой.
.macro FETCH_CHECKED
.if MAX_PROGRAM_SIZE_CHECK
...
.endif
FETCH
.endmПроверка на выход за пределы 512 ячеек программы сделана отключаемой (с помощью переменной времени компиляции), чтобы можно было оценить, насколько она замедляет выполнение (почти не замедляет). Если она сработала, интерпретатор байткода печатает сообщение и выходит, как и в остальных случаях обработки ошибок.
Сейчас перейдем к более важному: FETCH и DECODE. Их задача состоит в получении опкода и его непосредственного операнда, если этот опкод его принимает. Но использование целого условного перехода для анализа, нужен ли опкоду непосредственный операнд - расточительно. Лучше мы всегда будем выбирать его, а если опкоду он не нужен - это не наша проблема. Таким образом, можно все свести к двум строчкам:
.macro FETCH
mov (prog_mem, pc, 4), opcode32 # prog_mem[pc]
.endm
.macro DECODE
mov 4(prog_mem, pc, 4), immed32 # prog_mem[pc+1]
.endmВы же помните, что в GAS операнд-источник (source) слева, а операнд-приемник (destination) - справа? Окей, я просто на всякий случай спросил.
Опытный ассемблерный программист может заметить, что мы могли бы избавиться от базового адреса prog_mem, сложив его с pc на старте программы. Я тоже поначалу попал в эту ловушку. В результате программа становится немного медленнее. Это из-за того, что в сервисных процедурах Jump и Je, которые отвечают за прыжки по байткоду, появляется необходимость домножать непосредственный операнд на 4 (размер слова виртуальной машины в байтах). Так как непосредственный операнд прыжков может быть отрицательным числом (для прыжков назад), то оптимальный способ сделать это - использовать арифметический сдвиг SAR. Но даже в этом случае это лишняя команда в часто выполняемой процедуре, которая занимает время. На моей машине это означает, в среднем, разницу между 3.02 и 2.94 секундами выполнения всей программы. Можно пойти на такие жертвы, если надо сэкономить регистр для prog_mem, но в этом нет нужды: регистров пока хватает.
Еще одной отброшенной идей является попытка вместо чтения двух 32-разрядных значений, прочесть одно 64-разрядное и применить сдвиги и перемещения, чтобы получать нужные половины. Но на это уходит больше времени, чем удается выиграть - возможно на машинах с более медленным доступом к памяти это бы сработало лучше.
Наконец, переходим к DISPATCH - последней инструкции каждой сервисной процедуры:
.macro DISPATCH
jmp *(routines, opcode64, 8)
.endmМы совершаем прыжок по адресу, лежащему в массиве указателей. Адрес массива лежит в routunes, номер элемента массива - в opcode64, а размер адреса - 8 байт. По сути, это значит достать значение из routines+(opcode64*8) и прыгнуть по этому адресу. Возможно, эти подробные объяснения будут полезны тем, кто не знаком с ассемблером GAS.
Интересный факт о из жизни opcode64: он инициализируется в FETCH и используется в DISPATCH. И до следующего FETCH любая сервисная процедура может использовать его в качестве временного регистра, убедившись только, что перед следующим FETCH его верхняя половина заполнена нулями. Почти то же самое можно сказать и о immed64 - особенно для тех процедур, которые не используют непосредственное значение. Таким образом у нас уже 3 свободных регистра - с ними мы можем развернуться на полную! Но, не пытайтесь объяснить такую стратегию использования регистров компилятору...
Ах да, мы чуть не забыли про ADVANCE_PC:
.macro ADVANCE_PC cnt:req
.if \cnt == 1
inc pc
.else
lea \cnt(pc), pc
.endif
.if (STEPLIMIT_CHECK || STEPCNT)
# Аксакалы верят что если разнести инкремент и проверку, то
# это позволит процессору выполнить все быстрее
inc steps
.endif
.if STATE_RUNNING_CHECK
test state, state # Cpu_Running(0) != state
jne handle_state_not_running
.endif
.if STEPLIMIT_CHECK
cmp steps, steplimit # steps >= steplimit
jl handle_steplimit_reached
.endif
.endmТак как каждая сервисная процедура сама знает, есть ли у нее непосредственный операнд или нет, я параметризовал этот макрос, чтобы он инкрементировал Program Counter в зависимости от переданного аргумента. В исследуемой виртуальной машине нет опкодов, где Program Counter надо сдвигать больше чем на 2, поэтому использование INC или LEA - оптимально для всех случаев.
Ускорение петли обратной связи может привести к пороговым эффектам. Замедление петли обратной связи может привести к упущенным возможностям.
Итак, наша виртуальная машина - стековая, сервисные процедуры получают значения из стека и помещают свои результаты на стек. Для удобства есть даже нотация стековых диаграмм, напоминающая рунический орнамент:
Типичная сервисная процедура у Atakua выглядит так:
void sr_Swap(cpu_t *pcpu, decode_t *pdecoded) {
uint32_t tmp1 = pop(pcpu);
uint32_t tmp2 = pop(pcpu);
BAIL_ON_ERROR();
push(pcpu, tmp1);
push(pcpu, tmp2);
ADVANCE_PC();
*pdecoded = fetch_decode(pcpu);
DISPATCH();
}Поэтому первое, что нам понадобится - это вспомогательные подпрограммы push() и pop() - они инлайнятся почти во все сервисные процедуры. Их особенность в том, что они проверяют выход за границы стека:
static inline void push(cpu_t *pcpu, uint32_t v) {
assert(pcpu);
if (pcpu->sp >= STACK_CAPACITY-1) {
printf("Stack overflow\n");
pcpu->state = Cpu_Break;
return;
}
pcpu->stack[++pcpu->sp] = v;
}
static inline uint32_t pop(cpu_t *pcpu) {
assert(pcpu);
if (pcpu->sp < 0) {
printf("Stack underflow\n");
pcpu->state = Cpu_Break;
return 0;
}
return pcpu->stack[pcpu->sp--];
}Поэтому мы должны делать так же:
.macro PUSH_IMM reg
.if STACK_CHECK
cmp sp, stack_min
jae handle_overflow
.endif
push \reg
.endm
.macro POP_IMM reg
.if STACK_CHECK
cmp sp, stack_max
jb handle_underflow
.endif
pop \reg
.endmОпытный системщик сразу заметит здесь, что от части этих проверок можно уклониться: в самом деле, если процедура забирает два слова со стека, а потом кладет два слова на стек, то нужна только одна проверка! К счастью, не потребуется писать сложный макрос, который будет вычислять совокупную проверку, потому что нас ждет классическая оптимизация реализаций языка Форт: кэширование верхушки стека в регистрах!
Чтобы пояснить это, требуется картинка:
Я измерил производительность без кеширования, с кешированием верхнего значения стека и двух верхних значений и решил остановиться на последнем варианте (он показал наилучшие результаты).
Взгляните, процедура SWAP вообще не трогает стек:
RTN Swap
xchg top, subtop
ADVANCE_PC 1
FETCH_DECODE
DISPATCH(RTN - это очень простой макрос, который формирует начало следующей процедуры, добавляя в нее увеличение счетчика вызова процедуры чтобы можно было оценить, какие процедуры вызываются чаще - небольшое удобство, которое можно отключить переменной времени компиляции):
.macro RTN name
.global srv_\name
.type srv_\name, @function
srv_\name:
.if DBGCNT
incq cnt_\name(%rip)
.endif
.endmВам, вероятно, интересно, сколько раз вызывается каждая сервисная процедура при исполнении нашего алгоритма? Вот данные:
Counters :
cnt_Print : 9592
cnt_Je : 910487889
cnt_Mod : 455189149
cnt_Sub : 455298740
cnt_Over : 1820985370
cnt_Swap : 910387890
cnt_Dup : 0
cnt_Drop : 99998
cnt_Push : 100000
cnt_Nop : 0
cnt_Halt : 1
cnt_Break : 0
cnt_Inc : 455198741
cnt_Jump : 455198741Две последних строчки прямо таки намекают, что их можно автоматизировано объединить в одну суперинструкцию - они идут в байткоде друг за другом. И таких мест там полно, например последовательность "OVER, OVER, SWAP" - это прямо таки лабораторная работа по peephole optimization. Надеюсь, я кого-то заинтересовал и скоро можно будет прочесть третью статью об оптимизации виртуальных машин, с еще более впечатляющими результатами.
Конечно, иногда за трюки со стеком приходится платить. Простые процедуры, вроде DROP, заставляют проталкивать через кэш значения по цепочке (поэтому больше двух элементов стека обычно не кэшируют):
RTN Drop
movq subtop, top # subtop -> top
POP_IMM subtop # from stack -> subtop
ADVANCE_PC 1
FETCH_DECODE
DISPATCHНо зато мы заставляем более сложные процедуры трогать стек только один, максимум два раза. Взгляните, например на OVER:
RTN Over
xchg top, subtop
PUSH_IMM top
ADVANCE_PC 1
FETCH_DECODE
DISPATCHВот его грубая альтернатива, без использования кеширования верхних элементов стека (5 обращений к стеку):
RTN Over
POP_IMM immed64
POP_IMM acc
PUSH_IMM acc
PUSH_IMM immed64
PUSH_IMM acc
ADVANCE_PC 1
FETCH_DECODE
DISPATCHДа, разумеется, ее можно сделать более элегантно с использованием косвенной адресации, но даже так это будет менее быстро. Мой лучший вариант был таким:
RTN Over
movq 8(sp), acc
PUSH_IMM acc
ADVANCE_PC 1
FETCH_DECODE
DISPATCHТаким же образом (почти не приходя в сознание) реализуются все остальные процедуры, которые нужны для исполнения оригинального алгоритма Primes. Я не стал реализовать ничего сверх необходимого:
Print
Je
Sub
Dup
Push
Nop
Halt
Break
Inc
Jump
Одна процедура заслуживает рассмотрения - MOD:
RTN Mod
# Так как мы для top выбрали RAX то не требуется
# делать "mov top, %rax" для подготовки к делению
test subtop, subtop
je handle_divide_zero
xor %rdx, %rdx # rdx = opcode64
div subtop # rdx:rax / operand -> rax, rdx
movq %rdx, top
POP_IMM subtop
ADVANCE_PC 1
FETCH_DECODE
DISPATCHВ ней мы видим, что с точки зрения работы со стеком она настолько же проста как DROP.
Один вводящий в заблуждение бенчмарк может за минуту достичь того, что невозможно получить за годы хорошей инженерной работы. (с) Dilbert.
Вот мои результаты профилирования программы в gprof.
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls Ts/call Ts/call name
31.23 0.86 0.86 srv_Swap
24.37 1.54 0.68 srv_Over
19.86 2.09 0.55 srv_Mod
16.25 2.54 0.45 srv_Je
3.61 2.64 0.10 srv_Sub
2.53 2.71 0.07 srv_Jump
1.08 2.77 0.03 srv_IncА это результаты замера времени оригинальным бенчмарком Atakua. По сравнению с картинкой в его статье, можно видеть, что с 2015 года компьютеры стали быстрее, но, конечно, не настолько, как хотелось бы. Поэтому людям, которые понимают как оптимизировать скорость работы, всегда будет чем заняться.
Итак, способен ли оптимизированный интерпретатор байткода виртуальной машины обогнать двоичную трансляцию? Или, как многие начинающие компиляторщики считают, это невозможно? Является ли JIT (или AOT) - нашей последней надеждой на производительность? Думаю, я смог ответить на этот вопрос.
Посмотрим, что на это ответит сообщество любителей компилирующих виртуальных машин. Если оно существует, то, где-то через 7-9 лет я надеюсь прочитать еще одну статью..
Статья написана, и я отлично повеселился, пора и на работу! Спасибо за внимание!
Весь исходный код можно посмотреть в моем форке репозитория Atakua. Там есть интересные вещи, которые не поместились в статью.
Комментарии (70)
orefkov
06.11.2024 14:32Правильно ли я понимаю, что раз мы много чего делаем глобальным, многопоточным это не сделать? А в случае кооперативной многозадачности (типа фиберы, корутины) надо будет добавлять код по сохранению/восстановлению глобальных значений в некий контекст выполнения?
imitron
06.11.2024 14:32Не совсем. Нам никто не мешает запустить несколько потоков в каждом из которых будет своя виртуальная машина - это будет классическая многопоточность, где у каждой ВМ есть свой стек, но при этом могут быть общие области памяти (и критические секции)
PrinceKorwin
06.11.2024 14:32Можно. Но нативные треды прожорливее, чем зеленые треды (корутины и прочее).
Жаль это убивать на корню.
Rigidus Автор
06.11.2024 14:32Это еще один хороший пример "общего мнения", которое легко опровергнуть - прожорливость нативных тредов в современных операционных системах связана с тем, что для того чтобы создать/остановить/продолжить/завершить их - требуется обращение к ядру, а значит переключение контекста.
Если все нативные треды созданы в начале программы и завершены в конце, а в процессе работы у них нет или мало "точек рандеву" - то они будут быстрее чем зеленые треды, потому что среда выполнения (интерпретатор) не обслуживает диспетчер тредов и эти точки рандеву.
Это огромный класс задач: например у вас может быть IDE, в которой один поток занимается подсветкой синтаксиса, другой - пользовательским интерфейсом, третий - чем то еще.
Прожорливость зеленых тредов становится видна если их создавать и уничтожать на каждый чих: тогда накладные расходы становятся дороже чем полезная нагрузка.
Но, даже если мы делаем зеленые треды, можно посмотреть, что будет занимать время при их переключении в среде выполнения. В текущем варианте ВМ все они будут разделять общий код и данные, но стек у каждого зеленого треда будет свой, это значит что весь контекст выполнения который нужно переключить - это:
- указатель стека
- кэшированные два элемента стека
- program counter
Все остальное - глобальное в регистрах.
Переключение (создание/уничтожение) будет требовать всего нескольких ассемблерных команд - и значит будет очень быстрымPrinceKorwin
06.11.2024 14:32Почему говоря о производительности вы не упоминаете память?
И по моему сложно не согласиться, что в любом случае нативные треды дороже. Всё, что вы написали - это попытки уменьшить их стоимость.
Я не говорю, что нативные треды это зло. Просто упомянул, что иметь возможность работы с зелёными стредами это большой плюс.
qw1
06.11.2024 14:32Их нельзя сравнивать в лоб. Это разные инструменты для разных задач. Зелёные предназначены чтобы обслуживать по 10к клиентов, при этом процессор в основном ждёт данные с сокетов, с БД или ждёт запись в файлы логов. А числодробилки на "зелёных" делать неэффективно - там нет точек await, когда треду нужно ожидание, а процессор можно передать другому треду.
PrinceKorwin
06.11.2024 14:32Согласен! Просто мне показалось, что ваше решение для многозадачности не поддерживает зеленые треды.
qw1
06.11.2024 14:32Не тот уровень абстракции. Компилятор, генерирующий байт-код, должен уметь async-функцию компилить в конечный автомат, т.е. 1 вызов фунции = 1 шаг автомата между точками await. Интерпретатор байт-кода может и не знать, что он выполняет не обычную функцию, а зелёную.
PrinceKorwin
06.11.2024 14:32Обычно для этого функции определенным образом помечают (async как ключевое слово перед определением функци). Поэтому, скорее всего, интерпретатор тоже может владеть такой информацией и понимать, что он исполняет зеленую функцию. Нет?
qw1
06.11.2024 14:32Можно, конечно, async вынести на уровень интерпретатора, и сделать поддержку в специальных опкодах. Но по классике, чтобы было оптимально, компилятор в байт-код генерирует код с поддержкой кооператива, чтобы не нагружать этим интерпретатор байт-кода.
В компилируемых языках процессор не знает, выполняет он "зелёную" функцию или обычную. Он молотит все опкоды подряд, которые ему подсунут. Никто пока не предложил инструкции процессора под async. Было бы выгодно - сделали бы.
orefkov
06.11.2024 14:32Меня в заблуждение ввела фраза "Для начала можно сделать все данные состояния интерпретатора глобальными переменными.". Только посмотрев код тщательнее, я понял, что "глобальными переменными" вы имеете ввиду не в рамках программы-хоста, а в рамках виртуальной машины. Ну и потом эти "глобальные переменные" прибиваете к регистрам. То есть перед началом выполнения кода ВМ заполняем регистры хоста из контекста выполнения, в случае прерывания выполнения кода ВМ сохраняем регистры хоста обратно в контекст выполнения, чтобы потом можно было возобновить выполнение. Тогда можно и несколько ВМ запускать в одном потоке поочерёдно.
qw1
06.11.2024 14:32В коде не вижу ничего особо глобального, во все функции передаётся контекст
cpu_t *А вообще, через кодогенерацию/макросы можно сделать до 16 копий (или сколько нужно) кода интерпретатора, и запускать эти копии на разных тредах.
Или через пре-процессор
namespace cpu1 { #include "cpu_impl.cpp" } namespace cpu2 { #include "cpu_impl.cpp" } namespace cpu3 { #include "cpu_impl.cpp" } ...
Cheater
06.11.2024 14:32Эм я правильно понимаю что эта VM способна выполнять только свои опкоды и не может вызвать например библиотечную ф-ю через POSIX ABI, тк для этого придётся потерять контроль над регистрами и стеком?
Rigidus Автор
06.11.2024 14:32Нет, неправильно. Более того она делает именно это в своей процедуре Print которая вызывает обычный такой библиотечно-POSIX-вый printf(), просто сохраняя/восстанавливая несколько регистров, которые в любом случае пришлось бы сохранять по ABI.
Мы можем добавить еще опкодов которые будут делать любые сисколлы или библиотечные вызовы или даже один опкод который сможет делать любой сискол по номеру - ограничений нет
checkpoint
06.11.2024 14:32Не пробовали ли Вы избавитьcя от вызова cервисной функции по указателю из таблицы (routines) ? Что если сделать указатель сервисной функции просто вычислимым ? Скажем, разместить код сервисных функций в памяти с равным интервалом кратным степени 2 и вычислять адрес путем сдвига опкода и прибавления смещения. На мой взгляд это должно еще немного увеличить производительность, так как процессору не нужно будет постоянно заглядывать в свой кэш для получения указателя.
Rigidus Автор
06.11.2024 14:32Я думаю, это блестящая идея! Стоит попробовать!
На самом деле, есть еще несколько интересных оптимизаций, которые можно было бы испробовать - одна из них - иметь два комплекта сервисных процедур: один для стека (top, subtop) а второй - для обратного ему (subtop, top).
Тогда процедура SWAP может не делать ничего кроме переключения с одного комплекта на другой. OVER тоже будет оптимизирован лучше в результате. Мы можем даже использовать "флаг направления (DF)" в процессоре для отслеживания какой комплект работает в данный момент.
Я предолагаю, что из-за этого предсказатель переходов будет предсказывать лучше, т.к. у него будет больше переходов и информационная нагрузка на один переход уменьшится. Приглашаю это проверить вместе.
checkpoint
06.11.2024 14:32Попробуйте пожалуйста, мне очень интересно каков будет эффект. :)
Rigidus Автор
06.11.2024 14:32Я измерил размеры всех сервисных процедур:
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
qw1
06.11.2024 14:32Можно выровнять на 0x80, или даже на 0x40, если большие функции, типа Print, разбить на функции поменьше и основное их тело вынести в другое место.
qw1
06.11.2024 14:32Ну, или как вариант, сделать таблицу трамплинов
.align 8 jumps: jmp Opcode_Add .align 8 jmp Opcode_And ... // rcx = next opcode lea rax, [jumps + rcx*8] jmp raxДвойной прыжок, но второй не косвенный, а прямой - конвеер должен понимать, какой код будет сразу после прыжка и начинать его выполнять
Rigidus Автор
06.11.2024 14:32попробуешь провести экперимент? там в Makefile чтобы запустить бенчмарк достаточно
make measure
checkpoint
06.11.2024 14:32Еще одно замечения по методике измерения. Для чистоты эксперимента нужно убрать вызов Printf, иначе Вы замеряете производительность очень медленной библиотечной функции vfprintf, а также системного вызова write и кучу сопутствующего всякого разного.
Rigidus Автор
06.11.2024 14:32Убирать нельзя, т.к. в исходной статье измерения проводятся вместе с printf. С другой стороны она не оказывает серьезного влияния на общий бенчмарк, т.к. вызывается всего лишь
9592раз.
checkpoint
06.11.2024 14:32Короче, я закоментировал вызов 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 сек. Моё предположение было в том, что функции выравненные по границе страниц могут выполнятся быстрее, но это предположение оказалось ложным.
Rigidus Автор
06.11.2024 14:32Можно ли ссылку на форк с изменениями?
checkpoint
06.11.2024 14:32Вот патч:
Патч для убирания вызова 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, nmaxRigidus Автор
06.11.2024 14:32
У меня вот такие результаты.
checkpoint
06.11.2024 14:32Не густо, но тоже результат. :)
Дайте мне свой код, я прогоню его на моей машине.
Rigidus Автор
06.11.2024 14:32Кажется что разница значительная, но на самом деле картинка вводит в заблуждение. Добавление native варианта позволяет сопоставить в масштабе
checkpoint
06.11.2024 14:32Вы задачу у native увеличить не забыли ? У меня native выполняется на этой задаче более 5 сек.
checkpoint
06.11.2024 14:32Да, volatile для всех переменных в цикле native тоже не забудьте. Иначе компилятор сожмет его до пустого цикла. :-)
checkpoint
06.11.2024 14:32native без pintf() на этой же увеличенной задаче на моей машине дает 5.26 сек.
checkpoint
06.11.2024 14:32На самом деле, есть еще несколько интересных оптимизаций, которые можно было бы испробовать - одна из них - иметь два комплекта сервисных процедур: один для стека (top, subtop) а второй - для обратного ему (subtop, top)
Эта оптимизация скорее важна для Forth машин, для той же Жабы она скорее всего бесполезна.
Приглашаю это проверить вместе.
Я сейчас увлечен немного другой темой. Но тема VM тоже интересна как вариант минималистичной ОС для синтезируемой ЭВМ.
Rigidus Автор
06.11.2024 14:32Я как раз читаю эту статью, принципы из ее начала резонируют с моим ощущением "как правильно". Я бы был заинтересован в изготовлении тестового стенда для опробования всего этого в железе и экспериментов
checkpoint
06.11.2024 14:32У меня в голове крутится идея сделать VM поверх получившейся синтезируемой ЭВМ, с примитивами для работы с периферией (клавиатурой, отображения на VGA монитор и тд). Forth не плохо подходит под эту тему. Еще мне нравится Inferno - это тоже байт-кодовая VM. Далее использовать её для всяких экспериментов в пром автоматизации, а также как персональную ЭВМ независимую от глобального стека ПО. Если Вам интересно позаниматься этой темой я могу выслать платку "Карно", их есть у меня. :)
Rigidus Автор
06.11.2024 14:32Я хотел бы поучаствовать в этом совместном проекте. У меня давно зреет идея о FPGA-компьютере в формате клавиатуры, способном подключаться к экранам через HDMI и содержащем внутри себя Forth-машину, которую можно было бы разрабатывать и на обычном GNU/Linux/FreeBSD компьютере. Я запускал Plan9 очень давно и было бы интересно потестить Inferno и 9p-протокол снова
checkpoint
06.11.2024 14:32Я пробовал Plan9 и Inferno в конце 90-х. Да, с тех пор запало в душу. Короче, присылайте свой адрес в личку. :)
qw1
06.11.2024 14:32Несколько месяцев назад в комментариях прорабатывали версию кеширования верхушки стека в регистрах, но так, чтобы на каждую глубину стека, загруженную в регистры, был свой вариант обработчиков байт-кода. Тогда DROP - это просто NO-OP (переход на ветку с меньшей глубиной стека в регистрах), какой-нибудь ADD - это add rax, rbx с переходом на другую ветку. Получается довольно интересно по скорости, но с большим гемором в реализации интерпретатора, кучу дублирующегося кода надо писать руками.
Rigidus Автор
06.11.2024 14:32Спасибо за ссылку, там интересные идеи. Я думаю стоит написать генератор, который смог бы для каждого варианта стека из обычного набора сервисных процедур сгенерировать несколько стекозависимых. Это было бы интересно обсудить
qw1
06.11.2024 14:32Мне кажется все варианты всех опкодов на все возможные глубины стека быстрее написать руками, чем пытаться создавать обобщённый генератор.
Rigidus Автор
06.11.2024 14:32Мне больше нравится обобщенное решение, т.к. я не уверен в своей способности не внести каких-нибудь багов по невнимательности. Особенно когда мы делаем несколько вариантов одной и той же реализации ВМ под разные процессоры: x86_64, ARM, RISC-V...
qw1
06.11.2024 14:32Было бы интересно играться размером вершины стека, которая лежит в регистрах, а также стратегией передвижения окна. Например, если все регистры заняты, вытеснить в память только 1, а все остальные сдвинуть, или вытеснить половину, чтобы вытеснения были пореже. А может, выгодно вытеснять сразу 3/4? Аналогично с обратным процессом - если кеш опустел, подгружать по 1 регистру, или сразу 6, чтобы пореже на это отвлекаться.
Тут да, ручное написание вариантов ограничивает поле для экспериментов. Но видимо под каждый опкод нужно будет писать свой шаблон, потому что своя специфика в каждом случае.
e2k_sid
06.11.2024 14:32Попробуйте сравнить скорость самогобыстрого интерпретатора со скоростью интерпретатора в OpenJDK. Многие гениальные идеи отпадут сами собой.
Rigidus Автор
06.11.2024 14:32Я взял код из 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-код не в состоянии обогнать оптимизированный интерпретатор байткода.
Вы всерьез ожидали иного результата?e2k_sid
06.11.2024 14:32Запуск java-машины очень дорогой процесс. Сравните время "gcc --version" и "java --version". При старте java-машины выполняется инициализация контекста. Как-то делал замер, и у меня получилось что-то вроде ~20 млн. байт-код инструкций - это только инициализация. Обработка "--version" потребует все несколько десятков инструкций. Причем много функций исполняется 1-2 раза. Однако jit-компилятор пытается многие из них оптимизировать. В итоге время компиляции не окупается, так как нативная версия функции может вообще не исполнится ни разу. Поэтому действительно "java --version" работает медленнее, чем "java --version -Xint". Но это классическая проблема любой jit-системы, выигрыш от исполнения оптимизированной версии должен перевесить время, затраченное на компиляцию. А это бывает не всегда. Для любой jit-системы можно найти анти-патерн.
Вывод - учите матчасть.imitron
06.11.2024 14:32java запускалась без jit-компиляции. В обоих случаях измеряется полное время программы, с любой подготовкой контекста, запуском и остальными приготовлениями.
e2k_sid
06.11.2024 14:32Ок, было сказано, что
> Java-код не в состоянии обогнать оптимизированный интерпретатор байткода
А где сказано, что количество байт-код инструкций при обоих сравнениях одинаковое, и где обоснования, что семантика байткод инструкций идентичная?
Как без этого можно утверждать, что один интерпретатор быстрее, и Вы всерьез полагаете, что в OpenJDK не оптимизированный интерпретатор?
Просто абсолютное общее время работы не говорит само по себе ни о чем.imitron
06.11.2024 14:32Я пожалуй воздержусь от спора. Иначе тут будет затратное мероприятие по отводу аргументов лернейской гидры - с одним справился, тут тебя еще десятью закидают :) Специалист извлечет для себя методы и подходы из статьи, баталии в комментариях - это непродуктивный спор с теми, кто, к сожалению, не сможет улучить время в бенчмарке.
e2k_sid
06.11.2024 14:32Полностью с Вами согласен. Нужно любые утверждения из всех научных статей принимать сугубо на веру. В заголовке же написано про наиболее быстрый интерпретатор среди всех возможных, значит так оно и есть! Вопросы - да зачем? А всех этих дармоедов из OpenJDK, CoreNET и V8/Chrome надо разогнать к чертям собачьим.
Mingun
06.11.2024 14:32Ну вообще написано про быстрейший из рассмотренных, а "среди всех возможных" -- это вы сами выдумали. Хотите опровергнуть -- ну так напишите 9-й, быстрейшей из этих 9. Или хотя бы укажите на неоптимальности в этом. По мне, так прекрасная статья, показывающая, как правильно подходить к оптимизации, написанная легким для чтения языком (как и предыдущая, которую она дополняет).
Я так понимаю, вы разбираетесь с том, какие техники оптимизации применены в интерпретаторе JVM, ну так может напишите статью об этом? А если сохраните тот же легкий стиль изложения, как у вышеупомянутых авторов, цены ей не будет.
e2k_sid
06.11.2024 14:32Не являюсь разработчиком JVM, хотя действительно в свое время не мало просидел в отладчике gdb и над кодом генерации кода интерпретатора, и над уже сгенерированном в памяти кодом самого интерпретатора. Не меньше, если не больше времени просидел в отладчике gdb над кодом генератора Baseline транслятора в Firefox. Медитировал над исходными кодами. Что было, то было :). Разработал даже как-то интерпретатор одного регистрового байткода целиком на ассемблере для одного процессора со статическим планированием :)). С производительностью близкой уже к шаблонному транслятору. И это тоже было.
Теперь, что касается данной статьи и моих начальных "оценок". Тут я с "оценками", мдя, но не буду о грустном :). Все что автор рассказал про свой интерпретатор, все классно. Технологии им примененные и достигнутый результат (для одной конкретной стековой машины) достойны серьезных похвал. Кстати, как и достижения разработчиков JVM. И разработчиков V8.Но вот когда в конце статьи целиком и полностью посвященной одному конкретному интерпретатору, пусть и наиболее быстрому, делается вывод о JIT-компиляции. Хм. А где в статье разбор jit-компиляции-то, чтобы выводы о ней делать? Поскольку интерпретатор наиболее быстрый, то jit-компиляция ... А что собственно jit-компиляция-то?
Не будь таких выводов о jit/aot - и это была статья с совсем другим посылом.Mingun
06.11.2024 14:32Но ведь в статье каких-то выводов о JIT/AOT нет, лишь замечание о том, что усилия по их написанию могут оказаться неадекватными полученному ускорению, в некоторых случаях может оказаться быстрее написать правильно оптимизированный интерпретатор, чем правильно оптимизированный JIT/AOT. Ведь в оригинальной статье последним рассматривался примитивный JIT.
Вот под вашим комментарием автор действительно не учел, что старт JVM тоже какое-то время занял и он померял не только алгоритм.
e2k_sid
06.11.2024 14:32Как рассказывали знающие люди, еще в самом начале пути, разработчики java-машины были уверены, что им достаточно сделать только интерпретатор. Это сейчас говорим java-машина, а подразумеваем jit-компилятор. Но так было не всегда. Однако, очень быстро разработчики убедились, что jit-компилятор делать придется. И да, производительности много не бывает. Поэтому разработчики java-машины (лет 40 назад?) уже наступили на эти грабли. И нет, сколь угодно быстрого интерпретатора недостаточно.
Можно сказать, ну всегда найдутся ниши там где производительность не важна. Ну во-первых что это за ниши такие и кому это будет интересно? А во-вторых, а зачем тогда быстрый интерпретатор, производительность-то не важна? Да и дело в экосистеме. Кого, как, куда и кто пересадит на совершенно новую ВМ? И Зачем?
checkpoint
06.11.2024 14:32От специалиста который провел не одну ночь в gdb я хотел бы услышать более аргументированное обьяснение того, почему JIT выигрывает над "до предела заоптимизированной" JVM. Делательно, с примерами машинного кода, что во что компилируется, и сопоставить это с тем как реализовано в JVM. Короче, с Вас ответная статья. :)
qw1
06.11.2024 14:32Вам не очевидно, что любой интерпретатор будет проигрывать native? Хотя бы потому что, процессору приходится выполнять в разы больше инструкций для выполнения одного и того же действия.
e2k_sid
06.11.2024 14:32Элементарно есть масштабируемость по количеству итераций цикла? Когда внутренний цикл погружаем во внешний, чтобы исключить постоянные накладные расходы на раскрутку.
При старте java-машины происходит инициализация стандартной java-библиотеки. Java-библиотека написана на java ("ДБ." Лавров.) И это дорогой процесс. А только потом "пролетает" код собственно примера.
ДОПОЛНЕНИЕ. Хотя не-а, похоже я сильно ошибся, насчет сложности старта java-машины. Либо в примере должны быть import'ы или new Object.
e2k_sid
06.11.2024 14:32Увеличил счетчик в цикле в 2 раза (i < 2*
100000)$ time java Main > /dev/null
real 0m6,139s
$ time java -Xint Main > /dev/nullreal 0m22,493s
Нативный код из-под java-компилятора быстрее java-интерпретатора. Вы ожидали иного результата?Rigidus Автор
06.11.2024 14:32В этой статье мы сравниваем не интерпретируемую джаву с компилируемой а разные способы создавать интерпретаторы байткода.
Подождите следующей статьи :)e2k_sid
06.11.2024 14:32Михаил, конечно большинство моих комментариев были идиотскими (впрочем может как и этот), но и они отчасти есть следствие очень неаккуратных формулировок
> Является ли JIT (или AOT) - нашей последней надеждой на производительность? Думаю, я смог ответить на этот вопрос.
> Вывод: Java-код не в состоянии обогнать оптимизированный интерпретатор байткода.
В x86-процессоре есть предсказатель переходов. Но если код интерпретатора фиксирован, и исполняется не только маленький цикл интерпретируемой программы, то и такой планировщик не панацея.
Шаблонный транслятор tier-1 раскручивает байткод в прямые последовательности в пределах одного линейного блока. Это идеальная ситуация для аппаратного планировщика. И даже на переходах из байткода ситуация на порядок станет лучше.
Кроме того, jit-компиляторы уровня tier-2 в jit-языках, на мой взгляд, чаще занимаются не столько архитектурными оптимизациями, сколько оптимизациями этих самых языков. (Особенно это наглядно для языков с динамической типизацией.) Но и архитектурными оптимизациями тоже. Так tier-2 компиляторы преобразуют стековый байткод в регистровое промежуточное представление (в пределах линейного блока). Ну про инлайн и не вспоминаем (его и на байткоде делать можно). А нативный код, полученный из регистрового представления лучше планируется и быстрее исполняется из-за аппаратных особенностей.
e2k_sid
06.11.2024 14:32Кроме того мой комментарий был про то, что прежде чем в очередной раз изобретать велосипед, то есть придумывать самыйбыстрый интерпретатор байт-кода стекового представления, прежде хорошо изучите устройство и принципы работы таких интерпретаторов, как интерпретатора байт-кода в OpenJDK.
Хотя должен также предупредить, что в виде C++ или даже asm-кода его в исходных кодах проекта Вы не найдете :), там есть только C++-код генерации кода интерпретатора :))). Но когда это останавливало нас, профеcсионалов :))?e2k_sid
06.11.2024 14:32И хотя Baseline в Firefox - это по сути шаблонный транслятор, включающий при этом паттерны динамической детипизации (JS - ужасный язык), но в плане работы со стековым байткодом, Baseline как брат-близнец похож на генератор интерпретатора в OpenJDK. Предполагаю, что и в CoreNET и V8/Chrome принципы быстрой интерпретации стекового представления схожи. Коммуниздят идеи друг у друга и не краснеют :).
e2k_sid
06.11.2024 14:32Если исходить из научного дискурса, поиска знаний.
То было у меня такое исследование - сделать интерпретатор регистрового представления. В компилятор javac (из OpenJDK) сделал патч, в рамках которого из Java-AST вместо стандартного байткода стандартной стековой машины создавался регистровый байткод самопальной виртуальной машины. Утверждать о корректности сравнения конечно не могу, кроме просто интерпретации кода есть еще семантика стандарта исходного языка. Но в первом приближении, можно предполагать, что удалось достичь паритета между стековым интерпретатором из OpenJDK и регистровым интерпретатором из самопальной ВМ. При этом интерпретация одной регистровой инструкции конечно занимает больше времени, но в среднем регистровых инструкций меньше. Вот и вышел баш на баш.
При написании регистрового интерпретатора пришлось долго "воевать" с компилятором gcc, чтобы заработали jump'ы из asm-вставок и ручное распределение части указателей на регистры (gcc все норовил сделать ряд оптимизаций).
Поэтому с научной точки зрения, опираясь на очень косвенные данные, можно осторожно предположить, что для x86, то есть out-of-order процессора (arm/mips сюда же видимо), производительности стекового и регистрового интерпретаторов в общем и целом равны, если каждый из интерпретаторов достаточно оптимизирован. Но это как отправная точка для исследования.
В этом смысле, разработчики OpenJDK/Firefox/CoreNET/Chrome вложили очень много сил и времени в разработку быстрых интерпретаторов стековых машин. И с наскоку их обойти, ну наверное, не то чтобы не получится, но затруднительно. Хотя может и получится. Но нужны корректные сравнения и легко читаемые "проценты".
Rigidus Автор
06.11.2024 14:32>> прежде хорошо изучите устройство и принципы работы таких интерпретаторов, как интерпретатора байт-кода в OpenJDK.
Давайте перейдем в более конструктивную плоскость. В этой статье были изложены принципы оптимизации интерпретаторов, которые дают измеримый эффект для производительности. Я бы хотел узнать, какие принципы могут еще улучшить перформанс (неважно откуда они будут - из OpenJDK или других источников). Можете поделиться?e2k_sid
06.11.2024 14:32Михаил, если говорить про реализацию интерпретатора конкретно для вашего стекового байткода, то наверное, действительно ваша реализация будет самой эффективной. Особенно при условии что берутся маленькие циклы на байткоде. И скорее всего вы действительно достигли эффективности шаблонного транслятора, и в этом достижение серьёзное. Однако на более разнообразном байткоде шаблонный транслятор за счёт аппаратного планировщика скорее всего даст лучший результат.
Что касается сравнений. Если была бы речь про то, что ваша реализация, например, java-машины как системы целиком быстрее, то тогда понятно. Берем одинаковые Java программы и сравниваем общее время для двух машин. Но при этом гарантируем для программистов идентичную семантику java-программ. Но все равно это про системы целиком. И тогда могут сравниваться подходы в целом.
В общем, подобное надо сравнивать с подобным. Если сравниваются два интерпретатора, то у них должны быть одинаковые байт-код программы на входе. Ну и по-хорошему идентичная семантика. Иначе это сравнение в непонятных попугаях. Тогда некорректно говорить, что один быстрее другого. У них контекст разный. Именно как интерпретаторов а не VM.
При этом в целом возможно ваши подходы в чем-то и эффективней подходов из openjdk. А может они сопоставимы по эффективности. А может у OpenJDK чуть эффективней.
Однако в любом случаи, когда вы, Михаил, в конце статьи переходите к обобщающему выводу относительно jit-компиляторов доводов не хватает. Собственно вот что "зацепило" именно меня :). И это безотносительно ваших реальных достижений по созданию очень быстрого интерпретатора для конкретного стекового представления.
imitron
06.11.2024 14:32Я думаю, что просто не могу не оставить это тут: https://lex-kravetski.livejournal.com/253994.html
MasterMentor
vjft - интересно. А грамматика GL-ля уже есть?