Вот пример кода , о котором я буду говорить в этом вопросе.
Я пишу синтаксический анализатор на C ++, где общий шаблон включает значение входящий поток символов или токенов и вызов различных функций синтаксического анализа в зависимости от значения. В приведенном выше примере я демонстрирую это, используя разные parse_@
функции для разных случаев.
Самая прямая реализация - это switch
и ручная запись всех случаев, например
switch (*stream)
{
case 'a': return parse_a(stream);
case 'b': return parse_b(stream);
// ...
default: return *stream;
}
Это достаточно хорошо, но в некоторых случаях эти переключатели необходимо синхронизировать для нескольких функций и файлов. По этой причине я использую массив constexpr
, в котором я храню пары указателей значения и функции парсера для представления различных случаев. Это массив parsers
в примере.
С его помощью можно написать такую функцию, как
int parse(char const *stream)
{
return [&]<std::size_t ...Ns>(std::index_sequence<Ns...>) {
auto const c = *stream;
int result = c;
((
c == parsers[Ns].c
? (void)(result = parsers[Ns].fn(stream))
: (void)0
), ...);
return result;
}(std::make_index_sequence<parsers.size()>{});
}
Это имеет ту же функциональность, что и исходная функция switch
, и вы можете определите разные случаи как
constexpr std::array parsers = {
S{ 'a', &parse_a },
S{ 'b', &parse_b },
// ...
};
, что так же хорошо, как case 'a': return parse_a(stream);
imo.
Это дает тот же код, что и функция switch
с clang и -O3
, что это замечательно, но если я использую нетривиальный тип в качестве возвращаемого значения функций синтаксического анализатора, у нас возникают дополнительные накладные расходы на сначала создание экземпляра этого типа, а затем его присвоение. Это также мешает компилятору выполнять хвостовые вызовы функций синтаксического анализатора.
Из-за этого я подумал о том, чтобы получить указатель функции синтаксического анализатора из массива и выполнить косвенный вызов с ним, ожидая генерации кода, аналогичного предыдущему function.
int parse(char const *stream)
{
return [&]<std::size_t ...Ns>(std::index_sequence<Ns...>) {
auto const c = *stream;
int (*fn)(char const *) = nullptr;
((
c == parsers[Ns].c
? (void)(fn = parsers[Ns].fn)
: (void)0
), ...);
return fn == nullptr ? c : fn(stream);
}(std::make_index_sequence<parsers.size()>{});
}
С этой функцией сгенерированный код по-прежнему имеет поведение switch
с clang, но разные случаи go от
jmp parse_b(char const*) # TAILCALL
до
mov ecx, offset parse_b(char const*)
jmp rcx # TAILCALL
Таким образом, вместо выполнения обычного хвостового вызова код перемещает указатель функции в регистр и немедленно выполняет хвостовой вызов из этого регистра. Для меня это выглядит как очевидная упущенная оптимизация, которая может иметь серьезные последствия для производительности. (В моем тестировании я измерил разницу в производительности на 20-25%)
Есть ли способ сделать функцию синтаксического анализатора с подходом массива constexpr
для нетривиальных возвращаемых типов, которые имеют генерацию кода, аналогичную генерации кода switch
function?
В качестве примечания: g cc не создает код, подобный switch
, ни для одной из функций синтаксического анализатора массива, но по-прежнему имеет аналогичные косвенные вызовы, где указатель на функцию перенесен в регистр прямо перед хвостовым вызовом.