Сколько кода занимает оператор switch?

Question

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

typedef struct container{ 
    type1 a; 
    type2 b; 
    type3 c; 
}container; 

static container d; 
//option A 
void foo(int num) 
{ 
    void* x; 
    switch (num) 
    { 
    case 1: 
     x = &d->a; 
     break; 
    case 2: 
     x = &d->b; 
     break; 
    case 3: 
     x = &d->c; 
     break; 
    default: 
     x = NULL; 
     break; 
    } 
    // do something with x 
} 
// option B 
const void* lookup_table[] = { 
    d.a, 
    d.b, 
    d.c, 
    NULL 
}; 

void foo(int num) 
{ 
    void* x = lookup_table[num]; 
    // do something with x 
} 

Как бы оператор switch разбился на сборку и насколько он был бы больше в кодовом пространстве? Стоит ли использовать таблицу поиска вместо использования оператора switch?

Answer 1

Вопрос не имеет точного значения. Оптимизирующий компилятор (очень часто), по крайней мере, компилирует целую функцию (и часто всю единицу перевода) сразу.

Прочитано R.Sayle на компиляционных переключателях. Вы узнаете, что для этого существует несколько конкурирующих стратегий (таблицы перехода, сбалансированные деревья, условные перемещения, таблицы перехода хэша и т. Д.), И некоторые из них могут быть объединены.

Доверьте свой optimizing compiler, чтобы сделать достаточно хороший выбор для компиляции кода вашего коммутатора. Для GCC скомпилируйте с gcc -Wall -O2 -march=native, возможно, добавив -fverbose-asm -S (и/или заменив -O2 на -O3), если вы хотите просмотреть сгенерированный ассемблер. Узнать также о gcc -flto -O3 и т. Д.

^{Конечно, для целей бенчмаркинга и для производственного кода вы всегда должны просить ваш компилятор оптимизировать.}

Обратите внимание, что в качестве расширения (принято также Clang/LLVM ...) GCC имеет labels as values (с непрямым goto с). С их помощью вы могли бы использовать использование таблиц прыжка или иметь threaded code. Это не всегда сделает ваш код быстрее (например, из-за branch prediction).

Answer 2

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

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

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

Answer 3

Другой способ смотреть на сообщение:

void foo(int num) { void* x; switch (num)... хорошо справляется с num вне диапазона 1,2,3.

void foo(int num) { void* x = lookup_table[num]; имеет неопределенное поведение, когда num находится за пределами диапазона 0,1,2,3.

---

Некоторые могут тогда сказать num диапазон не является проблемой. Но об этом не сообщалось. И так это с обслуживанием кода - много неустановленных, подразумеваемых и иногда ложно предполагаемых условий.

Стоит ли использовать таблицу поиска вместо использования оператора switch?

Для стоимости обслуживания, я бы с switch().

Answer 4

Как уже отмечалось другими, современные оптимизирующие компиляторы попытаются выбрать хорошую стратегию для компиляции коммутаторов в более эффективный код. Ханс Веннборг выступил на собрании разработчиков LLVM 2015 года о recent switch lowering improvements, который дает вам краткое введение в эту тему.

Так лучше, чтобы компилятор выполнял свою работу и решал наиболее читаемое решение, чем тот, который, по вашему мнению, является наиболее эффективным.

Если вы хотите увидеть, что код Clang производит для вашего файла коммутатора, вы можете использовать -S или -S -emit-llvm.