Почему компиляторы C оптимизируют переключение и если по-другому

9

Недавно я работал над личным проектом, когда наткнулся на странную проблему.

В очень узком цикле у меня есть целое число со значением от 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поисковой таблицей немного ускоряется: попробуйте онлайн!

LambdaBeta
источник
4
Я подозреваю, что ответ «Компиляторы не всегда делают правильный выбор». Я просто скомпилировал ваш код в объект с GCC 8.3.0 с -O3, и он скомпилировал cчто-то, вероятно, хуже, чем aили b( cимел два условных перехода плюс несколько битовых манипуляций, по сравнению только с одним условным переходом и более простой битовой манипуляцией для b), но все же лучше чем наивный предмет по предметным тестам. Я не уверен, что вы действительно просите здесь; простой факт заключается в том, что оптимизирующий компилятор может превратить любой из них в любой другой, если он того пожелает, и нет жестких и быстрых правил для того, что он будет или не будет делать.
ShadowRanger
Моя проблема в том, что мне нужно, чтобы он был быстрым, но решение if не слишком излечимо. Есть ли способ заставить компилятор достаточно оптимизировать более чистое решение? Кто-нибудь может объяснить, почему он не может сделать это в этом случае?
LambdaBeta
Я бы начал с определения, по крайней мере, функций как статических, или даже лучше их встроенных.
Wildplasser
@wildplasser ускоряет его, но ifвсе еще бьет switch(как ни странно, поиск становится еще быстрее) [TIO, чтобы следовать]
LambdaBeta
@LambdaBeta Нет способа указать компилятору оптимизировать определенным образом. Вы заметите, что clang и msvc генерируют совершенно другой код для них. Если вам все равно, и вы просто хотите, чтобы все работало лучше на gcc, тогда выберите это. Оптимизация компилятора основана на эвристике, и она не дает оптимального решения во всех случаях; Они стараются быть хорошими в среднем, а не оптимальными во всех случаях.
Cubic

Ответы:

6

Если вы явно перечислите все случаи, gcc очень эффективен:

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;
            case 2: case 3: case 6: case 7: case 10: case 11: case 14: case 15: 
        //default:
            return 0;
    }
}

просто скомпилирован в простую проиндексированную ветку:

c:
        and     edi, 15
        jmp     [QWORD PTR .L10[0+rdi*8]]
.L10:
        .quad   .L12
        .quad   .L12
        .quad   .L9
        .quad   .L9
        .quad   .L11
        .quad   .L11
        .quad   .L9
        .quad   .L9
        .quad   .L12
etc...

Обратите внимание, что если он default:не прокомментирован, gcc возвращается к своей версии с вложенными ветвями.

Ален Мериго
источник
1
@LambdaBeta Вам следует подумать о том, чтобы не принять мой ответ и принять его, потому что современные процессоры Intel могут выполнять два параллельных индексированных чтения / цикла памяти, тогда как пропускная способность моего трюка, вероятно, составляет 1 поиск / цикл. С другой стороны, возможно, мой хак больше поддается 4-сторонней векторизации с SSE2 pslld/ psradили их 8-канальными эквивалентами AVX2. Многое зависит от других особенностей вашего кода.
Iwillnotexist Idonotexist
4

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

Код как:

if (num == 0 || num == 1 || num == 8 || num == 9) 
    return -1;

if (num == 4 || num == 5 || num == 12 || num == 13)
    return 1;

не будет проходить проверку компетентными C-кодерами; три или четыре рецензента одновременно восклицали бы: «Это должно быть switch

Для компиляторов Си не стоит анализировать структуру ifоператоров для преобразования в таблицу переходов. Условия для этого должны быть правильными, а количество возможных вариантов в куче ifутверждений астрономическое. Анализ сложен и, скорее всего, будет отрицательным (например, «нет, мы не можем преобразовать эти значения ifв a switch»).

Kaz
источник
Я знаю, именно поэтому я начал с выключателя. Тем не менее, решение if значительно быстрее в моем случае. Я в основном спрашиваю, есть ли способ убедить компилятор использовать лучшее решение для переключателя, так как он смог найти шаблон в ifs, но не в переключателе. (Мне не особенно нравятся ifs, потому что они не так понятны или понятны)
LambdaBeta
Проголосовали, но не приняли, так как именно поэтому я и задал этот вопрос. Я хочу использовать переключатель, но он слишком медленный в моем случае, я хочу избежать, ifесли это вообще возможно.
LambdaBeta
@LambdaBeta: Есть ли какая-то причина избегать таблицы поиска? Сделайте это staticи используйте назначенные инициализаторы C99, если вы хотите прояснить, что вы назначаете, и это совершенно нормально.
ShadowRanger
1
Я бы начал хотя бы с отбрасывания младшего бита, чтобы оптимизатору было меньше работы.
R .. GitHub ОСТАНОВИТЬ ЛЬДА
@ShadowRanger К сожалению, это все еще медленнее, чем if(см. Редактирование). @R .. Я разработал полное побитовое решение для компилятора, которым я сейчас и пользуюсь. К сожалению, в моем случае это enumзначения, а не голые целые числа, поэтому побитовые хаки не очень удобны в обслуживании.
LambdaBeta
4

Следующий код вычислит ваш поиск без ветвей, без LUT, за ~ 3 такта, ~ 4 полезных инструкции и ~ 13 байт inlineмашинного кода x86 с высокой функциональностью.

Это зависит от целочисленного представления дополнения 2.

Однако вы должны убедиться, что u32и s32typedefs действительно указывают на 32-битные целые типы без знака и со знаком. stdint.hтипы uint32_tи int32_tбыло бы подходящим, но я понятия не имею, доступен ли вам заголовок.

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 d(int num){
    typedef unsigned int u32;
    typedef signed   int s32;

    // const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
    // 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
    // Hexadecimal:                   F     0     5     0     F     0     5     0
    const u32 K = 0xF050F050U;

    return (s32)(K<<(num+num)) >> 30;
}

int main(void){
    for(int i=0;i<16;i++){
        if(a(i) != d(i)){
            return !0;
        }
    }
    return 0;
}

Смотрите сами здесь: https://godbolt.org/z/AcJWWf


На выбор постоянной

Ваш поиск для 16 очень маленьких констант от -1 до +1 включительно. Каждый вписывается в 2 бита, и их 16, которые мы можем изложить следующим образом:

// const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
// 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
// Hexadecimal:                   F     0     5     0     F     0     5     0
u32 K = 0xF050F050U;

Помещая их с индексом 0, ближайшим к старшему значащему биту, один сдвиг 2*numпоместит бит знака вашего 2-битного числа в бит знака регистра. Если сдвинуть вправо 2-битное число на 32-2 = 30 битов, знак расширяет его до полного int, завершая фокус.

Ивилнотексист Идонотексист
источник
Это может быть просто самый чистый способ сделать это с magicкомментарием, объясняющим, как его восстановить. Не могли бы вы объяснить, как вы пришли к этому?
LambdaBeta
Принимается, так как это можно сделать «чистым» и при этом быть быстрым. (через некоторую магию препроцессора :) < xkcd.com/541 >)
LambdaBeta
1
Бьет мою попытку без !!(12336 & (1<<x))-!!(771 & (1<<x));
ответвлений
0

Вы можете создать тот же эффект, используя только арифметику:

// produces : -1 -1 0 0 1 1 0 0 -1 -1 0 0 1 1 0 0 ...
int foo ( int x )
{
    return 1 - ( 3 & ( 0x46 >> ( x & 6 ) ) );
}

Хотя технически это все же (побитовый) поиск.

Если вышесказанное кажется слишком загадочным, вы также можете сделать:

int foo ( int x )
{
    int const y = x & 6;
    return (y == 4) - !y;
}
KevinZ
источник