Как ускорить динамическую отправку на 20% с помощью вычисляемых переходов в стандартном C++ ⇐ C++

[Anonymous]

Я читал об интерпретаторах виртуальных машин и наткнулся на вычисляемые методы . Судя по всему, они позволяют значительно улучшить производительность некоторых фрагментов кода. Самый известный пример — основной цикл интерпретатора виртуальной машины.
Рассмотрим такую ​​простую виртуальную машину:

Код: Выделить всё

#include 

enum class Opcode
{
HALT,
INC,
DEC,
BIT_LEFT,
BIT_RIGHT,
RET
};

int main()
{
Opcode program[] = { // an example program that returns 10
Opcode::INC,
Opcode::BIT_LEFT,
Opcode::BIT_LEFT,
Opcode::BIT_LEFT,
Opcode::INC,
Opcode::INC,
Opcode::RET
};

int result = 0;

for (Opcode instruction : program)
{
switch (instruction)
{
case Opcode::HALT:
break;
case Opcode::INC:
++result;
break;
case Opcode::DEC:
--result;
break;
case Opcode::BIT_LEFT:
result = 1;
break;
case Opcode::RET:
std::cout  оператор:
[code]goto some_label;

some_label:
do_something();

Это не считается хорошим кодом (и на это есть веская причина!). Хотя существуют веские аргументы против использования goto (большинство из которых связаны с удобством сопровождения кода), для этой отвратительной функции есть применение. Это повышение производительности.
Использование оператора goto может быть быстрее, чем вызов функции. Это связано с тем, что при вызове функции необходимо выполнить объем «бумажной работы», такой как настройка стека и возврат значения. Между тем, goto иногда можно преобразовать в одну ассемблерную инструкцию jmp.
Чтобы использовать весь потенциал goto, необходимо использовать расширение компилятора GCC. было сделано, что позволяет goto быть более динамичным. То есть метка для перехода может быть определена во время выполнения.
Это расширение позволяет получить указатель метки, аналогичный указателю на функцию, и переходимк нему:

Код: Выделить всё

    void* label_ptr = &&some_label;
goto (*label_ptr);

some_label:
do_something();

Это интересная концепция, которая позволяет нам еще больше улучшить нашу простую виртуальную машину. Вместо использования оператора switch мы будем использовать массив указателей меток (так называемая таблица переходов), а затем переходим к соответствующему (код операции будет использоваться для индексировать массив):

Код: Выделить всё

// [Courtesy of Eli Bendersky][4]
// This code is licensed with the [Unlicense][5]

int interp_cgoto(unsigned char* code, int initval) {
/* The indices of labels in the dispatch_table are the relevant opcodes
*/
static void* dispatch_table[] = {
&&do_halt, &&do_inc, &&do_dec, &&do_mul2,
&&do_div2, &&do_add7, &&do_neg};
#define DISPATCH() goto *dispatch_table[code[pc++]]

int pc = 0;
int val = initval;

DISPATCH();
while (1) {
do_halt:
return val;
do_inc:
val++;
DISPATCH();
do_dec:
val--;
DISPATCH();
do_mul2:
val *= 2;
DISPATCH();
do_div2:
val /= 2;
DISPATCH();
do_add7:
val += 7;
DISPATCH();
do_neg:
val = -val;
DISPATCH();
}
}

Эта версия примерно на 25 % быстрее, чем та, в которой используется переключатель (та, что указана в связанном сообщении блога, а не та, что выше). Это связано с тем, что после каждой операции выполняется только один переход вместо двух.
Поток управления с помощью переключателя:

Например, если мы хотим выполнить Opcode::FOO, а затем Opcode::SOMETHING , это будет выглядеть так:

Как видите, после выполнения инструкции выполняются два перехода. казнён. Первый возвращается к коду переключателя, а второй — к фактической инструкции.
Напротив, если бы мы использовали массив указателей меток (напоминаем, , они нестандартные), у нас будет только один переход:


Следует отметить, что помимо экономя циклы за счет меньшего количества операций, мы также повышаем качество прогнозирования ветвей, устраняя дополнительный переход.
Теперь мы знаем, что используя массив указателей меток вместо переключателя
code> мы можем значительно улучшить производительность нашей виртуальной машины (примерно на 20%). Я подумал, что, возможно, это может иметь и другие применения.
Я пришел к выводу, что этот метод можно использовать в любой программе, в которой есть цикл, в котором он последовательно и косвенно отправляет некоторую логику. Простым примером этого (кроме виртуальной машины) может быть вызов виртуального метода для каждого элемента контейнера полиморфных объектов:

Код: Выделить всё

std::vector objects;
objects = get_objects();
for (auto object : objects)
{
object->foo();
}

Теперь у этого гораздо больше приложений.
Однако есть одна проблема: в стандартном C++ нет ничего похожего на указатели меток. Таким образом, возникает вопрос: есть ли способ имитировать поведение вычисляемых переходов в стандартном C++, который мог бы соответствовать им по производительности?.
Есть еще один недостаток использования переключателя. Мне об этом напомнил пользователь 1937198. Это обязательная проверка. Короче говоря, он проверяет, соответствует ли значение переменной внутри переключателя какому-либо регистру. Он добавляет избыточное ветвление (эта проверка предусмотрена стандартом).
В ответ на cmaster я поясню, какова моя идея по уменьшению накладных расходов на вызовы виртуальных функций. Грязным подходом к этому было бы иметь идентификатор в каждом производном экземпляре, представляющий его тип, который будет использоваться для индексации таблицы переходов (массив указателей меток). Проблема в том, что:

• В стандартном C++ нет таблиц переходов.
• Это потребовало бы изменения всех переходов. таблицы при добавлении нового производного класса.

Я был бы благодарен, если бы кто-нибудь придумал какую-нибудь магию шаблонов (или макрос в качестве последнего Resort), что позволило бы написать его более чистым, расширяемым и автоматизированным, вот так:

Подробнее здесь: https://stackoverflow.com/questions/587 ... standard-c