В clang совсем недавно добавили аннотацию [[clang::musttail]], которая гарантирует (и не компилируется, если невозможно), что при вызове return не нужно аллоцировать памяти для стека и можно прыгать на адрес функции без его распила. Синтаксис примерно такой:
Например, когда парсят мои любимые (нет) протобуфы, очень много проводится времени, чтобы вызвать callback, если поле было неправильно десериализовано. В итоге _InternalParse цикл выглядит как-то так:
1. Парсим поле в switch case стиле, проверяем, что ок, если не ок, останавливаемся и возвращаем ошибку
2. Парсим следующее поле и делаем те же проверки
3. ...
В итоге получалось, что код для "ошибочного коллбека" очень много где встречается на пути до финального парсинга, и компилятору было очень сложно поставить его в правильное место, чтобы не испортить перформанс цикла. Да и обычный диспатч по тегам добавлял проблем. Это исправлялось с Profile Guided Optimization, когда компилятору кормили профиль, и иногда оптимизировались tail вызовы в обычный jmp. Но это было похоже на игру, сможет ли компилятор понять это по циклам в сотни-тысячи полей, которые кушали больше всего CPU. Часто ответ был нет :(. Компилятор не всемогущий.
С tail call можно делать следующие вещи
1. Парсим первое поле, если не ок, делаем tail call на "ошибочный коллбек"
2. Если ок, делаем tail call на функцию парсинга следующего поля. Это можно вычислить исходя из тега протобуфа (там последние 3 бита означают тип) и таблички функций без любых if. Возвращаться не надо, поэтому tail call корректен
3. И так далее...
Мы избавляемся от цикла, который должен оптимизироваться под branch prediction процессора, из-за tail call не создаем дополнительной памяти на стеке и просто делаем jmp. Красота.
Протобуфы сейчас парсятся где-то со скоростью 400-600 MB/s и эта скорость не менялась примерно 6 лет. С развитием simdjson, который парсит json со скоростью 2-3GB/s, встала задача о том, а можно ли парсить протобуфы быстро. Для SIMD ответ оказался, что нет, varint кодирование, которое хранит основную информацию в 7 битах, не дружит с SIMD.
Зато протобуфы нашли себя в другой нише — полностью убирание всей памяти стека, рекурсии и branch prediction на номера тегов. В моих экспериментах я получал стабильно 1.5GB/s, что в 3-4 раза быстрее обычного парсинга. Но simdjson был хорошим пинком команде протобуфа задуматься о том, что пора бы развиваться.
В Q2 будет допилено до апстрима (там будут санкции команде, если нет). Блог моего коллеги Josh (команда Google Protobuf), который вышел с этой идеей и будет это допинывать
https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html
int g(int);
int f(int x) {
[[clang::musttail]] return g(x);
}
tail call уже давно оптимизируются компиляторами (не создают пролога и эпилога для вызовов функций), но тем не менее это весьма полезно для некоторых вещей, чтобы обманывать branch prediction и динамически прыгать на куски кода (читай, goto с динамическими адресами и понятным кодом).Например, когда парсят мои любимые (нет) протобуфы, очень много проводится времени, чтобы вызвать callback, если поле было неправильно десериализовано. В итоге _InternalParse цикл выглядит как-то так:
1. Парсим поле в switch case стиле, проверяем, что ок, если не ок, останавливаемся и возвращаем ошибку
2. Парсим следующее поле и делаем те же проверки
3. ...
В итоге получалось, что код для "ошибочного коллбека" очень много где встречается на пути до финального парсинга, и компилятору было очень сложно поставить его в правильное место, чтобы не испортить перформанс цикла. Да и обычный диспатч по тегам добавлял проблем. Это исправлялось с Profile Guided Optimization, когда компилятору кормили профиль, и иногда оптимизировались tail вызовы в обычный jmp. Но это было похоже на игру, сможет ли компилятор понять это по циклам в сотни-тысячи полей, которые кушали больше всего CPU. Часто ответ был нет :(. Компилятор не всемогущий.
С tail call можно делать следующие вещи
1. Парсим первое поле, если не ок, делаем tail call на "ошибочный коллбек"
2. Если ок, делаем tail call на функцию парсинга следующего поля. Это можно вычислить исходя из тега протобуфа (там последние 3 бита означают тип) и таблички функций без любых if. Возвращаться не надо, поэтому tail call корректен
3. И так далее...
Мы избавляемся от цикла, который должен оптимизироваться под branch prediction процессора, из-за tail call не создаем дополнительной памяти на стеке и просто делаем jmp. Красота.
Протобуфы сейчас парсятся где-то со скоростью 400-600 MB/s и эта скорость не менялась примерно 6 лет. С развитием simdjson, который парсит json со скоростью 2-3GB/s, встала задача о том, а можно ли парсить протобуфы быстро. Для SIMD ответ оказался, что нет, varint кодирование, которое хранит основную информацию в 7 битах, не дружит с SIMD.
Зато протобуфы нашли себя в другой нише — полностью убирание всей памяти стека, рекурсии и branch prediction на номера тегов. В моих экспериментах я получал стабильно 1.5GB/s, что в 3-4 раза быстрее обычного парсинга. Но simdjson был хорошим пинком команде протобуфа задуматься о том, что пора бы развиваться.
В Q2 будет допилено до апстрима (там будут санкции команде, если нет). Блог моего коллеги Josh (команда Google Protobuf), который вышел с этой идеей и будет это допинывать
https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html