Вопрос по cyclomatic-complexity, c#, switch-statement, dictionary, clr – В словарях switch и vs для значения Func, что быстрее и почему?

41

Предположим, есть следующий код:

private static int DoSwitch(string arg)
{
    switch (arg)
    {
        case "a": return 0;
        case "b": return 1;
        case "c": return 2;
        case "d": return 3;
    }
    return -1;
}

private static Dictionary<string, Func<int>> dict = new Dictionary<string, Func<int>>
    {
        {"a", () => 0 },
        {"b", () => 1 },
        {"c", () => 2 },
        {"d", () => 3 },
    };

private static int DoDictionary(string arg)
{
    return dict[arg]();
}

Перебирая оба метода и сравнивая, я получаю, что словарь работает немного быстрее, даже когда «a», «b», «c», «d» расширен, чтобы включить больше ключей. Почему это так?

Связано ли это с цикломатической сложностью? Это потому, что джиттер компилирует операторы возврата в словаре в нативный код только один раз? Это потому, что поиск в словаре O (1), которыйможет быть не так для оператора switch? (Это только догадки)

Просто интересно, почему ваш словарь & lt; string, Func & lt; int & gt; & gt; вместо просто & lt; string, int & gt ;? DGH
Я хочу сделать это более общим, так какFuncs изменится, но я хотел увидеть значение словаряFunc в самом простом случае. cubetwo1729
Компилятор может на самом деле превратить вашswitch в словарь в какой-то момент, поэтому убедитесь, что вы проверили это с реальным вводом. Brian Rasmussen
При рассмотрении кода IL кажется, что единственные кэшированные анонимные делегаты предназначены для словаря, а не для операторов переключения. cubetwo1729
@ cubetwo1729 Компилятор генерирует код по-разному в зависимости от фактического переключателя / регистра. Brian Rasmussen

Ваш Ответ

4   ответа
36

Это хороший пример того, почему микро-тесты могут вводить в заблуждение. Компилятор C # генерирует разные IL в зависимости от размера переключателя / регистра. Так что переключение на строку, как это

switch (text) 
{
     case "a": Console.WriteLine("A"); break;
     case "b": Console.WriteLine("B"); break;
     case "c": Console.WriteLine("C"); break;
     case "d": Console.WriteLine("D"); break;
     default: Console.WriteLine("def"); break;
}

производить IL, который по существу делает следующее для каждого случая:

L_0009: ldloc.1 
L_000a: ldstr "a"
L_000f: call bool [mscorlib]System.String::op_Equality(string, string)
L_0014: brtrue.s L_003f

и позже

L_003f: ldstr "A"
L_0044: call void [mscorlib]System.Console::WriteLine(string)
L_0049: ret 

То есть это серия сравнений. Так что время выполнения линейно.

Однако добавление дополнительных случаев, например, чтобы включить все буквы из a-z, изменяет сгенерированный IL на что-то вроде этого для каждого:

L_0020: ldstr "a"
L_0025: ldc.i4.0 
L_0026: call instance void [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)

а также

L_0176: ldloc.1 
L_0177: ldloca.s CS$0$0001
L_0179: call instance bool [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::TryGetValue(!0, !1&)
L_017e: brfalse L_0314

и наконец

L_01f6: ldstr "A"
L_01fb: call void [mscorlib]System.Console::WriteLine(string)
L_0200: ret 

То есть теперь он использует словарь вместо последовательности сравнения строк и, таким образом, получает производительность словаря.

Другими словами, код IL, сгенерированный для них, отличается, и это только на уровне IL. JIT-компилятор может оптимизировать дальше.

TL;DRТаким образом, мораль этой истории заключается в том, чтобы смотреть на реальные данные и профиль, а не пытаться оптимизировать их на основе микропроцессоров.

VS2015 + больше этого не делает
1

Как и во многих вопросах, связанных с решениями компилятора кода, ответом будет «это зависит».

Построение вашей собственной хеш-таблицы, вероятно, будет выполняться быстрее, чем код, сгенерированный компилятором, во многих случаях, потому что у компилятора есть другие метрики стоимости, которые он пытается сбалансировать, а вы нет: в первую очередь, потребление памяти.

Хеш-таблица будет использовать больше памяти, чем несколько инструкций IL if-then-else. Если компилятор выкладывает хеш-таблицу для каждого оператора switch в программе, использование памяти будет взрываться.

По мере роста количества блоков case в операторе switch вы, вероятно, увидите, что компилятор создает другой код. Чем больше случаев, тем больше оправдание тому, что компилятор отказывается от небольших и простых шаблонов if-then-else в пользу более быстрых, но более толстых альтернатив.

Я не знаю, если компиляторы C # или JIT выполняют эту конкретную оптимизацию, но общий трюк компилятора для операторов switch, когда селекторов case много и в основном последовательных, заключается в вычислении вектора перехода. Это требует больше памяти (в виде сгенерированных компилятором таблиц переходов, встроенных в поток кода), но выполняется за постоянное время. Вычтите arg - & quot; a & quot ;, используйте результат в качестве индекса в таблице переходов, чтобы перейти к соответствующему блоку падежей. Бум, вы сделали, независимо от того, есть ли 20 или 2000 случаев.

Компилятор с большей вероятностью перейдет в режим таблицы переходов, когда тип селектора переключателя - char, int или enumand Значения селекторов падежей в основном последовательные («плотные»), поскольку эти типы могут быть легко вычтены для создания смещения или индекса. Селекторы строк немного сложнее.

Селекторы строк "интернированы" компилятором C #, то есть компилятор добавляет значения селекторов строк во внутренний пул уникальных строк. В качестве идентификатора можно использовать адрес или токен интернированной строки, что позволяет проводить оптимизацию в стиле int при сравнении внутренних строк для идентификации / байтового равенства. При наличии достаточного количества селекторов C # компилятор создаст код IL, который ищет внутренний эквивалент строки arg (поиск в хэш-таблице), а затем сравнивает (или таблицы переходов) интернированный токен с предварительно вычисленными токенами селектора регистра.

Если вы можете уговорить компилятор на создание кода таблицы переходов в случае селектора char / int / enum, это может выполняться быстрее, чем при использовании вашей собственной хеш-таблицы.

В случае селектора строк IL-код все еще должен выполнять поиск хеша, поэтому любая разница в производительности при использовании вашей собственной хеш-таблицы, вероятно, является стиркой.

В общем, однако, вы не должны слишком подробно останавливаться на этих нюансах компилятора при написании кода приложения. Операторы Switch, как правило, гораздо легче читать и понимать, чем хеш-таблицу указателей на функции. Операторы switch, которые достаточно велики, чтобы перевести компилятор в режим таблицы переходов, часто слишком велики, чтобы их можно было прочитать человеком.

Если вы обнаружите, что оператор switch находится в «горячей точке» вашего кода, и вы с помощью профилировщика оценили, что он оказывает ощутимое влияние на производительность, то изменение кода для использования собственного словаря является разумным компромиссом для повышения производительности.

Написание кода для использования хеш-таблицы с самого начала, без измерения производительности, оправдывающего этот выбор, является чрезмерной разработкой, которая приведет к непостижимому коду с неоправданно высокой стоимостью обслуживания. Будь проще.

44

Короткий ответ: оператор switch выполняется линейно, а словарь - логарифмически.

На уровне IL небольшой оператор switch обычно реализуется как серия операторов if-elseif, сравнивающих равенство переключаемой переменной и каждого случая. Таким образом, этот оператор будет выполняться за время, линейно пропорциональное количеству допустимых опций для myVar; случаи будут сравниваться в порядке их появления, а наихудший сценарий состоит в том, что все сравнения проверяются и либо последнее совпадает, либо ни одно не выполняется. Таким образом, с 32 вариантами наихудший случай состоит в том, что он не является ни одним из них, и код будет выполнять 32 сравнения для определения этого.

Словарь, с другой стороны, использует оптимизированную по индексу коллекцию для хранения значений. В .NET словарь основан на Hashtable, который имеет практически постоянное время доступа (недостатком является крайне низкая эффективность использования пространства). Другие параметры, обычно используемые для «отображения» такие коллекции, как словари, включают сбалансированные древовидные структуры, такие как красно-черные деревья, которые обеспечивают логарифмический доступ (и эффективность линейного пространства). Любой из них позволит коду найти ключ, соответствующий собственному «случаю» в коллекции (или определить, что она не существует) гораздо быстрее, чем оператор switch может сделать то же самое.

EDIT: Другие ответы и комментаторы касались этого, так что в интересах полноты я тоже. Компилятор Microsoft делаетnot всегда компилируйте переключатель в if / elseif, как я предполагал изначально. Обычно это происходит с небольшим количеством случаев и / или с «разреженным» случаи (неинкрементные значения, такие как 1, 200, 4000). При больших наборах смежных случаев компилятор преобразует переключатель в «таблицу переходов». используя оператор CIL. При больших наборах разреженных случаев компилятор может реализовать двоичный поиск, чтобы сузить поле, а затем «провалиться». небольшое количество редких случаев или реализовать таблицу переходов для смежных случаев.

Однако компилятор обычно выбирает реализацию, которая является наилучшим компромиссом производительности и эффективности использования пространства, поэтому он будет использовать таблицу переходов только для большого количества плотно упакованных случаев. Это связано с тем, что для таблицы переходов требуется пространство в памяти в том порядке, в каком она должна охватывать все случаи, что в редких случаях крайне неэффективно с точки зрения памяти. Используя словарь в исходном коде, вы в основном заставляете руку компилятора; он будет делать это по-своему, вместо того, чтобы идти на компромисс с производительностью для повышения эффективности памяти.

Таким образом, я ожидал бы, что в большинстве случаев в источнике можно использовать оператор switch или Dictionary, чтобы он работал лучше при использовании Dictionary. В любом случае следует избегать большого числа случаев в выражениях switch, поскольку они менее ремонтопригодны.

@KeithS: Откуда вы знаете, что словарь .NET использует красно-черное двоичное дерево? cubetwo1729
И заявление переключателяmay быть реализован как таблица переходов, это не обязательно.
Если словарь реализован с помощью хеш-таблицы, то время поиска равно O (1). Это все еще будет относительно медленнее, чем время компиляцииswitch хоть.
Стандартный словарь в .net использует хеш-таблицу.
Словарь .NET фактически использует хеш-таблицу; Я отредактировал соответственно. Java-эквивалент Map реализован тремя различными способами, в том числе с использованием RBT.
1

По умолчанию переключение на строку реализовано как конструкция if / else / if / else. Как предположил Брайан, компилятор преобразует переключатель в хеш-таблицу, когда он становится больше. Барт де Смет показывает этов этом канале9 видео(переключатель обсуждается в 13:50)

Компилятор не делает это для 4 элементов, потому что он консервативный, чтобы не допустить, чтобы затраты на оптимизацию перевесили преимущества. Создание хеш-таблицы требует немного времени и памяти.

Похожие вопросы