Сейчас в репозитории есть ветка 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?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Если в Шарпе свитч на 10 элементов прогнать, скажем, миллион раз, то он будет заметно быстрее аналогичной конструкции на ифах, если выбираемое вхождение находится ближе к концу (т.е. чтобы в него попасть, приходится пройти через цепочку проверок).
Это языком. А ты попробуй на практике. Причем с аналогом вариантов.
ВВ>Кстати, есть ли тесты, на которых текущая реализация Свитча оказывается быстрее Иф-ов?
Тебе же сказали при К > 11.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>Целые числа даже не стал тестировать — там тривиально.
А зря. Для них может оказаться совсем другой расклад. Я думаю для них К > 4 уже может дать выигрыш.
А учитывая то, что именно целые важны для оптимизации разных там ДКА — это становится весьма важным вопросом.
H>Более 10-12 вхождений для вариантов, но это эвристика полученная экспериментами с компилятором.
Опять же на задачах типа генерируемых ДКА — это может быть не так.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>Здравствуйте, Ka3a4oK, Вы писали:
H>>>Я прекрасно понимаю для чего нужен switch — для константного времени выбора действия. KK>>Может логарифмического?
H>Нет. Константного.
Не понимать. Я вижу два варианта с приемлемым потреблением памяти:
1. Цепочка ифов, т.е. линейный поиск (время O(n))
2. Бинарный поиск по множеству значений (время O(log n))
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Воронков Василий, Вы писали: ВВ>>Если в Шарпе свитч на 10 элементов прогнать, скажем, миллион раз, то он будет заметно быстрее аналогичной конструкции на ифах, если выбираемое вхождение находится ближе к концу (т.е. чтобы в него попасть, приходится пройти через цепочку проверок). VD>Это языком.
Язык — это главный инструмент программиста. Особенно РСНД-нера
VD>А ты попробуй на практике. Причем с аналогом вариантов.
Варианты меня мало интересуют в данном вопросе.
Касательно целых — если сравнивать именно Свитч и *цепочку ифов*, то результат будет прекрасно виден и на таком коде:
for (var i = 0; i < ITER; i++)
{
switch (x)
{
case 0: y += 0; break;
case 1: y += 1; break;
case 2: y += 2; break;
case 3: y += 3; break;
case 4: y += 4; break;
}
}
Где ITER равен, скажем, 10*1000*1000.
Если же сравнивать свитч и то, что наколдовал компилятор при трансляции цепочки иф-ов в релизе, то результат может быть какой угодно. Вопрос — что мы сравниваем?
Надо понимать, что любой простенький тест будет слишком искусственным и слишком простым, а следовательно, вариант с иф-ами будет легко поддаваться оптимизации. Тот же Шарп его разгрызет в момент.
А вот если дать компилятору обухом по голове, чтобы он иф-ы не трогал, то результат получается очень даже убедительным:
class Program
{
static void Main(string[] args)
{
var ITER = 1000*1000*1000;
var x = 3;
var y = 0;
x = GetX();
var dt = DateTime.Now;
for (var i = 0; i < ITER; i++)
{
switch (x)
{
case 0: y += 0; break;
case 1: y += 1; break;
case 2: y += 2; break;
case 3: y += 3; break;
case 4: y += 4; break;
}
}
Console.WriteLine("Switch: {0}", DateTime.Now - dt);
y = 0;
x = GetX2();
dt = DateTime.Now;
for (var i = 0; i < ITER; i++)
{
if (x == 0) {
y += 0;
}
else if (x == 1) {
y += 1;
}
else if (x == 2) {
y += 2;
}
else if (x == 3) {
y += 3;
}
else if (x == 4) {
y += 4;
}
}
Console.WriteLine("If: {0}", DateTime.Now - dt);
}
static int GetX() { return 3; }
static int GetX2() { return Int32.Parse("3"); }
}
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Вообще-то в строгом смысле у свитча не константное время. Константное время означает, что для свитча с любым количеством элементов скорость доступа к конкретному элементу будет одинакова. Это не так. ВВ>У свитча доступ к элементу не зависит от порядка элементов. В реальном же коде может оказаться, что выбор варианта через бинарный поиск будет быстрее свитча.
В двух словах — полный бред.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
ВВ>>Вообще-то в строгом смысле у свитча не константное время. Константное время означает, что для свитча с любым количеством элементов скорость доступа к конкретному элементу будет одинакова. Это не так. ВВ>>У свитча доступ к элементу не зависит от порядка элементов. В реальном же коде может оказаться, что выбор варианта через бинарный поиск будет быстрее свитча. VD>В двух словах — полный бред.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>А что там организовывать? Создай матч на целые из четырех вхождений, всегда выбирается 3-е или 4-е вхождение, код самих вхождений по скорости выполнения аналогичен скорости потенциальных проверок. Ну и завернуть все это, скажем, в цикл на 10 миллионов итераций. Все сразу будет видно.
Отличный подход для измерения сфероконей вакуумных.
Вот только они никому не интересны. Интересны реальные задачи. А на реальных задачах применение свитчей всегда дает проигрыш во времени. Причем если в релизе он мелкий, то в дебаге уже более заметный.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Ka3a4oK, Вы писали:
KK>Во что в итоге превратится следующая конструкция?
Свитч — это оп-код такой в МСИЛе. Формирует джамп-таблицу. Джамп-таблицу с таким дырами, как в твоем примере, генерировать никто в здравом уме не будет. Компилятор Шарпа использует и 1) и 2), в зависимости от ситуации. Немерл, как я понимаю, только 1).
Здравствуйте, Воронков Василий, Вы писали:
ВВ>>>Вообще-то в строгом смысле у свитча не константное время. Константное время означает, что для свитча с любым количеством элементов скорость доступа к конкретному элементу будет одинакова. Это не так. ВВ>>>У свитча доступ к элементу не зависит от порядка элементов. В реальном же коде может оказаться, что выбор варианта через бинарный поиск будет быстрее свитча. VD>>В двух словах — полный бред.
ВВ>Ты с чем-то не согласен?
Да. Со всеми твоим словами прорепетированными выше. Время конечно константное. И бинарный поиск никак не может быть быстрее прямой индексации.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Вот только они никому не интересны. Интересны реальные задачи. А на реальных задачах применение свитчей всегда дает проигрыш во времени. Причем если в релизе он мелкий, то в дебаге уже более заметный.
С чего бы это?
На 99% реальных задач разницы во времени видно попросту не будет, что там свитч, что цепочка ифов.
Здравствуйте, VladD2, Вы писали:
VD>Да. Со всеми твоим словами прорепетированными выше. Время конечно константное. И бинарный поиск никак не может быть быстрее прямой индексации.
Фига. Любое измерение скорости в данном случае предполагает, что придется свитч заворачивать в цикл — что в общем и является реальными случаем использования в случае с теми же ДКА, — и тут вылезает интересный момент: чем больше свитч, тем больше времени уходит на загрузку самой джамп-таблицы, что как раз и делает оба моих утверждения верными в реальной жизни.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Язык — это главный инструмент программиста. Особенно РСНД-нера
ВВ>Варианты меня мало интересуют в данном вопросе.
Ну, а что тогда в разговор лезешь? Тут как раз речь в основном о них идет.
ВВ>Касательно целых — если сравнивать именно Свитч и *цепочку ифов*, то результат будет прекрасно виден и на таком коде:
ВВ>
ВВ>for (var i = 0; i < ITER; i++)
ВВ>{
ВВ> switch (x)
ВВ> {
ВВ> case 0: y += 0; break;
ВВ> case 1: y += 1; break;
ВВ> case 2: y += 2; break;
ВВ> case 3: y += 3; break;
ВВ> case 4: y += 4; break;
ВВ> }
ВВ>}
ВВ>
На таком коде вообще ничего хорошего видно не будет. Это даже не сфероконь, а бред сивой кобылы. Пятая итерация и далее всегда будет дуплить в дефолт (которого здесь даже нет).
ВВ>Где ITER равен, скажем, 10*1000*1000.
Да хоть миллиард. Современные процессоры так устроены, что они будут отлично предсказывать переход. И получишь ты производительность тестового случая. А вот в реальных условиях все будет совсем не так.
ВВ>Если же сравнивать свитч и то, что наколдовал компилятор при трансляции цепочки иф-ов в релизе, то результат может быть какой угодно. Вопрос — что мы сравниваем?
Скорость конечного приложения. Это если говорить о нас.
ВВ>Надо понимать, что любой простенький тест будет слишком искусственным и слишком простым, а следовательно, вариант с иф-ами будет легко поддаваться оптимизации. Тот же Шарп его разгрызет в момент.
Мы и понимаем. Потому тестируемся на компиляции компилятора. Где много разного кода.
ВВ>А вот если дать компилятору обухом по голове, чтобы он иф-ы не трогал, то результат получается очень даже убедительным:
ВВ>
ВВ> switch (x)
ВВ> {
ВВ> case 0: y += 0; break;
ВВ> case 1: y += 1; break;
ВВ> case 2: y += 2; break;
ВВ> case 3: y += 3; break;
ВВ> case 4: y += 4; break;
ВВ> }
...
ВВ> if (x == 0) {
ВВ> y += 0;
ВВ> }
ВВ>
Меня тут больше интересуют друге вопросы.
1. Как у тебя этот код вообще (без дефолта) скомпилировался?
2. Что вызывается на пятой и последующих итерациях?
3. Зачем у ифов бессмысленные скобки?
ВВ>Разница на порядок однако.
Меня порядки сфероконей не интересуют даже если они не находятся в вакууме.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
VD>>Да. Со всеми твоим словами прорепетированными выше. Время конечно константное. И бинарный поиск никак не может быть быстрее прямой индексации.
ВВ>Фига. Любое измерение скорости в данном случае предполагает, что придется свитч заворачивать в цикл
Тоже мимо. Можно поступать проще. Есть реальные приложения. Можно измерять их конечную скорость.
В прочем я говорил о твоих словах. Свитч таки имеет константное время (проверка + индексированный доступ). И никакой бинарный поиск не может с ним конкурировать.
ВВ> — что в общем и является реальными случаем использования в случае с теми же ДКА, — и тут вылезает интересный момент: чем больше свитч, тем больше времени уходит на загрузку самой джамп-таблицы, что как раз и делает оба моих утверждения верными в реальной жизни.
Ошибочны твои утверждения. Все таблицы попадают в память еще при компиляции (джитом или нгеном). Таблицы не влезающих в кэши современных процессоров я себе даже представить боюсь.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Ну, а что тогда в разговор лезешь? Тут как раз речь в основном о них идет.
Тут речь об ограничении на кол-ве элементов в свитче, которое есть и для целых тоже.
ВВ>>
ВВ>>for (var i = 0; i < ITER; i++)
ВВ>>{
ВВ>> switch (x)
ВВ>> {
ВВ>> case 0: y += 0; break;
ВВ>> case 1: y += 1; break;
ВВ>> case 2: y += 2; break;
ВВ>> case 3: y += 3; break;
ВВ>> case 4: y += 4; break;
ВВ>> }
ВВ>>}
ВВ>>
VD>На таком коде вообще ничего хорошего видно не будет. Это даже не сфероконь, а бред сивой кобылы. Пятая итерация и далее всегда будет дуплить в дефолт (которого здесь даже нет).
Посмотри код внимательно, свитч идет не по переменной цикла.
ВВ>>Где ITER равен, скажем, 10*1000*1000. VD>Да хоть миллиард. Современные процессоры так устроены, что они будут отлично предсказывать переход. И получишь ты производительность тестового случая. А вот в реальных условиях все будет совсем не так.
Как и в любом тесте
ВВ>>Если же сравнивать свитч и то, что наколдовал компилятор при трансляции цепочки иф-ов в релизе, то результат может быть какой угодно. Вопрос — что мы сравниваем? VD>Скорость конечного приложения. Это если говорить о нас.
Компилятор ваш, если верить Камиллу, плохой пример для тестирования преимущества свитчей — ведь это уже тестировали до вас и преимуществ не выяснили, разве нет?
Опять же — ну получите вы скорость одного конечного приложения — что это скорость будет говорить о скорости других приложений?
ВВ>>Надо понимать, что любой простенький тест будет слишком искусственным и слишком простым, а следовательно, вариант с иф-ами будет легко поддаваться оптимизации. Тот же Шарп его разгрызет в момент.
VD>Мы и понимаем. Потому тестируемся на компиляции компилятора. Где много разного кода.
ВВ>>А вот если дать компилятору обухом по голове, чтобы он иф-ы не трогал, то результат получается очень даже убедительным:
ВВ>>
ВВ>> switch (x)
ВВ>> {
ВВ>> case 0: y += 0; break;
ВВ>> case 1: y += 1; break;
ВВ>> case 2: y += 2; break;
ВВ>> case 3: y += 3; break;
ВВ>> case 4: y += 4; break;
ВВ>> }
VD>...
ВВ>> if (x == 0) {
ВВ>> y += 0;
ВВ>> }
ВВ>>
VD>Меня тут больше интересуют друге вопросы. VD>1. Как у тебя этот код вообще (без дефолта) скомпилировался?
Это С#. Все прекрасно компилируется. В чем проблема?
VD>2. Что вызывается на пятой и последующих итерациях?
Вызывается всегда один и тот же case 3. Выборка идет не по переменной цикла, а по переменной х.
VD>3. Зачем у ифов бессмысленные скобки?
ВВ>>Разница на порядок однако. VD>Меня порядки сфероконей не интересуют даже если они не находятся в вакууме.
Хех, ты даже код внимательно не посмотрел.
Re[4]: CIL switch и сопоставление с образцом
От:
Аноним
Дата:
14.09.10 15:12
Оценка:
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, hardcase, Вы писали:
H>>Сужение области применимости этой оптимизации (матч на 12 и более вариантов использует switch, остальные — if-ы) ускорило компиляцию на ~4-5сек (/t:Stage1 /p:Configuration=Release).
VD>А другие константы пробовал? Скажем 5 или 7?
Нет. Меня больше варианты интересуют. Параметр просто от балды поставил, прикинув количество потенциальных арифметических операций для вычисления перехода.
4 последовательных числа будут также последовательно сравниваться (ок, параметр можно поправить), 5 уже будут в switch превращаться.
H>>Нет. Константного.
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
...
З.Ы. могу заблуждаться в своих суждениях.
KK>Во что в итоге превратится следующая конструкция?
KK>
Здравствуйте, VladD2, Вы писали:
VD>Тоже мимо. Можно поступать проще. Есть реальные приложения. Можно измерять их конечную скорость. VD>В прочем я говорил о твоих словах. Свитч таки имеет константное время (проверка + индексированный доступ). И никакой бинарный поиск не может с ним конкурировать.
Свитч — это время на загрузку джамп-таблицы + индексированный доступ. Второе константно, первое — нет. Сумма их обоих так же неконстантна.
ВВ>> — что в общем и является реальными случаем использования в случае с теми же ДКА, — и тут вылезает интересный момент: чем больше свитч, тем больше времени уходит на загрузку самой джамп-таблицы, что как раз и делает оба моих утверждения верными в реальной жизни. VD>Ошибочны твои утверждения. Все таблицы попадают в память еще при компиляции (джитом или нгеном). Таблицы не влезающих в кэши современных процессоров я себе даже представить боюсь.
Ну тест, проводенный мной года два назад, как раз показал, что при серьезном распухании свитчей время сильно уплывает. Надо проверить еще раз, есть подозрение, что таблица все же загружается на лету.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>На 99% реальных задач разницы во времени видно попросту не будет, что там свитч, что цепочка ифов.
Ну, вот на одной реальной задаче — компиляции вручную написанного компилятора разница есть. Не очень большая, но таки есть. Лобовой вариант — генерация свтича (для вариантов) для трех и более последовательно идущих элементов дает замедление на 5 секунд в релизе (и намного более существенное в дебаге). Оптимизация для 12 последовательно идущих элементов дает 5 секунд выигрыша.
С целыми расклад несколько другой. Там нет проверок на null которые есть при переходе по вариантам имеющим умолчальное вхождение match-а. Там хардкейс выбрал константу — 5. Видимо тесты показали, что так оно эффективнее.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Воронков Василий, Вы писали: ВВ>>На 99% реальных задач разницы во времени видно попросту не будет, что там свитч, что цепочка ифов. VD>Ну, вот на одной реальной задаче — компиляции вручную написанного компилятора разница есть. Не очень большая, но таки есть. Лобовой вариант — генерация свтича (для вариантов) для трех и более последовательно идущих элементов дает замедление на 5 секунд в релизе (и намного более существенное в дебаге). Оптимизация для 12 последовательно идущих элементов дает 5 секунд выигрыша.
Замедление чего? Времени компляции компилятора? Времени компиляции самим компилятором? Компиляции чего? Самого компилятора?
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Свитч — это время на загрузку джамп-таблицы + индексированный доступ. Второе константно, первое — нет. Сумма их обоих так же неконстантна.
Похоже у тебя давно не было плодотворных дискуссий (тобишь — флэймов). Только вот мне в них влезать не охота. Так что последний раз отвечаю. Не понял, твои проблемы.
1. Никакой загрузки во время выполнения быть не должно. Таблицы должны формироваться и помещаться в память при джитае или нгене.
2. Даже если такое есть, то время все равно будет константным, так как под константностью времени понимают одинаковое время на поиск любого элемента присутствующего в таблице. Учитывая что таблицу нужно (или не нужно) грузить каждый раз, время по любому будет одинаковым.
Для поиска элемента не входящего в таблицу скорость окнечно же будет другой, но она так же будет сегда одинаковой.
Изменения значения константы от размеров таблицы или других условий не влияет на константность доступа.
Константность доступа не тоже самое что одинакова или высокая скорость. Например, алгоритм парсинга Паркат обеспечивает константное время парсинга. Но при этом размер константы завист от количества правил и является для реальных грамматик неприемлемо большой. Это может показаться смешным, но замена константного Пакрата на экспоненциальный (в некоторых случаях) простой рекурсивный спуск увеличивает скорость разбора реальных грамматик во много раз.
Так что константный != быстрый. Мы же хотим иметь более высокую скорость работы обычных приложений.
ВВ>Ну тест, проводенный мной года два назад, как раз показал, что при серьезном распухании свитчей время сильно уплывает. Надо проверить еще раз, есть подозрение, что таблица все же загружается на лету.
Проверяй.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Тут речь об ограничении на кол-ве элементов в свитче, которое есть и для целых тоже.
Хардкейс же тебе сказал, что для целых ограничение другое.
ВВ>Посмотри код внимательно, свитч идет не по переменной цикла.
ОК, но оно константное. Тогда он вообще может быть заинлайнен с полным устранением свитча.
ВВ>Как и в любом тесте
Потому их нужно в треш отправить. А тесты проводить на реальных приложениях.
ВВ>Компилятор ваш, если верить Камиллу, плохой пример для тестирования преимущества свитчей — ведь это уже тестировали до вас и преимуществ не выяснили, разве нет?
Дык если есть замедление, то дальше уже идти не куда. Нужна не максимальная производительность для случая конкретного сфероконя, а общая высокая производительность среднего приложения. В компиляторе кода много. Так что если он замедляется от некоторых показателей констант, то эти константы имеет смысл менять.
ВВ>Опять же — ну получите вы скорость одного конечного приложения — что это скорость будет говорить о скорости других приложений?
Извини, но спорить ради спора у меня желания нет. Думаю, что мою позицию ты понял. Доказывать тебе что-то я не имеют никакого желания. Будешь делать свой компилятор, поступай как считаешь нужным.
VD>>Меня тут больше интересуют друге вопросы. VD>>1. Как у тебя этот код вообще (без дефолта) скомпилировался?
ВВ>Это С#. Все прекрасно компилируется. В чем проблема?
Мне казалось, что шарп не позволяет без дефолта свитчи делать. Мдя, очередное разочарование.
VD>>2. Что вызывается на пятой и последующих итерациях?
ВВ>Вызывается всегда один и тот же case 3. Выборка идет не по переменной цикла, а по переменной х.
А где гарантия, что код метода не заинлайнен, и что все свитч не выкинут к чертям?
ВВ>Хех, ты даже код внимательно не посмотрел.
Я вообще не люблю смотреть на сфероконей.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Замедление чего? Времени компляции компилятора? Времени компиляции самим компилятором? Компиляции чего? Самого компилятора?
Времени компиляции компилятором своих исходников. Т.е. если в буте бинарники со свитчами, то компиляция одного и того же кода проходит медленнее.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[15]: CIL switch и сопоставление с образцом
От:
Аноним
Дата:
14.09.10 15:42
Оценка:
Здравствуйте, 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
А>...
А>
А>З.Ы. могу заблуждаться в своих суждениях.
Что собой представляет таблица переходов как структура данных? Как она строится и как в ней производится поиск?
Здравствуйте, 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>А где гарантия, что код метода не заинлайнен, и что все свитч не выкинут к чертям?
Здравствуйте, 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 с теми же целями.
Чем не нравится вариант с ограничением:
Спорить, надеюсь, не будешь, что в ряде случаев использование джамп-таблицы вместо цепочки переходов может очень сильно влиять на производительности? В итоге получается ситуация — добавил/убрал лишний кейс, и полностью поменялся генерируемый код — а вместе с ним кардинально изменилась и скорость работы. Мне кажется, это не есть гуд.
Кстати, пропуски при построении свитча по целым учитываются?
Для управления оптимизирующего алгоритма в компиляторе появились два дополнительных параметра: -min-switch-size-variants (-Oswv) и -min-switch-size-ordinals (-Oswo).
Также в MSBuild-тасках теперь есть возможность указывать параметры командной строки с помощью тега <CustomArguments>,
например:
Здравствуйте, Воронков Василий, Вы писали:
ВВ>1. Ввести опцию компилятора forceSwitch, при которой джамп-таблица генерируется для любого кол-ва вхождений ВВ>2. Добавить специальное ключевое слово, атрибут, whatever с теми же целями.
Я повторюсь, но это несколько бессмысленно для матчинга по вариантам... Ну не дает оно прироста на 10 вхождениях.
ВВ>Чем не нравится вариант с ограничением:
ВВ>Кстати, пропуски при построении свитча по целым учитываются?
Алгоритм закрывает до двух пропусков в матче, как по числам так и по вариантам.
Здравствуйте, 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>
Здравствуйте, Воронков Василий, Вы писали:
H>>Что-то я сомневаюсь в том, что C# компилятор производит оптимизацию №2. H>>На каком количестве разреженных вхождений бинарный поиск будет в среднем быстрее линейного?
ВВ>
ВВ> switch (x)
ВВ> {
ВВ> case 0: x += 1; break;
ВВ> case 5: x += 1; break;
ВВ> case 100: x += 1; break;
ВВ> case 200: x += 1; break;
...
ВВ>
А можно объяснить как приведенный код отвечает на поставленный вопрос?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Подумай сам. Глупо ведь на основании синтетических тестов вводить оптимизации которые замедляют реальные приложения?
А какой прирост (в процентах) скорости работы реального приложения в виде компилятора дала реализация Switch?
Здравствуйте, Воронков Василий, Вы писали:
ВВ>А какой прирост (в процентах) скорости работы реального приложения в виде компилятора дала реализация Switch?
В релизе при константе 12 ~ +5 секунд на двух минутах. При константе 3 ~ -5 секунд.
Короче незначительный.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Здравствуйте, VladD2, Вы писали:
VD>>Подумай сам. Глупо ведь на основании синтетических тестов вводить оптимизации которые замедляют реальные приложения?
ВВ>А какой прирост (в процентах) скорости работы реального приложения в виде компилятора дала реализация Switch?
В процентах не считал. Но разница в несколько секунд сборки самого себя.
Здравствуйте, VladD2, Вы писали:
VD>Кстати, у меня тут была одна идея... Вместо использования виртуального метода можно в каждый вариант (в базовый тип) добавлять поле типа int (или даже byte) и инициализировать его для каждого своим значением, и проверять потом именно его.
VD>Это немного увеличит объем памяти занимаемый вариантами и потребует лишний инструкции при создании их экземпляров, но возможно это увеличит скорость ПМ.
Попробовал — стало медленнее (заменил виртуальный вызов обращением к полю _N_VariantCode).
Патч можно забрать тут.
Здравствуйте, hardcase, Вы писали:
H>Попробовал — стало медленнее (заменил виртуальный вызов обращением к полю _N_VariantCode). H>Патч можно забрать тут.
То есть увеличение потребления памяти на один вариант влияет на производительность сильнее устранения виртуального вызова на один match?
Это хороший урок... значит есть смысл оптимизировать в компиляторе использование памяти.
Здравствуйте, catbert, Вы писали:
C>Здравствуйте, hardcase, Вы писали:
H>>Попробовал — стало медленнее (заменил виртуальный вызов обращением к полю _N_VariantCode). H>>Патч можно забрать тут.
C>То есть увеличение потребления памяти на один вариант влияет на производительность сильнее устранения виртуального вызова на один match? C>Это хороший урок... значит есть смысл оптимизировать в компиляторе использование памяти.
Здравствуйте, hardcase, Вы писали:
H>Ну, я не исключаю что у меня просто руки кривые.
Ну, вроде бы в патче ляпов не видно... единственное, может быть прокол в самом тестировании... ты одинаковые версии кода компилировал для измерения производительности?
Здравствуйте, catbert, Вы писали:
C>То есть увеличение потребления памяти на один вариант влияет на производительность сильнее устранения виртуального вызова на один match? C>Это хороший урок... значит есть смысл оптимизировать в компиляторе использование памяти.
Это ничего не значит. Там факторов выше крыши.
Скажем там есть статический вызов который тоже нужно устранить. Без него рассклд может быть совсем другим.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
