Вопрос по switch-statement, c++, c – Смена оператора с огромным количеством дел

8

Что произойдет, еслиswitch имеет более 5000case, Каковы недостатки и как мы можем заменить это чем-то быстрее?

Примечание: я не собираюсь использовать массив для хранения дел, так какЭто то же самое.

Вы можете использоватьмассив указателей на функции, Это'во много раз быстрее, чем любое сравнение, НО мой вопрос ... как вы можетеуправлять и поддерживать код сswitch/case заявление с 5000 случаев? Adriano Repetti
Почему вы хотите сравнить 5000 случаев? Можно'Вы сжимаете / реорганизуете код, чтобы получить меньше случаев в каждом сегменте кода? mmoment
Если вам нужно переключиться между 5000 делами, это звучит как плохое замысел. В противном случае яЯ бы тоже использовал указатели функций. dtech
@mmoment: Refacotring - определенно решение, но я ищу другой путь. MarsRover

Ваш Ответ

4   ответа
0

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

Один из способов разбить оператор switch - использовать группирование,

int getIt(int input)
{
  int bucket = input%16;
  switch(bucket)
  {
    case 1:
      return getItBucket1(input);
    case 2:
      return getItBucket2(input);
    ...
    ...
  }
  return -1;
}

Таким образом, в приведенном выше коде мы разбили наш оператор switch на 16 частей. Легко изменить количество сегментов в автоматически сгенерированном коде.

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

11

нет особой причины думать, что тыЯ хочу что-нибудь, кроме оператора switch / case (и действительно, ябуду активно ожидать, что это будет бесполезно). Компилятор должен создать эффективный диспетчерский код, который может включать некоторую комбинацию статических [разреженных] таблиц и прямой индексации, двоичного ветвления и т. Д .; Это'Он получил представление о статических значениях дел и должен отлично работать (перенастраивая его на лету каждый раз, когда вы меняете дела, тогда как новые значения, которые нене вписывается в ручной подход - например, дико отличающиеся значения, когда выУ меня был довольно упакованный поиск в массиве - это могло потребовать переделки кода или молча вызвать вздутие памяти или падение производительности).

Люди действительно заботились об этом, когда C пытался победить программистов на хардкорных сборках ... компиляторы были привлечены к ответственности за генерацию хорошего кода. Поместите другой путь - если этоне (измеримо) сломан, неэто исправить.

В более общем смысле этоздорово быть любопытным к таким вещам и привлекать людейс идеями об альтернативах и их последствиях для производительности, но если выдействительно Тщательность и разница в производительности могут оказать полезное влияние на вашу программу (особенно, если это предусмотрено профилированием), а затем всегда сравнивайте ее с реальной работой.

@TonyDelroy, если то, что он должен выполнять в каждом случае, действительно тривиально, тогда использование ассемблерного кода в качестве значений enum может быть его лучшим решением (как это делали оригинальные версии функции BitBlt). Если он должен вызвать более сложную функцию, яЯ не уверен, что планирование команд действительно будет для него проблемой. Adriano Repetti
Да, я верю, что компилятор сделает переключение регистров эффективным, хотя 5000 случаев не являются нормальными. Возможно, массив указателей на функции лучше, по крайней мере, код будет выглядеть лучше. Mine
Одна из проблем заключается в том, что компилятору требуется огромное время для компиляции огромного куска кода в одном файле. shuva
@Adriano: действительные точки, где это применимо ... ура. Tony Delroy
3

айней мере, это делает код немного более читабельным.

Вопрос'Единственное явное требование былочто-то быстрее... хэш-карта, вероятно, будет значительно медленнее, как и принудительный вызов вне линии (который обычно на порядок медленнее, чем встроенный код для одной простой операции, в которой важна скорость переключения), особенно если случаи неt случайно разбросаны по большому диапазону. Tony Delroy
9

если кто-то застрянет со старым / глючным / неэффективным компилятором или просто любит взломать.

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

В задней части салфетки пример;

switch (n) {
    case 1: foo(); break;
    case 2: bar(); break;
    case 3: baz(); break;
}

с помощью такого куска кода компилятор может создать массив jump_addresses и напрямую получить адрес по массиву [n]. Теперь поиск просто занял O (1). Но если у вас был переключатель, как показано ниже:

switch (n) {
    case 10: foo(); break;
    case 17: bar(); break;
    case 23: baz(); break;
    // and a lot other
}

компилятору необходимо сгенерировать таблицу, содержащую пары case_id, jump_address и код для поиска в той структуре, которая в худшем варианте реализации может принять O (n). (Достойные компиляторы чертовски оптимизируют такой сценарий, когда они полностью раскрыты, включив свои флаги оптимизации до такой степени, что, когда вам нужно отладить такой оптимизированный код, ваш мозг начинает жариться.)

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

Для завершения примера вы можете написать второй оператор switch с помощью "метки как значения особенность как это:

const void *cases[] = {&&case_foo, &&case_bar, &&case_baz, ....};
goto *labels[n];
case_foo:
    foo();
    goto switch_end;
case_bar:
    bar();
    goto switch_end;
case_baz:
    baz();
    goto switch_end;
// and a lot other
switch_end:

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

Как заключительные заметки; это улучшит вашу ежедневную работу? Нет. Это улучшит ваши навыки? Да, и, исходя из опыта, я однажды обнаружил, что улучшил алгоритм безопасности в смарт-карте, просто оптимизировав значения регистров. Это странный мир.

спасибо за ответ, это не часть моего дизайна, но кто-то задал мне этот вопрос, и я попытался объяснить его, используя массив указателей на функции. Но это был не быстрый путь. Я сам искал более быстрый путь, я не говорю о читабельности или дизайне здесь. MarsRover

Похожие вопросы