Подтвердить что ты не робот

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

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

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

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;
    }
}

И вот версия "callback function":

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]) ();
}

Итак, какая версия будет быстрее? Являются ли накладные расходы на функциональный вызов, устраняя преимущество скорости по сравнению с обычным оператором switch (или if)?

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

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

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

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

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

Ответ 5

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

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

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

Ответ 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 <=
}