Оптимизация ветвления

Какова наилучшая реализация с точки зрения производительности разветвленных вызовов функций?Оптимизация ветвления

В наивном случае у нас есть довольно большой оператор switch, который интерпретирует байт-код и выполняет вызов функции в зависимости от кода.

В нормальном случае мы вычислили gotos и метки, которые делают то же самое.

Каков наилучший способ сделать это?

Абстрактный пример,

 
schedule: 
    swap_entity(); 
    goto *entity_start(); 

lb_code1: 
    do_stuff(); 
    goto *next_code_item(); 

lb_code2: 
    do_stuff(); 
    goto *next_code_item(); 

...

Edit: Моя ссылка на "разветвленной вызовы функций", возможно, несколько ошибочно. Выполнение разветвленного кода.

источник

2009-08-26 psyeugenic

AFAIK, лучше, чем метки первого класса, представляет собой не что иное, как компиляцию JIT, в идеале с некоторой оптимизацией с использованием информации о времени выполнения, чтобы убить все ненужные коды. Но в основном «абсолютный лучший». Пфф. Никогда этого не видел. – gimpf

Согласовано с компиляцией (генерация кода, JIT или иным образом), являющаяся «абсолютной наилучшей». Индексирование в массив указателей функций работает, если все операторы имеют одинаковый тип. –

Абсолютное лучшее, возможно, было глупо говорить, но «более быстрый способ» был бы более точным. – psyeugenic

Если вы ищете ускорение скорости здесь, вы должны посмотреть на другие механизмы отправки байт-кода. Было a question which sort-of asked that before.

В принципе, у вас теперь есть goto, который, вероятно, неправильно прогнозируется каждый раз, за которым следует вызов функции. С такой техникой, как direct threading, вы, вероятно, можете значительно уменьшить накладные расходы переводчика. Inline threading сложнее, но с большей пользой.

В другом вопросе я дал further resources.

источник

2009-08-27 15:20:34

Может быть, массив указателей на функции, на догадку:

void dispatch(Message* message) 
{ 
    //MessageType is a finite enum 
    MessageType messageType = message->messageType; 
    int index = (int)messageType; 
    //there's an array element for each enum value 
    FunctionPointer functionPointer = arrayOfFunctionPointers[index]; 
    (*functionPointer)(message); 
}

Фактический ответ зависит от оборудования, и зависит от таких вещей, как размер проблемы и кэш процессора.

источник

2009-08-26 20:14:14 ChrisW

Только для моего собственного назидания, что такое тип данных сообщения? Я спрашиваю, потому что не помню -> в C. – CAbbott

Я даю «сообщение» в качестве примера «определяемого пользователем типа», т. Е. Структуры; эта гипотетическая структура будет содержать несколько полей, один из которых называется messageType, тип которого является MessageType, который является определяемым пользователем типом перечисления. «' -> '» идет с «' * '» и связан с тем, что экземпляр передается указателем вместо значения. – ChrisW

@Chris - спасибо за объяснение, я не мог вспомнить, когда был введен синтаксис '->', я думал, что это было введение C++ (т.е. message-> messageType vs. (* message) .messageType – CAbbott

Это зависит. Как правило, какой-то подход, основанный на таблицах, будет самым быстрым, но вы вполне можете обнаружить, что это то, что реализовано вашим оператором switch. Конечно, вы должны не считать это прочитанным, что ЛЮБАЯ рекомендация в этой области от пользователей SO является лучшим. Если мы что-то предлагаем, вам необходимо реализовать его и измерить производительность в сборке с включенной оптимизацией компилятора.

источник

2009-08-26 20:19:05

Оптимизация ветвления

ответ

Смежные вопросы