CIL switch и сопоставление с образцом
От: hardcase Пират http://nemerle.org
Дата: 12.09.10 18:05
Оценка: 224 (8)
Сейчас в репозитории есть ветка cil_switch в которой ведется работа над реализацией сопоставления с образцом на основе опкода SWITCH.
Предлагаю протестировать производительность match-а ревизии r9137 (более поздние требуют изменения исходников для полного 4-стадийного билда).
Опкод SWITCH генерируется для значений интегральных типов, влезающих в System.Int32 и вариантов, enum-ы пока не поддерживаются (ведем охоту на ведьм).

З.Ы. Другая хорошая новость Nemerle.Compiler.dll проходит тесты PEVerify.
/* иЗвиНите зА неРовнЫй поЧерК */
Re: CIL switch и сопоставление с образцом
От: hardcase Пират http://nemerle.org
Дата: 13.09.10 15:05
Оценка:
Здравствуйте, hardcase, Вы писали:

H>Предлагаю протестировать производительность match-а ревизии r9137 (более поздние требуют изменения исходников для полного 4-стадийного билда).


Забавно, но в этом тесте с вариантой размером 9 разницы с прежним каскадом условий совершенно никакой нет. Возможно на таких объемах вызов _N_GetVariantCodeSafe / _N_GetVariantCode съедает весь профит.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[2]: CIL switch и сопоставление с образцом
От: VladD2 Российская Империя www.nemerle.org
Дата: 13.09.10 15:35
Оценка:
Здравствуйте, hardcase, Вы писали:

H>>Предлагаю протестировать производительность match-а ревизии r9137 (более поздние требуют изменения исходников для полного 4-стадийного билда).


H>Забавно, но в этом тесте с вариантой размером 9 разницы с прежним каскадом условий совершенно никакой нет. Возможно на таких объемах вызов _N_GetVariantCodeSafe / _N_GetVariantCode съедает весь профит.


Кстати, у меня тут была одна идея... Вместо использования виртуального метода можно в каждый вариант (в базовый тип) добавлять поле типа int (или даже byte) и инициализировать его для каждого своим значением, и проверять потом именно его.

Это немного увеличит объем памяти занимаемый вариантами и потребует лишний инструкции при создании их экземпляров, но возможно это увеличит скорость ПМ.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: CIL switch и сопоставление с образцом
От: hardcase Пират http://nemerle.org
Дата: 14.09.10 05:58
Оценка:
Здравствуйте, hardcase, Вы писали:

H>Сейчас в репозитории есть ветка cil_switch в которой ведется работа над реализацией сопоставления с образцом на основе опкода SWITCH.


Ветка интегрирована в trunk.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[2]: CIL switch и сопоставление с образцом
От: hardcase Пират http://nemerle.org
Дата: 14.09.10 10:36
Оценка:
Здравствуйте, hardcase, Вы писали:

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


H>>Сейчас в репозитории есть ветка cil_switch в которой ведется работа над реализацией сопоставления с образцом на основе опкода SWITCH.


H>Ветка интегрирована в trunk.


Сужение области применимости этой оптимизации (матч на 12 и более вариантов использует switch, остальные — if-ы) ускорило компиляцию на ~4-5сек (/t:Stage1 /p:Configuration=Release).
/* иЗвиНите зА неРовнЫй поЧерК */
Re[3]: CIL switch и сопоставление с образцом
От: Воронков Василий Россия  
Дата: 14.09.10 11:09
Оценка:
Здравствуйте, hardcase, Вы писали:

H>Сужение области применимости этой оптимизации (матч на 12 и более вариантов использует switch, остальные — if-ы) ускорило компиляцию на ~4-5сек (/t:Stage1 /p:Configuration=Release).


Ключик бы добавить типа forceSwitch — чтобы можно было и для небольшого кол-ва вхождений использовать именно Switch.
Re[4]: CIL switch и сопоставление с образцом
От: hardcase Пират http://nemerle.org
Дата: 14.09.10 11:21
Оценка:
Здравствуйте, Воронков Василий, Вы писали:

ВВ>Ключик бы добавить типа forceSwitch — чтобы можно было и для небольшого кол-ва вхождений использовать именно Switch.


В текущей реализации это бессмысленно. Для матчей меньше 10-15 штук свич только замедляет код.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[5]: CIL switch и сопоставление с образцом
От: Воронков Василий Россия  
Дата: 14.09.10 13:27
Оценка:
Здравствуйте, hardcase, Вы писали:

ВВ>>Ключик бы добавить типа forceSwitch — чтобы можно было и для небольшого кол-ва вхождений использовать именно Switch.

H>В текущей реализации это бессмысленно. Для матчей меньше 10-15 штук свич только замедляет код.

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

Кстати, есть ли тесты, на которых текущая реализация Свитча оказывается быстрее Иф-ов?
Re[6]: CIL switch и сопоставление с образцом
От: hardcase Пират http://nemerle.org
Дата: 14.09.10 13:42
Оценка:
Здравствуйте, Воронков Василий, Вы писали:

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


ВВ>>>Ключик бы добавить типа forceSwitch — чтобы можно было и для небольшого кол-ва вхождений использовать именно Switch.

H>>В текущей реализации это бессмысленно. Для матчей меньше 10-15 штук свич только замедляет код.

ВВ>Почему? Как тестируешь?

ВВ>Если в Шарпе свитч на 10 элементов прогнать, скажем, миллион раз, то он будет заметно быстрее аналогичной конструкции на ифах, если выбираемое вхождение находится ближе к концу (т.е. чтобы в него попасть, приходится пройти через цепочку проверок).

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

Целые числа даже не стал тестировать — там тривиально.

ВВ>Кстати, есть ли тесты, на которых текущая реализация Свитча оказывается быстрее Иф-ов?


Более 10-12 вхождений для вариантов, но это эвристика полученная экспериментами с компилятором.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[7]: CIL switch и сопоставление с образцом
От: Воронков Василий Россия  
Дата: 14.09.10 13:50
Оценка:
Здравствуйте, hardcase, Вы писали:

H>Я тестирую матчинг на вариантах. Тест, где последовательные isinst рвут свич в текущей реализации я привел во втором посте.

H>Тестирую компилятором, ибо это интереснее всего.
H>Целые числа даже не стал тестировать — там тривиально.

Однако для целых чисел преимущество свитча может быть видно и на <= 12 элементов, так что ключик бы не помешал.
К тому же преимущество CIL Switch — это не всегда скорость, а зачастую отсуствие завязки на последовательность вхождений — т.е. от "перестановки слагаемых" у нас скорость исполнения не меняется, что иногда важно.

Вообще этот switch нужен для весьма специфических сценариев, зачем там вообще варианты
Re[8]: CIL switch и сопоставление с образцом
От: hardcase Пират http://nemerle.org
Дата: 14.09.10 13:52
Оценка: +1
Здравствуйте, Воронков Василий, Вы писали:

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


H>>Я тестирую матчинг на вариантах. Тест, где последовательные isinst рвут свич в текущей реализации я привел во втором посте.

H>>Тестирую компилятором, ибо это интереснее всего.
H>>Целые числа даже не стал тестировать — там тривиально.

ВВ>Однако для целых чисел преимущество свитча может быть видно и на <= 12 элементов, так что ключик бы не помешал.


А я не говорил что для чисел используется 12 вхождений. Для них порог сейчас 5.

ВВ>К тому же преимущество CIL Switch — это не всегда скорость, а зачастую отсуствие завязки на последовательность вхождений — т.е. от "перестановки слагаемых" у нас скорость исполнения не меняется, что иногда важно.


Я прекрасно понимаю для чего нужен switch — для константного времени выбора действия. Так вот это константное время для матчинга по вариантам оправдывается лишь при достаточно большом их количестве.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[9]: CIL switch и сопоставление с образцом
От: Ka3a4oK  
Дата: 14.09.10 13:59
Оценка:
H>Я прекрасно понимаю для чего нужен switch — для константного времени выбора действия.
Может логарифмического?
Re[9]: CIL switch и сопоставление с образцом
От: Воронков Василий Россия  
Дата: 14.09.10 14:00
Оценка:
Здравствуйте, hardcase, Вы писали:

ВВ>>Однако для целых чисел преимущество свитча может быть видно и на <= 12 элементов, так что ключик бы не помешал.

H>А я не говорил что для чисел используется 12 вхождений. Для них порог сейчас 5.

Откуда вообще возникла необходимость в этом порогое? C# без него обходится как-то.

ВВ>>К тому же преимущество CIL Switch — это не всегда скорость, а зачастую отсуствие завязки на последовательность вхождений — т.е. от "перестановки слагаемых" у нас скорость исполнения не меняется, что иногда важно.

H>Я прекрасно понимаю для чего нужен switch — для константного времени выбора действия. Так вот это константное время для матчинга по вариантам оправдывается лишь при достаточно большом их количестве.

Где ваши доказательства? Я вполне могу себе представить стейт-машину с 3-4 состояниями, где отсутствие связи между порядков вариантом и скоростью выбора не помешало бы.
Re[10]: CIL switch и сопоставление с образцом
От: hardcase Пират http://nemerle.org
Дата: 14.09.10 14:00
Оценка:
Здравствуйте, Ka3a4oK, Вы писали:

H>>Я прекрасно понимаю для чего нужен switch — для константного времени выбора действия.

KK>Может логарифмического?

Нет. Константного.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[10]: CIL switch и сопоставление с образцом
От: hardcase Пират http://nemerle.org
Дата: 14.09.10 14:03
Оценка:
Здравствуйте, Воронков Василий, Вы писали:

ВВ>Где ваши доказательства? Я вполне могу себе представить стейт-машину с 3-4 состояниями, где отсутствие связи между порядков вариантом и скоростью выбора не помешало бы.


Отлично, я раз за тебя. А теперь взгляни на начальное сообщение топика:

Предлагаю протестировать производительность match-а ревизии r9137 (более поздние требуют изменения исходников для полного 4-стадийного билда).


Если тебе интересная такая машина — организуй тесты, вместе на них посмотрим.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[10]: CIL switch и сопоставление с образцом
От: hardcase Пират http://nemerle.org
Дата: 14.09.10 14:06
Оценка:
Здравствуйте, Воронков Василий, Вы писали:

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


ВВ>>>Однако для целых чисел преимущество свитча может быть видно и на <= 12 элементов, так что ключик бы не помешал.

H>>А я не говорил что для чисел используется 12 вхождений. Для них порог сейчас 5.

ВВ>Откуда вообще возникла необходимость в этом порогое? C# без него обходится как-то.


Из-за того, что алгоритм построения TExpr.Switch един для вариантов и интегральных типов (compile_switch). Параметр нужно было специфицировать.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[11]: CIL switch и сопоставление с образцом
От: Воронков Василий Россия  
Дата: 14.09.10 14:19
Оценка:
Здравствуйте, hardcase, Вы писали:

H>

Предлагаю протестировать производительность match-а ревизии r9137 (более поздние требуют изменения исходников для полного 4-стадийного билда).

H>Если тебе интересная такая машина — организуй тесты, вместе на них посмотрим.

А что там организовывать? Создай матч на целые из четырех вхождений, всегда выбирается 3-е или 4-е вхождение, код самих вхождений по скорости выполнения аналогичен скорости потенциальных проверок. Ну и завернуть все это, скажем, в цикл на 10 миллионов итераций. Все сразу будет видно.
Re[11]: CIL switch и сопоставление с образцом
От: Воронков Василий Россия  
Дата: 14.09.10 14:20
Оценка:
Здравствуйте, hardcase, Вы писали:

ВВ>>Откуда вообще возникла необходимость в этом порогое? C# без него обходится как-то.

H>Из-за того, что алгоритм построения TExpr.Switch един для вариантов и интегральных типов (compile_switch). Параметр нужно было специфицировать.

Ничего не понял. Ты имеешь в виду, что тебе нужно знать размер джамп-таблицы? А причем тут это?
Re[11]: CIL switch и сопоставление с образцом
От: Воронков Василий Россия  
Дата: 14.09.10 14:28
Оценка:
Здравствуйте, hardcase, Вы писали:

H>>>Я прекрасно понимаю для чего нужен switch — для константного времени выбора действия.

KK>>Может логарифмического?
H>Нет. Константного.

Вообще-то в строгом смысле у свитча не константное время. Константное время означает, что для свитча с любым количеством элементов скорость доступа к конкретному элементу будет одинакова. Это не так.
У свитча доступ к элементу не зависит от порядка элементов. В реальном же коде может оказаться, что выбор варианта через бинарный поиск будет быстрее свитча.
Re[3]: CIL switch и сопоставление с образцом
От: VladD2 Российская Империя www.nemerle.org
Дата: 14.09.10 14:28
Оценка:
Здравствуйте, hardcase, Вы писали:

H>Сужение области применимости этой оптимизации (матч на 12 и более вариантов использует switch, остальные — if-ы) ускорило компиляцию на ~4-5сек (/t:Stage1 /p:Configuration=Release).


А другие константы пробовал? Скажем 5 или 7?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.