Является ли условный оператор медленным?
Я просматривал некоторый код с огромным оператором switch и оператором if-else для каждого случая и сразу почувствовал необходимость оптимизировать. Как хороший разработчик, я должен постараться получить некоторые жесткие временные факты и начать с трех вариантов:
Исходный код выглядит так:
public static bool SwitchIfElse(Key inKey, out char key, bool shift) { switch (inKey) { case Key.A: if (shift) { key = 'A'; } else { key = 'a'; } return true; case Key.B: if (shift) { key = 'B'; } else { key = 'b'; } return true; case Key.C: if (shift) { key = 'C'; } else { key = 'c'; } return true; ... case Key.Y: if (shift) { key = 'Y'; } else { key = 'y'; } return true; case Key.Z: if (shift) { key = 'Z'; } else { key = 'z'; } return true; ... //some more cases with special keys... } key = (char)0; return false; }Второй вариант преобразован для использования условного оператора:
public static bool SwitchConditionalOperator(Key inKey, out char key, bool shift) { switch (inKey) { case Key.A: key = shift ? 'A' : 'a'; return true; case Key.B: key = shift ? 'B' : 'b'; return true; case Key.C: key = shift ? 'C' : 'c'; return true; ... case Key.Y: key = shift ? 'Y' : 'y'; return true; case Key.Z: key = shift ? 'Z' : 'z'; return true; ... //some more cases with special keys... } key = (char)0; return false; }Поворот с использованием словаря, предварительно заполненного парами ключ / символ:
public static bool DictionaryLookup(Key inKey, out char key, bool shift) { key = '\0'; if (shift) return _upperKeys.TryGetValue(inKey, out key); else return _lowerKeys.TryGetValue(inKey, out key); }
Примечание: два оператора switch имеют одинаковые регистры, а словари имеют одинаковое количество символов.
Я ожидал, что 1) и 2) будут несколько похожими по производительности и что 3) будет немного медленнее.
Для каждого метода, выполняемого два раза по 10.000.000 итераций для прогрева и затем по таймеру, к моему изумлению, я получаю следующие результаты:
- 0,0000166 миллисекунд за звонок
- 0,0000779 миллисекунд за звонок
- 0.0000413 миллисекунд за звонок
Как это может быть? Условный оператор в четыре раза медленнее, чем операторы if-else, и почти в два раза медленнее, чем поиск по словарю. Я что-то здесь упускаю или условный оператор по своей сути медленный?
Обновление 1: несколько слов о моей тестовой подвеске. Я запускаю следующий (псевдо) код для каждого из перечисленных выше вариантов в скомпилированном в Release Project.NET 3.5 в Visual Studio 2010. Оптимизация кода включена, а константы DEBUG/TRACE отключены. Я запускаю измеряемый метод один раз для разминки, а затем выполняю время. Метод run выполнял метод для большого количества итераций, с shift установить в true и false и выбрать набор клавиш ввода:
Run(method);
var stopwatch = Stopwatch.StartNew();
Run(method);
stopwatch.Stop();
var measure = stopwatch.ElapsedMilliseconds / iterations;
Метод Run выглядит следующим образом:
for (int i = 0; i < iterations / 4; i++)
{
method(Key.Space, key, true);
method(Key.A, key, true);
method(Key.Space, key, false);
method(Key.A, key, false);
}
Обновление 2: копая дальше, я посмотрел на IL, сгенерированный для 1) и 2), и обнаружил, что основные структуры переключателей идентичны, как и следовало ожидать, но тела корпусов имеют небольшие различия. Вот IL, на который я смотрю:
1) Если / еще заявление:
L_0167: ldarg.2
L_0168: brfalse.s L_0170
L_016a: ldarg.1
L_016b: ldc.i4.s 0x42
L_016d: stind.i2
L_016e: br.s L_0174
L_0170: ldarg.1
L_0171: ldc.i4.s 0x62
L_0173: stind.i2
L_0174: ldc.i4.1
L_0175: ret
2) Условный оператор:
L_0165: ldarg.1
L_0166: ldarg.2
L_0167: brtrue.s L_016d
L_0169: ldc.i4.s 0x62
L_016b: br.s L_016f
L_016d: ldc.i4.s 0x42
L_016f: stind.i2
L_0170: ldc.i4.1
L_0171: ret
Некоторые наблюдения:
- Условный оператор ветвится когда
shiftравно true, если if / else разветвляется, когдаshiftложно - Хотя 1) на самом деле компилируется с несколькими инструкциями, а не 2), число команд, выполняемых при
shiftлибо true, либо false, равны для двух. - Порядок команд для 1) таков, что всегда занят только один слот стека, а 2) всегда загружает два.
Означает ли какое-либо из этих наблюдений, что условный оператор будет работать медленнее? Есть ли другие побочные эффекты, которые вступают в игру?
8 ответов
Очень странная, возможно, оптимизация.NET имеет обратный эффект в вашем случае:
Автор разобрал несколько версий троичных выражений и обнаружил, что они идентичны операторам if с одним небольшим отличием. Тернарный оператор иногда создает код, который проверяет противоположное условие, которое вы ожидаете, так как в нем проверяется, что подвыражение ложно, а не проверяет, истинно ли оно. Это переупорядочивает некоторые инструкции и может иногда повышать производительность.
http://dotnetperls.com/ternary
Вы можете рассмотреть ToString для значения перечисления (для не особых случаев):
string keyValue = inKey.ToString();
return shift ? keyValue : keyValue.ToLower();
РЕДАКТИРОВАТЬ:
Я сравнил метод if-else с тернарным оператором и с 1000000 циклами тернарный оператор всегда по крайней мере так же быстр, как метод if-else (иногда на несколько миллисекунд быстрее, что поддерживает текст выше). Я думаю, что вы допустили ошибку в измерении времени, которое потребовалось.
Мне было бы интересно узнать, тестируете ли вы это с помощью Debug или Release build. Если это отладочная сборка, то, скорее всего, разница может быть разницей из-за НЕДОСТАТОКА низкоуровневых оптимизаций, которые компилятор добавляет при использовании режима Release (или вручную отключает режим отладки и включает оптимизации компилятора).
Однако я ожидаю, что с оптимизацией, что троичный оператор будет либо такой же скорости, либо немного быстрее, чем оператор if/else, в то время как поиск в словаре самый медленный. Вот мои результаты: 10 миллионов разминочных итераций и 10 миллионов приуроченных к каждой:
РЕЖИМ ОТЛАДКИ
If/Else: 00:00:00.7211259
Ternary: 00:00:00.7923924
Dictionary: 00:00:02.3319567
РЕЖИМ ВЫПУСКА
If/Else: 00:00:00.5217478
Ternary: 00:00:00.5050474
Dictionary: 00:00:02.7389423
Я думаю, что здесь интересно отметить, что до того, как оптимизация была включена, троичные вычисления были медленнее, чем if/else, а после - быстрее.
РЕДАКТИРОВАТЬ:
После небольшого тестирования в практическом смысле разница между if / else и ternary практически отсутствует. Хотя троичный код приводит к меньшему IL, они работают почти так же, как и другие. В дюжине различных тестов с двоичным файлом режима выпуска результаты if / else и ternary были либо идентичны, либо отклонялись на доли миллисекунды для 10000000 итераций. Иногда, если / иначе было немного быстрее, иногда троичным, но при всей практичности они выполняют то же самое.
Словарь работает значительно хуже, с другой стороны. Когда дело доходит до такого рода оптимизаций, я бы не стал тратить время на выбор между if / else и троичным, если код уже существует. Однако, если у вас в настоящее время есть реализация словаря, я определенно реорганизовал бы ее, чтобы использовать более эффективный подход и улучшить вашу производительность примерно на 400% (во всяком случае, для данной функции).
Интересно, я ушел и разработал небольшой класс IfElseTernaryTest здесь, хорошо, код на самом деле не "оптимизирован" или хороший пример, но тем не менее... ради обсуждения:
public class IfElseTernaryTest
{
private bool bigX;
public void RunIfElse()
{
int x = 4; int y = 5;
if (x > y) bigX = false;
else if (x < y) bigX = true;
}
public void RunTernary()
{
int x = 4; int y = 5;
bigX = (x > y) ? false : ((x < y) ? true : false);
}
}
Это был дамп кода IL... интересная часть состояла в том, что троичные инструкции в IL были на самом деле короче, чем if....
.class /*02000003*/ public auto ansi beforefieldinit ConTern.IfElseTernaryTest
extends [mscorlib/*23000001*/]System.Object/*01000001*/
{
.field /*04000001*/ private bool bigX
.method /*06000003*/ public hidebysig instance void
RunIfElse() cil managed
// SIG: 20 00 01
{
// Method begins at RVA 0x205c
// Code size 44 (0x2c)
.maxstack 2
.locals /*11000001*/ init ([0] int32 x,
[1] int32 y,
[2] bool CS$4$0000)
.line 19,19 : 9,10 ''
//000013: }
//000014:
//000015: public class IfElseTernaryTest
//000016: {
//000017: private bool bigX;
//000018: public void RunIfElse()
//000019: {
IL_0000: /* 00 | */ nop
.line 20,20 : 13,23 ''
//000020: int x = 4; int y = 5;
IL_0001: /* 1A | */ ldc.i4.4
IL_0002: /* 0A | */ stloc.0
.line 20,20 : 24,34 ''
IL_0003: /* 1B | */ ldc.i4.5
IL_0004: /* 0B | */ stloc.1
.line 21,21 : 13,23 ''
//000021: if (x > y) bigX = false;
IL_0005: /* 06 | */ ldloc.0
IL_0006: /* 07 | */ ldloc.1
IL_0007: /* FE02 | */ cgt
IL_0009: /* 16 | */ ldc.i4.0
IL_000a: /* FE01 | */ ceq
IL_000c: /* 0C | */ stloc.2
IL_000d: /* 08 | */ ldloc.2
IL_000e: /* 2D | 09 */ brtrue.s IL_0019
.line 21,21 : 24,37 ''
IL_0010: /* 02 | */ ldarg.0
IL_0011: /* 16 | */ ldc.i4.0
IL_0012: /* 7D | (04)000001 */ stfld bool ConTern.IfElseTernaryTest/*02000003*/::bigX /* 04000001 */
IL_0017: /* 2B | 12 */ br.s IL_002b
.line 22,22 : 18,28 ''
//000022: else if (x < y) bigX = true;
IL_0019: /* 06 | */ ldloc.0
IL_001a: /* 07 | */ ldloc.1
IL_001b: /* FE04 | */ clt
IL_001d: /* 16 | */ ldc.i4.0
IL_001e: /* FE01 | */ ceq
IL_0020: /* 0C | */ stloc.2
IL_0021: /* 08 | */ ldloc.2
IL_0022: /* 2D | 07 */ brtrue.s IL_002b
.line 22,22 : 29,41 ''
IL_0024: /* 02 | */ ldarg.0
IL_0025: /* 17 | */ ldc.i4.1
IL_0026: /* 7D | (04)000001 */ stfld bool ConTern.IfElseTernaryTest/*02000003*/::bigX /* 04000001 */
.line 23,23 : 9,10 ''
//000023: }
IL_002b: /* 2A | */ ret
} // end of method IfElseTernaryTest::RunIfElse
.method /*06000004*/ public hidebysig instance void
RunTernary() cil managed
// SIG: 20 00 01
{
// Method begins at RVA 0x2094
// Code size 27 (0x1b)
.maxstack 3
.locals /*11000002*/ init ([0] int32 x,
[1] int32 y)
.line 25,25 : 9,10 ''
//000024: public void RunTernary()
//000025: {
IL_0000: /* 00 | */ nop
.line 26,26 : 13,23 ''
//000026: int x = 4; int y = 5;
IL_0001: /* 1A | */ ldc.i4.4
IL_0002: /* 0A | */ stloc.0
.line 26,26 : 24,34 ''
IL_0003: /* 1B | */ ldc.i4.5
IL_0004: /* 0B | */ stloc.1
.line 27,27 : 13,63 ''
//000027: bigX = (x > y) ? false : ((x < y) ? true : false);
IL_0005: /* 02 | */ ldarg.0
IL_0006: /* 06 | */ ldloc.0
IL_0007: /* 07 | */ ldloc.1
IL_0008: /* 30 | 0A */ bgt.s IL_0014
IL_000a: /* 06 | */ ldloc.0
IL_000b: /* 07 | */ ldloc.1
IL_000c: /* 32 | 03 */ blt.s IL_0011
IL_000e: /* 16 | */ ldc.i4.0
IL_000f: /* 2B | 01 */ br.s IL_0012
IL_0011: /* 17 | */ ldc.i4.1
IL_0012: /* 2B | 01 */ br.s IL_0015
IL_0014: /* 16 | */ ldc.i4.0
IL_0015: /* 7D | (04)000001 */ stfld bool ConTern.IfElseTernaryTest/*02000003*/::bigX /* 04000001 */
.line 28,28 : 9,10 ''
//000028: }
IL_001a: /* 2A | */ ret
} // end of method IfElseTernaryTest::RunTernary
Таким образом, кажется, что троичный оператор, по-видимому, короче, и я думаю, быстрее, поскольку используется меньше инструкций... но на этом основании, это кажется противоречащим вашему случаю № 2, что удивительно...
Изменить: После комментария Скай, предлагая "раздувание кода для № 2", это опровергнет то, что сказал Скай!!! Хорошо, код другой, контекст другой, это пример упражнения, чтобы проверить дамп IL, чтобы увидеть...
Я ожидаю, что № 1 и № 2 будут одинаковыми. Оптимизатор должен привести к тому же коду. Словарь в #3, как ожидается, будет медленным, если только он не оптимизирован так, чтобы фактически не использовать хеш.
При кодировании систем реального времени мы всегда использовали справочную таблицу - простой массив - для перевода, как показано в вашем примере. Это самый быстрый способ, когда диапазон ввода довольно мал.
Я не совсем понимаю, почему вы ожидаете, что оператор if будет медленнее, чем поиск по словарю. По крайней мере, хэш-код должен быть рассчитан, а затем его нужно искать в списке. Я не понимаю, почему вы предполагаете, что это быстрее, чем cmp/jmp.
В частности, я даже не думаю, что метод, который вы оптимизируете, настолько хорош; кажется, что это можно сделать лучше на этапе вызова (хотя я не уверен, так как вы не предоставили контекст).
Предполагая, что вы беспокоитесь о производительности этого метода (а если нет, зачем его публиковать?), Вам следует рассмотреть возможность сохранения char значения в массиве и преобразование Key значения для индекса в массиве.
У меня нет VS, но наверняка есть простой встроенный способ получить ключ как персонажа? Что-то вроде toString метод, чтобы вы могли заменить это чудовищное switch с этим:
if (shift)
return inKey.toString().toUppercase();
else
return inKey.toString().toLowercase();
Я бы выбрал третий вариант только потому, что он более читабелен / удобен в обслуживании. Могу поспорить, что этот код не является узким местом производительности вашего приложения.