Ускорение больших переключателей и if-elses

Question

Что я могу сделать, чтобы вручную улучшить большие переключатели и скорость if-elses?Возможно, мне понадобится какая-нибудь хеш-таблица или таблица поиска.

Я работаю с кодами gcc и C, я сомневаюсь, что gcc имеет какие-либо встроенные оптимизации для этого.это то, на что похож каждый переключатель, сделайте что-нибудь, основываясь на том, является ли конкретное int каким-либо значением.Мои if-elses выглядят так:

if( !strcmp( "val1", str ) )
foo();
else if( !strcmp( "val2", str ) )
foo2();
...

У меня также есть ifs, которые делают это

if( struct.member1 != NULL )
foo();
if( struct.member2 != NULL )
foo2();

EDIT2: Спасибо всем.Я не уверен, какой из них я должен выбрать в качестве ответа, потому что многие из этих ответов имеют веские аргументы и ценную информацию.К сожалению, я должен выбрать только один.Но спасибо всем!В конце концов, использование идеальной хеш-таблицы кажется лучшим способом получить время O (n) для доступа как для if, так и для переключателей.

Answer 1

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

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

Answer 2

Чтобы использовать хеш-таблицу:

1. Выберите хеш-функцию. Это одна важная персона. Есть компромиссы между скоростью, качеством хэша и размером вывода. Алгоритмы шифрования могут создавать хорошие хэш-функции. Хеш-функция выполняет некоторые вычисления, используя все биты вашего входного значения, чтобы вернуть некоторое выходное значение с меньшим количеством битов.
2. Таким образом, хеш-функция принимает строку и возвращает целое число от 0 до N
3. Теперь вы можете искать указатель на функцию в таблице размера N.
4. Каждая запись в таблице будет связанным списком (или некоторой другой доступной для поиска структурой данных) из-за вероятности столкновения, то есть две строки, которые отображаются на одно и то же значение хеш-функции.

* 1013 Е.Г. *

lets say hash(char*) returns a value between 0 and 3.
hash("val1") returns 2
hash("val2") returns 0
hash("val3") also returns 0
hash("val4") returns 1

Теперь ваша хеш-таблица выглядит примерно так:

table[0] ("val2",foo2) ("val3", foo3)
table[1] ("val4",foo4)
table[2] ("val1",foo1)
table[3] <empty>

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

Answer 3

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

Answer 4

(я цитирую некоторые из моих предыдущих исследований, которые я написал по этой теме)
В тесте specINT2006, 458.sjeng, в котором реализован симулятор шахмат, используется много операторов switch для обработки различных шахматных фигур.Каждый оператор имеет вид, подобный следующему:

switch (board[from]) {  
case (wpawn): ...  
case (wknight): ... 

, который генерирует компилятор (gcc) в виде последовательности команд, подобной следующей:

40752b: mov -0x28(%rbp),%eax
40752e: mov 0x4238(,%rax,8),%rax
407536: jmpq *%rax

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

Я оставлю остальные ваши вопросы другим.

Answer 5

Хеш-таблица идеально подходит для ускорения сравнения строк.Возможно, вы захотите заглянуть в библиотеку строк, которая не использует строки с нулевым символом в конце, как это делает C stdlib.Множество манипуляций со строками в C включает в себя много «просмотрите строку для nul, затем выполните свою работу».Строковая библиотека, такая как SafeStr , хранит информацию о длине строк, поэтому нет необходимости записывать время на поиск nuls, особенно для строк с неравной длиной

Answer 6

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

• Если вы знаете, что они отличаются довольно хорошо в 4-й позиции, вы могли бы сделать switch на str[3] и только затем сделайте strcmp.
• Или посмотрите какую-нибудь контрольную сумму и switch.

Но все это сделано вручную, вам определенно следует проверить ассемблер, который создает gcc.

Answer 7

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

Если есть более распространенные случаи, чем другие (одна или две вещи происходят чаще, чем остальные), поместите их в начало переключателя / if / else, таким образом, в более распространенных случаях ваша программа сделает это только первой одно или два сравнения и замыкание его пути. Вообще хорошая идея для любого кода ИМХО.

Answer 8

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

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

Другая вещь - это if-else, когда они содержат некоторые сложные логические выражения. Я не буду отвечать на эту часть вопроса здесь.

Answer 9

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