5

Что лучше использовать: if\else или switch\case?

int a = 3;

if (a == 1)
{
    ...
}
else if (a == 2)
{
    ...
}
else
{
    ...
}

switch(a)
{
    case 1:
        ...
        break;

    case 2:
        ...
        break;

    default:
        ...
        break;
}
  • Какая из этих конструкций работает быстрее? Почему?
  • Когда лучше использовать то или другое?

3 ответа 3

22

Ответ выше не совсем корректный, даже учитывая комментарий.

Если значения лежат рядом, например:

switch (x)
{
    case 0: /* */ break;
    case 1: /* */ break;
    case 2: /* */ break;
    case 3: /* */ break;
    case 4: /* */ break;
    case 5: /* */ break;
}

В таком случае компилятор генерирует таблицу переходов (jump table) (IL-код):

switch (IL_0043, IL_004e, IL_0059, IL_0064, IL_006f, IL_007a)

Время работы такой таблицы O(1). Не нужно волноваться, если несколько значений упущено, и они не идут один за другим, в таком случае компилятор все равно генерирует таблицу переходов:

switch (x)
{
    case 0: /* */ break;
    case 1: /* */ break;
    case 2: /* */ break;
    case 3: /* */ break;
    case 4: /* */ break;
    case 5: /* */ break;
    case 9: /* */ break;
    case 13: /* */ break;
}

IL:

switch (IL_0043, IL_004e, IL_0059, IL_0064, IL_006f, IL_007a, IL_009a, IL_009a, IL_009a, IL_0085, IL_009a, IL_009a, IL_009a, IL_0090)

Как видно, "дырки" заполнились переходами за конец конструкции switch: IL_009a

Если расстояние между значениями слишком большое для построение одной таблицы, компилятор может разделить их на 2+ таблицы. Например:

switch (x)
{
    case 0: /* */ break;
    case 1: /* */ break;
    case 2: /* */ break;
    case 3: /* */ break;
    case 2000000000: /* */ break;
    case 2000000001: /* */ break;
    case 2000000002: /* */ break;
    case 2000000003: /* */ break;
    case 2000000004: /* */ break;
}

IL:

IL_0004: ldloc.0
IL_0005: switch (IL_0037, IL_0042, IL_004d, IL_0058)

IL_001a: ldloc.0
IL_001b: ldc.i4 2000000000
IL_0020: sub
IL_0021: switch (IL_0063, IL_006e, IL_0079, IL_0084)

Как видно из примера выше, компилятор выделил 2 таблицы переходов. Для другой таблицы из значения вычитается 2,000,000,000. В общем случае скорость выполнения O(1) или O(m), где m - количество групп.

Посмотрим что будет в общем случае. Я взял 20 случайных чисел:

switch (x)
{
    case 955626049: /* */ break;
    case 1732096473: /* */ break;
    case 1416261125: /* */ break;
    case 901627868: /* */ break;
    case 713886433: /* */ break;
    case 289231272: /* */ break;
    case 598309392: /* */ break;
    case 1284278823: /* */ break;
    case 1517161566: /* */ break;
    case 1548994144: /* */ break;
    case 1854092737: /* */ break;
    case 1725885116: /* */ break;
    case 1984539276: /* */ break;
    case 558794563: /* */ break;
    case 337975821: /* */ break;
    case 1687544575: /* */ break;
    case 1048183578: /* */ break;
    case 102389471: /* */ break;
    case 1017837673: /* */ break;
    case 1012360293: /* */ break;
}

В таком случае компилятор их сортирует, и ищет бинарным поиском:

IL_0004: ldloc.0
IL_0005: ldc.i4 1017837673
IL_000a: bgt IL_0099

IL_000f: ldloc.0
IL_0010: ldc.i4 598309392
IL_0015: bgt.s IL_0058

IL_0017: ldloc.0
IL_0018: ldc.i4 289231272
IL_001d: bgt.s IL_0036

IL_001f: ldloc.0
IL_0020: ldc.i4 102389471
IL_0025: beq IL_016e

IL_002a: ldloc.0
IL_002b: ldc.i4 289231272
IL_0030: beq IL_0126

IL_0035: ret

IL_0036: ldloc.0
IL_0037: ldc.i4 337975821
IL_003c: beq IL_015c

IL_0041: ldloc.0
IL_0042: ldc.i4 558794563
IL_0047: beq IL_0156

IL_004c: ldloc.0
IL_004d: ldc.i4 598309392
IL_0052: beq IL_012c

IL_0057: ret

IL_0058: ldloc.0
IL_0059: ldc.i4 901627868
IL_005e: bgt.s IL_0077

IL_0060: ldloc.0
IL_0061: ldc.i4 713886433
IL_0066: beq IL_0120

IL_006b: ldloc.0
IL_006c: ldc.i4 901627868
IL_0071: beq IL_011a

IL_0076: ret

IL_0077: ldloc.0
IL_0078: ldc.i4 955626049
IL_007d: beq IL_0108

IL_0082: ldloc.0
IL_0083: ldc.i4 1012360293
IL_0088: beq IL_017a

IL_008d: ldloc.0
IL_008e: ldc.i4 1017837673
IL_0093: beq IL_0174

IL_0098: ret

IL_0099: ldloc.0
IL_009a: ldc.i4 1548994144
IL_009f: bgt.s IL_00d6

IL_00a1: ldloc.0
IL_00a2: ldc.i4 1284278823
IL_00a7: bgt.s IL_00bd

IL_00a9: ldloc.0
IL_00aa: ldc.i4 1048183578
IL_00af: beq IL_0168

IL_00b4: ldloc.0
IL_00b5: ldc.i4 1284278823
IL_00ba: beq.s IL_0132

IL_00bc: ret

IL_00bd: ldloc.0
IL_00be: ldc.i4 1416261125
IL_00c3: beq.s IL_0114

IL_00c5: ldloc.0
IL_00c6: ldc.i4 1517161566
IL_00cb: beq.s IL_0138

IL_00cd: ldloc.0
IL_00ce: ldc.i4 1548994144
IL_00d3: beq.s IL_013e

IL_00d5: ret

IL_00d6: ldloc.0
IL_00d7: ldc.i4 1725885116
IL_00dc: bgt.s IL_00ef

IL_00de: ldloc.0
IL_00df: ldc.i4 1687544575
IL_00e4: beq.s IL_0162

IL_00e6: ldloc.0
IL_00e7: ldc.i4 1725885116
IL_00ec: beq.s IL_014a

IL_00ee: ret

IL_00ef: ldloc.0
IL_00f0: ldc.i4 1732096473
IL_00f5: beq.s IL_010e

IL_00f7: ldloc.0
IL_00f8: ldc.i4 1854092737
IL_00fd: beq.s IL_0144

IL_00ff: ldloc.0
IL_0100: ldc.i4 1984539276
IL_0105: beq.s IL_0150

IL_0107: ret

В таком случае скорость выполнения будет O(log n).

Аналогичная if then else конструкция выполняется за O(n). А это значит switch почти всегда быстрее if then else.

Все примеры IL скомпилированы для .NET версии 4.6

Дополнение для String:

Для типа string работает немного по-другому, так как таблицу переходов не построить, а искать бинарным поиском (перебирая каждый символ) - неоптимально. В таком компилятор считает хеш всех строк, а потом во время выполнения считает хеш от входящей строки, и ищет бинарным поиском. Пример:

switch (x)
{
    case "ff": return 10;
    case "f1": return 11;
    case "f2": return 12;
    case "f3": return 13;
    case "f4": return 14;
    case "f5": return 15;
    case "f6": return 16;
    case "f7": return 17;
    case "f8": return 18;
    case "f9": return 19;
    case "10": return 20;
    case "11": return 21;
    case "12": return 22;
    default:
        return 0;
}

IL-код:

IL_0001: call uint32 '<PrivateImplementationDetails>'::ComputeStringHash(string)
IL_0006: stloc.0
IL_0007: ldloc.0
IL_0008: ldc.i4 89242279
IL_000d: bgt.un.s IL_0063

IL_000f: ldloc.0
IL_0010: ldc.i4 38909422
IL_0015: bgt.un.s IL_003d

IL_0017: ldloc.0
IL_0018: ldc.i4 5354184
IL_001d: beq IL_0147

IL_0022: ldloc.0
IL_0023: ldc.i4 22131803
IL_0028: beq IL_0159

IL_002d: ldloc.0
IL_002e: ldc.i4 38909422
IL_0033: beq IL_011d

IL_0038: br IL_01da

IL_003d: ldloc.0
IL_003e: ldc.i4 55687041
IL_0043: beq IL_0132

IL_0048: ldloc.0
IL_0049: ldc.i4 72464660
IL_004e: beq IL_00f3

IL_0053: ldloc.0
IL_0054: ldc.i4 89242279
IL_0059: beq IL_0108

IL_005e: br IL_01da

IL_0063: ldloc.0
IL_0064: ldc.i4 1972548895
IL_0069: bgt.un.s IL_008b

IL_006b: ldloc.0
IL_006c: ldc.i4 122797517
IL_0071: beq.s IL_00de

IL_0073: ldloc.0
IL_0074: ldc.i4 810679896
IL_0079: beq.s IL_00c9

IL_007b: ldloc.0
IL_007c: ldc.i4 1972548895
IL_0081: beq IL_01a4

IL_0086: br IL_01da

IL_008b: ldloc.0
IL_008c: ldc.i4 2006104133
IL_0091: bgt.un.s IL_00ae

IL_0093: ldloc.0
IL_0094: ldc.i4 1989326514
IL_0099: beq IL_0195

IL_009e: ldloc.0
IL_009f: ldc.i4 2006104133
IL_00a4: beq IL_0186

IL_00a9: br IL_01da

IL_00ae: ldloc.0
IL_00af: ldc.i4 -28201054
IL_00b4: beq IL_0168

IL_00b9: ldloc.0
IL_00ba: ldc.i4 -11423435
IL_00bf: beq IL_0177

IL_00c4: br IL_01da

После этого идет сравнение методом System.String::op_Equality (так как хеш может совпать и у разных строк). Этот механизм не является хеш-таблицей, так как в хеш-таблицы скорость доступа к элементу O(1), а здесь просто бинарный поиск за O(log n)

Я попытался создать очень большой switch на 60 строк, но ничего не изменилось.

7
  • 1
    Стоит уточнить, что и это не полный ответ, так как у компилятора есть много различных оптимизаций для switch-case и if-else. И в случае такого выбора: case "Hello": return 1; вместо меток перехода может быть использована коллекция Dictionary<string, int>. Наверняка, с приходом паттерн-матчинга будет добавлено ещё множество оптимизаций, которые сделают поведение switch-case ещё менее предсказуемым. 31 авг 2017 в 15:56
  • 1
    Вы не правы. Добавил информацию про string
    – Zergatul
    31 авг 2017 в 18:13
  • 2
    А почему вы смотрите в IL, а не в генерируемый после JIT машинный код? Основная часть оптимизаций происходит именно там.
    – VladD
    31 авг 2017 в 19:30
  • Компилятор c# раскручивает switch до уже достаточно простых инструкций. Если в IL коде генерируется бинарный поиск за O(log n), но оптимизатор JIT ну никак не оптимизирует его до O(1).
    – Zergatul
    31 авг 2017 в 21:55
  • @Zergatul: Но он может соптимизировать цепочку ифов.
    – VladD
    31 авг 2017 в 22:27
12

Оба условных оператора работают с одинаковой скоростью. Так как на уровне машинных команд они преобразуются в одни и те же инструкции.

Выбирать имеет смысл только по вкусу и по задаче.

switch может работать только с одной переменной. У if таких ограничений нет.

На мой взгляд, язык C# слишком высокоуровневый для такого рода оптимизаций.

Пишите читаемый код ;)

1
  • 6
    Дополню: если в switch много условий, то используется Dictionary
    – Vlad
    21 авг 2015 в 12:53
3

Вы задаётесь неправильным вопросом.

Если ваша задача — ускорить вашу программу, то решением этой задачи никогда не будет «заменить свитч на последовательность ифов» или наоборот. Ускорение программы проводится на уровне используемых алгоритмов и структур данных.

Тот факт, что один или другой вариант в тех или иных условиях, на той или иной версии компилятора выполняется на несколько наносекунд быстрее, не стоит потраченных на него байт текста.

Во-первых, вы должны помнить, что ваша главная задача — не выиграть 10 тактов процессора (несчастное переключение контекста стоит намного больше!), а сделать вашу программу понятной. Поэтому вы должны использовать switch там, где это прибавляет читаемости коду, там, где это соответствует тому, что именно вы хотите сказать этим кодом. И использовать if там, где это лучше отражает вашу мысль.

Например, если вы устраиваете перебор значений enum'а, то чаще всего вам нужен switch. А если вы реально проверяете несколько условий, особенно с длинными вычислениями, то, возможно, лучше цепочка if'ов.

Ну и во-вторых, то, что на одной версии компилятора один из методов выражения одной и той же идеи компилируется в более быстрый код, чем другой метод — штука временная и преходящая. Помните, что в C++ сначала рекомендовалось возвращать значения по ссылке для скорости, а затем пришёл тренд «want speed? pass by value!», и наверняка это поменялось сейчас ещё раз.

Поскольку код имеет одинаковый смысл, то в любом из его вариантов рано или поздно он будет компилироваться в одно и то же. JIT-компилятор C# покамест не генерирует одинаковый объектный код для этих двух случаев, а вот компиляторы C++ уже умеют.

Итак, то, какая из имплементаций скорее, а какая медленнее — это не абсолютное понятие.


Вы не должны жертвовать читаемостью кода ради сиюминутной мизерной выгоды. Пишите не «как скорее», а «как правильнее». Расходы на поддержку плохо написанного кода несравнимо больше выгод от микрооптимизаций.

2
  • Это правильно, но все же может стоит упомянуть, что в случае цепочки if-ов и если логика чтения кода в соответствии с алгоритмом не страдает и вы знаете, что некоторые условия более вероятны, то следует вытаскивать их к началу цепочки.
    – avp
    31 авг 2017 в 22:02
  • @avp: В ассемблерном листинге, который я привёл, видно, что этим занимается сам компилятор. Поэтому лучше дать хинты для компилятора, или использовать profile-guided optimization (особенно удобно это делать как раз JIT-компилятору!)
    – VladD
    31 авг 2017 в 22:27

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.