Comments 26
Каждый виртуальный вызов:
Чтение vtable pointer
Чтение адреса функции из vtable
Indirect jump (CPU не может предсказать)
а обычный вызов (или direct jump) CPU может предсказать?
Вроде там кеш памяти программ должен работать, ему вроде бы пофигу Indirect jump это или direct jump, если вызов по тому же адресу повторяется кеш работает, если адрес новый то нет.
Чтение адреса функции из vtable - это чтение ИНТа, Чтение vtable pointer - совсем необязательно - это обычно конст-экспрешен как раз, но вообще это то же чтение ИНТа.
Обычный прямой вызов предсказывать не надо, там адрес однозначно вычисляется ) На косвенных и условных включается предсказатель, там уже как получится.
Чтение vtable pointer - совсем необязательно - это обычно конст-экспрешен как раз
С чего бы (если у нас иерархия наследования и приходит указатель на объект базового класса, часто абстрактного)? И в любом случае зачитывание нескольких слов из памяти - это не бесплатно (причём в данном случае второе чтение зависит от первого, там как что на клоктики влияет latency того уровня памяти, в который попадём).
С чего бы (если у нас иерархия наследования и приходит указатель на объект базового класса, часто абстрактного)?
таблица виртуальных функций определена даже через абстрактный базовый класс статически, иначе как компилятор может найти ее? Сколько бы там не было уровней наследования они просто меняют значения в ячейках этой таблицы, сама таблица уже не меняется, или я чего-то не учитываю?
Привет!
Да, обычный вызов (direct call) CPU предсказывает гораздо лучше.
Причина не в кэше памяти, а в том, что у direct call цель перехода известна заранее - адрес зашит прямо в инструкции. CPU может заранее начать подтягивать инструкции и почти не ошибается.
В случае virtual вызова цель становится известна только после чтения vptr и vtable, и сам переход - это indirect call. Такие переходы CPU предсказывает хуже, особенно если реальные типы объектов часто меняются.
Если vtable и код функции лежат в L1-кэше это ускоряет доступ но не отменяет indirect, CPU узнаёт адрес слишком поздно, и при ошибке предсказания приходится сбрасывать конвейер.
https://godbolt.org/z/ca31T8cf6 - я сделал минимальный пример на котором видно как работает виртуализация
call(A*, int volatile&):
mov rax, qword ptr [rdi] ; читаем vptr из объекта
mov rax, qword ptr [rax + 16] ; берем адрес нужной виртуальной функции
jmp rax ; indirect jump
call(C*, int volatile&):
jmp C::func(int volatile&) ; direct jump
C::func(int volatile&):
mov eax, dword ptr [rsi]
lea eax, [rax + 4*rax]
lea eax, [rax + 2*rax]
mov dword ptr [rsi], eax
ret
Справедливости ради, если компилятор может девиртуализировать вызов, он превращается в обычный direct call и весь этот overhead исчезает
я про то что вот это:
mov rax, qword ptr [rdi] ; читаем vptr из объекта
mov rax, qword ptr [rax + 16] ; берем адрес нужной виртуальной функции
по сравнению с этим:
CALLинструкцияСохранение регистров на стек
Создание stack frame (пролог)
Возврат и восстановление (эпилог)
RETинструкция+ вы параметры наверно забыли которые надо на стек положить
ну это какие то жалкие проценты наверно не больше 10% когда вызов совсем пустой, это даже с учетом того что "CPU предсказывает хуже".
Я правда не помню чтобы CPU инструкции анализировал чтобы выбрать с какого адреса дальше конвейер грузить, но я давно не занимался, может CPU научили, может я что-то пропустил.
во первых, virtual не даст заинлайнить код, и оверхед обычного вызова, про который вы пишете, будет в дополненение к оверхеду виртуализации.
https://godbolt.org/z/4vrx1aTrz - тут я убрал noinline и это хорошо видно в ассемблере
call(A*, int volatile&):
mov rax, qword ptr [rdi]
mov rax, qword ptr [rax + 16]
jmp rax ; всё еще indirect call
call(C*, int volatile&):
mov eax, dword ptr [rsi] ; сработал inline, больше нет call
lea eax, [rax + 4*rax]
lea eax, [rax + 2*rax]
mov dword ptr [rsi], eax
retво вторых, indirect jmp + два mov это не бесплатно само по себе, это дополнительные инструкции в hot path
в третьих, indirect call усложняет branch prediction процесса, misprediction это откат конвейера - 15-20 циклов на ровном месте, это дороже инструкций vtable. В hot path это может быть критично, но это дешево
https://quick-bench.com/q/wZIoe19-C6zRnts3Js5OufEmI4U - тут видно что при 4 типах из-за как раз missprediction время выполнения увеличивается в 4 раз
хотя на 1 типе разницы почти, inline ≈ direct call вероятно из-за погрешностей бенчмарка, из-за того что в inline почти не происходит работы он должен был быть быстрее direct call раза в 4, но у меня в бенчах получалось либо 0, либо примерно direct call, может у вас получится написать бенчмарк который корректно замерит :)
в третьих, indirect call усложняет branch prediction процесса, misprediction это откат конвейера - 15-20 циклов на ровном месте, это дороже инструкций vtable. В hot path это может быть критично, но это дешево
Виртуальные функции хороши когда мы достаем объекты из динамически линкуемой библиотеки (.so библиотеки). И это точно не hot path! А в hot path и статические вызовы это непозволительная роскошь, как вы и написали в статье.
2. Кэш предсказаний (Branch Target Buffer, BTB)
Чтобы не ждать декодирования, процессор использует Branch Target Buffer (BTB) — специализированный кэш, хранящий:
адрес инструкции перехода (branch instruction address);
предсказанный адрес цели (target address).
Как это работает:
Пока инструкция перехода ещё движется по конвейеру, процессор проверяет BTB по текущему адресу программы.
Если запись найдена, процессор сразу начинает загружать инструкции с предсказанного адреса цели.
Позже, когда инструкция будет декодирована, предсказание сверяется с реальным адресом. Если оно верно — конвейер работает без остановок. Если нет — происходит сброс (pipeline flush) и загрузка с правильного адреса.
все таки это что-то вроде кеша, но виртуальные функции чаще всего нужны чтобы заменить switch-case -ы (правильное использование), при использовании switch-case ошибки предсказания будут совершенно те же самые, поэтому не факт что их надо учитывать если мы решили кейсы оформить как функции.
Вы правы, switch-case тоже имеет indirect jump и misprediction.
Но разница в том, что код case'ов находится рядом (один I-cache), а виртуальные функции разбросаны по памяти. Плюс при switch компилятор видит весь код и может оптимизировать, а при virtual - нет.
Но в целом согласен - если альтернатива виртуалке это switch на 20 типов, разница будет небольшой :)
поидее dtc предсказывается, соотв если убрать цикл и кинуть указатели вместо switch-case может что-то и ускорится(я посмотрел на конструкцию - пока не стал так делать, а на С++ когда пишу пофиг почему-то на переходы), но поидее может быть не безопасно, трюк со стеком и стековым вреймом идеально работает в виртуальной машине, а в трансляцию идёт просто переход, потомучто по конвенции можно настроить аргумент и возврат, на С++ не смотрел на С так у меня (простенько всё и компилятор и интерпретатор(2 в одном у меня) делают это, ну разве что для уверенности в транслятор можно после call func добавить ради уверенности push rax-смотря какой тип вм и какая логика трансляции в ассемблер) а вообще зависит от ситуации просто у меня пока после вызова функции в цикле потом идут принты поэтому я пока так сделал, а так по ситуации наверно конечно
ответил не туда :)
Не совсем правильно сравнивать производительность с другими либами. По научному нужно считать флопсы и Гб/с. Мой ECS прототип использует L2 кэш и AVX512 за счет этого в 1000 раз быстрее entt.
Как раз корректно сравнивать одинаковые по логике кейсы и выполнение систем, а не синтетику на миллионы сущностей с SIMD обработкой, которой в реальном проекте не будет в 99 процентов кейсов.
Про такие оптимизации расказывали еще на GDC 10 лет назад. Утеряные технологии древних) Сейчас оптимизация по L2 есть в MASS для UE.
А зачем нужно оптимизировать по L2 можно убедиться если нагрузить RAM всего одним потоком и посмотреть как работает встройка. На дешевых интелах у меня получались лаги в 100-200мс на каждый кадр.
По использованию SIMD https://gdcvault.com/play/1022248/SIMD-at-Insomniac-Games-How
По оптимизации по L2 идея в том, чтобы загрузить часть данных в L2 и прогнать все системы для них, затем загрузить следующую часть. Аналогично работают тайловые ГПУ на мобилках.
Оптимизации примитивные, проблема продумать архитектуру, чтобы эти оптимизации можно было использовать.
Ну как по мне это все очень классно в теории и синтетических расчетов позиций или примитивной математики для большого кол сущностей, на практике же мне даже не приходят в голову кейсы под такое, если у вас куча систем по одним и тем же данным то что-то тут не так. А что касается SIMD то опять же, подходит только для малого количества кейсов, в реальных системах будет куча логики, ветвлений и прочего, для конкретных оптимизаций конечно спору нет, но в разрезе архитектуры самого ядра ECS опять же не понятно. Ну разве что симуляцию частиц делать или подобные технодемки, но там проще на GPU переключиться опять же) Если у вас есть какие то примеры реального повсеместного применения, то поделитесь, будет интересно.
Я больше по графике, но у меня вылезают проблемы, когда CPU выжирает всю пропускную способность общей памяти. Поэтому смотрю как можно оптимизировать эту часть.
а вы пробовали bvh структуру ускорения? там красиво выходит но предел по миру в целом если не пользоваться отсеканиями в момент рендера, упор на 200 - это гарантия работы на любой карточке, дальнейшие числа можно выжать только при хитростях убирая линейные участки на отсекающиеся, в чем может помоч bvh(отсекание частично может помоч ту проблему какую решал Кармак, но просто мы будем знать обьём, соотв тут всё будет на ускоренном обьеме и направлении)
суть в том, что после потолка линейности на железке, надо делать отсекания, чтобы в этот момент кванта делать счет физики по той же структуре кстати, поэтому она ветвистая и даст ускорение - это теоретический пойнт, который я лично нащупал
я пошел дальше в тестах и сделал шаблон рендера на дереве тоже! и получилось 2 дерева рендерят свои 2 дерева, суть проста уи и 3д обьекты унифицированы по классификации геометрии в пространстве и дальше просто летим, но почему-то рендердок с этими фишками не запускается уже
не бойтесь этой структуры и сделайте даже интерфейс по нему, даст прирост, у меня демка не большая, но уже чувствуется масштаб, правда нету паттерна билд и ощущения, что действительно в мире, но там просто нужны паттерны производящие такие как фабрика и билдер наверное
С исключениями спорно сформулирован пункт.
Если исключения обрабатывать не в месте вызова, а несколькими слоями выше, то кода будет меньше, а границы try шире. В случае очень низкой вероятности ошибки эксперименты показывают что исключения не такие уж и медленные.
Но даже в таком случае они делают время выполнения непредсказуемым, что может быть важно для real time приложений. Но, например, для молотилки чисел это может быть не критично, хотя тоже high performance.
Да, по идее если в самом горячем цикле try/сatch нет, то влияния от компиляции с исключениями быть не должно - вспомогательные таблицы лежат в отдельных секциях, на кодогенерацию и использование icache не влияют. Главное кидать их в действительно исключительных случаях (отвалилась сетка или диск и т.п.), а не при любых неожиданных входных данных.
Согласен, если try/catch далеко от hot path - влияние минимально. Моя рекомендация больше про "не оборачивать каждый вызов в цикле", а не "никогда не использовать исключения".
Для I/O и редких ошибок - исключения ок
В hot-path, как вы верно подметили - как повезет
Отличная статья, определенно в закреп! Некоторые отдельные тезисы хотелось бы обсудить
Профилируйте Release билд с debug symbols (
-O2 -g), не Debug!
Вопрос, насколько отличается -O2 и -O3? По моему опыту например SIMD clang/gcc поагрессивней в SIMD оптимизациях при -O3, но реально я не никогда особо не замерял, так как для критической части кода SIMDы писал вручную.
1. Меньше кода = быстрее
Категорически не согласен, причем вы сами приводите пример #10 когда это не так -- как-будто хочется уточнения. Ну и касательно примера 10 тоже хочется отметить, что это должно сворачиваться в SIMD.
Деление - дорого
Бессмертная классик, я бы всё-таки дополнил, что деление на константу сильно дешевле деления на переменную.
Ну и отдельно хотелось бы отметить что у вас в кучу смешаны оптимизации разных типов, хотел бы от вас комментарий по опыту. Лично я при оптимизации стараюсь придерживаться приоритета кэш промахи -> ветвление -> арифметика, сам не до конца уверен что это универсальный подход. А какого подхода придерживаетесь вы?
Привет, спасибо!
Вопрос, насколько отличается -O2 и -O3? По моему опыту например SIMD clang/gcc поагрессивней в SIMD оптимизациях при -O3, но реально я не никогда особо не замерял, так как для критической части кода SIMDы писал вручную.
я тоже не замерял разницу O2 и O3, указал O2 потому что на MSVC нет О3, а хотелось что-то универсальное написать. Но по ощущениям - О3 очень агрессивен, и намного охотнее векторизует циклы.
Вообще основной посыл был в том что - профилируйте на билдах с оптимизиациями.
Я не раз встречался на работе с тем, что ко мне приходили и говорили - лагает!
Я расчехляю профилировщик, собираю билд, и не лагает, вот совсем. А оказывалось, что человек замерял на дебаг билде :)
Я сам будучи джуном как-то долго и упорно оптимизровал работу с std::vector под дебагом, на дебаге стало работать действительно быстрей, правда на релизе замедлилось :)
Категорически не согласен, причем вы сами приводите пример #10 когда это не так -- как-будто хочется уточнения. Ну и касательно примера 10 тоже хочется отметить, что это должно сворачиваться в SIMD.
Ценное уточнение. Я, наверное, не до конца раскрыл мысль, но моя идея в том что нужно писать минимально необходимое количество кода. То есть весь сахар, функции, абстракции и тп не бесплатные, и в hot path могут стрельнуть.
Я вообще подумывал: "а не написать ли ecs на С"... :)
Ну и отдельно хотелось бы отметить что у вас в кучу смешаны оптимизации разных типов, хотел бы от вас комментарий по опыту. Лично я при оптимизации стараюсь придерживаться приоритета кэш промахи -> ветвление -> арифметика, сам не до конца уверен что это универсальный подход. А какого подхода придерживаетесь вы?
Согласен с вашим подходом.
Какой смысл оптимизировать итерацию по std::map если проблема в первую очередь в физике, а не в коде.
Сначала нужно правильно данные подготовить, потом минимизировать накладные расходы на их обработку.
В целом, если данные в памяти лежат эффективно, то это уже успех.
Причем это касается как проектирования новой системы так и оптимизации уже готовых.
На работе не часто приходят задачи - сделай чтобы работало так быстро насколько это возможно, и как правило низковисящие фрукты это - неправильный контейнер, неправильный доступ, лишние аллокации. А это всё как раз кэш мисы. И когда этот вопрос решаешь - то качество уже приемлемо для продакшена.
Про деление на константу - да, компилятор заменяет на умножение + сдвиг. Добавлю в статью, спасибо!
я тоже не замерял разницу O2 и O3, указал O2 потому что на MSVC нет О3
Проверил ради интереса на этом тесте:
https://habr.com/ru/articles/685228/
разница между -O3 и -O2 у Clang 5%. MSVC в 2022 отставал от Clang с любыми опциями (см. последний раздел).
Анатомия performance-critical C++ кода на примере ECS