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

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

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

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

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

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

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 х 5000 пикселей? Я попытался провести некоторое тестирование, но мои результаты повсюду, так как система (мобильное устройство) имеет всевозможные элементы, работающие в фоновом режиме, которые могут искажать результаты.

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

Спасибо заранее!

Гав

4b9b3361

ОТВЕТЫ

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

Ответ 5

Коммутатор/случай чрезвычайно быстрый по сравнению с эквивалентом if/else: он обычно реализуется как таблица перехода. Однако он по-прежнему имеет стоимость.

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

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

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

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

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

EDIT: Если вы используете GCC, чтобы избавиться от вызова функции, вы можете использовать goto и метки как значения: найдите нужную метку внутри коммутатора, а затем просто прыгайте в нее каждый раз. Я думаю, что это должно сэкономить несколько циклов.

Ответ 7

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

jmp {baseaddress} + switchcasenum

Ответ 8

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

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

Ответ 9

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

Ответ 10

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

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

Ответ 11

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

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

Ответ 12

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

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

Ответ 13

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

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

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

Чтобы вы получили вызовы, например:

computeWeight[mode](pixel);

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

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

Ответ 14

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

Итак, если случай 4 случается чаще, чем случай 1, он должен быть над ним:

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

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

Приветствия!

Ответ 15

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

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

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

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