>> смывает TLB Все так. И в реальных программах именно это и происходит, поэтому я склонен оставлять это в бенчмарке как возмущающий элемент реальной жизни
Вариант без printf() несложно получить, но я упорствую в своем глупом мнении, что printf() это правильная, реальная нагрузка, которая в числе прочего вымывает из кэша полезные для производительности линии.
(32*1024) / (255*6) 32килобайтный кэш / 6 вариантов всех 255 инструкций
Вот результаты бенчмарка с размером задачи 100000 (как в оригинале). Интересующий нас столбец - asmtrm
В результате мы экономим пространство за счет времени исполнения (в asmexp все функции выровнены на 0x80, а в asmtrm - на 0x10). На моей машине L1 кэш инструкций составляет 704 килобайта, поэтому имеет смысл использовать трамплины для того чтобы иметь несколько наборов кода - пока мы попадаем в кэш.
Можно попробовать оценить, сколько можно иметь кодовых наборов. За образец можно взять виртуальную машину WASM, у нее однобайтовый опкод, на текущий момент занято где-то 200 команд, но можно брать по максимуму - 255.
Даже если кешировать три элемента стека (а не два, как сейчас) и мы хотим варианты наборов процедур для всех перестановок, нам нужно 6 вариантов. Тогда мы попадаем в этот кэш при среднем размере процедуры в 471 байт (что довольно много).
На практике не все опкоды из этих 255 работают со стеком, так что можно чувствовать себя еще свободнее. Но на машине @checkpoint c 32 килобайтами средний размер процедуры будет только 21 байт, что уже несколько стесняет, даже если мы будем расширять большие процедуры за счет тех что меньше среднего размера.
Спасибо за уточнение и, конечно, за оригинальную статью, она вдохновляет.
Мне кажется в этой теме еще довольно много пространства для работы студентов: не только оптимизация, но и, например: - написание отладчика байткода, - сэмплирующего профайлера, - инструмента для определения целей для Instr_Jump, Instr_Je и Instr_Jne, чтобы правильно собирать суперинструкции, - сама сборка суперинструкций, - и наконец, jit-компилятор, опирающийся на профилировку времени исполнения.
Уже хватит на несколько курсовых, ну или семестровых работ - я не знаю актуальный уровень студентов. У меня ушло где-то две недели по вечерам на написание ассемблерного интерпретатора, допускаю что среднему студенту потребуется больше времени.
А ведь можно взяться за что-то посложнее: - применение деоптимизаций в случаях есть байткоду позволяется самомодификция (нужно будет расширить список опкодов), - компилятор небольшого подмножества си-подобного языка в байткод, - построение объектной системы, - эвристический декомпилятор, восстанавливающий высокоуровневые конструкции языка из байткода, - написание генетического алгоритма построения программы для прохождения какой-нибудь классической игры, вроде диггера, или даже марио и минимизация её методами машинного обучения.
Что-то из этого (или даже все) я бы с удовольствием прочел на хабре.
= 0.00017558259 % составляют вызовы байткода Instr_Print от всех вызовов всех байткодов. Если принт руинит перформанс при таком проценте, то я прям даже не знаю..
Есть один аспект, когда компилятор хуже: отладка. Отладчик байткода пишется довольно легко (я даже думаю, не написать ли об этом следующую статью). Но если мы компилируем, да еще и применяем оптимизации, то сложность отладчика резко возрастает и это перестает быть "проектом выходного дня".
Я бы оставил printf() считая его частью задачи. Редко мы используем интерпретаторы общего назначения исключительно для числодробилок без i/o. Для того чтобы нивелировать случайные эффекты, лучше запускать бенчмарк 5 раз, как это сделано у @Atakua. С увеличением задачи согласен, все стало уже слишком быстрым
Я работаю над этим сейчас, пока результаты спорные: - с одной стороны больше кода - бранч-предиктору легче (но возможно это проявляется лишь на коротких программах как представленная @Atakua - с другой стороны, больше кода - больше кэш-миссов - с третьей вообще все очень сильно зависит от нюансов ассемблерной реализации и сочетания с другими способами оптимизации. Для такого тюнинга уже хочется иметь какой-то решатель, который выбирает способ оптимизации в зависимости от внешних условий. Но это уже круто отличается от подхода "давайте возьмем интерпретатор, напишем его возможно более оптимально, и нам не потребуется писать сложный jit" - т.к. такой селектор оптимизаций будет приближаться по сложности к jit.
Моя статья своей задачи достигла: интерпретатор с малой сложностью показывает достаточно высокую производительность (даже выше чем ожидалось) путем применения небольшого количества приемов. Можно применить больше приемов и выжать еще немного.
Дальше есть два пути: 1. попробовать включить два приема, предложенных в комментариях: - отказ о указателя на таблицу сервисных процедур (все процедуры будут одного размера) - зависимость набора процедур от состояния стека (его глубины и порядка элементов в нем, возможно что-то еще) 2. двигаться в сторону суперинструкций, объединяя в одну инструкцию идущие подряд. Строго говоря, это уже немного jit (я считаю что граница проходит там, где мы начинаем создавать машинный код на который передаем управление)
Оба этих подхода интересные, но увеличивают сложность и становятся ненадежными с точки зрения выигрыша: первый зависит попадания процедур в кэш, второй требует нахождения компромисса между затратами на предобработку и ускорением обработанного байткода. Вывод будет неочевидным - если затюнить параметры иначе можно получить радикально отличающиеся бенчмарки. (Это было бы хорошо если бы мне платили за развязывание споров.) В моей статье этой неочевидности нет - ассемблерный оптимизированный интерпретатор реально быстрый и очевидно по каким причинам.
Да, конечно, забыл, но в оправдание могу сказать, что я просто хотел чтобы ось Y начиналась от нуля, а то это получается "лгать при помощи графиков".
Сейчас я пытаюсь проверить, как распределение кода влияет на промахи кэша. Выше уже предложили (а я немного адаптировал идею), что если оставлять в начале сервисной процедуры только 16-32 байт кода, а до остального прыгать jump-ом то может быть это сможет дать лучшее попадание в кэш для тех процедур, которые не превышают эти 16-32 байта и не такую большую просадку из-за jump-а потому что он будет хорошо предсказываться.
Убирать нельзя, т.к. в исходной статье измерения проводятся вместе с printf. С другой стороны она не оказывает серьезного влияния на общий бенчмарк, т.к. вызывается всего лишь 9592 раз.
Решение, на мой взгляд, есть - переход от общего взвешивания к индивидуальному. Я бы хотел чтобы у каждой статьи или комментария плюс человека, которому я доверяю весил во много раз больше, чем плюс нонейма. Таким образом будет формироваться мой, индивидуализированный рейтинг статьи, а не общехабровский рейтинг "миллиона мух"
>> смывает TLB
Все так. И в реальных программах именно это и происходит, поэтому я склонен оставлять это в бенчмарке как возмущающий элемент реальной жизни
Вариант без printf() несложно получить, но я упорствую в своем глупом мнении, что printf() это правильная, реальная нагрузка, которая в числе прочего вымывает из кэша полезные для производительности линии.
(32*1024) / (255*6)
32килобайтный кэш / 6 вариантов всех 255 инструкций
Да, проверил трамплины: https://habr.com/ru/articles/856480/comments/#comment_27547640
Я нашел время проверить, насколько трамплины замедляют выполнение, сделал таблицу трамплинов:
на старте ее адрес загружается в %rdi
dispatch теперь стал таким:
Вот результаты бенчмарка с размером задачи 100000 (как в оригинале). Интересующий нас столбец - asmtrm
В результате мы экономим пространство за счет времени исполнения (в asmexp все функции выровнены на 0x80, а в asmtrm - на 0x10). На моей машине L1 кэш инструкций составляет 704 килобайта, поэтому имеет смысл использовать трамплины для того чтобы иметь несколько наборов кода - пока мы попадаем в кэш.
Можно попробовать оценить, сколько можно иметь кодовых наборов. За образец можно взять виртуальную машину WASM, у нее однобайтовый опкод, на текущий момент занято где-то 200 команд, но можно брать по максимуму - 255.
Даже если кешировать три элемента стека (а не два, как сейчас) и мы хотим варианты наборов процедур для всех перестановок, нам нужно 6 вариантов. Тогда мы попадаем в этот кэш при среднем размере процедуры в 471 байт (что довольно много).
На практике не все опкоды из этих 255 работают со стеком, так что можно чувствовать себя еще свободнее. Но на машине @checkpoint c 32 килобайтами средний размер процедуры будет только 21 байт, что уже несколько стесняет, даже если мы будем расширять большие процедуры за счет тех что меньше среднего размера.
На этих бенчмарках вызов printf() не удалялся
Возможно res стоит возвращать: я не знаю насколько умный компилятор Java но он может соптимизировать цикл т.к. res нигде не применяется
Предлагаю проверить. Я немного занят рабочей задачей прямо сейчас, смогу вернуться к интерпретатору после ее решения
Спасибо за уточнение и, конечно, за оригинальную статью, она вдохновляет.
Мне кажется в этой теме еще довольно много пространства для работы студентов: не только оптимизация, но и, например:
- написание отладчика байткода,
- сэмплирующего профайлера,
- инструмента для определения целей для Instr_Jump, Instr_Je и Instr_Jne, чтобы правильно собирать суперинструкции,
- сама сборка суперинструкций,
- и наконец, jit-компилятор, опирающийся на профилировку времени исполнения.
Уже хватит на несколько курсовых, ну или семестровых работ - я не знаю актуальный уровень студентов. У меня ушло где-то две недели по вечерам на написание ассемблерного интерпретатора, допускаю что среднему студенту потребуется больше времени.
А ведь можно взяться за что-то посложнее:
- применение деоптимизаций в случаях есть байткоду позволяется самомодификция (нужно будет расширить список опкодов),
- компилятор небольшого подмножества си-подобного языка в байткод,
- построение объектной системы,
- эвристический декомпилятор, восстанавливающий высокоуровневые конструкции языка из байткода,
- написание генетического алгоритма построения программы для прохождения какой-нибудь классической игры, вроде диггера, или даже марио и минимизация её методами машинного обучения.
Что-то из этого (или даже все) я бы с удовольствием прочел на хабре.
(9592 / 5462956111) * 100
= 0.00017558259 % составляют вызовы байткода Instr_Print от всех вызовов всех байткодов. Если принт руинит перформанс при таком проценте, то я прям даже не знаю..
Есть один аспект, когда компилятор хуже: отладка. Отладчик байткода пишется довольно легко (я даже думаю, не написать ли об этом следующую статью). Но если мы компилируем, да еще и применяем оптимизации, то сложность отладчика резко возрастает и это перестает быть "проектом выходного дня".
Я бы оставил printf() считая его частью задачи. Редко мы используем интерпретаторы общего назначения исключительно для числодробилок без i/o. Для того чтобы нивелировать случайные эффекты, лучше запускать бенчмарк 5 раз, как это сделано у @Atakua. С увеличением задачи согласен, все стало уже слишком быстрым
Я работаю над этим сейчас, пока результаты спорные:
- с одной стороны больше кода - бранч-предиктору легче (но возможно это проявляется лишь на коротких программах как представленная @Atakua
- с другой стороны, больше кода - больше кэш-миссов
- с третьей вообще все очень сильно зависит от нюансов ассемблерной реализации и сочетания с другими способами оптимизации. Для такого тюнинга уже хочется иметь какой-то решатель, который выбирает способ оптимизации в зависимости от внешних условий. Но это уже круто отличается от подхода "давайте возьмем интерпретатор, напишем его возможно более оптимально, и нам не потребуется писать сложный jit" - т.к. такой селектор оптимизаций будет приближаться по сложности к jit.
Моя статья своей задачи достигла: интерпретатор с малой сложностью показывает достаточно высокую производительность (даже выше чем ожидалось) путем применения небольшого количества приемов. Можно применить больше приемов и выжать еще немного.
Дальше есть два пути:
1. попробовать включить два приема, предложенных в комментариях:
- отказ о указателя на таблицу сервисных процедур (все процедуры будут одного размера)
- зависимость набора процедур от состояния стека (его глубины и порядка элементов в нем, возможно что-то еще)
2. двигаться в сторону суперинструкций, объединяя в одну инструкцию идущие подряд. Строго говоря, это уже немного jit (я считаю что граница проходит там, где мы начинаем создавать машинный код на который передаем управление)
Оба этих подхода интересные, но увеличивают сложность и становятся ненадежными с точки зрения выигрыша: первый зависит попадания процедур в кэш, второй требует нахождения компромисса между затратами на предобработку и ускорением обработанного байткода. Вывод будет неочевидным - если затюнить параметры иначе можно получить радикально отличающиеся бенчмарки. (Это было бы хорошо если бы мне платили за развязывание споров.) В моей статье этой неочевидности нет - ассемблерный оптимизированный интерпретатор реально быстрый и очевидно по каким причинам.
Я в чем-то неправ?
Экспериментирую тут https://github.com/rigidus/interpreters-comparison/tree/checkpoint (можно на ты, так как-то привычнее - я родом из интернета до роскомнадзора)
Думаю о комбинации этих идей: https://habr.com/ru/articles/856480/comments/#comment_27534590
Да, конечно, забыл, но в оправдание могу сказать, что я просто хотел чтобы ось Y начиналась от нуля, а то это получается "лгать при помощи графиков".
Сейчас я пытаюсь проверить, как распределение кода влияет на промахи кэша. Выше уже предложили (а я немного адаптировал идею), что если оставлять в начале сервисной процедуры только 16-32 байт кода, а до остального прыгать jump-ом то может быть это сможет дать лучшее попадание в кэш для тех процедур, которые не превышают эти 16-32 байта и не такую большую просадку из-за jump-а потому что он будет хорошо предсказываться.
Кажется что разница значительная, но на самом деле картинка вводит в заблуждение. Добавление native варианта позволяет сопоставить в масштабе
У меня вот такие результаты.
Можно ли ссылку на форк с изменениями?
Убирать нельзя, т.к. в исходной статье измерения проводятся вместе с printf. С другой стороны она не оказывает серьезного влияния на общий бенчмарк, т.к. вызывается всего лишь
9592раз.Решение, на мой взгляд, есть - переход от общего взвешивания к индивидуальному. Я бы хотел чтобы у каждой статьи или комментария плюс человека, которому я доверяю весил во много раз больше, чем плюс нонейма. Таким образом будет формироваться мой, индивидуализированный рейтинг статьи, а не общехабровский рейтинг "миллиона мух"
попробуешь провести экперимент? там в Makefile чтобы запустить бенчмарк достаточно