Недавно я работал над личным проектом, когда наткнулся на странную проблему.
В очень узком цикле у меня есть целое число со значением от 0 до 15. Мне нужно получить -1 для значений 0, 1, 8 и 9 и 1 для значений 4, 5, 12 и 13.
Я повернулся к Godbolt, чтобы проверить несколько вариантов, и был удивлен, что компилятор не мог оптимизировать оператор switch так же, как цепочка if.
Ссылка здесь: https://godbolt.org/z/WYVBFl
Код является:
const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
int a(int num) {
return lookup[num & 0xF];
}
int b(int num) {
num &= 0xF;
if (num == 0 || num == 1 || num == 8 || num == 9)
return -1;
if (num == 4 || num == 5 || num == 12 || num == 13)
return 1;
return 0;
}
int c(int num) {
num &= 0xF;
switch (num) {
case 0: case 1: case 8: case 9:
return -1;
case 4: case 5: case 12: case 13:
return 1;
default:
return 0;
}
}
Я бы подумал, что b и c дадут одинаковые результаты, и я надеялся, что смогу прочитать побитные хаки, чтобы сам придумать эффективную реализацию, поскольку мое решение (оператор switch - в другой форме) было довольно медленным.
Как ни странно, он был b
скомпилирован в бит-хаки, но c
был либо в значительной степени неоптимизирован, либо сведен к другому случаю в a
зависимости от целевого оборудования.
Кто-нибудь может объяснить, почему существует это несоответствие? Каков «правильный» способ оптимизации этого запроса?
РЕДАКТИРОВАТЬ:
осветление
Я хочу, чтобы решение для переключения было самым быстрым или аналогичным «чистым» решением. Однако при компиляции с оптимизацией на моей машине решение if значительно быстрее.
Я написал быструю программу для демонстрации, и TIO дает те же результаты, что и на местном уровне: попробуйте онлайн!
С static inline
поисковой таблицей немного ускоряется: попробуйте онлайн!
источник
-O3
, и он скомпилировалc
что-то, вероятно, хуже, чемa
илиb
(c
имел два условных перехода плюс несколько битовых манипуляций, по сравнению только с одним условным переходом и более простой битовой манипуляцией дляb
), но все же лучше чем наивный предмет по предметным тестам. Я не уверен, что вы действительно просите здесь; простой факт заключается в том, что оптимизирующий компилятор может превратить любой из них в любой другой, если он того пожелает, и нет жестких и быстрых правил для того, что он будет или не будет делать.if
все еще бьетswitch
(как ни странно, поиск становится еще быстрее) [TIO, чтобы следовать]Ответы:
Если вы явно перечислите все случаи, gcc очень эффективен:
просто скомпилирован в простую проиндексированную ветку:
Обратите внимание, что если он
default:
не прокомментирован, gcc возвращается к своей версии с вложенными ветвями.источник
pslld
/psrad
или их 8-канальными эквивалентами AVX2. Многое зависит от других особенностей вашего кода.У компиляторов C есть особые случаи
switch
, потому что они ожидают, что программисты поймут идиомуswitch
и используют ее.Код как:
не будет проходить проверку компетентными C-кодерами; три или четыре рецензента одновременно восклицали бы: «Это должно быть
switch
!»Для компиляторов Си не стоит анализировать структуру
if
операторов для преобразования в таблицу переходов. Условия для этого должны быть правильными, а количество возможных вариантов в кучеif
утверждений астрономическое. Анализ сложен и, скорее всего, будет отрицательным (например, «нет, мы не можем преобразовать эти значенияif
в aswitch
»).источник
if
если это вообще возможно.static
и используйте назначенные инициализаторы C99, если вы хотите прояснить, что вы назначаете, и это совершенно нормально.if
(см. Редактирование). @R .. Я разработал полное побитовое решение для компилятора, которым я сейчас и пользуюсь. К сожалению, в моем случае этоenum
значения, а не голые целые числа, поэтому побитовые хаки не очень удобны в обслуживании.Следующий код вычислит ваш поиск без ветвей, без LUT, за ~ 3 такта, ~ 4 полезных инструкции и ~ 13 байт
inline
машинного кода x86 с высокой функциональностью.Это зависит от целочисленного представления дополнения 2.
Однако вы должны убедиться, что
u32
иs32
typedefs действительно указывают на 32-битные целые типы без знака и со знаком.stdint.h
типыuint32_t
иint32_t
было бы подходящим, но я понятия не имею, доступен ли вам заголовок.Смотрите сами здесь: https://godbolt.org/z/AcJWWf
На выбор постоянной
Ваш поиск для 16 очень маленьких констант от -1 до +1 включительно. Каждый вписывается в 2 бита, и их 16, которые мы можем изложить следующим образом:
Помещая их с индексом 0, ближайшим к старшему значащему биту, один сдвиг
2*num
поместит бит знака вашего 2-битного числа в бит знака регистра. Если сдвинуть вправо 2-битное число на 32-2 = 30 битов, знак расширяет его до полногоint
, завершая фокус.источник
magic
комментарием, объясняющим, как его восстановить. Не могли бы вы объяснить, как вы пришли к этому?!!(12336 & (1<<x))-!!(771 & (1<<x));
Вы можете создать тот же эффект, используя только арифметику:
Хотя технически это все же (побитовый) поиск.
Если вышесказанное кажется слишком загадочным, вы также можете сделать:
источник