VPF::switch vs if - Форум программистов

volatile

Дата 24.3.2011, 01:12 (ссылка)

(голосов:7)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Мне самому стало интересно, насколько компилятор оправдывает ожидания.
Итак для сравнения были взяты процедуры.
1. с switch

Код


int f_switch ( int v , stopwatch2 & sw)
{
    int res = 0;
    sw.resume (); // Включаем секундомер
    switch (v)
    {
       case V01: res = 0xc9ab9ade; break;
       case V02: res = 0x012c03c6; break;
       case V03: res = 0x25995a7a; break;
       case V04: res = 0xffa77b13; break;
       case V05: res = 0xac8b916e; break;
       case V06: res = 0x21f396b5; break;
       case V07: res = 0x9d90573c; break;
       case V08: res = 0x297000f8; break;
       case V09: res = 0xab55d6b9; break;
       //----- и.т.д.

2. с if

Код


int f_if ( int v , stopwatch2 & sw)
{
    int res = 0;
    sw.resume (); // Включаем секундомер
    if      ( v == V01 ) res = 0xc9ab9ade;
    else if ( v == V02 ) res = 0x012c03c6;
    else if ( v == V03 ) res = 0x25995a7a;
    else if ( v == V04 ) res = 0xffa77b13;
    else if ( v == V05 ) res = 0xac8b916e;
    else if ( v == V06 ) res = 0x21f396b5;
    else if ( v == V07 ) res = 0x9d90573c;
    else if ( v == V08 ) res = 0x297000f8;
    else if ( v == V09 ) res = 0xab55d6b9;
    //----- и.т.д.

В качестве значений для кейсов были выбраны беспорядочные числа. Чтобы компилятор не смог построить талбицу переходов

Код


// Беспорядочные числа. 
enum { 
   V01 = 0x887ced83,
   V02 = 0xfa6b5543,
   V03 = 0x480cefba,
   V04 = 0x150fe719,
   V05 = 0x375f0cde,
   V06 = 0x9cb85e21,
   V07 = 0x9d260ca2,
   V08 = 0x10ed5ae3,
   V09 = 0x0274316c,
   V10 = 0x2f1ad325,
   V11 = 0x9b2f60e2,
   V12 = 0x5ce2f85f,
   V13 = 0x86f37e94,
   //----- и.т.д.

И второй случай числа идущие подряд. Для проверки способности компилера построить таблицу переходов.

Код


enum { 
   V01,   V02,   V03,   V04,   V05,   V06,   V07,   V08,
   V09,   V10,   V11,   V12,   V13,   V14,   V15,   V16,
   V17,   V18,   V19,   V20,   V21,   V22,   V23,   V24,
   //----- и.т.д.

В качестве бенчмарка употреблен класс секундомера использующий __rdtsc ();

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

Код


00401000 ; int __cdecl f_switch(int, class stopwatch2 &)
00401000 ?f_switch@@YAHHAAVstopwatch2@@@Z proc near ; DATA XREF: _wmain+16o
00401000
00401000 arg_0           = dword ptr  4
00401000 arg_4           = dword ptr  8
00401000
00401000                 push    esi
00401001                 mov     esi, [esp+4+arg_4]
00401005                 cmp     byte ptr [esi+8], 0
00401009                 jnz     short loc_40101B
0040100B                 rdtsc
0040100D                 sub     eax, [esi]
0040100F                 mov     byte ptr [esi+8], 1
00401013                 sbb     edx, [esi+4]
00401016                 mov     [esi], eax
00401018                 mov     [esi+4], edx
0040101B
0040101B loc_40101B:                             ; CODE XREF: f_switch(int,stopwatch2 &)+9j
0040101B                 mov     eax, [esp+4+arg_0]
0040101F                 cmp     eax, 6166B26h
00401024                 jg      loc_4013F1
0040102A                 jz      loc_4013E7
00401030                 cmp     eax, 0AFFE3C3Ah
00401035                 jg      loc_401219
0040103B                 jz      loc_40120F
00401041                 cmp     eax, 94E1CF96h
00401046                 jg      loc_40113E
0040104C                 jz      loc_401134
00401052                 cmp     eax, 8A71496Dh
00401057                 jg      short loc_4010D5
00401059                 jz      short loc_4010CB
0040105B                 cmp     eax, 8754404Ah
00401060                 jg      short loc_4010A5
00401062                 jz      short loc_40109B
00401064                 cmp     eax, 860FF78Ah
00401069                 jz      short loc_401091
0040106B                 cmp     eax, 8651A68Dh
00401070                 jz      short loc_401087
00401072                 cmp     eax, 86F37E94h
00401077                 jnz     loc_401769
0040107D                 mov     ecx, 0CE56C442h
00401082                 jmp     loc_40177C
00401087 ; ---------------------------------------------------------------------------
00401087
00401087 loc_401087:                             ; CODE XREF: f_switch(int,stopwatch2 &)+70j
00401087                 mov     ecx, 6FFCF3D9h
0040108C                 jmp     loc_40177C
00401091 ; ---------------------------------------------------------------------------
00401091
00401091 loc_401091:                             ; CODE XREF: f_switch(int,stopwatch2 &)+69j
00401091                 mov     ecx, 0E84841B6h
00401096                 jmp     loc_40177C
0040109B ; ---------------------------------------------------------------------------
0040109B
0040109B loc_40109B:                             ; CODE XREF: f_switch(int,stopwatch2 &)+62j
0040109B                 mov     ecx, 0F424647Dh
004010A0                 jmp     loc_40177C
004010A5 ; ---------------------------------------------------------------------------
004010A5
004010A5 loc_4010A5:                             ; CODE XREF: f_switch(int,stopwatch2 &)+60j
004010A5                 cmp     eax, 877B3043h
004010AA                 jz      short loc_4010C1
004010AC                 cmp     eax, 887CED83h
004010B1                 jnz     loc_401769
004010B7                 mov     ecx, 0C9AB9ADEh
004010BC                 jmp     loc_40177C
004010C1 ; ---------------------------------------------------------------------------

Лучше это видно на картинке (кликабельно)

Для Чисел идущих подряд, все как и ожидалось компилер сделал таблицу перехода.
(смотрим внимательно на 23 строку "jmp ds:off_4013F8[eax*4]"

Код


00401000 ; int __cdecl f_switch(int, class stopwatch2 &)
00401000 ?f_switch@@YAHHAAVstopwatch2@@@Z proc near ; DATA XREF: _wmain+16o
00401000
00401000 arg_0           = dword ptr  4
00401000 arg_4           = dword ptr  8
00401000
00401000                 push    esi
00401001                 mov     esi, [esp+4+arg_4]
00401005                 cmp     byte ptr [esi+8], 0
00401009                 jnz     short loc_40101B
0040100B                 rdtsc
0040100D                 sub     eax, [esi]
0040100F                 mov     byte ptr [esi+8], 1
00401013                 sbb     edx, [esi+4]
00401016                 mov     [esi], eax
00401018                 mov     [esi+4], edx
0040101B
0040101B loc_40101B:                             ; CODE XREF: f_switch(int,stopwatch2 &)+9j
0040101B                 mov     eax, [esp+4+arg_0]
0040101F                 cmp     eax, 62h        ; switch 99 cases
00401022                 ja      loc_4013D7      ; default
00401028                 jmp     ds:off_4013F8[eax*4] ; switch jump
0040102F
0040102F loc_40102F:                             ; DATA XREF: .text:off_4013F8o
0040102F                 mov     ecx, 0C9AB9ADEh ; jumptable 00401028 case 0
00401034                 jmp     loc_4013DC
00401039 ; ---------------------------------------------------------------------------
00401039
00401039 loc_401039:                             ; CODE XREF: f_switch(int,stopwatch2 &)+28j
00401039                                         ; DATA XREF: .text:off_4013F8o
00401039                 mov     ecx, 12C03C6h   ; jumptable 00401028 case 1
0040103E                 jmp     loc_4013DC
00401043 ; ---------------------------------------------------------------------------
00401043
00401043 loc_401043:                             ; CODE XREF: f_switch(int,stopwatch2 &)+28j
00401043                                         ; DATA XREF: .text:off_4013F8o
00401043                 mov     ecx, 25995A7Ah  ; jumptable 00401028 case 2
00401048                 jmp     loc_4013DC

Ну и наконец для ифов, все прямолинейно.

Код


00401590 ; int __cdecl f_if(int, class stopwatch2 &)
00401590 ?f_if@@YAHHAAVstopwatch2@@@Z proc near  ; DATA XREF: _wmain+9o
00401590
00401590 arg_0           = dword ptr  4
00401590 arg_4           = dword ptr  8
00401590
00401590                 push    esi
00401591                 mov     esi, [esp+4+arg_4]
00401595                 cmp     byte ptr [esi+8], 0
00401599                 jnz     short loc_4015AB
0040159B                 rdtsc
0040159D                 sub     eax, [esi]
0040159F                 mov     byte ptr [esi+8], 1
004015A3                 sbb     edx, [esi+4]
004015A6                 mov     [esi], eax
004015A8                 mov     [esi+4], edx
004015AB
004015AB loc_4015AB:                             ; CODE XREF: f_if(int,stopwatch2 &)+9j
004015AB                 mov     eax, [esp+4+arg_0]
004015AF                 test    eax, eax
004015B1                 jnz     short loc_4015BD
004015B3                 mov     ecx, 0C9AB9ADEh
004015B8                 jmp     loc_401B61
004015BD ; ---------------------------------------------------------------------------
004015BD
004015BD loc_4015BD:                             ; CODE XREF: f_if(int,stopwatch2 &)+21j
004015BD                 cmp     eax, 1
004015C0                 jnz     short loc_4015CC
004015C2                 mov     ecx, 12C03C6h
004015C7                 jmp     loc_401B61
004015CC ; ---------------------------------------------------------------------------
004015CC
004015CC loc_4015CC:                             ; CODE XREF: f_if(int,stopwatch2 &)+30j
004015CC                 cmp     eax, 2
004015CF                 jnz     short loc_4015DB
004015D1                 mov     ecx, 25995A7Ah
004015D6                 jmp     loc_401B61
004015DB ; ---------------------------------------------------------------------------
004015DB
004015DB loc_4015DB:                             ; CODE XREF: f_if(int,stopwatch2 &)+3Fj
004015DB                 cmp     eax, 3
004015DE                 jnz     short loc_4015EA
004015E0                 mov     ecx, 0FFA77B13h
004015E5                 jmp     loc_401B61
004015EA ; ---------------------------------------------------------------------------
004015EA
004015EA loc_4015EA:                             ; CODE XREF: f_if(int,stopwatch2 &)+4Ej
004015EA                 cmp     eax, 4
004015ED                 jnz     short loc_4015F9
004015EF                 mov     ecx, 0AC8B916Eh
004015F4                 jmp     loc_401B61
004015F9 ; ---------------------------------------------------------------------------
004015F9
004015F9 loc_4015F9:                             ; CODE XREF: f_if(int,stopwatch2 &)+5Dj
004015F9                 cmp     eax, 5
004015FC                 jnz     short loc_401608
004015FE                 mov     ecx, 21F396B5h
00401603                 jmp     loc_401B61

Результаты по времени. для беспорядочных чисел. Левое число, просто результат вычислений, чтобы оптимизатор не выкинул вообще весь цикл, ну и чтобы сравнить одинаковость результата.
Время находиться справа. (в %)

Код


result = 1703336373   if     = 100.0%
result = 1703336373   switch =  68.3%

Результаты по времени. для чисел идущих подряд

Код


result = 945107626   if     = 100.0%
result = 945107626   switch =  51.6%

Использовалась MSVS 2008. Коммандная строка:

Код


/O2 /Ob2 /Oi /Ot /GL /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /FD /EHsc /MT /GS- /Gy /Yu"stdafx.h" /Fp"Release\switch_vs_if.pch" /Fo"Release\\" /Fd"Release\vc90.pdb" /W3 /nologo /c /Zi /TP /errorReport:prompt

Полный проект, и полные тексты дизасембированных процедур (IDA) - в аттаче.

Резюме: Иф в любом варианте (беспорядочные числа, или порядочные) проигрывает свитчу.
Проигрывает не так много как в теории, сказывается видимо промахи очереди комманд, но проигрывает надежно.

Присоединённый файл ( Кол-во скачиваний: 6 )

switch_vs_if.rar 50,96 Kb

kemiisto

Дата 24.3.2011, 01:42 (ссылка)

(нет голосов)

Загрузка ...

Дикий Кот. =^.^=

Награды: 1

Профиль
Группа: Участник Клуба
Сообщений: 3292
Регистрация: 29.7.2007

Репутация: 2
Всего: 160

Ну вот уже что-то.

Пробовал на VS2010 как x86, так и x64. Цифры подтверждаю.

А почему такой большой разброс?

Цитата(volatile @ 23.3.2011, 23:12

)

Резюме: Иф в любом варианте (беспорядочные числа, или порядочные) проигрывает свитчу.

У меня такое ощущение, что невозможность аналогичной оптимизации для if вызвана тем, что в С/С++ отсуствует многоветочный if. Судя по стандарту:

Цитата

selection-statement:
if ( condition ) statement
if ( condition ) statement else statement
switch ( condition ) statement

То есть вместо многоветочного if имеем глубоко вложенный if. Попробовать бы тот же бенчмарк на языках с "настоящим" многоветочным if. Ada, Fortran, ... Будет время, запилю что-нибудь на последнем.

Пока я соглашусь с тем, что в С++ if не выиграет у switch.

--------------------

XMPP-канал.

Unit testing isn't enough. You need static typing.

Пей, кури, пиши на си! smile

mes

Дата 24.3.2011, 20:15 (ссылка)

(голосов:2)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(kemiisto @ 24.3.2011, 00:42

)

if не выиграет у switch.

дело не в ифе и свитче.. а в оптимизации.. в случае с ифом у компилятора связаны руки..
зато при свитче он может делать все что захочет не нарушая семантики выражения..

Добавлено через 1 минуту и 26 секунд
т.е. другими словами, если программист потратит свое время и съоптимизирует алгоритм, то скорость будет как у свитча..

--------------------

http://opendots.net

KaraKum

Дата 24.3.2011, 20:22 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 640
Регистрация: 3.12.2007

Репутация: 1
Всего: 1

Кстати, в ассемблерном коде простых if'а и switch'а:

Код


if(value == 0)
{
}
else if(value == 1)
{
}
else if(value == 2) ...
--------------------------------------
switch(value)
{
     case 0:
     break;
     case 1:
     break;
     case 2: ...
}

видно что на один if() затрачивается 2 операции, а на один case затрачивается 3 операции.

bsa

Дата 24.3.2011, 23:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

KaraKum, это потому что в случае switch работа идет с бинарным деревом. Зато суммарное количество операций ниже.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »