Здравствуйте, hardcase, Вы писали:
H>Здравствуйте, Ka3a4oK, Вы писали:
KK>>1. небольшие дыры -> таблица с константным временем KK>>2. большие дыры -> бинарный поиск(или может даже хэш-таблица при большом количестве элементов)
H>Что-то я сомневаюсь в том, что C# компилятор производит оптимизацию №2. H>На каком количестве разреженных вхождений бинарный поиск будет в среднем быстрее линейного?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
var x = 5;
switch (x)
{
case 0: x += 1; break;
case 5: x += 1; break;
case 100: x += 1; break;
case 200: x += 1; break;
case 300: x += 1; break;
case 400: x += 1; break;
case 500: x += 1; break;
case 600: x += 1; break;
case 700: x += 1; break;
case 800: x += 1; break;
case 900: x += 1; break;
case 1000: x += 1; break;
case 1100: x += 1; break;
case 1200: x += 1; break;
case 1300: x += 1; break;
case 1400: x += 1; break;
case 1500: x += 1; break;
case 1600: x += 1; break;
case 1700: x += 1; break;
case 1800: x += 1; break;
case 1900: x += 1; break;
case 2000: x += 1; break;
case 2100: x += 1; break;
case 2200: x += 1; break;
case 2300: x += 1; break;
case 2400: x += 1; break;
case 2500: x += 1; break;
case 2600: x += 1; break;
case 2700: x += 1; break;
case 2800: x += 1; break;
case 2900: x += 1; break;
case 3000: x += 1; break;
case 3100: x += 1; break;
case 3200: x += 1; break;
case 3300: x += 1; break;
case 3400: x += 1; break;
case 3500: x += 1; break;
case 3600: x += 1; break;
case 3700: x += 1; break;
case 3800: x += 1; break;
case 3900: x += 1; break;
case 4000: x += 1; break;
case 4100: x += 1; break;
case 4200: x += 1; break;
case 4300: x += 1; break;
case 4400: x += 1; break;
case 4500: x += 1; break;
case 4600: x += 1; break;
case 4700: x += 1; break;
case 4800: x += 1; break;
case 4900: x += 1; break;
case 5000: x += 1; break;
case 5100: x += 1; break;
case 5200: x += 1; break;
case 5300: x += 1; break;
case 5400: x += 1; break;
case 5500: x += 1; break;
case 5600: x += 1; break;
case 5700: x += 1; break;
case 5800: x += 1; break;
case 5900: x += 1; break;
case 6000: x += 1; break;
case 6100: x += 1; break;
case 6200: x += 1; break;
case 6300: x += 1; break;
case 6400: x += 1; break;
case 6500: x += 1; break;
case 6600: x += 1; break;
case 6700: x += 1; break;
case 6800: x += 1; break;
case 6900: x += 1; break;
case 7000: x += 1; break;
case 7100: x += 1; break;
case 7200: x += 1; break;
case 7300: x += 1; break;
case 7400: x += 1; break;
case 7500: x += 1; break;
case 7600: x += 1; break;
case 7700: x += 1; break;
case 7800: x += 1; break;
case 7900: x += 1; break;
case 8000: x += 1; break;
case 8100: x += 1; break;
case 8200: x += 1; break;
case 8300: x += 1; break;
case 8400: x += 1; break;
case 8500: x += 1; break;
case 8600: x += 1; break;
case 8700: x += 1; break;
case 8800: x += 1; break;
case 8900: x += 1; break;
case 9000: x += 1; break;
case 9100: x += 1; break;
case 9200: x += 1; break;
case 9300: x += 1; break;
case 9400: x += 1; break;
case 9500: x += 1; break;
case 9600: x += 1; break;
case 9700: x += 1; break;
case 9800: x += 1; break;
case 9900: x += 1; break;
case 10000: x += 1; break;
}
}
}
}
Здравствуйте, hardcase, Вы писали:
ВВ>>1. Ввести опцию компилятора forceSwitch, при которой джамп-таблица генерируется для любого кол-ва вхождений ВВ>>2. Добавить специальное ключевое слово, атрибут, whatever с теми же целями. H>Я повторюсь, но это несколько бессмысленно для матчинга по вариантам... Ну не дает оно прироста на 10 вхождениях.
Я про целые.
ВВ>>Чем не нравится вариант с ограничением: ВВ>>Кстати, пропуски при построении свитча по целым учитываются? H>Алгоритм закрывает до двух пропусков в матче, как по числам так и по вариантам.
А почему именно два? Какое кол-во пропускает допускает Шарп?
уже свитча не будет?
Тот же Шарп будет генерировать свитч даже если в первом случае пропуск хоть 1000, может разбить конструкцию на несколько свитчей, использовать комбинацию свитчей, бинарного поиска и пр.
Я к чему — реализация свитча задача весьма ответственная. Особенно в Немерле, весь код на котором — это сплошной матч. Получается, ты делаешь очень серьезное корневое изменение в компиляторе и все ограничения и логику лучше не брать с потолка. В итоге может оказаться, что компилятор сам себя собирает хорошо, а вот люди, скачавшие последнюю версию Немерла, обнаружат, что производительность упала. Свитч — штука специфическая, может помочь, а может и навредить.
В итоге — стоит ли игра свеч? А именно — реализация, при которой компилятор сам решает, когда ему использовать свитч? Свитч — средство оптимизации, так почему бы ему не остаться таковым? ИМХО идеальным вариантом было бы сделать специальный атрибут UseCilSwitch, который можно приставить к матчу — и тогда, и только тогда, компиляция будет происходить в свитч. Это сохранит обратную совместимость, упростит задачу по разработке и Свитч в общем будет тем, чем он на самом деле является — средством оптимизации.
ВВ>уже свитча не будет? ВВ>Тот же Шарп будет генерировать свитч даже если в первом случае пропуск хоть 1000, может разбить конструкцию на несколько свитчей, использовать комбинацию свитчей, бинарного поиска и пр.
Скачай исходники, собери компилятор и посмотри — я верю, ты сможешь.
Тема для того и создавалась.
ncc делает кое что из этого, за исключением двоичного поиска, реализовать который не такая уж и простая задача.
ВВ>В итоге — стоит ли игра свеч? А именно — реализация, при которой компилятор сам решает, когда ему использовать свитч? Свитч — средство оптимизации, так почему бы ему не остаться таковым? ИМХО идеальным вариантом было бы сделать специальный атрибут UseCilSwitch, который можно приставить к матчу — и тогда, и только тогда, компиляция будет происходить в свитч.
ВВ>Это сохранит обратную совместимость,
А она терялась?
ВВ>упростит задачу по разработке
Нисколько не упростит, а даже усложнит.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Здравствуйте, hardcase, Вы писали:
H>>Здравствуйте, Ka3a4oK, Вы писали:
KK>>>1. небольшие дыры -> таблица с константным временем KK>>>2. большие дыры -> бинарный поиск(или может даже хэш-таблица при большом количестве элементов)
H>>Что-то я сомневаюсь в том, что C# компилятор производит оптимизацию №2. H>>На каком количестве разреженных вхождений бинарный поиск будет в среднем быстрее линейного?
Но это при условии, что логика case-ов исключительно тривиальна.
И если данная конструкция действительно будет востребована, реализовать бинарный поиск я смогу, но сейчас этот пример слишком абстрактен.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>В итоге — стоит ли игра свеч? А именно — реализация, при которой компилятор сам решает, когда ему использовать свитч?
Здравствуйте, Воронков Василий, Вы писали:
ВВ>В итоге — стоит ли игра свеч? А именно — реализация, при которой компилятор сам решает, когда ему использовать свитч? Свитч — средство оптимизации, так почему бы ему не остаться таковым?
Являясь средством оптимизации он применяется компилятором только тогда, когда его применение оправдано. Управлять "оправданностью" можно с помощью параметров -Oswv и -Oswo.
H>Но это при условии, что логика case-ов исключительно тривиальна. H>И если данная конструкция действительно будет востребована, реализовать бинарный поиск я смогу, но сейчас этот пример слишком абстрактен.
А в чем проблема реализации при нетривиальной логике? И что является мерой тривиальности?
Здравствуйте, Ka3a4oK, Вы писали:
H>>Но это при условии, что логика case-ов исключительно тривиальна. H>>И если данная конструкция действительно будет востребована, реализовать бинарный поиск я смогу, но сейчас этот пример слишком абстрактен.
KK>А в чем проблема реализации при нетривиальной логике? И что является мерой тривиальности?
Баланс времени выбора и времени исполнения блока.
Если блок складывает два числа, то да, время выбора действия будет превалировать, если же блок вызывает пару-тройку виртуальных функций, то время выбора становится все менее значимым — зачем оптимизировать то, что практически никак не сказывается на производительности?
Здравствуйте, Ka3a4oK, Вы писали:
KK>Т.е. я правильно ли понимаю, что данное усовершенствование (применение инстуркции switch для патерн матчинга) будет работать только при патерн-матчинге интегральных типов, при этом множество выбора должно быть "без пропусков"?
Нет, не правильно. Пропуски возможны, так как хардкейс реализовал забивку небольшого числа пропусков переходами на default-обработчик.
Кроме того switch генерируется и для вариантов. При этом у базового типа (самого варианта) вызывается виртуальный метод возвращающий целочисленный идентификатор. Кроме того делается проверка на null. Именно эти телодвижения приводят к тому, что паттерн-матчинг по вариантам незначительно замедлился. И именно для этого случая хардкейс ввел константу (12) минимального идущего подряд числа значений.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Ka3a4oK, Вы писали:
KK>А в чем проблема реализации при нетривиальной логике? И что является мерой тривиальности?
Проблема реализации — время на ее реализацию и тестирование.
Хардкейс же говорит о том, что овчинка скорее всего не будет стоить выделки. Бинарный поиск не даст сущетвенного выигрыша по сравнению с линейным просто потому, что на небольшом количестве элементов (что является самым частым случаем) разница не будет заметна в микроскоп, а на фоне вычислений внутри самих обработчиков ее вообще заметно не будет.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>Баланс времени выбора и времени исполнения блока. H>Если блок складывает два числа, то да, время выбора действия будет превалировать, если же блок вызывает пару-тройку виртуальных функций, то время выбора становится все менее значимым — зачем оптимизировать то, что практически никак не сказывается на производительности?
К сожалению тут без тестов ничего сказать нельзя. Мое предположение — разница будет не значительна, но может оказаться более значимой на программах с автогенерируемыми матчами (опять же в качестве примера возьмем генераторы ДКА).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Мне непонятно, зачем вообще нужно какое-то ограничение на кол-во вхождение в свитче.
Тебе просто поспорить хочется. Тебе же русским языком сказали. Провели эксперименты которые выявили, что для вариантов данная оптимизация начинает что-то давать только с 12 элементов в свитче.
Какие еще у тебя вопросы тут возникают?
ВВ>>>Вызывается всегда один и тот же case 3. Выборка идет не по переменной цикла, а по переменной х. VD>>А где гарантия, что код метода не заинлайнен, и что все свитч не выкинут к чертям?
ВВ>Какой метод? Методы со свитчами не инлайнятся.
Метод возвращающий константу точно заинлайнится. Далее спокойно можно выкинуть весь свичь. Кроме того тут будет работать предсказание переходов процессора (которое не сработает в случае случайного индекса).
Короче — это очередная синтетика на которую я даже смотреть не хочу. К рассмотрению принимаются только осмысленные алгоритмы или полноценные приложения. А то что синтетика ровным счтетом ничего не показывает я понял еще десять лет тому назад.
Подумай сам. Глупо ведь на основании синтетических тестов вводить оптимизации которые замедляют реальные приложения?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
И? Какого-то невероятного роста затрат я не вижу. Ежу понятно, что чем больше кода, тем дольше он выполняется. Тупое чтение одной ячейки кэша против чтения нескольких ее линеек, а то и переход на чтение памяти. К тому же кода нет, так что вообще не ясно что обсуждается.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
In some cases the compiler will use a CIL switch statement which is indeed a constant time branch using a jump table. However, in sparse cases as pointed out by Ivan Hamilton the compiler may generate something else entirely.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
VD>>Времени компиляции компилятором своих исходников. Т.е. если в буте бинарники со свитчами, то компиляция одного и того же кода проходит медленнее.
ВВ>Кстати, здесь может играть роль тот фактор, что ДЖИТ не инлайнит методы, в которых есть оп-код Switch.
Может. Хотя вроде как начиная с 3.5 это не так.
А может быть еще 1000 причин среди которых работа кэша и т.п. Заниматься серьезным анализом (граничащим с кандидатским дисером по сложности) я не намерен. Если у тебя есть лишнее время, то валяй, разберись и выдай народу точные выкладки. Но не надо делать далеко идущих выводов на основании синтетических тестов.
ВВ>Ну и само собой для небольших кейсов Switch может попортить работу предсказателю.
И это тоже возможно.
ВВ> Наконец у вас есть дополнительных cost для свитчей по вариантам — проверка на нуль (ты сам говорил) и вызов виртуального метода, который возвращает код вхождения (?). Для целых эти накладные расходы отсутствуют.
Совершенно верно. Потому хардкейс и разделил константы для свитча по интам и свтича по вариантам.
ВВ>Как обычно я забыл, что в Немерле *все* условные конструции — это матч. И сие, конечно, вносит свои коррективы.
Ага. Наконец то ты стал понимать, что есть куча разных "но" о которых мы иной раз даже не догадываемся.
ВВ>Тут возможно два варианта:
ВВ>1. Ввести опцию компилятора forceSwitch, при которой джамп-таблица генерируется для любого кол-ва вхождений ВВ>2. Добавить специальное ключевое слово, атрибут, whatever с теми же целями.
Ключевое слово — это уже перебор, на мой взгляд. Вот ввести опцию компилятора позволяющую задать минимальное число подряд идущих индексов для которых генерируется свитч — это можно и не сложно. Даже можно добавить две таких опции. Одну для целых и перечислений, а вторую для вариантов.
ВВ>Чем не нравится вариант с ограничением:
ВВ>Спорить, надеюсь, не будешь, что в ряде случаев использование джамп-таблицы вместо цепочки переходов может очень сильно влиять на производительности?
Буду. "Очень сильно" — это преувеличение. В любом случае это будут проценты. Скорее всего даже не десятки.
Тут еще нужно понимать, что немерл — это не язык для людей типа Дворкина которые пытаются выжать биты из любого байта. Немерл — это высокоуровневый язык обеспечивающий приемлемую производительность для большинства задач (сравнимую с шаропом, но не обязательно равную ему). Люди пишущие на немреле скорее всего предпочтут циклу вызов функции высшего порядка. А это уже оврехэд. Другими словами люди пишущие немреле предпочтут небольшой оверхэд, если при этом код окажется проще и короче.
Отсюда забивать голову тонкими деталями политически не верно. Мы должны обеспечить хорошую производительность в общем. Подобранные тестовым путем константы решают эту задачу.
При это, конечно, наличие опций компилятора позволяющих изменить значения по умолчанию вряд ли кому-то помешают, а значит вполне приемлемы. Но вот введение специальных операторов — это полнейший перебор. Если кому-то там нужна числодробильная производительность, то лучше выбрать С++, или написать на нем критический к времени выполнения код.
ВВ>В итоге получается ситуация — добавил/убрал лишний кейс, и полностью поменялся генерируемый код — а вместе с ним кардинально изменилась и скорость работы. Мне кажется, это не есть гуд.
Не будет никакого координационного изменения. Будет незначительное изменение.
ВВ>Кстати, пропуски при построении свитча по целым учитываются?
Учитываются. До трех, если не ошибаюсь.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>Также в MSBuild-тасках теперь есть возможность указывать параметры командной строки с помощью тега <CustomArguments>, H>например: H>
