CIL switch и сопоставление с образцом - Nemerle

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

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

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

H>Нет. Константного.

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

Во что в итоге превратится следующая конструкция?

match(x)
{
|1 =>...
|5 =>...
|20 =>...
|500 =>...
|3000 =>...
|16365 =>...
}

Здравствуйте, 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"); }
}

В релизе выдает:

Switch: 00:00:00.4687710
If: 00:00:04.1564968

Разница на порядок однако.

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

ВВ>Вообще-то в строгом смысле у свитча не константное время. Константное время означает, что для свитча с любым количеством элементов скорость доступа к конкретному элементу будет одинакова. Это не так.
ВВ>У свитча доступ к элементу не зависит от порядка элементов. В реальном же коде может оказаться, что выбор варианта через бинарный поиск будет быстрее свитча.

В двух словах — полный бред.

Здравствуйте, 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;
ВВ>            }
ВВ>

ВВ>В релизе выдает:

ВВ>

ВВ>Switch: 00:00:00.4687710
ВВ>If: 00:00:04.1564968
ВВ>

Меня тут больше интересуют друге вопросы.
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;
ВВ>>            }
ВВ>>

ВВ>>В релизе выдает:

ВВ>>

ВВ>>Switch: 00:00:00.4687710
ВВ>>If: 00:00:04.1564968
ВВ>>

VD>Меня тут больше интересуют друге вопросы.
VD>1. Как у тебя этот код вообще (без дефолта) скомпилировался?

Это С#. Все прекрасно компилируется. В чем проблема?

VD>2. Что вызывается на пятой и последующих итерациях?

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

VD>3. Зачем у ифов бессмысленные скобки?

ВВ>>Разница на порядок однако.
VD>Меня порядки сфероконей не интересуют даже если они не находятся в вакууме.

Хех, ты даже код внимательно не посмотрел.

Здравствуйте, 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>

KK>match(x)
KK>{
KK>|1 =>...
KK>|5 =>...
KK>|20 =>...
KK>|500 =>...
KK>|3000 =>...
KK>|16365 =>...
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. Выборка идет не по переменной цикла, а по переменной х.

А где гарантия, что код метода не заинлайнен, и что все свитч не выкинут к чертям?

ВВ>Хех, ты даже код внимательно не посмотрел.

Я вообще не люблю смотреть на сфероконей.

От:	VladD2	www.nemerle.org
Дата:	14.09.10 14:30
Оценка:

От:	VladD2	www.nemerle.org
Дата:	14.09.10 14:34
Оценка:

	От:	Ka3a4oK
	Дата:	14.09.10 14:41
	Оценка:

	От:	Воронков Василий
	Дата:	14.09.10 14:46
	Оценка:

От:	VladD2	www.nemerle.org
Дата:	14.09.10 14:47
Оценка: