Сейчас в репозитории есть ветка cil_switch в которой ведется работа над реализацией сопоставления с образцом на основе опкода SWITCH.
Предлагаю протестировать производительность match-а ревизии r9137 (более поздние требуют изменения исходников для полного 4-стадийного билда).
Опкод SWITCH генерируется для значений интегральных типов, влезающих в System.Int32 и вариантов, enum-ы пока не поддерживаются (ведем охоту на ведьм).
З.Ы. Другая хорошая новость Nemerle.Compiler.dll проходит тесты PEVerify.
Здравствуйте, hardcase, Вы писали:
H>Предлагаю протестировать производительность match-а ревизии r9137 (более поздние требуют изменения исходников для полного 4-стадийного билда).
Забавно, но в этом тесте с вариантой размером 9 разницы с прежним каскадом условий совершенно никакой нет. Возможно на таких объемах вызов _N_GetVariantCodeSafe / _N_GetVariantCode съедает весь профит.
Здравствуйте, hardcase, Вы писали:
H>>Предлагаю протестировать производительность match-а ревизии r9137 (более поздние требуют изменения исходников для полного 4-стадийного билда).
H>Забавно, но в этом тесте с вариантой размером 9 разницы с прежним каскадом условий совершенно никакой нет. Возможно на таких объемах вызов _N_GetVariantCodeSafe / _N_GetVariantCode съедает весь профит.
Кстати, у меня тут была одна идея... Вместо использования виртуального метода можно в каждый вариант (в базовый тип) добавлять поле типа int (или даже byte) и инициализировать его для каждого своим значением, и проверять потом именно его.
Это немного увеличит объем памяти занимаемый вариантами и потребует лишний инструкции при создании их экземпляров, но возможно это увеличит скорость ПМ.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>Сейчас в репозитории есть ветка cil_switch в которой ведется работа над реализацией сопоставления с образцом на основе опкода SWITCH.
Здравствуйте, hardcase, Вы писали:
H>Здравствуйте, hardcase, Вы писали:
H>>Сейчас в репозитории есть ветка cil_switch в которой ведется работа над реализацией сопоставления с образцом на основе опкода SWITCH.
H>Ветка интегрирована в trunk.
Сужение области применимости этой оптимизации (матч на 12 и более вариантов использует switch, остальные — if-ы) ускорило компиляцию на ~4-5сек (/t:Stage1 /p:Configuration=Release).
Здравствуйте, hardcase, Вы писали:
H>Сужение области применимости этой оптимизации (матч на 12 и более вариантов использует switch, остальные — if-ы) ускорило компиляцию на ~4-5сек (/t:Stage1 /p:Configuration=Release).
Ключик бы добавить типа forceSwitch — чтобы можно было и для небольшого кол-ва вхождений использовать именно Switch.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Ключик бы добавить типа forceSwitch — чтобы можно было и для небольшого кол-ва вхождений использовать именно Switch.
В текущей реализации это бессмысленно. Для матчей меньше 10-15 штук свич только замедляет код.
Здравствуйте, hardcase, Вы писали:
ВВ>>Ключик бы добавить типа forceSwitch — чтобы можно было и для небольшого кол-ва вхождений использовать именно Switch. H>В текущей реализации это бессмысленно. Для матчей меньше 10-15 штук свич только замедляет код.
Почему? Как тестируешь?
Если в Шарпе свитч на 10 элементов прогнать, скажем, миллион раз, то он будет заметно быстрее аналогичной конструкции на ифах, если выбираемое вхождение находится ближе к концу (т.е. чтобы в него попасть, приходится пройти через цепочку проверок).
Кстати, есть ли тесты, на которых текущая реализация Свитча оказывается быстрее Иф-ов?
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Здравствуйте, hardcase, Вы писали:
ВВ>>>Ключик бы добавить типа forceSwitch — чтобы можно было и для небольшого кол-ва вхождений использовать именно Switch. H>>В текущей реализации это бессмысленно. Для матчей меньше 10-15 штук свич только замедляет код.
ВВ>Почему? Как тестируешь? ВВ>Если в Шарпе свитч на 10 элементов прогнать, скажем, миллион раз, то он будет заметно быстрее аналогичной конструкции на ифах, если выбираемое вхождение находится ближе к концу (т.е. чтобы в него попасть, приходится пройти через цепочку проверок).
Я тестирую матчинг на вариантах. Тест, где последовательные isinst рвут свич в текущей реализации я привел во втором посте.
Тестирую компилятором, ибо это интереснее всего.
Целые числа даже не стал тестировать — там тривиально.
ВВ>Кстати, есть ли тесты, на которых текущая реализация Свитча оказывается быстрее Иф-ов?
Более 10-12 вхождений для вариантов, но это эвристика полученная экспериментами с компилятором.
Здравствуйте, hardcase, Вы писали:
H>Я тестирую матчинг на вариантах. Тест, где последовательные isinst рвут свич в текущей реализации я привел во втором посте. H>Тестирую компилятором, ибо это интереснее всего. H>Целые числа даже не стал тестировать — там тривиально.
Однако для целых чисел преимущество свитча может быть видно и на <= 12 элементов, так что ключик бы не помешал.
К тому же преимущество CIL Switch — это не всегда скорость, а зачастую отсуствие завязки на последовательность вхождений — т.е. от "перестановки слагаемых" у нас скорость исполнения не меняется, что иногда важно.
Вообще этот switch нужен для весьма специфических сценариев, зачем там вообще варианты
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Здравствуйте, hardcase, Вы писали:
H>>Я тестирую матчинг на вариантах. Тест, где последовательные isinst рвут свич в текущей реализации я привел во втором посте. H>>Тестирую компилятором, ибо это интереснее всего. H>>Целые числа даже не стал тестировать — там тривиально.
ВВ>Однако для целых чисел преимущество свитча может быть видно и на <= 12 элементов, так что ключик бы не помешал.
А я не говорил что для чисел используется 12 вхождений. Для них порог сейчас 5.
ВВ>К тому же преимущество CIL Switch — это не всегда скорость, а зачастую отсуствие завязки на последовательность вхождений — т.е. от "перестановки слагаемых" у нас скорость исполнения не меняется, что иногда важно.
Я прекрасно понимаю для чего нужен switch — для константного времени выбора действия. Так вот это константное время для матчинга по вариантам оправдывается лишь при достаточно большом их количестве.
Здравствуйте, hardcase, Вы писали:
ВВ>>Однако для целых чисел преимущество свитча может быть видно и на <= 12 элементов, так что ключик бы не помешал. H>А я не говорил что для чисел используется 12 вхождений. Для них порог сейчас 5.
Откуда вообще возникла необходимость в этом порогое? C# без него обходится как-то.
ВВ>>К тому же преимущество CIL Switch — это не всегда скорость, а зачастую отсуствие завязки на последовательность вхождений — т.е. от "перестановки слагаемых" у нас скорость исполнения не меняется, что иногда важно. H>Я прекрасно понимаю для чего нужен switch — для константного времени выбора действия. Так вот это константное время для матчинга по вариантам оправдывается лишь при достаточно большом их количестве.
Где ваши доказательства? Я вполне могу себе представить стейт-машину с 3-4 состояниями, где отсутствие связи между порядков вариантом и скоростью выбора не помешало бы.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Где ваши доказательства? Я вполне могу себе представить стейт-машину с 3-4 состояниями, где отсутствие связи между порядков вариантом и скоростью выбора не помешало бы.
Отлично, я раз за тебя. А теперь взгляни на начальное сообщение топика:
Предлагаю протестировать производительность match-а ревизии r9137 (более поздние требуют изменения исходников для полного 4-стадийного билда).
Если тебе интересная такая машина — организуй тесты, вместе на них посмотрим.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Здравствуйте, hardcase, Вы писали:
ВВ>>>Однако для целых чисел преимущество свитча может быть видно и на <= 12 элементов, так что ключик бы не помешал. H>>А я не говорил что для чисел используется 12 вхождений. Для них порог сейчас 5.
ВВ>Откуда вообще возникла необходимость в этом порогое? C# без него обходится как-то.
Из-за того, что алгоритм построения TExpr.Switch един для вариантов и интегральных типов (compile_switch). Параметр нужно было специфицировать.
Предлагаю протестировать производительность match-а ревизии r9137 (более поздние требуют изменения исходников для полного 4-стадийного билда).
H>Если тебе интересная такая машина — организуй тесты, вместе на них посмотрим.
А что там организовывать? Создай матч на целые из четырех вхождений, всегда выбирается 3-е или 4-е вхождение, код самих вхождений по скорости выполнения аналогичен скорости потенциальных проверок. Ну и завернуть все это, скажем, в цикл на 10 миллионов итераций. Все сразу будет видно.
Здравствуйте, hardcase, Вы писали:
ВВ>>Откуда вообще возникла необходимость в этом порогое? C# без него обходится как-то. H>Из-за того, что алгоритм построения TExpr.Switch един для вариантов и интегральных типов (compile_switch). Параметр нужно было специфицировать.
Ничего не понял. Ты имеешь в виду, что тебе нужно знать размер джамп-таблицы? А причем тут это?
Здравствуйте, hardcase, Вы писали:
H>>>Я прекрасно понимаю для чего нужен switch — для константного времени выбора действия. KK>>Может логарифмического? H>Нет. Константного.
Вообще-то в строгом смысле у свитча не константное время. Константное время означает, что для свитча с любым количеством элементов скорость доступа к конкретному элементу будет одинакова. Это не так.
У свитча доступ к элементу не зависит от порядка элементов. В реальном же коде может оказаться, что выбор варианта через бинарный поиск будет быстрее свитча.
Здравствуйте, hardcase, Вы писали:
H>Сужение области применимости этой оптимизации (матч на 12 и более вариантов использует switch, остальные — if-ы) ускорило компиляцию на ~4-5сек (/t:Stage1 /p:Configuration=Release).
А другие константы пробовал? Скажем 5 или 7?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.