Накладные расходы оператора switch в C

Question

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

Я перебираю все пиксели изображения и вычисляю новое значение в зависимости от пройденного режима.

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

Код будет выглядеть следующим образом:

for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             switch (mode)                  /* select the type of calculation */
             {
                case 0:
                weight = dCentre / maxDistanceEdge;
                case 1: 
                    weight = (float)x/width;             
                    break;
                case 2: 
                    weight = (float)y/height;
                    break;
                case 3: 
                    weight = dBottomLeft / maxDistanceCorner;
                    break;
                case 4: 
                    weight = dTopRight / maxDistanceCorner;
                    break;
                default: 
                weight = 1;
                break;
            }
             // Calculate the new pixel value given the weight
             ...
            }             

    }

Ожидаете ли вы увидеть большие издержки, если это изображение будет более 5000 x 5000 пикселей? Я пытался провести какое-то тестирование, но мои результаты повсюду, поскольку система (мобильное устройство) работает в фоновом режиме, что может искажать результаты.

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

Заранее спасибо!

Гав

Answer 1

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

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

switch (mode)                  /* select the type of calculation */
{
case 0:
    weight = dCentre / maxDistanceEdge;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
case 1:
    for (x = 0; x < width; x++) {
        weight = (float)x/width;
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
case 2:
    // note - the loops have been swapped to get the weight calc out of the inner loop
    for (y = 0; y < height; y++) {
        weight = (float)y/height;
        for (x = 0; x < width; x++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
case 3:
    weight = dBottomLeft / maxDistanceCorner;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
case 4:
    weight = dTopRight / maxDistanceCorner;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
default:
    weight = 1;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;

// etc..
}

Answer 2

Если эффективность важнее размера кода, тогда да, вы должны создать избыточные подпрограммы. Оператор case - это одна из самых низких вещей, которую вы можете сделать в C, но она не равна нулю - она ​​должна ветвиться в зависимости от режима, и поэтому потребуется время. Если вы действительно хотите получить максимальную производительность, выньте случай из цикла, даже за счет дублирования цикла.

Answer 3

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

Answer 4

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

Answer 5

Переключатель / регистр чрезвычайно быстр по сравнению с аналогом с if / else: обычно он реализован в виде таблицы переходов. Однако это все еще имеет стоимость.

Пока вы оптимизируете вещи:

1) Попробуйте зациклить строки, а не столбцы (переключайте циклы x и y "for"), одно решение может быть невероятно быстрее другого из-за управления кэш-памятью.

2) Замена всех делений на умножения обратного (предварительно рассчитанного) даст вам значительный выигрыш и, вероятно, приемлемую потерю точности.

Answer 6

Ради эффективности вам лучше вывести switch из цикла.

Я бы использовал указатели функций следующим образом:

double fun0(void) { return dCentre/maxDistanceEdge; }
double fun1(void) { return (float)x/width; }
/* and so on ... */

double (*fun)(void);

switch (mode)                  /* select the type of calculation */
{
    case 0: fun = fun0;
            break;
    case 1: fun = fun1;
            break;
    case 2: fun = fun2;
            break;
    case 3: fun = fun3;
            break;
    case 4: fun = fun3;
            break;
    default : fun = fun_default;
            break;
}

for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             weight = fun();
             // Calculate the new pixel value given the weight
             ...
        }
}

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

РЕДАКТИРОВАТЬ: Если вы используете GCC, чтобы избавиться от вызова функции, вы можете использовать goto и метки в качестве значений: найти правильную метку внутри коммутатора и затем просто перейти к этому каждый раз. Я думаю, что это должно спасти еще несколько циклов.

Answer 7

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

Реальная проблема с эффективностью в этом случае - это подразделения. Мне кажется, что все знаменатели операций деления являются константами (ширина, высота, max ...), и они не будут меняться на протяжении всего изображения. Если мое предположение верно, то это простые переменные, которые могут изменяться в зависимости от загруженного изображения, так что изображение любого размера может использоваться во время выполнения, теперь это позволяет загружать изображения любого размера, но это также означает, что компилятор не может их оптимизировать в гораздо более простую операцию умножения, которую он мог бы сделать, если бы они были объявлены "const". Мое предложение состояло бы в том, чтобы предварительно рассчитать обратные значения этих констант и умножить. Насколько я помню, операция умножения занимает около 10 тактов, тогда как деление занимает около 70. Это увеличение на 60 циклов на пиксель, а с вышеупомянутым 5000x5000 это предполагаемое увеличение скорости на 1,5 секунды на 1 ГГц процессор.

Answer 8

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

Answer 9

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

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

Answer 10

Коммутаторы не должны создавать каких-либо значительных накладных расходов, они скомпилированы в своего рода массив указателей на нижнем уровне, тогда это эффективно

jmp {baseaddress} + switchcasenum