Выполнение массива функций над операторами if и switch

Question

Я пишу очень критичную для кода часть кода, и у меня возникла эта сумасшедшая идея заменить операторы case (или операторы if) массивом указателей на функции.

Позвольте мне продемонстрировать; здесь идет нормальная версия:

while(statement)
{
    /* 'option' changes on every iteration */

    switch(option)
    {
        case 0: /* simple task */ break;
        case 1: /* simple task */ break;
        case 2: /* simple task */ break;
        case 3: /* simple task */ break;
    }
}

А вот версия «функции обратного вызова»:

void task0(void) {
    /* simple task */
}

void task1(void) {
    /* simple task */
}

void task2(void) {
    /* simple task */
}

void task3(void) {
    /* simple task */
}

void (*task[4]) (void);

task[0] = task0;
task[1] = task1;
task[2] = task2;
task[3] = task3;

while(statement)
{
    /* 'option' changes on every iteration */

    /* and now we call the function with 'case' number */
    (*task[option]) ();
}

Так какая версия будет быстрее? Затраты на вызов функции исключают преимущество в скорости по сравнению с оператором обычного переключения (или если)?

Конечно, последняя версия не так удобна для чтения, но я ищу всю возможную скорость.

Я собираюсь сравнить это с настройкой, но если у кого-то уже есть ответ, я не буду беспокоиться.

Answer 1

Я думаю, что в конце дня ваши операторы switch будут самыми быстрыми, потому что указатели на функции имеют «накладные расходы» на поиск функции и сам вызов функции.Переключатель - это просто таблица JMP прямо.Конечно, зависит от разных вещей, на которые только тестирование может дать вам ответ.Это моя цена в два цента.

Answer 2

Во-первых, я бы случайно приостановил несколько раз, чтобы убедиться, что на эту диспетчеризацию потрачено достаточно времени, чтобы даже потратить его на оптимизацию.

Во-вторых, если это так, так каккаждая ветвь тратит очень мало циклов, вам нужна таблица переходов, чтобы добраться до нужной ветки.Причина существования операторов switch состоит в том, чтобы предложить компилятору, что он может сгенерировать единицу, если значения переключателей компактны.

Как долго список значений переключателей?Если оно короткое, то if-лестница все еще может быть быстрее, особенно если вы поместите наиболее часто используемые коды вверху.Альтернативой лестнице if (которую я никогда не видел) - это if-дерево, эквивалент кода двоичного дерева.

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

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

Answer 3

Какая версия будет быстрее, зависит. Наивная реализация switch - это огромная конструкция if ... else if ... else if ..., означающая, что для выполнения требуется в среднем O (n) времени, где n - количество случаев. Ваша таблица переходов O (1), поэтому чем больше разных случаев и чем больше используются более поздние, тем больше вероятность того, что таблица переходов будет лучше. Для небольшого числа случаев или для коммутаторов, где первый случай выбирается чаще, чем другие, наивная реализация лучше. Ситуация осложняется тем фактом, что компилятор может выбрать использование таблицы переходов, даже если вы написали переключатель, если он считает, что это будет быстрее.

Единственный способ узнать, какой вариант выбрать, - проверить производительность своего кода.

Answer 4

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

Answer 5

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

1. Переход намного дешевле, чем вызов (который должен сохранять регистры с ограниченным вызовом, настраивать стек и т. Д.).
2. Код в случаях оператора switch может использовать значения выражений, уже кэшированные в регистрах вызывающей стороны.

Вполне возможно, что чрезвычайно продвинутый компилятор может определить, что указатель вызова через функцию относится только к одной из небольшого набора функций статического связывания, и тем самым сильно оптимизировать вещи, возможно, даже исключая вызовы и заменяя их переходами , Но я бы на это не рассчитывал.

Answer 6

Я прибыл на этот пост недавно, так как мне было интересно то же самое. Я нашел время, чтобы попробовать это. Это, конечно, в значительной степени зависит от того, что вы делаете, но для моей виртуальной машины это было приличное ускорение (15-25%) и позволило мне упростить некоторый код (что, вероятно, привело к значительному увеличению скорости). В качестве примера (код упрощен для ясности) цикл «for» можно было легко реализовать с помощью цикла for:

void OpFor( Frame* frame, Instruction* &code )
{
  i32 start = GET_OP_A(code);
  i32 stop_value = GET_OP_B(code);
  i32 step = GET_OP_C(code);
  // instruction count (ie. block size)
  u32 i_count = GET_OP_D(code);
  // pointer to end of block (NOP if it branches)
  Instruction* end = code + i_count;

  if( step > 0 )
  {
    for( u32 i = start; i < stop_value; i += step )
    {
      // rewind instruction pointer
      Instruction* cur = code;

      // execute code inside for loop
      while(cur != end)
      {
        cur->func(frame, cur);
        ++cur;
      }
    }
  }
  else
    // same with <=
}