Изначально все задержки в коде рассчитаны под v3, где у load'а минимальная задержка в 3 такта. На >= v4 нужно добавлять такты под новую задержку load'ов :(, иначе будут блокировки.
В этом файле реализация интерпретатора на e2k-ассемблере некоторого "типового" байткода. У байткода очень "жирная" кодировка, но зато классический loop + switch оптимизирован по самую маковку.
Если будут еще соревнования, то как основа для задачи под звездочкой вот здесь есть интерпретатор https://gitflic.ru/project/e2khome/lccrt/blob?file=lib%2Firr%2Flccrt_jite2k.c&branch=master одной виртуальной машины, написанный на e2k-ассемблере. Особенность данного интерпретатора, что вместо switch-case, в нем есть таблица переходов и подготовка перехода выполняется явно с помощью ассемблера. Есть конвейризация, то есть начало исполнения следующей байткод-инструкции совмещено за счет широкой команды с завершением исполнения текущей команды. Интерпретатор получился весьма шустрым, реально шустрым и в чем-то сопоставимым с шаблонным транслятором, плата - это очень жирный байт-код. Вместо кода инструкции хранится 8-байтный адрес перехода. Также особенностью интерпретатора является то, что для каждой байткод-команды есть ровно две реализации. Одна со станками C0/C1, а другая со станками C2/C3. И эти реализации чередуются как черные и белые шахматные клетки.
За последние 2 месяца были проведены работы по оптимизации вызовов из библиотеки runtime-поддержки liblccrt_s (все функции с префиксом __lccrt_) для Mesa в режиме llvmpipe.
Давно есть планы сделать "ленивую" компиляцию для llvm-JIT в рамках llvm-lcc (сначала на -O1, а потом на -O3 в фоне с горячей заменой скрытой от пользователя), но пока банально не хватает ресурсов.
Компилятор clang преобразует C++ код в llvm-IR. Представление llvm-IR - это почти язык Си, но только с invoke/landigpad'ами (и то можно обойтись парой setjmp/longjmp). По сути всё lower-ится в Си. После lowering'а будут только глобалы/локалы и указатели с load/store'ами. Куда пишем - "слева", что пишем - "справа".
В целом по картинкам из статьи - очень красиво. Подскажите, пожалуйста, дуги между блоками создаются вручную (итоговый путь на холсте)? Можно ли перетаскивать блоки? При перетаскивании блока, что происходит с отображением дуг?
Любой out-of-order процессор, для получения производительности скорее всего будет в общем и целом копировать x86. (Но это мои предположения.) Иначе он будет отставать по производительности. Топовые процессоры ARM по-моему тоже уже давно out-of-order. Как впрочем и MIPS.
Интел несколько раз кажется собирался сделать данные о микрокоде открытыми. Но так и не стал этого делать. Иначе потеряется совместимость (во все стороны). Код собранный под один конкретный процессор может элементарно не заработать на другом. А IT-индустрия к этому не привыкла. И по-моему проприетарная интеловская библиотека MKL оптимизирована под каждую разновидность процессора.
Также надо помнить о том, что x86-ассемблер и x86-регистры - это давно уже виртуальный ассемблер и виртуальные регистры. Аппаратура на лету преобразует их микро-код и на лету работает аппаратный распределитель регистров. Реальные инструкции микро-кода на лету перемешиваются и выполняются в оптимальном порядке. Это еще до всякого конвейера!!! То есть на конвейер идет уже цепочка микро-кода.
Если адрес load'а из микро-кода известен за ранее. И аппаратный планировщик установил отсутствие зависимостей с операциями записи, то аппаратный планировщик может спланировать такой load раньше других операций. Тем самым уменьшается вероятность промаха в кеш.
Как-то видел статью (но потом не смог ее найти), в которой говорилось про один из x86-процессоров, что в нем есть несколько АЛУ-устройств и несколько разноплановых инструкций микро-кода могут выполняться параллельно. То есть в конвейере еще может быть и несколько трактов исполнения. А вы говорите никто в мире не делает VLIW'ов :)))). Просто вам это может быть не видно.
Как конкретно работает тот или иной x86/arm/mips/riscv-процессор - это коммерческая тайна. И кто хитрее сделает предсказатель, тот на НЕКОТОРЫХ задачах и будет быстрее. Под любой предсказатель можно сделать антипаттерн.
Одним из первых конвейер в процессоре применил академик Лебедев. Идея конечно носилось в воздухе.
В конвейере исполнение операций разбито на стадии. И инструкции исполняются не последовательно а одновременно. Точнее до того, как закончилось исполнение предыдущих операций начинается исполнение следующих.
Чем отличается исполнение бранча по фиксированному смещению, от бранча по регистру. На стадии декодирования инструкции уже известен адрес перехода. Поэтому конвейер может приступить к началу исполнения инструкций за бранчем. А вот для бранча по регистру адрес перехода становится только после того, как будет прочитано значение регистра. А это происходит на несколько стадий позже. Поэтому бранчи по косвенности работают заметно медленнее. Поэтому вызов виртуальной функции по умолчанию более медленный, чем явный вызов функции по имени.
В x86 процессорах (и других out-of-order процессорах) есть предсказатель переходов. Простой предсказатель по ip-адресу бранча может закешировать адрес перехода. Грубо говоря, если последние 7 раз подряд вы перешли на один и тот же адрес из данного ip, то скорее всего и на 8 раз из данного ip туда перейдете. В чем отличие интерпретатора и почему, в частности, помогает даже шаблонный транслятор. После исполнения, например, байткод-инструкции PUSH для некоторой байткод-программы вы перейдете на произвольную байткод-инструкцию. Только в очень маленьком и простом цикле последовательность байткод-команд будет фиксированной. И только в этом случае будет хорошо работать предсказатель. Например, в этом цикле после PUSH всегда идет SUB. И тогда к ip-бранчу в конце PUSH закешируется ip-адрес начала участка интерпретации SUB. А если после PUSH иногда SUB, иногда LOAD, иногда SWAP, то предсказатель не сможет "угадывать" адрес.
Сугубо в рамках научной дискуссии. У меня есть пример с "абстрактной" виртуальной машиной с регистровым, а не стековым байткодом. Регистры конечно виртуальные. Байткод более жирный (сейчас это не так критично как в 90-е), исполнение одной инструкции более длинное. Но количество инструкций в среднем меньше. Смотрел только на двух модельных тестах. Регистровый байткод получался из пропатченного javac. Тем самым в обоих случаях было одинаковое java-AST.
В режиме только интерпретации время исполнения получилось одинаковое с OpenJDK. То есть в среднем стековый и регистровый интерпретаторы дали на x86 в моем случае одинаковый результат. (Но в разных виртуальных машинах.)
Почему регистровая машина? Лично мне примерно известно как сделать быстрый регистровый интерпретатор для одного in-order процессора, но неизвестно как для этого процессора сделать быстрый стековый интерпретатор. Кроме того, на регистровом представлении (llvm-IR подобном) удобно делать peephole-оптимизации.
Написание статьи - дело хлопотное, особенно когда в основе есть только гипотезы и домыслы. Ради хохмы, здесь и сейчас могу предложить презентацию с доклада :) на близкую тему. Презентация небольшая, много времени не займет. Вдруг лично для Вас там будут интересные идеи.
После доклада ко мне подошел сотрудник Huawei (бывший коллега) и сказал, что (на весну 2023) они уже два или три года (точно не помню) уже занимаются схожим проектом в Huawei. Как обычно все украдено до нас :). Но у Huawei есть на "стартапы" ресурсы :(.
Это прописные, азбучные истины. Изложены они правильно и хорошо. И они верны, на то они и прописные. Периодически их действительно надо повторять.
От себя добавлю еще одну. При фиксировании spec-набора любой оптимизатор очень быстро становится спеко-ориентированным. Причем без фиксации spec-набора (бенчмарков) сравнения невозможны в принципе. Так и живем :).
Тем не менее, основной посыл в моей статье не про сравнение производительности двух "абстрактных" интерпретаторов.
В данном случае меня не интересует гадание на кофейной гуще. Меня интересуют данные, которые можно измерить, для которых можно провести эксперимент. Это в схоластике можно до бесконечности спорить о том, сколько ангелов может поместиться на конце булавочной jl-иголки.
Была идея поместить обе трассы в asm-файлы. Подготовить входные данные как-то массивы с байткодом, массивы с начальным состояниям стеков, сделать asm-вставки, чтобы записать в нужные регистры ссылки на массивы. И зациклить работу, чтобы иметь рафинированные измерения. Тогда были бы два компактных и удобных теста для дальнейшего исследования. Задача любопытная, но трудоемкая. Поэтому оставим ее разработчикам наиболее быстрого интерпретатора. Они же не платят мне за работу аналитика :)?
Так что мне хватило макро-измерений с помощью time. И даже если будет их запуск (В ДРУГОМ JIT-КОНТЕКСТЕ!!!) на 30% быстрее, и что? Это не принципиально.
Меня ИНТЕРЕСУЕТ СОВСЕМ ДРУГОЕ - где ОБГОН JIT/AOT? Хотя бы ДОГОН. А для этого нужны не десятки процентов. Для это нужны разы.
Изначально все задержки в коде рассчитаны под v3, где у load'а минимальная задержка в 3 такта. На >= v4 нужно добавлять такты под новую задержку load'ов :(, иначе будут блокировки.
Ссылка от "тех.поддержки" :), вдруг будет интересно
https://gitflic.ru/project/e2khome/lccrt/blob?file=lib%2Firr%2Flccrt_jite2k.c&branch=master
В этом файле реализация интерпретатора на e2k-ассемблере некоторого "типового" байткода. У байткода очень "жирная" кодировка, но зато классический loop + switch оптимизирован по самую маковку.
Если будут еще соревнования, то как основа для задачи под звездочкой вот здесь есть интерпретатор https://gitflic.ru/project/e2khome/lccrt/blob?file=lib%2Firr%2Flccrt_jite2k.c&branch=master одной виртуальной машины, написанный на e2k-ассемблере. Особенность данного интерпретатора, что вместо switch-case, в нем есть таблица переходов и подготовка перехода выполняется явно с помощью ассемблера. Есть конвейризация, то есть начало исполнения следующей байткод-инструкции совмещено за счет широкой команды с завершением исполнения текущей команды. Интерпретатор получился весьма шустрым, реально шустрым и в чем-то сопоставимым с шаблонным транслятором, плата - это очень жирный байт-код. Вместо кода инструкции хранится 8-байтный адрес перехода. Также особенностью интерпретатора является то, что для каждой байткод-команды есть ровно две реализации. Одна со станками C0/C1, а другая со станками C2/C3. И эти реализации чередуются как черные и белые шахматные клетки.
Поддержка elbrus-v2 завершена:
https://gitflic.ru/project/e2khome/llvm-project-e-2-k/commit/17696e0bc40cbc2cbca95c07b90ffab5ce06222a
Если найдется время, то хорошо бы снять профиль
$$ perf record ...За последние 2 месяца были проведены работы по оптимизации вызовов из библиотеки runtime-поддержки liblccrt_s (все функции с префиксом __lccrt_) для Mesa в режиме llvmpipe.
В ближайшее время в дистрибутив скорее всего будут обновлены версии liblccrt/libccopt до:
ECOMP_R30_COMMIT=148093LLVM_13_COMMIT=8337f2844ab67ce6078fcc89b762ead65ada9d5eLLVM_17_COMMIT=cbf84a8f35917ad76435f4ec92661f859fbf88bdДавно есть планы сделать "ленивую" компиляцию для llvm-JIT в рамках llvm-lcc (сначала на -O1, а потом на -O3 в фоне с горячей заменой скрытой от пользователя), но пока банально не хватает ресурсов.
Чтобы собрать llvm-17 с заданием версии процессора по умолчанию можно использовать параметры из этого комита:
https://gitflic.ru/project/e2khome/llvm-project-e-2-k/commit/afc470d078cdaa3625c75dcf5936d2af91e23cc6
Компилятор clang преобразует C++ код в llvm-IR. Представление llvm-IR - это почти язык Си, но только с invoke/landigpad'ами (и то можно обойтись парой setjmp/longjmp). По сути всё lower-ится в Си. После lowering'а будут только глобалы/локалы и указатели с load/store'ами. Куда пишем - "слева", что пишем - "справа".
Какие есть не сложные способы автоматического проведения дуг?
В целом по картинкам из статьи - очень красиво.
Подскажите, пожалуйста, дуги между блоками создаются вручную (итоговый путь на холсте)? Можно ли перетаскивать блоки? При перетаскивании блока, что происходит с отображением дуг?
Любой out-of-order процессор, для получения производительности скорее всего будет в общем и целом копировать x86. (Но это мои предположения.) Иначе он будет отставать по производительности. Топовые процессоры ARM по-моему тоже уже давно out-of-order. Как впрочем и MIPS.
Интел несколько раз кажется собирался сделать данные о микрокоде открытыми. Но так и не стал этого делать. Иначе потеряется совместимость (во все стороны). Код собранный под один конкретный процессор может элементарно не заработать на другом. А IT-индустрия к этому не привыкла. И по-моему проприетарная интеловская библиотека MKL оптимизирована под каждую разновидность процессора.
_
Если load заблокировался аппаратный планировщик может начать исполнять другие инструкции, для которых уже готовы значения входных операндов.
Утилита perf по-моему умеет выводить статистику о среднем количестве инструкций микрокода на один такт процессора.
Поэтому замеры, замеры и еще раз замеры!
Также надо помнить о том, что x86-ассемблер и x86-регистры - это давно уже виртуальный ассемблер и виртуальные регистры. Аппаратура на лету преобразует их микро-код и на лету работает аппаратный распределитель регистров. Реальные инструкции микро-кода на лету перемешиваются и выполняются в оптимальном порядке. Это еще до всякого конвейера!!! То есть на конвейер идет уже цепочка микро-кода.
Если адрес load'а из микро-кода известен за ранее. И аппаратный планировщик установил отсутствие зависимостей с операциями записи, то аппаратный планировщик может спланировать такой load раньше других операций. Тем самым уменьшается вероятность промаха в кеш.
Как-то видел статью (но потом не смог ее найти), в которой говорилось про один из x86-процессоров, что в нем есть несколько АЛУ-устройств и несколько разноплановых инструкций микро-кода могут выполняться параллельно. То есть в конвейере еще может быть и несколько трактов исполнения. А вы говорите никто в мире не делает VLIW'ов :)))). Просто вам это может быть не видно.
Как конкретно работает тот или иной x86/arm/mips/riscv-процессор - это коммерческая тайна. И кто хитрее сделает предсказатель, тот на НЕКОТОРЫХ задачах и будет быстрее. Под любой предсказатель можно сделать антипаттерн.
Одним из первых конвейер в процессоре применил академик Лебедев. Идея конечно носилось в воздухе.
В конвейере исполнение операций разбито на стадии. И инструкции исполняются не последовательно а одновременно. Точнее до того, как закончилось исполнение предыдущих операций начинается исполнение следующих.
Чем отличается исполнение бранча по фиксированному смещению, от бранча по регистру. На стадии декодирования инструкции уже известен адрес перехода. Поэтому конвейер может приступить к началу исполнения инструкций за бранчем. А вот для бранча по регистру адрес перехода становится только после того, как будет прочитано значение регистра. А это происходит на несколько стадий позже. Поэтому бранчи по косвенности работают заметно медленнее. Поэтому вызов виртуальной функции по умолчанию более медленный, чем явный вызов функции по имени.
В x86 процессорах (и других out-of-order процессорах) есть предсказатель переходов. Простой предсказатель по ip-адресу бранча может закешировать адрес перехода. Грубо говоря, если последние 7 раз подряд вы перешли на один и тот же адрес из данного ip, то скорее всего и на 8 раз из данного ip туда перейдете. В чем отличие интерпретатора и почему, в частности, помогает даже шаблонный транслятор. После исполнения, например, байткод-инструкции PUSH для некоторой байткод-программы вы перейдете на произвольную байткод-инструкцию. Только в очень маленьком и простом цикле последовательность байткод-команд будет фиксированной. И только в этом случае будет хорошо работать предсказатель. Например, в этом цикле после PUSH всегда идет SUB. И тогда к ip-бранчу в конце PUSH закешируется ip-адрес начала участка интерпретации SUB. А если после PUSH иногда SUB, иногда LOAD, иногда SWAP, то предсказатель не сможет "угадывать" адрес.
Сугубо в рамках научной дискуссии. У меня есть пример с "абстрактной" виртуальной машиной с регистровым, а не стековым байткодом. Регистры конечно виртуальные. Байткод более жирный (сейчас это не так критично как в 90-е), исполнение одной инструкции более длинное. Но количество инструкций в среднем меньше. Смотрел только на двух модельных тестах. Регистровый байткод получался из пропатченного javac. Тем самым в обоих случаях было одинаковое java-AST.
В режиме только интерпретации время исполнения получилось одинаковое с OpenJDK. То есть в среднем стековый и регистровый интерпретаторы дали на x86 в моем случае одинаковый результат. (Но в разных виртуальных машинах.)
Почему регистровая машина? Лично мне примерно известно как сделать быстрый регистровый интерпретатор для одного in-order процессора, но неизвестно как для этого процессора сделать быстрый стековый интерпретатор. Кроме того, на регистровом представлении (llvm-IR подобном) удобно делать peephole-оптимизации.
Написание статьи - дело хлопотное, особенно когда в основе есть только гипотезы и домыслы. Ради хохмы, здесь и сейчас могу предложить презентацию с доклада :) на близкую тему. Презентация небольшая, много времени не займет. Вдруг лично для Вас там будут интересные идеи.
После доклада ко мне подошел сотрудник Huawei (бывший коллега) и сказал, что (на весну 2023) они уже два или три года (точно не помню) уже занимаются схожим проектом в Huawei. Как обычно все украдено до нас :). Но у Huawei есть на "стартапы" ресурсы :(.
Это прописные, азбучные истины. Изложены они правильно и хорошо. И они верны, на то они и прописные. Периодически их действительно надо повторять.
От себя добавлю еще одну. При фиксировании spec-набора любой оптимизатор очень быстро становится спеко-ориентированным. Причем без фиксации spec-набора (бенчмарков) сравнения невозможны в принципе. Так и живем :).
Тем не менее, основной посыл в моей статье не про сравнение производительности двух "абстрактных" интерпретаторов.
В данном случае меня не интересует гадание на кофейной гуще. Меня интересуют данные, которые можно измерить, для которых можно провести эксперимент. Это в схоластике можно до бесконечности спорить о том, сколько ангелов может поместиться на конце булавочной jl-иголки.
Была идея поместить обе трассы в asm-файлы. Подготовить входные данные как-то массивы с байткодом, массивы с начальным состояниям стеков, сделать asm-вставки, чтобы записать в нужные регистры ссылки на массивы. И зациклить работу, чтобы иметь рафинированные измерения. Тогда были бы два компактных и удобных теста для дальнейшего исследования. Задача любопытная, но трудоемкая. Поэтому оставим ее разработчикам наиболее быстрого интерпретатора. Они же не платят мне за работу аналитика :)?
Так что мне хватило макро-измерений с помощью time. И даже если будет их запуск (В ДРУГОМ JIT-КОНТЕКСТЕ!!!) на 30% быстрее, и что? Это не принципиально.
Меня ИНТЕРЕСУЕТ СОВСЕМ ДРУГОЕ - где ОБГОН JIT/AOT? Хотя бы ДОГОН. А для этого нужны не десятки процентов. Для это нужны разы.