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

Я пишу очень критичную для кода часть кода, и у меня возникла эта сумасшедшая идея о замене операторов 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]) ();
}

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

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

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

Источник

7 ответов

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

Источник

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

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

Источник

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

Источник

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

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

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

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

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

Источник

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

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

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

Источник

Я прибыл на этот пост недавно, так как мне было интересно то же самое. Я нашел время, чтобы попробовать это. Это, безусловно, во многом зависит от того, что вы делаете, но для моей виртуальной машины это было приличное ускорение (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 <=
}
Источник

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

func * pFunc = myStaticArrayOfFuncPtrs[iCase];pFunc->Exec();

switch быстрее, чем if else, для большего количества случаев, потому что он использует двоичное дерево.

в C ++ вы можете использовать шаблоны вместо func ptrs.

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

иметь код в операторе case быстрее всего, но возникают проблемы.

func ptrs в массиве также имеет то преимущество, что упрощает сопровождение кода. переключатели с кодом в каждом случае становятся длинными, и вы сидите там, прокручивая весь день, чтобы найти случай, который хотите посмотреть.

func ptrs работают быстро, но работают больше, чем шаблоны.

Источник
Другие вопросы по тегам