Ограничения операторов переключения C# – почему?

https://stackoverflow.com/questions/44905

09-06-2019
|

Вопрос

При написании оператора switch существует два ограничения на то, что вы можете включить в операторах case.

Например (и да, я знаю, если вы делаете подобные вещи, это, вероятно, означает, что ваш объектно-ориентированный (ОО) архитектура сомнительна — это всего лишь надуманный пример!),

  Type t = typeof(int);

  switch (t) {

    case typeof(int):
      Console.WriteLine("int!");
      break;

    case typeof(string):
      Console.WriteLine("string!");
      break;

    default:
      Console.WriteLine("unknown!");
      break;
  }

Здесь оператор switch() завершается с ошибкой «Ожидается значение целочисленного типа», а операторы case завершаются с ошибкой «Ожидается постоянное значение».

Почему вводятся эти ограничения и каково их основное обоснование?Я не вижу причин, по которым оператор переключения имеет поддаваться только статическому анализу, и почему включаемое значение должно быть целым (то есть примитивным).Каково оправдание?

Решение

Это мой оригинальный пост, который вызвал некоторые споры... потому что это неправильно:

Оператор Switch-это не то же самое, что большой оператор IF-ELSE.Каждый случай должен быть уникальным и оценивать статически.Оператор Switch выполняет постоянную ветвь времени независимо от того, сколько у вас случаев.Заявление IF-ELSE оценивает каждое условие, пока не найдет тот, который будет истинным.

Фактически, оператор переключения C# нет всегда ветвь постоянного времени.

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

На самом деле это довольно легко проверить, написав различные операторы переключения C#, некоторые разреженные, некоторые плотные, и просмотрев полученный CIL с помощью инструмента ildasm.exe.

Другие советы

Важно не путать оператор переключения C# с инструкцией переключения CIL.

Переключатель CIL представляет собой таблицу переходов, для которой требуется индекс в наборе адресов перехода.

Это полезно только в том случае, если случаи переключателя C# являются соседними:

case 3: blah; break;
case 4: blah; break;
case 5: blah; break;

Но бесполезно, если это не так:

case 10: blah; break;
case 200: blah; break;
case 3000: blah; break;

(Вам понадобится таблица размером около 3000 записей, с использованием только 3 слотов)

При использовании несмежных выражений компилятор может начать выполнять линейные проверки if-else-if-else.

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

Если наборы выражений содержат группы смежных элементов, компилятор может выполнить поиск в двоичном дереве и, наконец, переключить CIL.

Здесь полно «может» и «может быть», и это зависит от компилятора (может отличаться от Mono или Rotor).

Я воспроизвел ваши результаты на своей машине, используя соседние случаи:

общее время выполнения 10-позиционного переключения, 10000 итераций (мс):25.1383
приблизительное время на 10-позиционный переключатель (мс):0,00251383

общее время выполнения 50-позиционного переключения, 10000 итераций (мс):26.593
приблизительное время на 50-позиционный переключатель (мс):0,0026593

общее время выполнения переключения на 5000 направлений, 10000 итераций (мс):23.7094
приблизительное время на 5000 переключателей (мс):0,00237094

общее время выполнения переключения на 50 000 направлений, 10 000 итераций (мс):20.0933
приблизительное время на 50000 переключений (мс):0,00200933

Затем я также использовал выражения несмежного регистра:

общее время выполнения 10-позиционного переключения, 10000 итераций (мс):19,6189
приблизительное время на 10-позиционный переключатель (мс):0,00196189

общее время выполнения 500-позиционного переключения, 10000 итераций (мс):19.1664
приблизительное время на 500-позиционный переключатель (мс):0,00191664

общее время выполнения переключения на 5000 направлений, 10000 итераций (мс):19,5871
приблизительное время на 5000 переключателей (мс):0,00195871

Несмежный оператор переключения регистра 50 000 не будет компилироваться.
«Выражение слишком длинное или сложное для компиляции рядом с «ConsoleApplication1.Program.Main(string[])»

Что забавно, так это то, что поиск в двоичном дереве происходит немного (вероятно, не статистически) быстрее, чем команда переключения CIL.

Брайан, ты использовал слово "постоянный", что имеет очень определенное значение с точки зрения теории сложности вычислений.В то время как упрощенный пример смежного целого числа может давать CIL, который считается O(1) (константа), разреженным примером является O(log n) (логарифмический), примеры с кластерами лежат где-то посередине, а небольшие примеры — O(n) (линейный ).

Это даже не касается ситуации со строкой, в которой статический Generic.Dictionary<string,int32> может быть создан, и при первом использовании он понесет определенные накладные расходы.Производительность здесь будет зависеть от производительности Generic.Dictionary.

Если вы проверите Спецификация языка C# (Не спецификация CIL) Вы найдете «15.7.2 Оператор Switch» не упоминает о «постоянном времени» или о том, что базовая реализация даже использует инструкцию по переключению CIL (будьте очень осторожны с тем, чтобы предположить такие вещи).

В конце концов, переключение C# против целочисленного выражения в современной системе — это операция, занимающая доли микросекунды, и обычно о ней не стоит беспокоиться.

Конечно, это время будет зависеть от машин и условий.Я бы не обращал внимания на эти тесты времени, продолжительность в микросекундах, о которой мы говорим, затмевается любым выполняемым «реальным» кодом (и вы должны включить некоторый «настоящий код», иначе компилятор оптимизирует ветку), или джиттер в системе.Мои ответы основаны на использовании ИЛ-ДАСМ для проверки CIL, созданного компилятором C#.Конечно, это не окончательный вариант, поскольку фактические инструкции, которые выполняет ЦП, затем создаются JIT.

Я проверил окончательные инструкции ЦП, фактически выполняемые на моей машине x86, и могу подтвердить, что простой соседний переключатель set делает что-то вроде:

  jmp     ds:300025F0[eax*4]

Где поиск по двоичному дереву полон:

  cmp     ebx, 79Eh
  jg      3000352B
  cmp     ebx, 654h
  jg      300032BB
  …
  cmp     ebx, 0F82h
  jz      30005EEE

Первая причина, которая приходит на ум, исторический:

Поскольку большинство программистов C, C++ и Java не привыкли к таким свободам, они их не требуют.

Другая, более веская причина заключается в том, что сложность языка увеличится:

Прежде всего, следует ли сравнивать объекты с .Equals() или с == оператор?Оба варианта действительны в некоторых случаях.Должны ли мы ввести для этого новый синтаксис?Должны ли мы позволить программисту ввести свой собственный метод сравнения?

Кроме того, разрешение включения объектов будет сломать основные предположения об операторе переключения.Существует два правила, управляющих оператором переключения, которые компилятор не смог бы обеспечить, если бы объектам было разрешено включение (см. Спецификация языка C# версии 3.0, §8.7.2):

Значения меток переключателей постоянный
Значения меток переключателей отчетливый (чтобы для данного выражения переключателя можно было выбрать только один блок переключателей)

Рассмотрим этот пример кода в гипотетическом случае, когда разрешены непостоянные значения регистра:

void DoIt()
{
    String foo = "bar";
    Switch(foo, foo);
}

void Switch(String val1, String val2)
{
    switch ("bar")
    {
        // The compiler will not know that val1 and val2 are not distinct
        case val1:
            // Is this case block selected?
            break;
        case val2:
            // Or this one?
            break;
        case "bar":
            // Or perhaps this one?
            break;
    }
}

Что будет делать код?Что, если операторы случая будут переупорядочены?Действительно, одна из причин, по которой C# сделал провал переключения незаконным, заключается в том, что операторы переключения могут быть произвольно переставлены.

Эти правила созданы не просто так — для того, чтобы программист, взглянув на один блок case, мог точно узнать точное условие, при котором этот блок вводится.Когда вышеупомянутый оператор переключения вырастет до 100 или более строк (а так и будет), такие знания станут неоценимыми.

Кстати, VB, имея такую же базовую архитектуру, позволяет гораздо более гибко Select Case (приведенный выше код будет работать в VB) и по-прежнему создает эффективный код, где это возможно, поэтому аргумент, связанный с техническими ограничениями, должен быть тщательно рассмотрен.

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

Компилятор может (и делает) по своему выбору:

создать большой оператор if-else
используйте инструкцию переключения MSIL (таблица переходов)
Создайте generic.dictionaryu003Cstring,int32> , заполнить его при первом использовании и назовите generic.dictionary <> :: trygetValue () для индекса для передачи в инструкцию по переключению MSIL (таблица прыжков)
Используйте комбинацию переключателей if-elses & msil "

Оператор переключения НЕ ЯВЛЯЕТСЯ ветвью постоянного времени.Компилятор может найти более короткие пути (с использованием хэш-групп и т. д.), но в более сложных случаях будет генерироваться более сложный код MSIL, причем некоторые случаи разветвляются раньше, чем другие.

Для обработки случая String компилятор (в какой-то момент) будет использовать a.Equals(b) (и, возможно, a.GetHashCode() ).Я думаю, что для компилятора было бы тривиально использовать любой объект, удовлетворяющий этим ограничениям.

Что касается необходимости статических выражений регистра...некоторые из этих оптимизаций (хеширование, кэширование и т. д.) были бы недоступны, если бы выражения case не были детерминированными.Но мы уже видели, что иногда компилятор все равно просто выбирает упрощенный путь «если иначе, если еще»…

Редактировать: Ломакс - Ваше понимание оператора typeof неверно.Оператор typeof используется для получения объекта System.Type для типа (не имеет ничего общего с его супертипами или интерфейсами).Проверка совместимости объекта с заданным типом во время выполнения является задачей оператора is.Использование здесь «typeof» для обозначения объекта не имеет значения.

Говоря по этой теме, по словам Джеффа Этвуда, оператор switch — это злодеяние программирования.Используйте их экономно.

Часто ту же задачу можно выполнить с помощью таблицы.Например:

var table = new Dictionary<Type, string>()
{
   { typeof(int), "it's an int!" }
   { typeof(string), "it's a string!" }
};

Type someType = typeof(int);
Console.WriteLine(table[someType]);

Я не вижу причин, по которым оператор переключения должен поддаваться только статическому анализу.

Правда, это не так. иметь to, и многие языки действительно используют операторы динамического переключения.Однако это означает, что изменение порядка предложений «case» может изменить поведение кода.

Здесь есть интересная информация о дизайнерских решениях, которые вошли в «переключатель»: Почему оператор переключения C# спроектирован таким образом, чтобы не допустить провала, но при этом требует перерыва?

Разрешение динамических выражений регистра может привести к таким чудовищам, как этот PHP-код:

switch (true) {
    case a == 5:
        ...
        break;
    case b == 10:
        ...
        break;
}

который, честно говоря, должен просто использовать if-else заявление.

Microsoft наконец услышала вас!

Теперь с C# 7 вы можете:

switch(shape)
{
case Circle c:
    WriteLine($"circle with radius {c.Radius}");
    break;
case Rectangle s when (s.Length == s.Height):
    WriteLine($"{s.Length} x {s.Height} square");
    break;
case Rectangle r:
    WriteLine($"{r.Length} x {r.Height} rectangle");
    break;
default:
    WriteLine("<unknown shape>");
    break;
case null:
    throw new ArgumentNullException(nameof(shape));
}

Это не причина, но в разделе 8.7.2 спецификации C# говорится следующее:

Управляющий тип оператора переключения устанавливается выражением переключения.Если тип выражения переключателя — sbyte, byte, short, ushort, int, uint, long, ulong, char, string или тип перечисления, то это управляющий тип оператора переключателя.В противном случае должно существовать ровно одно определяемое пользователем неявное преобразование (§6.4) из типа выражения переключателя в один из следующих возможных управляющих типов:сбайт, байт, короткий, ushort, int, uint, длинный, ulong, char, строка.Если такого неявного преобразования не существует или существует более одного такого неявного преобразования, возникает ошибка времени компиляции.

Спецификация C# 3.0 находится по адресу:http://download.microsoft.com/download/3/8/8/388e7205-bc10-4226-b2a8-75351c669b09/CSharp%20Language%20Specification.doc

Ответ Иуды выше дал мне идею.Вы можете «подделать» поведение переключателя OP, описанное выше, используя Dictionary<Type, Func<T>:

Dictionary<Type, Func<object, string,  string>> typeTable = new Dictionary<Type, Func<object, string, string>>();
typeTable.Add(typeof(int), (o, s) =>
                    {
                        return string.Format("{0}: {1}", s, o.ToString());
                    });

Это позволяет связать поведение с типом в том же стиле, что и оператор переключения.Я считаю, что у него есть дополнительное преимущество: при компиляции в IL он использует ключ вместо таблицы переходов в стиле переключателя.

Я полагаю, что нет фундаментальной причины, по которой компилятор не мог бы автоматически преобразовать ваш оператор переключения в:

if (t == typeof(int))
{
...
}
elseif (t == typeof(string))
{
...
}
...

Но особой выгоды от этого не будет.

Оператор Case для целочисленных типов позволяет компилятору выполнить ряд оптимизаций:

Дублирование отсутствует (если только вы не дублируете метки регистра, которые обнаруживает компилятор).В вашем примере t может соответствовать нескольким типам из-за наследования.Должно ли быть выполнено первое совпадение?Все они?
Компилятор может реализовать оператор переключения над целочисленным типом с помощью таблицы переходов, чтобы избежать всех сравнений.Если вы включаете перечисление с целочисленными значениями от 0 до 100, то оно создает массив со 100 указателями, по одному на каждый оператор переключения.Во время выполнения он просто ищет адрес из массива на основе включенного целочисленного значения.Это обеспечивает гораздо лучшую производительность во время выполнения, чем выполнение 100 сравнений.

В соответствии с документация по оператору переключения если существует однозначный способ неявного преобразования объекта к целочисленному типу, то это будет разрешено.Я думаю, вы ожидаете такого поведения, при котором для каждого оператора случая оно будет заменено на if (t == typeof(int)), но это откроет целую банку червей, если вы перегрузите этот оператор.Поведение изменится, если детали реализации оператора переключателя изменятся, если вы неправильно написали переопределение ==.Сокращая сравнения с целочисленными типами и строками, а также с теми вещами, которые можно свести к целочисленным типам (и это предназначено), они избегают потенциальных проблем.

написал:

«Инструкция переключения выполняет ветвь с постоянным временем независимо от того, сколько у вас случаев».

Поскольку язык позволяет нить Тип, который будет использоваться в операторе переключения. Я предполагаю, что компилятор не может сгенерировать код для реализации ветки с постоянным временем для этого типа и ему необходимо сгенерировать стиль if-then.

@mweerden - А, понятно.Спасибо.

У меня нет большого опыта работы с C# и .NET, но кажется, что разработчики языка не разрешают статический доступ к системе типов, за исключением узких случаев.А тип Ключевое слово возвращает объект, поэтому он доступен только во время выполнения.

Я думаю, Хенк справился с задачей «нет статического доступа к системе типов».

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

я согласен с этот комментарий что использование табличного подхода зачастую лучше.

В C# 1.0 это было невозможно, поскольку в нем не было дженериков и анонимных делегатов.В новых версиях C# есть все необходимое, чтобы сделать эту работу.Также полезно иметь обозначение объектных литералов.

У меня практически нет знаний C#, но я подозреваю, что либо переключатель был просто взят, как это происходит в других языках, не задумываясь о том, чтобы сделать его более общим, либо разработчик решил, что расширять его не стоит.

Строго говоря, вы абсолютно правы, что нет никаких оснований налагать на него эти ограничения.Можно предположить, что причина в том, что для разрешенных случаев реализация очень эффективна (как предложил Брайан Энсинк (44921)), но я сомневаюсь, что реализация очень эффективна (по отношению кif-операторы), если я использую целые числа и некоторые случайные случаи (например.345, -4574 и 1234203).И в любом случае, какой вред разрешить его для всего (или, по крайней мере, большего) и сказать, что он эффективен только для определенных случаев (например, для (почти) последовательных чисел).

Однако я могу предположить, что кто-то может захотеть исключить типы по причинам, например, указанным lomaxx (44918).

Редактировать:@Хенк (44970):Если строки являются максимально общими, строки с одинаковым содержимым также будут указателями на одну и ту же ячейку памяти.Затем, если вы можете быть уверены, что строки, используемые в случаях, сохраняются в памяти последовательно, вы можете очень эффективно реализовать переключатель (т.с выполнением в порядке 2 сравнений, сложения и двух прыжков).

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow