Накладные расходы оператора 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

Что касается внутренних циклов ... 0-> var лучше сделать var-> 0, так как var-- запускает нулевой флаг (6502 дня). Этот подход также означает, что «ширина» загружается в x и может быть забыта, то же самое относится и к «высоте». Кроме того, пиксели в памяти обычно располагаются слева-> справа, сверху-> снизу, поэтому в качестве внутреннего цикла определенно необходимо указать x.

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

Кроме того ... и очень важно, что ваши операторы switch имеют только 2 случая, которые используют x или y. Остальные константы.

 switch (mode)                  /* select the type of calculation */
 {
     case 0:
        weight = dCentre / maxDistanceEdge;
        break;
     //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;
 }

Таким образом, в основном, если вес цикла 1 или 2 не рассчитан перед циклом.

... Y loop code here

    if (mode == 2) { weight = (float)y/height; } // calc only once per Y loop

    ... X loop here

        if (mode == 1) { weight = (float)x/width; } // after this all cases have filled weight
        calc_pixel_using_weight(weight);

Я считаю, что операторы switch очень недобрые, если данные редки. Для <4 элементов я бы выбрал if-then-else и убедился, что самые распространенные случаи находятся на вершине. Если первое условие улавливает 90% случаев, вы в основном попали в хомире. Аналогично, если какое-то другое условие <1%, ставьте его последним. </p>

Answer 2

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

Если вы не читаете 'mode' из файла или из введенного ввода, метод расчета может быть определен во время компиляции. Как правило, вы не хотите переносить вычисления из времени компиляции во время выполнения.

В любом случае код будет легче читать, и никто не будет сбит с толку относительно того, собирались ли вы добавить оператор break в первом случае или нет.

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

Answer 3

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

Так что, если случай 4 происходит чаще, чем случай 1, он должен быть выше него:

switch (mode) {
    case 4:
        // ..
        break;
    case 1:
        // ..
        break;
}

Жаль, что вы не использовали c ++, потому что тогда оператор switch мог бы быть заменен полиморфизмом.

Ура!

Answer 4

но эффективность - вот название игры здесь.

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

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

Так что вы в конечном итоге с такими вызовами, как:

computeWeight[mode](pixel);

При 5000x5000 пикселей накладные расходы на вызов функции можно также уменьшить, вызвав функцию для диапазона пикселей, а не отдельных пикселей.

Вы также можете использовать развертывание цикла и передачу параметров по ссылке / указателю для дальнейшей оптимизации.

Answer 5

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

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

Answer 6

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

Кстати: понимание такого рода вещей - довольно хороший аргумент для того, чтобы потратить пару недель на изучение какой-то сборки в какой-то момент вашей карьеры ...