Борьба с генерацией странного кода для косвенных вызовов - PullRequest
Новая
       206

Борьба с генерацией странного кода для косвенных вызовов

0 голосов
/ 05 августа 2020

Вот пример кода , о котором я буду говорить в этом вопросе.

Я пишу синтаксический анализатор на 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, ни для одной из функций синтаксического анализатора массива, но по-прежнему имеет аналогичные косвенные вызовы, где указатель на функцию перенесен в регистр прямо перед хвостовым вызовом.

...