четверг, 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 может быть и невозможно.