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

8

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

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

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

Ваш Ответ

4   ответа
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
0

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

Один из способов разбить оператор 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 пытался победить программистов на хардкорных сборках ... компиляторы были привлечены к ответственности за генерацию хорошего кода. Иными словами, если он (измеримо) не сломан, не исправляйте его.

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

@Mine: массив указателей на функции сделает код читабельным. но я ищу более быстрое решение. MarsRover
Одна из проблем заключается в том, что компилятору требуется огромное время для компиляции огромного куска кода в одном файле.
Да, я верю, что компилятор сделает переключение регистров эффективным, хотя 5000 случаев не являются нормальными. Возможно, массив указателей на функции лучше, по крайней мере, код будет выглядеть лучше.
@TonyDelroy, если то, что он должен выполнять в каждом случае, действительно тривиально, тогда использование ассемблерного кода в качестве значений enum может быть его лучшим решением (как это делали оригинальные версии функции BitBlt). Если он должен вызывать более сложную функцию, я не уверен, действительно ли планирование команд будет для него проблемой.
@Mine: 5000 случаев не являются нормальными в типичном коде уровня приложения, но говорят, что вы пишете компилятор или операционную систему - или компилируете код, созданный какой-то автоматизированной системой, такой как совершенный генератор хеш-таблиц - вы можете разумно ожидать, что такой код будет работать как смазанная молния. Согласно моему комментарию к ответу Расти, использование указателей функций во время выполнения действительно может негативно повлиять на производительность, поскольку вызовы вне строки, которые в конечном итоге делают что-то тривиальное (например, установка / увеличениеint) может быть на порядок медленнее.
3

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

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

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