Здравствуйте, Воронков Василий, Вы писали:

ВВ>Замедление чего? Времени компляции компилятора? Времени компиляции самим компилятором? Компиляции чего? Самого компилятора?

Времени компиляции компилятором своих исходников. Т.е. если в буте бинарники со свитчами, то компиляция одного и того же кода проходит медленнее.

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Воронков Василий, Вы писали:

ВВ>>На 99% реальных задач разницы во времени видно попросту не будет, что там свитч, что цепочка ифов.

VD>С целыми расклад несколько другой. Там нет проверок на null которые есть при переходе по вариантам имеющим умолчальное вхождение match-а. Там хардкейс выбрал константу — 5. Видимо тесты показали, что так оно эффективнее.

Нет. я взял это число с потолка.

Здравствуйте, Аноним, Вы писали:

А>4 последовательных числа будут также последовательно сравниваться (ок, параметр можно поправить), 5 уже будут в switch превращаться.

Хорошо бы провести отдельный тест с целыми. Потому как в одном я с Воронковым согласен — для негерированных ДКА свитчи могут оказаться предпочтительнее. Причем просто потому, что они более компактно в памяти представлены.

И вообще, константу для целых и вариантов надо разделить (если это еще не сделано).

KK>>Не понимать. Я вижу два варианта с приемлемым потреблением памяти:
KK>>1. Цепочка ифов, т.е. линейный поиск (время O(n))
KK>>2. Бинарный поиск по множеству значений (время O(log n))

А>А я вижу в построении таблицы переходов (грубо и абстрактно):

Это... Это уже слова Воронкова. Ты меня с ним не путай.

А>index — индекс в таблице переходов.
А>br_size — длина инструкции BR с адресом:
А>

А>jump index * br_size //переходим на index * br_size байт вперед, попадая на одну из jump-кейзов
А>jump case0  // переход на код кейза 0
А>jump case1  // переход на код кейза 1 и т.д.
А>jump case2
А>jump case3
А>...
А>

А>З.Ы. могу заблуждаться в своих суждениях.

Думаю, что ты прав.

А>Эта конструкция превратится в цепочку сравнений. Но, если народ настаивает, могу сделать и бинарный поиск.

Это было бы круто, но наверно имеет смысл остановиться пока. А то пределов совершенству нет.

Здравствуйте, Ka3a4oK, Вы писали:

KK>Не понимать. Я вижу два варианта с приемлемым потреблением памяти:
KK>1. Цепочка ифов, т.е. линейный поиск (время O(n))
KK>2. Бинарный поиск по множеству значений (время O(log n))

Тут надо понимать, что простые теоретические рассуждения могут не иметь ничего общего с реальностью, так как они не учитывают куча факторов (многие из которых мы даже представить не можем).

Скажем современные процессоры умеют предсказывать ветвление и осуществлять спекулятивные вычисления. Так найдя цепочку ифов (точнее их паттерн в инструкциях процессора) процессор может тупо распараллеливание их вычисления. Или еще что-то может повлиять (сбросы кэшей и т.п.). Так что единственный реальный критерий истины — это практика.

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Аноним, Вы писали:

А>>4 последовательных числа будут также последовательно сравниваться (ок, параметр можно поправить), 5 уже будут в switch превращаться.

VD>Хорошо бы провести отдельный тест с целыми. Потому как в одном я с Воронковым согласен — для негерированных ДКА свитчи могут оказаться предпочтительнее. Причем просто потому, что они более компактно в памяти представлены.

VD>И вообще, константу для целых и вариантов надо разделить (если это еще не сделано).

Константа для целых задается зесь (DecisionTreeCompiler.n line 422).
Константа для варинат — здесь (DecisionTreeCompiler.n line 367).

А>А я вижу в построении таблицы переходов (грубо и абстрактно):

А>index — индекс в таблице переходов.
А>br_size — длина инструкции BR с адресом:
А>

А>jump index * br_size //переходим на index * br_size байт вперед, попадая на одну из jump-кейзов
А>jump case0  // переход на код кейза 0
А>jump case1  // переход на код кейза 1 и т.д.
А>jump case2
А>jump case3
А>...
А>

А>З.Ы. могу заблуждаться в своих суждениях.

Что собой представляет таблица переходов как структура данных? Как она строится и как в ней производится поиск?

Здравствуйте, Ka3a4oK, Вы писали:

KK>Что собой представляет таблица переходов как структура данных? Как она строится и как в ней производится поиск?

Дык это надо дезасемблированный код смотреть. Мы же MSIL генерируем.

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Ka3a4oK, Вы писали:

KK>>Что собой представляет таблица переходов как структура данных? Как она строится и как в ней производится поиск?

VD>Дык это надо дезасемблированный код смотреть. Мы же MSIL генерируем.

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

Здравствуйте, Ka3a4oK, Вы писали:

KK>Здравствуйте, VladD2, Вы писали:

VD>>Здравствуйте, Ka3a4oK, Вы писали:

KK>>>Что собой представляет таблица переходов как структура данных? Как она строится и как в ней производится поиск?

VD>>Дык это надо дезасемблированный код смотреть. Мы же MSIL генерируем.

KK>Ну тогда скорей всего там бинарный поиск и используется в общем случае. Т.е. говорить о константном времени выбора в худшем случае мы не можем.

Вот это вряд ли. Пройди по ссылке на описание опкода switch в первом сообщении.

Здравствуйте, Ka3a4oK, Вы писали:

VD>>Дык это надо дезасемблированный код смотреть. Мы же MSIL генерируем.

KK>Ну тогда скорей всего там бинарный поиск и используется в общем случае. Т.е. говорить о константном времени выбора в худшем случае мы не можем.

MSIL switch не работает с таблицами имеющими пропуски и генерирует (по видимому) тупой goto по адресу.

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Ka3a4oK, Вы писали:

VD>>>Дык это надо дезасемблированный код смотреть. Мы же MSIL генерируем.

KK>>Ну тогда скорей всего там бинарный поиск и используется в общем случае. Т.е. говорить о константном времени выбора в худшем случае мы не можем.

VD>MSIL switch не работает с таблицами имеющими пропуски и генерирует (по видимому) тупой goto по адресу.

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

Здравствуйте, VladD2, Вы писали:

ВВ>>Тут речь об ограничении на кол-ве элементов в свитче, которое есть и для целых тоже.
VD>Хардкейс же тебе сказал, что для целых ограничение другое.

Мне непонятно, зачем вообще нужно какое-то ограничение на кол-во вхождение в свитче.

ВВ>>Вызывается всегда один и тот же case 3. Выборка идет не по переменной цикла, а по переменной х.
VD>А где гарантия, что код метода не заинлайнен, и что все свитч не выкинут к чертям?

Какой метод? Методы со свитчами не инлайнятся.

Здравствуйте, VladD2, Вы писали:

VD>Проверяй.

Вот тут за меня, оказывается, уже проверили:
http://stackoverflow.com/questions/44905/c-switch-statement-limitations-why#48060

Здравствуйте, Ka3a4oK, Вы писали:

KK>Т.е. я правильно ли понимаю, что данное усовершенствование (применение инстуркции switch для патерн матчинга) будет работать только при патерн-матчинге интегральных типов, при этом множество выбора должно быть "без пропусков"?

Погугли как это сделано в Шарпе. Для строк используется люкап-таблица. Пропуски допустимы, но для свича вида { case 0; case 3; } будет сгенерирована таблица с четырьмя вхождениями, половина из которых — "холостые". Естественно, есть некий максимальный предел для пропусков, после которых джамп-таблица не генерируется, и компилятор переходит на другой алгоритм.

Здравствуйте, Воронков Василий, Вы писали:

ВВ>Здравствуйте, Ka3a4oK, Вы писали:

KK>>Т.е. я правильно ли понимаю, что данное усовершенствование (применение инстуркции switch для патерн матчинга) будет работать только при патерн-матчинге интегральных типов, при этом множество выбора должно быть "без пропусков"?

ВВ>Погугли как это сделано в Шарпе. Для строк используется люкап-таблица. Пропуски допустимы, но для свича вида { case 0; case 3; } будет сгенерирована таблица с четырьмя вхождениями, половина из которых — "холостые". Естественно, есть некий максимальный предел для пропусков, после которых джамп-таблица не генерируется, и компилятор переходит на другой алгоритм.

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

1. небольшие дыры -> таблица с константным временем
2. большие дыры -> бинарный поиск(или может даже хэш-таблица при большом количестве элементов)

Здравствуйте, Ka3a4oK, Вы писали:

KK>1. небольшие дыры -> таблица с константным временем
KK>2. большие дыры -> бинарный поиск(или может даже хэш-таблица при большом количестве элементов)


Что-то я сомневаюсь в том, что C# компилятор производит оптимизацию №2.
На каком количестве разреженных вхождений бинарный поиск будет в среднем быстрее линейного?

Здравствуйте, VladD2, Вы писали:

ВВ>>Замедление чего? Времени компляции компилятора? Времени компиляции самим компилятором? Компиляции чего? Самого компилятора?
VD>Времени компиляции компилятором своих исходников. Т.е. если в буте бинарники со свитчами, то компиляция одного и того же кода проходит медленнее.

Кстати, здесь может играть роль тот фактор, что ДЖИТ не инлайнит методы, в которых есть оп-код Switch. Ну и само собой для небольших кейсов Switch может попортить работу предсказателю. Наконец у вас есть дополнительных cost для свитчей по вариантам — проверка на нуль (ты сам говорил) и вызов виртуального метода, который возвращает код вхождения (?). Для целых эти накладные расходы отсутствуют.

Как обычно я забыл, что в Немерле *все* условные конструции — это матч. И сие, конечно, вносит свои коррективы.
Тут возможно два варианта:

1. Ввести опцию компилятора forceSwitch, при которой джамп-таблица генерируется для любого кол-ва вхождений
2. Добавить специальное ключевое слово, атрибут, whatever с теми же целями.

Чем не нравится вариант с ограничением:

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

Кстати, пропуски при построении свитча по целым учитываются?

Здравствуйте, hardcase, Вы писали:


Для управления оптимизирующего алгоритма в компиляторе появились два дополнительных параметра: -min-switch-size-variants (-Oswv) и -min-switch-size-ordinals (-Oswo).

Также в MSBuild-тасках теперь есть возможность указывать параметры командной строки с помощью тега <CustomArguments>,
например:

<CustomArguments>
-Oswv:15 -Oswo:3
</CustomArguments>

Здравствуйте, Воронков Василий, Вы писали:

ВВ>1. Ввести опцию компилятора forceSwitch, при которой джамп-таблица генерируется для любого кол-ва вхождений
ВВ>2. Добавить специальное ключевое слово, атрибут, whatever с теми же целями.

Я повторюсь, но это несколько бессмысленно для матчинга по вариантам... Ну не дает оно прироста на 10 вхождениях.

ВВ>Чем не нравится вариант с ограничением:

ВВ>Кстати, пропуски при построении свитча по целым учитываются?

Алгоритм закрывает до двух пропусков в матче, как по числам так и по вариантам.

Здравствуйте, hardcase, Вы писали:

H>Алгоритм закрывает до двух пропусков в матче, как по числам так и по вариантам.

Поясню, для матча

match(x)
{
 | 0 =>  ...
 | 3 =>  ...
 | 6 =>  ...
 | 7 =>  ...
 | 8 =>  ...
 | 11 => ...
 | _ =>  ...
}

будет сгенерирован единственный switch.