Накладные расходы оператора switch в C
https://stackoverflow.com/questions/927403
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я довольно компетентный Java-программист, который совсем новичок в C.Я пытаюсь оптимизировать процедуру, которая имеет четыре режима работы.
Я перебираю все пиксели в изображении и вычисляю новое значение пикселя в зависимости от переданного "режима".
Мой вопрос касается накладных расходов оператора switch в двух вложенных циклах for.Мне были бы интересны любые ссылки на документацию, касающуюся относительной эффективности базовых операторов языка Си, математических и логических операций.
Код будет выглядеть следующим образом;
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 пикселей?Я пытался провести некоторое тестирование, но мои результаты разбросаны повсюду, поскольку в системе (мобильном устройстве) в фоновом режиме запущены всевозможные программы, которые могут исказить результаты.
Другой вариант - иметь отдельный метод для каждого режима, каждый со своими собственными четырьмя циклами.Очевидно, что это привело бы к появлению избыточного кода, но эффективность - это название игры здесь.
Заранее спасибо!
Гэв
Решение
Инструкции 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..
}
Другие советы
Если эффективность важнее размера кода, то да, вы должны создавать избыточные подпрограммы.Оператор case - это одна из самых низких накладных расходов, которые вы можете сделать в C, но она не равна нулю - ей придется ветвиться в зависимости от режима, и поэтому это займет время.Если вам действительно нужна максимальная производительность, выведите дело из цикла, даже ценой дублирования цикла.
Инструкции Switch настолько эффективны, насколько это вообще возможно.Они скомпилированы в таблицу переходов.На самом деле, именно поэтому switch настолько ограничен, насколько это возможно:вы можете написать только тот переключатель, для которого вы может скомпилируйте таблицы переходов на основе фиксированного значения.
По сравнению с математикой, которую вы выполняете в цикле, накладные расходы коммутатора, вероятно, будут минимальными.сказав это, единственный способ убедиться в этом - создать разные версии для двух разных подходов и рассчитать их время.
Переключение / case выполняется чрезвычайно быстро по сравнению с эквивалентом с if / else:обычно он реализуется в виде таблицы переходов.Однако это все еще имеет свою цену.
Пока вы что-то оптимизируете:
1) Попробуйте выполнять цикл по строкам, а не по столбцам (переключите x и y "для" циклов), одно решение может быть невероятно быстрее другого из-за управления кэш-памятью.
2) Замена всех делений на умножение (предварительно рассчитанного) обратного значения даст вам значительный выигрыш и, вероятно, приемлемую потерю точности.
Ради эффективности вам лучше пошевелиться 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 и метки как значения: найдите нужную метку внутри переключателя, а затем просто переходите к ней каждый раз.Я думаю, это должно сэкономить еще несколько циклов.
Коммутаторы не должны создавать каких-либо значительных накладных расходов, они компилируются в своего рода массив указателей на нижнем уровне, тогда это эффективно:
jmp {базовый адрес}+switchcasenum
Вероятно, это будет зависеть от того, насколько хорош предиктор ветвления вашего процессора и как ваш компилятор генерирует код для переключения.Для такого небольшого числа случаев это может сгенерировать дерево решений, и в этом случае обычное прогнозирование ветвления процессора должно позволить устранить большую часть накладных расходов.Все может быть немного хуже, если он сгенерирует таблицу переключений...
Тем не менее, лучший способ узнать это - составить профиль и посмотреть.
В дополнение к совету Джима, попробуйте поменять местами порядок циклов.Является ли замена циклов идеальной для случая 1, потребует тестирования, но я подозреваю, что это так.Вы почти всегда хотите, чтобы ваша координата x находилась внутри вашего внутреннего цикла, чтобы повысить производительность подкачки, поскольку это приводит к тому, что ваша функция имеет лучшую тенденцию оставаться в одной и той же общей области памяти на каждой итерации.А мобильное устройство с ограниченными ресурсами может иметь достаточно мало оперативной памяти, чтобы подчеркнуть это различие.
Извините, что затронул эту тему, но мне кажется, что переключатель ДАЛЕК от проблемы.
Реальная проблема с эффективностью в этом случае заключается в разделениях.Мне кажется, что все знаменатели операций деления являются константами (ширина, высота, макс ...), и они не будут меняться на протяжении всего изображения.Если мое предположение верно, то это простые переменные, которые могут изменяться в зависимости от загруженного изображения, так что изображение любого размера может использоваться во время выполнения, теперь это позволяет загружать изображения любого размера, но это также означает, что компилятор не может оптимизировать их для гораздо более простой операции умножения, которую он мог бы выполнить, если бы они были объявлены "const".Мое предложение состояло бы в том, чтобы предварительно вычислить обратные значения этих констант и умножить.Насколько я помню, операция умножения занимает около 10 тактов, в то время как деление занимает около 70.Это увеличение на 60 циклов на пиксель, а при вышеупомянутых 5000x5000 это, по оценкам, увеличение скорости на 1,5 секунды на процессоре с тактовой частотой 1 ГГц.
Зависит от чипа, компилятора и деталей кода, и ... но это часто реализуется в виде таблицы переходов, которая должна быть довольно быстрой.
КСТАТИ, понимание такого рода вещей - довольно веский аргумент для того, чтобы потратить пару недель на изучение какого-нибудь ассемблера на каком-то этапе вашей карьеры...
Использование переключателя, вероятно, лучше как с точки зрения скорости, так и с точки зрения времени программирования.Вы создаете меньше избыточного кода, и для этого, вероятно, не потребуется новый фрейм стека.
Переключатели настолько эффективны, что их можно использовать для действительно странных и сбивающих с толку задач черная магия.
но эффективность - это название игры в данном случае.
выполнение итерации по буферу изображения для вычисления новых значений пикселей звучит как типичная проблема с затруднительным параллелизмом, в этом смысле вы могли бы рассмотреть возможность переноса части работы в рабочие потоки, это должно ускорить вашу работу более заметно, чем микрооптимизации, такие как проблемы с переключением / регистрацией.
Кроме того, вместо того, чтобы выполнять инструкции ветвления каждый раз, вы могли бы вызывать указатель на функцию из массива указателей на функции, где индекс служит идентификатором вашего режима.
Так что в конечном итоге вы получите такие вызовы, как:
computeWeight[mode](pixel);
При разрешении 5000x5000 пикселей служебные данные при вызове функции также могут быть уменьшены за счет вызова функции для диапазона пикселей, а не для отдельных пикселей.
Вы также могли бы использовать развертывание цикла и передачу параметров по ссылке / указателю, чтобы еще больше оптимизировать это.
Уже приведено много хороших замечаний.Единственное, что я мог бы добавить к этому, это переместить наиболее частые случаи вверх по переключателю и наименее частые вниз.
Таким образом, если случай 4 встречается чаще, чем случай 1, он должен быть выше его:
switch (mode) {
case 4:
// ..
break;
case 1:
// ..
break;
}
Жаль, что вы не использовали c ++, потому что тогда оператор switch можно было бы заменить полиморфизмом.
Ваше здоровье !
В этой теме есть много творческих предложений о том, как избежать необходимости писать 5 отдельных функций.
Если вы не читаете "mode" из файла или из введенных входных данных, метод вычисления может быть определен во время компиляции.Как правило, вы не хотите переносить вычисления из времени компиляции во время выполнения.
В любом случае код был бы легче читаем, и никто не был бы сбит с толку относительно того, хотели ли вы вставить оператор break в первом случае или нет.
Кроме того, когда вы обнаружите ошибки в окружающем коде, вам не придется искать, было ли для перечисления установлено неправильное значение или нет.
Что касается внутренних петель...0-> var лучше сделать var->0, так как var-- запускает нулевой флаг (6502 дня).Такой подход также означает, что "width" загружается в x и о нем можно забыть, то же самое относится и к "height".Кроме того, пиксели в памяти обычно расположены слева-> справа, сверху-> снизу, поэтому определенно используйте 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% поставили это на последнее место.
