четверг, 27 сентября 2012 г.

if против switch

Вот интресный вопрос тут попался: что быстрее if или switch?
Всегда считал их эквивалентными и выбирал исходя из собственных эстетических соображений (т.е. всегда делал if-else), но в интернетах пишут, что switch быстрее из-за лучшей оптимизации. В общем решил проверить.

Есть функция со switch:

int get_digit(char num)
{
        switch(num)
        {
                case '0': return 0;
                case '1': return 1;
                case '2': return 2;
                case '3': return 3;
                case '4': return 4;
                case '5': return 5;
                case '6': return 6;
                case '7': return 7;
                case '8': return 8;
                case '9': return 9;
                default: return -1;
        };
}


И есть с if:

char get_digit(char num)
{
        if( num == '0' ) return 0;
        else if( num == '1' ) return 1;
        else if( num == '2' ) return 2;
        else if( num == '3' ) return 3;
        else if( num == '4' ) return 4;
        else if( num == '5' ) return 5;
        else if( num == '6' ) return 6;
        else if( num == '7' ) return 7;
        else if( num == '8' ) return 8;
        else if( num == '9' ) return 9;
        else return -1;
}


Сначала посмотрим во что они ассемблируются.

Switch:
...
        subl    $48, %edi
        cmpb    $9, %dil
        jbe     .L16
        rep
        ret
        .p2align 4,,10
        .p2align 3
.L16:
        movzbl  %dil, %edi
        jmp     *.L13(,%rdi,8)
        .section        .rodata
        .align 8
        .align 4
.L13:
        .quad   .L3
        .quad   .L14
        .quad   .L5
        .quad   .L6
        .quad   .L7
        .quad   .L8
        .quad   .L9
        .quad   .L10
        .quad   .L11
        .quad   .L12
        .text
        .p2align 4,,10
        .p2align 3
.L11:
        movl    $8, %eax
        ret
        .p2align 4,,10
        .p2align 3
...


If:
...
        cmpb    $48, -4(%rbp)
        jne     .L2
        movl    $0, %eax
        jmp     .L3
.L2:
        cmpb    $49, -4(%rbp)
        jne     .L4
        movl    $1, %eax
        jmp     .L3
...
 .L3:
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc


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

Как это отражается на практике: на вход подавался файл ~200 Мб. Результаты следующие:
$ time cat file | ./switch.out > /dev/null

real    0m11.727s
user    0m11.235s
sys     0m2.367s


$ time cat file | ./if.out > /dev/null

real    0m14.748s
user    0m14.677s
sys     0m2.400s


Выигрыш - 3 секунды. Какой вывод? А вот не знаю. Вроде бы switch и быстрее, но как-то я не очень люблю его. Думаю, выбор сильно зависит от ситуации, ибо такой тривиальный случай сравнения попадается не часто, а в более сложном заменить if на switch может быть и невозможно.

5 комментариев:

  1. А яя об этом знал! )) Была отличная статья Криса Касперски (в журнале "Программист") об особенности преобразований высокоуровневых языковых конструкций в ассемблер. В году этак 2007.
    Там было в том числе и сравнение ifов и switchей.

    Советую почитать.

    ОтветитьУдалить
    Ответы
    1. Эх, на сайте "Программиста" её фиг найдёшь, а в списке статей Касперски их слишком много, непонятно какая...

      Вот, а вообще узнал ещё одну интересную особенность. Наличие разницы в скорости исполнения зависит от архитектуры процессора. На эльбрусе, например вариант с if выполняется не медленнее ;)

      Удалить
  2. оно в зависимости от содержимого может сильно в разное компилиться. Добавь case 100500 для инта, таблички уже не будет ;)

    ОтветитьУдалить
    Ответы
    1. Не подтверждаю. Скомпилил 100500 - табличка, попытался 2000000 - gcc упал, попытался 1000000 - сожрал всю память, пришлось hard reset делать. Но в целом верю, что оно может по-другому отрабатывать, надо будет в саму фазу заглянуть.

      Удалить
    2. А, всё, да, понял про что ты. Согласен, тест довольно примитивный был. Открыл исходники gcc - там на этот счёт много забавных преобразований идёт.

      Удалить