Ответ на статью о «Наиболее быстром интерпретаторе»

Недавно была опубликована статья под заголовком «Глобально оптимальный, восьмой и наиболее быстрый вид интерпретаторов байткода». Несколько тезисов из статьи вызвали у меня сомнения в их справедливости. Об этом я попробовал написать ряд комментариев тире вопросов к указанной статье. Но основной лейтмотив всех ответов сводился к тому — «а ты напиши свою статью». Подход не столько инженерно-научный, сколько детсадовский. Мне бы хватило и содержательных ответов в формате комментариев, но как говорится — уговорили.

Итак, что же утверждается автором статьи про наиболее быстрый интерпретатор:

• Так что эта статья — туториал: как написать интерпретатор байткода, который может обгонять JIT/AOT-компиляцию по скорости.

• Итак, способен ли оптимизированный интерпретатор байткода виртуальной машины обогнать двоичную трансляцию? Или, как многие начинающие компиляторщики считают, это невозможно? Является ли JIT (или AOT) — нашей последней надеждой на производительность? Думаю, я смог ответить на этот вопрос.

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

Делает ли автор статьи о наиболее быстром интерпретаторе какие-либо сравнения с JIT-компиляцией? Нет. Он только исключительно рассказывает про свою реализацию интерпретатора. И использует некоторый бенчмарк Atakua, не уточняя что это за бенчмарк, что и как измеряется в рамках бенчмарка. Кроме того, в самом конце статьи сообщается, что

Посмотрим, что на это ответит сообщество любителей компилирующих виртуальных машин. Если оно существует, то, где-то через 7-9 лет я надеюсь прочитать еще одну статью.

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

Для начала по предложенной ссылке на проект interpreters-comparison, попробуем познакомиться с проектом поближе. Каких-либо специальных указаний не было, поэтому просто копируем проект по указанной автором ссылке. Информации в проекте предоставляется не так много, но если смотреть по истории изменений, то судя по всему собственно код наиболее быстрого интерпретатора написан на ассемблере и размещен в файле asmoptll.S. Исходя из содержимого Makefile’а итоговый исполняемый бинарник, создаваемый make командой — это asmopt. Вооружимся отладчиком gdb и попробуем получить трассу исполнения основного цикла.

Но в начале поговорим о том, какая программа исполняется в примере. Исходя из кода проекта в целом, байткод тестового примера (это видимо и есть бенчмарк?) определен в файле common.c в глобальном массиве Primes. Всю байткод-программу в терминах стековой машины из проекта interpreters-comparison легко посмотреть по ссылке в файле common.c. Здесь же приведем основной и самый горячий внутренний цикл, который состоит из следующих байткод инструкций абстрактной стековой машины из этого проекта:

Instr_Over, // nmax, c, divisor, c
Instr_Over, // nmax, c, divisor, c, divisor
Instr_Swap, // nmax, c, divisor, divisor, c
Instr_Mod, // nmax, c, divisor, c mod divisor
Instr_JE, +5, /* not_prime */ // nmax, c, divisor
Instr_Inc, // nmax, c, divisor+1
Instr_Jump, -15, /* back2 */ // nmax, c, divisor

Запустим теперь исполняемый файл asmopt под отладчиком gdb, немного подождем, прервем исполнение и воспользуемся gdb-командой display:
(gdb) display /i $pc

После чего будем использовать gdb-команду stepi и так достаточно быстро получим трассу исполнения самого горячего цикла, благо он не большой, и трасса получается достаточно быстро даже при таком ручном подходе. Приведу, полученною мной, трассу исполнения одной итерации цикла. В ней все x86-инструкции выполняются последовательно, но для удобства чтения вставлены дополнительные строки с названиями функций интерпретации разных байткод-инструкций:
// src_Over
0x555555555546 : xchg %rax,%r10
0x555555555548 : cmp %rsp,%rbx
0x55555555554b : jae 0x555555555497
0x555555555551 : push %rax
0x555555555552 : inc %r9
0x555555555555 : mov (%rsi,%r9,4),%edx
0x555555555559 : mov 0x4(%rsi,%r9,4),%r14d
0x55555555555e : jmpq *(%rdi,%rdx,8)
// src_Over
0x555555555546 : xchg %rax,%r10
0x555555555548 : cmp %rsp,%rbx
0x55555555554b : jae 0x555555555497
0x555555555551 : push %rax
0x555555555552 : inc %r9
0x555555555555 : mov (%rsi,%r9,4),%edx
0x555555555559 : mov 0x4(%rsi,%r9,4),%r14d
0x55555555555e : jmpq *(%rdi,%rdx,8)
// src_Swap
0x555555555535 : xchg %rax,%r10
0x555555555537 : inc %r9
0x55555555553a : mov (%rsi,%r9,4),%edx
0x55555555553e : mov 0x4(%rsi,%r9,4),%r14d
0x555555555543 : jmpq *(%rdi,%rdx,8)
// src_Mod
0x555555555590 : test %r10,%r10
0x555555555593 : je 0x5555555555b8
0x555555555595 : xor %rdx,%rdx
0x555555555598 : div %r10
0x55555555559b : mov %rdx,%rax
0x55555555559e : cmp %rsp,%rbp
0x5555555555a1 : jb 0x5555555554a6
0x5555555555a7 : pop %r10
0x5555555555a9 : inc %r9
0x5555555555ac : mov (%rsi,%r9,4),%edx
0x5555555555b0 : mov 0x4(%rsi,%r9,4),%r14d
0x5555555555b5 : jmpq *(%rdi,%rdx,8)
// srv_Je
0x5555555555dd : mov %rax,%r13
0x5555555555e0 : mov %r10,%rax
0x5555555555e3 : cmp %rsp,%rbp
0x5555555555e6 : jb 0x5555555554a6
0x5555555555ec : pop %r10
0x5555555555ee : test %r13,%r13
0x5555555555f1 : je 0x555555555603
0x5555555555f3 : lea 0x2(%r9),%r9
0x5555555555f7 : mov (%rsi,%r9,4),%edx
0x5555555555fb : mov 0x4(%rsi,%r9,4),%r14d
0x555555555600 : jmpq *(%rdi,%rdx,8)
// srv_Inc
0x55555555557e : inc %rax
0x555555555581 : inc %r9
0x555555555584 : mov (%rsi,%r9,4),%edx
0x555555555588 : mov 0x4(%rsi,%r9,4),%r14d
0x55555555558d : jmpq *(%rdi,%rdx,8)
// srv_Jump
0x5555555555c7 : movslq %r14d,%r14
0x5555555555ca : add %r14,%r9
0x5555555555cd : lea 0x2(%r9),%r9
0x5555555555d1 : mov (%rsi,%r9,4),%edx
0x5555555555d5 : mov 0x4(%rsi,%r9,4),%r14d
0x5555555555da : jmpq *(%rdi,%rdx,8)

Данная трасса очень хорошо согласуется с содержимым файла asmoptll.S, там есть определение всех srv-функций. Однако получить именно итоговый x86-код исполняемых srv-функций непосредственно из файла несколько сложнее, чем из трассы из-под gdb (дизассемблер объектника хорош когда уже знаешь что искать). Вот что проще, так это из файла asmoptll.S действительно гораздо легче понять логику интерпретации инструкций стековой машины. Несложно теперь установить и исходный алгоритм, использованный для создания байткод-программы, который на языке Си доступен в native.c:
for (int i = 2; i < 100000; i++) {
bool is_prime = true;
for (int divisor = 2; divisor < i; divisor++) {
if (i % divisor == 0) {
is_prime = false;
break;
}
}
if (is_prime) printf("[%d]\n", i);
}

Автор статьи про наиболее быстрый интерпретатор в своем комментарии любезно привел пример на java. Воспользуемся этим примером и проанализируем основной цикл в OpenJDK. Сначала с помощью утилиты javap попробуем получить байткод основного цикла. Похоже, что для случая OpenJDK байткод одной итерации будет устроен следующим образом:

12: iload_3
13: iload_1
14: if_icmpge 34
17: iload_1
18: iload_3
19: irem
20: ifne 28
...
28: iinc 3, 1
31: goto 12

Первое, что бросается в глаза — это то, что основная итерация состоит из 9 байткод инструкций заместо 7 байткод инструкций, как это было ранее для наиболее быстрого интерпретатора. Это говорит о том, что компилятор javac возможно сделал не самый оптимальный код или может быть стандарт Java на байткод вносит свои ограничения. В противоположность этому в проекте interpreters-comparison сама по себе байткод программа в части основного цикла выглядит более оптимальной и лучше оптимизированной. Но речь-то шла не про сравнение компиляторов, и не про то, кто сделает более оптимальный байткод. Верно? Речь шла про интерпретаторы, и про интерпретаторную наиболее быстрость. А интерпретатор обязан исполнять тот байткод, который ему передали на исполнение с одной стороны, а с другой стороны время работы интерпретатора напрямую зависит от количества инструкций. Сократили во входной байткод-программе на 20% количество инструкций — считай ускорили суммарное время работы интерпретатора на те же ~20%. Составим теперь трассу исполнения для OpenJDK, используя опцию -Xint, чтобы в OpenJDK работал только интерпретатор байткода:
// скорее всего это iload_3
0x7fffe49216c3: movzbl 0x1(%r13),%ebx
0x7fffe49216c8: inc %r13
0x7fffe49216cb: movabs $0x7ffff7d7ebc0,%r10
0x7fffe49216d5: jmpq *(%r10,%rbx,8)
// скорее всего это iload_1
0x7fffe49215be: push %rax
0x7fffe49215bf: mov -0x8(%r14),%eax
0x7fffe49215c3: movzbl 0x1(%r13),%ebx
0x7fffe49215c8: inc %r13
0x7fffe49215cb: movabs $0x7ffff7d7ebc0,%r10
0x7fffe49215d5: jmpq *(%r10,%rbx,8)
// скорее всего это if_icmpge 34
0x7fffe49253c7: mov (%rsp),%edx
0x7fffe49253ca: add $0x8,%rsp
0x7fffe49253ce: cmp %eax,%edx
0x7fffe49253d0: jl 0x7fffe4925413
0x7fffe4925413: movzbl 0x3(%r13),%ebx
0x7fffe4925418: add $0x3,%r13
0x7fffe492541c: movabs $0x7ffff7d813c0,%r10
0x7fffe4925426: jmpq *(%r10,%rbx,8)
// скорее всего это iload_1
0x7fffe49215bf: mov -0x8(%r14),%eax
0x7fffe49215c3: movzbl 0x1(%r13),%ebx
0x7fffe49215c8: inc %r13
0x7fffe49215cb: movabs $0x7ffff7d7ebc0,%r10
0x7fffe49215d5: jmpq *(%r10,%rbx,8)
// скорее всего это iload_3
0x7fffe49216be: push %rax
0x7fffe49216bf: mov -0x18(%r14),%eax
0x7fffe49216c3: movzbl 0x1(%r13),%ebx
0x7fffe49216c8: inc %r13
0x7fffe49216cb: movabs $0x7ffff7d7ebc0,%r10
0x7fffe49216d5: jmpq *(%r10,%rbx,8)
// скорее всего это irem
0x7fffe4923e27: mov %eax,%ecx
0x7fffe4923e29: mov (%rsp),%eax
0x7fffe4923e2c: add $0x8,%rsp
0x7fffe4923e30: cmp $0x80000000,%eax
0x7fffe4923e36: jne 0x7fffe4923e47
0x7fffe4923e47: cltd
0x7fffe4923e48: idiv %ecx
0x7fffe4923e4a: mov %edx,%eax
0x7fffe4923e4c: movzbl 0x1(%r13),%ebx
0x7fffe4923e51: inc %r13
0x7fffe4923e54: movabs $0x7ffff7d7ebc0,%r10
0x7fffe4923e5e: jmpq *(%r10,%rbx,8)
// скорее всего это ifne 28
0x7fffe4924ec7: test %eax,%eax
0x7fffe4924ec9: je 0x7fffe4924f0c
0x7fffe4924ecf: mov -0x18(%rbp),%rcx
0x7fffe4924ed3: movswl 0x1(%r13),%edx
0x7fffe4924ed8: bswap %edx
0x7fffe4924eda: sar $0x10,%edx
0x7fffe4924edd: movslq %edx,%rdx
0x7fffe4924ee0: add %rdx,%r13
0x7fffe4924ee3: movzbl 0x0(%r13),%ebx
0x7fffe4924ee8: testb $0x8,0x108(%r15)
0x7fffe4924ef0: je 0x7fffe4924efe
0x7fffe4924efe: movabs $0x7ffff7d813c0,%r10
0x7fffe4924f08: jmpq *(%r10,%rbx,8)
// скорее всего это iinc 3, 1
0x7fffe492463f: movsbl 0x2(%r13),%edx
0x7fffe4924644: movzbl 0x1(%r13),%ebx
0x7fffe4924649: neg %rbx
0x7fffe492464c: add %edx,(%r14,%rbx,8)
0x7fffe4924650: movzbl 0x3(%r13),%ebx
0x7fffe4924655: add $0x3,%r13
0x7fffe4924659: movabs $0x7ffff7d813c0,%r10
0x7fffe4924663: jmpq *(%r10,%rbx,8)
// скорее всего это goto 12
0x7fffe49256df: mov -0x18(%rbp),%rcx
0x7fffe49256e3: movswl 0x1(%r13),%edx
0x7fffe49256e8: bswap %edx
0x7fffe49256ea: sar $0x10,%edx
0x7fffe49256ed: movslq %edx,%rdx
0x7fffe49256f0: add %rdx,%r13
0x7fffe49256f3: movzbl 0x0(%r13),%ebx
0x7fffe49256f8: testb $0x8,0x108(%r15)
0x7fffe4925700: je 0x7fffe492570e
0x7fffe492570e: movabs $0x7ffff7d813c0,%r10
0x7fffe4925718: jmpq *(%r10,%rbx,8)


После того как в отладчике gdb трасса исполнения замкнулась и начала повторяться, то по моим подсчетам получилось так раз 9 участков кода — по одному на каждую байткод инструкцию. В нерелизных сборках OpenJDK очень много отладочных опций, но у меня сейчас под рукой нет таких сборок. В данном случае использую сугубо дистрибутивную java-машину. А значит придется опираться на догадки о соответствии байткод инструкций и соответствующих участках в трассе исполнение. Можно ли на основе приведенных трасс однозначно утверждать о наиболее быстрости одного или другого компилятора? Во-первых не настолько хорошо разбираюсь в x86-асемблере и устройстве x86-процессоров, чтобы только по asm-тексту предсказать точное время работы. Во-вторых, и что гораздо важнее, сравнение двух интерпретаторов из совершенно разных виртуальных машин, на разных байткод программах — это не особо корректная задача. В разных виртуальных машинах может выполнятся разный набор семантических и технологических действий. По-разному может быть устроено взаимодействие между интерпретатором и jit-компилятором и могут применяться разные стратегии jit-компиляции, определяющие дополнительную нагрузку на процесс интерпретации.

Но просто ради интереса посмотрим на абсолютное время работы разных байткод программ, в разных виртуальных машинах, на разных интерпретаторах. В конце концов, геометрия — это искусство делать правильные выводы из некорректных рисунков. И да, на разных x86-процессорах результаты могут несколько отличаться, а Вы как думали :)? Не исключено, нужно было как-то по особому собирать пример из проекта interpreters-comparison, однако про это ничего не сообщалось. Поэтому запускаем как есть:

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

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

В доступе у меня была вот такая x86-машина:
model name : Intel(R) Xeon(R) CPU E5-2690 v2 @ 3.00GHz
openjdk 11.0.6 2020-01-14

Программа native — это реализация на языке Си. Программа asmopt — это, судя по всему, наиболее быстрый интерпретатор. Программа Main — это реализация на языке Java. Здесь надо отметить, что автор статьи про наиболее быстрый интерпретатор приводит другие данные:

и получил время 3.945s (сравните с 3.228s …)

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

Значит, 3.945 / 3.228 = 1.22, другими словами, утверждается, что наиболее быстрый интерпретатор по абсолютному времени на разных байткод программах в разных виртуальных машинах с разной семантикой быстрее на 22%. У меня при измерениях указанным образом получилось наоборот 7.739 / 6.686 = 1.15, на 15% быстрее OpenJDK. Но в любом случае замах-то был на JIT-компиляторы! Не меньше! В конце концов, но у Вас же изначально есть тест native, так поделите две чиселки и получите 7.739 / 1.253 = 6.2 раза, Карл, или какое там у Вас соотношение получается. Где элементарная логика и откуда только берется это «Является ли JIT (или AOT) — нашей последней надеждой на производительность?«.

Итак, мне и всем читателям статьи про наиболее быстрый интерпретатор в самом начале пообещали, что

обгонять JIT/AOT-компиляцию по скорости

А что в итоге? Рассказали, как достичь результатов по скорости интерпретатора, которые по сути мало чем отличаются от результатов, достигнутых для интерпретаторов в OpenJDK/Firefox/Chrome/CoreNET много лет назад? Ну повторили, и что. А слабо сделать полноценную java машину-то? Ее-то повторите? И где это обещанное «обогнать»? Вот JIT-компилятор OpenJDK по сути догоняет реализацию на Си-коде и если увеличить время работы теста так и в принципе догонит. Это да. Это легко проверить и пощупать. Так что к чему все эти попытки по бросанию камней в огород JIT-компиляции? В общем сплошной кликбейт на марше.