Суперкомпиляторы
От: DSblizzard Россия  
Дата: 12.05.09 23:30
Оценка:
1) Сколько времени и памяти занимает суперкомпиляция по сравнению с обычной компиляцией? Насколько больше по размеру программа после суперкомпиляции?
2) Говорят, частичные вычисления не дружат с побочными эффектами. Насчет суперкомпиляции это тоже верно?
3) Как вы думаете, почему суперкомпиляторы не входили в мэйнстрим и до сих пор бы не вошли, если бы этим не занялся сам Турчин? Только из-за сложности реализации?
Программировать сложно. Но не программировать еще сложнее.
Re: Суперкомпиляторы
От: Pzz Россия https://github.com/alexpevzner
Дата: 13.05.09 00:16
Оценка:
Здравствуйте, DSblizzard, Вы писали:

DS>3) Как вы думаете, почему суперкомпиляторы не входили в мэйнстрим и до сих пор бы не вошли, если бы этим не занялся сам Турчин? Только из-за сложности реализации?


А сейчас входят?
Re[2]: Суперкомпиляторы
От: DSblizzard Россия  
Дата: 13.05.09 01:32
Оценка:
Для Явы делают суперкомпилятор. Пишут, что увеличивает скорость до 50 раз.
Программировать сложно. Но не программировать еще сложнее.
Re[3]: Суперкомпиляторы
От: Красин Россия  
Дата: 13.05.09 05:16
Оценка:
Здравствуйте, DSblizzard, Вы писали:

DS>Для Явы делают суперкомпилятор. Пишут, что увеличивает скорость до 50 раз.


Ссылочку можно? Я пока нашел эту, с указанием "The Java Supercompiler Version 1 is scheduled for completion in late 2003." без какой-либо ссылки на скачку и эту, где предлагается скачать альфа-версию, датированную 2008 годом (причем, судя по CHANGELOG, за последние 5 лет там поменялось всего несколько строк).
Re: Суперкомпиляторы
От: Tom Россия http://www.RSDN.ru
Дата: 13.05.09 05:41
Оценка: +3
Здравствуйте, DSblizzard, Вы писали:

DS>1) Сколько времени и памяти занимает суперкомпиляция по сравнению с обычной компиляцией? Насколько больше по размеру программа после суперкомпиляции?

DS>2) Говорят, частичные вычисления не дружат с побочными эффектами. Насчет суперкомпиляции это тоже верно?
DS>3) Как вы думаете, почему суперкомпиляторы не входили в мэйнстрим и до сих пор бы не вошли, если бы этим не занялся сам Турчин? Только из-за сложности реализации?

Просветите меня что это такое, с чем едят и зачем надо?
Народная мудрось
всем все никому ничего(с).
Re[3]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 13.05.09 08:39
Оценка: +1
Здравствуйте, DSblizzard, Вы писали:

DS>Для Явы делают суперкомпилятор. Пишут, что увеличивает скорость до 50 раз.


Бредят. Разве что в очень частных случаях.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Суперкомпиляторы
От: _FRED_ Черногория
Дата: 13.05.09 16:59
Оценка:
Здравствуйте, Tom, Вы писали:

DS>>1) Сколько времени и памяти занимает суперкомпиляция по сравнению с обычной компиляцией? Насколько больше по размеру программа после суперкомпиляции?


Tom>Просветите меня что это такое, с чем едят и зачем надо?

Суперкомпиляция в Википедии
Help will always be given at Hogwarts to those who ask for it.
Re[4]: Суперкомпиляторы
От: DSblizzard Россия  
Дата: 13.05.09 23:21
Оценка:
Нет, ничего другого предложить не могу. Я пока только теоретически интересовался, на реализации не смотрел.
Программировать сложно. Но не программировать еще сложнее.
Re[4]: Суперкомпиляторы
От: DSblizzard Россия  
Дата: 13.05.09 23:22
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Бредят. Разве что в очень частных случаях.


Можно поподробнее? Почему вы так считаете?
Программировать сложно. Но не программировать еще сложнее.
Re[4]: Суперкомпиляторы
От: DSblizzard Россия  
Дата: 14.05.09 00:00
Оценка:
Кстати, еще Supero есть для Хаскеля, для Scala что-то и еще для пары языков, не считая Рефала, уже не помню для каких.
Программировать сложно. Но не программировать еще сложнее.
Re[5]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 14.05.09 00:10
Оценка: +2
Здравствуйте, DSblizzard, Вы писали:

VD>>Бредят. Разве что в очень частных случаях.


DS>Можно поподробнее? Почему вы так считаете?


Чудес не бывает, чтобы получить выигрыш в 50 раз нужно исходно иметь огромные алгоритмические проблемы и искусственный интеллект который их исправит.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: Суперкомпиляторы
От: Sinclair Россия https://github.com/evilguest/
Дата: 14.05.09 09:27
Оценка: 23 (5) -1
Здравствуйте, VladD2, Вы писали:

VD>Чудес не бывает, чтобы получить выигрыш в 50 раз нужно исходно иметь огромные алгоритмические проблемы и искусственный интеллект который их исправит.

Да ладно. Никакого предела ускорению программ путём суперкомпиляции нету. Привожу простой пример: делаем разложение чисел на простые множители.
Обычный компилятор компиляет алгоритм, который получает O(exp(N)).

Суперкомпилятор запускает этот алгоритм на первом миллионе чисел и строит таблицу.
В итоге, для чисел в пределах первого миллиона результат суперкомпилированной программы работает за O(1). Поделив время работы первого варианта для достаточно большого числа K на это O(1), можно получить ускорение и в миллион раз. Никаких фундаментальных проблем нет.

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

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

В принципе, на локальном уровне этим уже занимаются современные компиляторы, особенно для неуправляемых языков. Суперкомпиляторы претендуют на глобальный уровень, только и всего.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[3]: Суперкомпиляторы
От: GlebZ Россия  
Дата: 14.05.09 11:08
Оценка: 58 (1)
Здравствуйте, _FRED_, Вы писали:

_FR>Суперкомпиляция в Википедии

Здесь получше описано:
здесь
Re[7]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 14.05.09 11:31
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Да ладно. Никакого предела ускорению программ путём суперкомпиляции нету. Привожу простой пример: делаем разложение чисел на простые множители.

S>Обычный компилятор компиляет алгоритм, который получает O(exp(N)).

То есть исходно мы имеем супер-нееэффективный алгоритм и путем его переписывания в эффективный получаем значительное ускорение?

Поделись тем как такой подход можно обобщить. Иначе это и есть частный случай.

S>Суперкомпилятор запускает этот алгоритм на первом миллионе чисел и строит таблицу.

S>В итоге, для чисел в пределах первого миллиона результат суперкомпилированной программы работает за O(1). Поделив время работы первого варианта для достаточно большого числа K на это O(1), можно получить ускорение и в миллион раз. Никаких фундаментальных проблем нет.

Гы-гы. Кремлевский мечтатель. Представим что у алгоритма есть 10 параметров или 2 но с очень большими значениями. В итоге мы получаем или многомерную структуру неопределенного размера стремящуюся к бесконечности, или двухмерную но тоже вылезающую за память компьюетра.

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

Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга.

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


Нужно понимать, что частные оптимизации мало интересны, так как устанешь затачивать под них компилятор.

То что ты описал влет оптимизируется путем тупой мемоизации (в том же Немерле — это ровно один атрибут на метод повесть).

S>Так что всё, что может сделать суперкомпилятор — это

S>а) устранить заведомо избыточную обобщённость (типична для суперумных библиотек на все случаи жизни, которые реально в конкретной программе используются в небольшом количестве сценариев)
S>б) провести спекулятивное устранение обобщённости (с этим сложнее, потому что нужно знать распределение значений входных параметров. И если в нём нет особенных неравномерностей, то ничего интересного суперкомпилятор не даст)

S>В принципе, на локальном уровне этим уже занимаются современные компиляторы, особенно для неуправляемых языков. Суперкомпиляторы претендуют на глобальный уровень, только и всего.


Ну, и как добиться ускорения в 50 раз?
Я вижу только один способ — писать чудовищно бездарный код и очень умный компилятор.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Суперкомпиляторы
От: GlebZ Россия  
Дата: 14.05.09 11:53
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга.

a)Это неверный подход изначально. Ускорять можно не алгоритм, а реализацию. Ты предлагаешь оптимизировать генеренный машиной код. Если он написан человеком, то чаще может быть оптимизирован(как в рамках суперкомпиляции, так и без оной)
б)В случае если есть неиспользуемые AST-tree ноды, то зачем из создавать? Не проще ли пропустить?

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

VD>Нужно понимать, что частные оптимизации мало интересны, так как устанешь затачивать под них компилятор.
Аднако в этом весь смысл. Правда никто и не говорит что в данный момент суперкомпиляторы есть кул. С наполнением алгоритмами оптимизации туговато... Во многом эти алгоритмы NP-задачи. Sinclair — правду молвит о проблеме нынешней применимости.

VD>То что ты описал влет оптимизируется путем тупой мемоизации (в том же Немерле — это ровно один атрибут на метод повесть).

Это не оптимизация. Это декларативное указание алгоритма выполнения

VD>Ну, и как добиться ускорения в 50 раз?

VD>Я вижу только один способ — писать чудовищно бездарный код и очень умный компилятор.
Если посмотреть на обобщенности современных библиотек, которые умеют все, и гладить и вышивать, частные случаи подобной оптимизации — возможны. Ну к примеру, оптимизировать Linq to entities запросы. Другой вопрос — нужны ли если производительность в подавляющем случае достаточна?
Re[8]: Суперкомпиляторы
От: Sinclair Россия https://github.com/evilguest/
Дата: 14.05.09 12:17
Оценка: 7 (2)
Здравствуйте, VladD2, Вы писали:

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


S>>Да ладно. Никакого предела ускорению программ путём суперкомпиляции нету. Привожу простой пример: делаем разложение чисел на простые множители.

S>>Обычный компилятор компиляет алгоритм, который получает O(exp(N)).

VD>То есть исходно мы имеем супер-нееэффективный алгоритм и путем его переписывания в эффективный получаем значительное ускорение?

Нет. Исходно мы имеем нормальный алгоритм A, который работает для любого инпута x из множества X.

Затем, путем ограничения набора инпутов множеством X'<X мы пытаемся получить частный случай этого алгоритма — A', который работает быстрее, чем A. Но только на инпутах из X'.

VD>Гы-гы. Кремлевский мечтатель. Представим что у алгоритма есть 10 параметров или 2 но с очень большими значениями. В итоге мы получаем или многомерную структуру неопределенного размера стремящуюся к бесконечности, или двухмерную но тоже вылезающую за память компьюетра.

Увы — эта красивая теория подтверждена суровой практикой. Представь, что у алгоритма есть 10 параметров, но в твоей конкретной программе 9 из них фиксированы, и меняется только десятый. Суперкомпилятор будет способен существенно улучшить характеристики этого алгоритма. Вопрос только в том, насколько часто встречаются такие программы.
VD>В общем, это все мечты. Если алгоритм исходно оптимальный, то никакие суперкомпиляторы его не ускорят (а замедлить могут).
Почитай что-нибудь про частичные вычисления.
VD>Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга.
Ок. Какие ограничения на инпут ты предлагаешь?

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


VD>Нужно понимать, что частные оптимизации мало интересны, так как устанешь затачивать под них компилятор.

Не частные, а частичные. Затачивать ничего не нужно. Всё заточится само.
VD>То что ты описал влет оптимизируется путем тупой мемоизации (в том же Немерле — это ровно один атрибут на метод повесть).
Нет, не всё. Речь же не просто о перечислении значений параметров. К примеру, если известно, что параметром некоторого floating-point алгоритма всегда будут целые числа, то частенько можно его подкрутить так, чтобы он был быстрее. Никакая мемоизация тут не спасёт.

VD>Ну, и как добиться ускорения в 50 раз?

Я тебе написал пример про разложение на множители. Там и 50000 можно получить. Тебе знаком полиномиальный алгоритм разложения на простые множители? Тогда тебя ждет премия Тьюринга.
VD>Я вижу только один способ — писать чудовищно бездарный код и очень умный компилятор.
Может, всё же почитаешь ссылки, прежде чем делать безапелляционные выводы?
Всё наоборот — пишем хороший код, и очень тупой, но тщательный компилятор.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[9]: Конкретный пример
От: palm mute  
Дата: 14.05.09 12:50
Оценка: 76 (5) +1
Здравствуйте, Sinclair, Вы писали:

VD>>То что ты описал влет оптимизируется путем тупой мемоизации (в том же Немерле — это ровно один атрибут на метод повесть).

S>Нет, не всё. Речь же не просто о перечислении значений параметров. К примеру, если известно, что параметром некоторого floating-point алгоритма всегда будут целые числа, то частенько можно его подкрутить так, чтобы он был быстрее. Никакая мемоизация тут не спасёт.

Товарищи описывают, как алгоритм Кнута-Морриса-Пратта получается из брутфорс-алгоритма путем partial evaluation: On Obtaining Knuth, Morris, and Pratt’s String Matcher by Partial Evaluation
Re[9]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 14.05.09 13:36
Оценка: +1 -2
Здравствуйте, Sinclair, Вы писали:

VD>>То есть исходно мы имеем супер-нееэффективный алгоритм и путем его переписывания в эффективный получаем значительное ускорение?

S>Нет. Исходно мы имеем нормальный алгоритм A, который работает для любого инпута x из множества X.

И из-за этого он медлееннее в 50 раз?
Чушь это.

S>Затем, путем ограничения набора инпутов множеством X'<X мы пытаемся получить частный случай этого алгоритма — A', который работает быстрее, чем A. Но только на инпутах из X'.


И получаем 50 раз? Можно ссылку на экспериментальную базу.

S>Увы — эта красивая теория подтверждена суровой практикой. Представь,


Не хочу представлять. Ссылки на экспериментальную базу будет достаточно.

S>что у алгоритма есть 10 параметров, но в твоей конкретной программе 9 из них фиксированы, и меняется только десятый.


ОК. Возьмем, к примеру, алгоритм парсинга Packrat которым я тут на дусуге изучал. Очень интересная штука. Дико гибкая и обещает парсинг за линейное время. Проблема только в том, что линейность достигается мемоизацией и объем таблицы мемоизации без оптимизаций становится равнымы ~ O(m*n) где m — количество правил, а n — это длинна входного потока (практически длина разбираемого файла).

Алгоритм весьма универсальный. Оптимизировать его тоже можно, но врунчую. Основные средства оптимизации — это уменьшение объема мемоизации и инлайнинг.

Внимание, вопрос! Как нам в данном случае поможет суперкомпиляция?

S> Суперкомпилятор будет способен существенно улучшить характеристики этого алгоритма. Вопрос только в том, насколько часто встречаются такие программы.


Так чтобы дать ускорение в 50 раз? Да раз в сто лет. Если не реже. Ежу понятно, что 50 раз это ужасно много.

VD>>Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга.

S>Ок. Какие ограничения на инпут ты предлагаешь?

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

S>Нет, не всё. Речь же не просто о перечислении значений параметров. К примеру, если известно, что параметром некоторого floating-point алгоритма всегда будут целые числа, то частенько можно его подкрутить так, чтобы он был быстрее. Никакая мемоизация тут не спасёт.


Если это известно, то это можно захардкодить. Причем получится даже проще. Но известно такое очень редко.

Суперкомпиляция полезна, например, для уничтожения замыканий и лямбд, путем замены их на циклы, в тех случаях когда это возможно, и путем инлайнинга.
Это даст ощутимый выигрыш. Но этот выигрыш будет варьироваться от десятых долей процента до нескольких раз. Он никогда не достигнет 50 раз! Точнее сказать, надо написать просто чудовищно не реалистичную программу забитую комбинаторами, чтобы достичь этих 50 раз. В реальной жизни такого не встречается.

VD>>Ну, и как добиться ускорения в 50 раз?

S>Я тебе написал пример про разложение на множители. Там и 50000 можно получить. Тебе знаком полиномиальный алгоритм разложения на простые множители? Тогда тебя ждет премия Тьюринга.

Это чушь, а не пример. Частный случай не реальной задачи.

VD>>Я вижу только один способ — писать чудовищно бездарный код и очень умный компилятор.

S>Может, всё же почитаешь ссылки, прежде чем делать безапелляционные выводы?

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

Суперкомпиляция — это частный случая частичного выполнения известного со врем ML-я и паттер-матчинга. Где можно его уже применяют. А в общем случае проекты вроде суперкомпиляторов для Явы просто дохнут ничем не закончившись. По всей видимости выхлоп не соответствует ожиданиям и авторы холодеют к данному подходу.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Конкретный пример
От: z00n  
Дата: 14.05.09 13:39
Оценка: 41 (3)
Здравствуйте, palm mute, Вы писали:

PM>Товарищи описывают, как алгоритм Кнута-Морриса-Пратта получается из брутфорс-алгоритма путем partial evaluation: On Obtaining Knuth, Morris, and Pratt’s String Matcher by Partial Evaluation


Второй хороший конкретный пример — паттерн-матчер Nemerle строится методом "partial evaluation" — т.е. из наивного "дерева решений" во вренмя компиляции таким способом убирают все "лишние" тесты ( ML pattern match compilation and partial evaluation (1996)).
Автор алгоритма (Sestoft) — соавтор книги Partial Evaluation and Automatic Program Generation, доступной свободно.
Re[9]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 14.05.09 13:42
Оценка:
Здравствуйте, GlebZ, Вы писали:

VD>>Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга.

GZ>a)Это неверный подход изначально. Ускорять можно не алгоритм, а реализацию. Ты предлагаешь оптимизировать генеренный машиной код. Если он написан человеком, то чаще может быть оптимизирован(как в рамках суперкомпиляции, так и без оной)
GZ>б)В случае если есть неиспользуемые AST-tree ноды, то зачем из создавать? Не проще ли пропустить?

Я привел пример алгоритма который давно известно как реализовать весьма эффективно. И будучи эффективно реализованным его хрена два соптимизируешь.

GZ>Аднако в этом весь смысл. Правда никто и не говорит что в данный момент суперкомпиляторы есть кул. С наполнением алгоритмами оптимизации туговато... Во многом эти алгоритмы NP-задачи. Sinclair — правду молвит о проблеме нынешней применимости.


Это все мечтания. Я не спорю, что для некоторых задач (вроде переписывания замыканий и ФВП в циклы) суперкомпиляция отличный алгоритм оптимизации, но никаких 50 раз в общем случае дабиться не получится. Это просто выдумки. Разы будет уже хорошо. Да и то в частном случае.

VD>>То что ты описал влет оптимизируется путем тупой мемоизации (в том же Немерле — это ровно один атрибут на метод повесть).

GZ>Это не оптимизация. Это декларативное указание алгоритма выполнения

Синклер привел примет того, что отлично оптимизируется этим метдом. Я ответил, что для данного случая есть в тысячи раз более простое решение.

VD>>Ну, и как добиться ускорения в 50 раз?

VD>>Я вижу только один способ — писать чудовищно бездарный код и очень умный компилятор.
GZ>Если посмотреть на обобщенности современных библиотек, которые умеют все, и гладить и вышивать, частные случаи подобной оптимизации — возможны. Ну к примеру, оптимизировать Linq to entities запросы. Другой вопрос — нужны ли если производительность в подавляющем случае достаточна?

ОК. Возьмем линк. Что там можно оптимизировать если запрос должен в рантайме превратиться в SQL?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Суперкомпиляторы
От: Klapaucius  
Дата: 14.05.09 14:12
Оценка: +2
Здравствуйте, VladD2, Вы писали:

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

VD>Это даст ощутимый выигрыш. Но этот выигрыш будет варьироваться от десятых долей процента до нескольких раз. Он никогда не достигнет 50 раз! Точнее сказать, надо написать просто чудовищно не реалистичную программу забитую комбинаторами, чтобы достичь этих 50 раз. В реальной жизни такого не встречается.

Написать "программу забитую комбинаторами" совсем не сложно. Здесь
Автор: Klapaucius
Дата: 20.03.08
очень простой комбинаторный парсер на C#, который работает в примерно в 500 раз медленнее, чем комбинаторный парсер на Хаскеле безо всякой суперкомпиляции — просто в C# почти совсем нет оптимизаций для функциональщины. Где-то рядом есть улучшенный варинат, который в 25 раз медленнее парсера на Хаскеле, что примерно соответствует обсуждаемым здесь порядкам ускорения.
... << RSDN@Home 1.2.0 alpha 4 rev. 1110>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[10]: Суперкомпиляторы
От: IT Россия linq2db.com
Дата: 14.05.09 14:47
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>ОК. Возьмем линк. Что там можно оптимизировать если запрос должен в рантайме превратиться в SQL?


Получаемый SQL. Правда непонятно зачем там суперкомпиляция, несложных эвристик вполне хватает.
Если нам не помогут, то мы тоже никого не пощадим.
Re[11]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 14.05.09 17:44
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>Написать "программу забитую комбинаторами" совсем не сложно. Здесь
Автор: Klapaucius
Дата: 20.03.08
очень простой комбинаторный парсер на C#, который работает в примерно в 500 раз медленнее, чем комбинаторный парсер на Хаскеле безо всякой суперкомпиляции


1. В Хаскеле (в некотрых компиляторах) применяется аналог суперкомпиляции "дедеревизация".
2. Не верю! Не верю, что в 500. Даже не верю, что в 10 раз медленее, если алгоритмически они эквивалентны.

K>- просто в C# почти совсем нет оптимизаций для функциональщины. Где-то рядом есть улучшенный варинат, который в 25 раз медленнее парсера на Хаскеле, что примерно соответствует обсуждаемым здесь порядкам ускорения.


Это гадание на кофейной гуще. Сначала нужно доказать алгоритмическую эквивалентность, а потом уже обсуждать преимущества и недостатки оптимизаций.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 14.05.09 17:49
Оценка:
Здравствуйте, IT, Вы писали:

VD>>ОК. Возьмем линк. Что там можно оптимизировать если запрос должен в рантайме превратиться в SQL?


IT>Получаемый SQL. Правда непонятно зачем там суперкомпиляция, несложных эвристик вполне хватает.


Скажу даже больше. Суперкомпиляция тут вообще ничего не даст, так как она будет оптимизировать код генерирующий SQL, а не SQL. Так что оптимизировать нужно алгоритмы, а не генерируемый код.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 14.05.09 17:55
Оценка:
Здравствуйте, GlebZ, Вы писали:

VD>>Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга.

GZ>a)Это неверный подход изначально. Ускорять можно не алгоритм, а реализацию.

На счет "ускорить реализацию". Синклер предлагал оптимизировать алгоритм путем автоматического создания таблицы решений для некоторых значений входных параметров. Это, по-твоему, не алгоритмическая оптимизация?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 14.05.09 18:10
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>Написать "программу забитую комбинаторами" совсем не сложно. Здесь
Автор: Klapaucius
Дата: 20.03.08
очень простой комбинаторный парсер на C#, который работает в примерно в 500 раз медленнее, чем комбинаторный парсер на Хаскеле безо всякой суперкомпиляции — просто в C# почти совсем нет оптимизаций для функциональщины. Где-то рядом есть улучшенный варинат, который в 25 раз медленнее парсера на Хаскеле, что примерно соответствует обсуждаемым здесь порядкам ускорения.


Кстати, подумай, что может сделать суперкомпилятор если программист для прсинга регулярной грамматики (которой является разбор числа) использует рекурсивный нисходящий парсер с бэктрэкингом но без мемоизации?
Самая разумная оптимизация тут будет использовать регулярные выражения (оптимально если их движок создают ДКА). Задача при этом еще и проще получится.
Никакая суперкомпиляция до этого не додумается.
Устранение комбинаторов позволит повысить скорость вычислений, но экспненциального характера алгоритма она не уберет.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Суперкомпиляторы
От: VoidEx  
Дата: 14.05.09 19:05
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Если это известно, то это можно захардкодить. Причем получится даже проще.

О, Боже! Слышу ли я это от сторонника метапрограммирования и написания как можно меньшего кода руками?
Re[11]: Суперкомпиляторы
От: SmbdRsdn2  
Дата: 14.05.09 19:16
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>который работает в примерно в 500 раз медленнее

Скорее в 50 раз медленнее. Написал подробнее об этом в той теме.

Haskel вариант запускался на C2D (3.12 GHz), дал примерно 50 mb/s.
Вариант на C# 3.0 у меня на C2D (2.4 Ghz), дал примерно 0.8 mb/s. (при на четверть более быстром процессоре будет примерно 1 mb/s)
Re[11]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 14.05.09 19:50
Оценка: +1 :)))
Здравствуйте, VoidEx, Вы писали:

VD>>Если это известно, то это можно захардкодить. Причем получится даже проще.

VE>О, Боже! Слышу ли я это от сторонника метапрограммирования и написания как можно меньшего кода руками?

Метапрограммирование — это средство автоматизировать процесс хардкодинга.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[12]: Суперкомпиляторы
От: thesz Россия http://thesz.livejournal.com
Дата: 14.05.09 21:23
Оценка:
IT>>Получаемый SQL. Правда непонятно зачем там суперкомпиляция, несложных эвристик вполне хватает.
VD>Скажу даже больше. Суперкомпиляция тут вообще ничего не даст, так как она будет оптимизировать код генерирующий SQL, а не SQL.

Это ограничение придумано тобой только что.

Я не вижу причин, по которым не...
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[13]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 14.05.09 22:13
Оценка:
Здравствуйте, thesz, Вы писали:

T>Это ограничение придумано тобой только что.


T>Я не вижу причин, по которым не...


А ты разберись в том о чем идет речь и увидишь. В кратце, linq выдает AST которое уже в рантайме преобразуется в SQL.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Суперкомпиляторы
От: Sinclair Россия https://github.com/evilguest/
Дата: 15.05.09 03:29
Оценка: 6 (1)
Здравствуйте, VladD2, Вы писали:

VD>И получаем 50 раз?

Легко.
VD>Можно ссылку на экспериментальную базу.
Тебе дали ссылку. Прямо здесь есть всё, что нужно.
S>>Увы — эта красивая теория подтверждена суровой практикой. Представь,

VD>Не хочу представлять. Ссылки на экспериментальную базу будет достаточно.

Конкретный пример: берём преобразование Фурье. Не нарошно пессимизированную версию, а честное FFT для комплексных чисел, работающее с N=2^K для любого R.
Затем суперкомпилируем его для N=4 (а реальные программы, как правило, редко преобразовывают чанки разной длины). Получаем ускорение в 20 раз:

Empirically, in Java, this gives a roughly 20 times speedup over the generic FFT. Similar results are obtained for larger n. For instance, the supercompiled FFT for an input series of length 16 may be obtained at the URL http://www.supercompilers.com/Fft.java.res16.html.

Оттуда же на близкую тебе тему:

Similarly, if one is writing a language interpreter, there is no need to hack one's interpreter to make it maximally efficient for the specific grammar one needs interpreted. Rather, one can write the language interpreter in a simple, general and maintainable way, and let the supercompiler do the specialization of the interpreter for a given grammar. This is an area in which significant experimentation with the Java supercompiler is going on right now. On a cursory consideration, it looks like a pure program specialization application, but when one studies the actual code of language interpreters, one realizes that program specialization will not solve the majority of code inefficiencies, so that a fuller supercompilation approach is required. Experimentation in this domain is going on currently, focusing on popular scripting languages such as XSLT, Perl and Tcl.

Перевод нужен?
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[12]: Суперкомпиляторы
От: Klapaucius  
Дата: 15.05.09 08:14
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>1. В Хаскеле (в некотрых компиляторах) применяется аналог суперкомпиляции "дедеревизация".


Так в C# версии проблем с промежуточными списками вроде как и нет. Там проблема в другом — код в котором много комбинаторов сам по себе ленивый, а средств для оптимизации такой ленивости в компиляторах strict языков по понятным причинам меньше, чем в GHC. В том треде варианты на OCaml и F# также сливали Хаскелю.

VD>2. Не верю! Не верю, что в 500. Даже не верю, что в 10 раз медленее, если алгоритмически они эквивалентны.


Алгоритмически они не совсем эквивалентны. Вариант, переписаный с Хаскеля один-в-один вообще не работал — переполнял стек, так что в некоторых местах рекурсия заменена на автоматы на yield return. Но я думаю, что соответствие в общем случае достаточно хорошее, а если это не так, то неплохо было бы показать где именно проблемы.

K>>- просто в C# почти совсем нет оптимизаций для функциональщины. Где-то рядом есть улучшенный варинат, который в 25 раз медленнее парсера на Хаскеле, что примерно соответствует обсуждаемым здесь порядкам ускорения.

VD>Это гадание на кофейной гуще. Сначала нужно доказать алгоритмическую эквивалентность, а потом уже обсуждать преимущества и недостатки оптимизаций.

Я то всего навсего попрытался показать, что комбинаторы могут обходиться гораздо дроже, чем в десятки процентов и еденицы раз. Согласен, что у моего обоснования есть изъяны, но в общем случае, мое утверждение лучше обосновано, чем Ваше, которое никак не доказано и даже не проиллюстрировано.
... << RSDN@Home 1.2.0 alpha 4 rev. 1110>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[10]: Суперкомпиляторы
От: GlebZ Россия  
Дата: 15.05.09 08:24
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>>>Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга.

GZ>>a)Это неверный подход изначально. Ускорять можно не алгоритм, а реализацию. Ты предлагаешь оптимизировать генеренный машиной код. Если он написан человеком, то чаще может быть оптимизирован(как в рамках суперкомпиляции, так и без оной)
GZ>>б)В случае если есть неиспользуемые AST-tree ноды, то зачем из создавать? Не проще ли пропустить?
VD>Я привел пример алгоритма который давно известно как реализовать весьма эффективно. И будучи эффективно реализованным его хрена два соптимизируешь.
Прооверквотю —
1) алгоритм написанный человеком неоптимален потому что он должен быть прежде всего понятен самому человеку. Такой оптимизацией занимаются все компиляторы
2) Для человека важна формализация парсируемого языка. Для оптимизатора важно то, что непротиворечивость результатов для потребляющих компонентов. Поэтому, если часть формализации неиспользуется, то ее вполне можно опустить.
Это к слову об оптимизации LL(1).

VD>ОК. Возьмем линк. Что там можно оптимизировать если запрос должен в рантайме превратиться в SQL?

А если не должен? При глобальном анализе доступно не только что нужно исполнять, но и как будут использоваться результаты. Одно кэширование повторяющихся выборок вполне может дать результат в те же 50 раз. Вопрос только в том, что выполнение в оперативе и так быстро.

VD>На счет "ускорить реализацию". Синклер предлагал оптимизировать алгоритм путем автоматического создания таблицы решений для некоторых значений входных параметров. Это, по-твоему, не алгоритмическая оптимизация?

Ну вместо алгоритм Штуцера назовешь это кэширующий алгоритм Штуцера. Любое действие можно описать алгоритмом. Но понятие алгоритм — нужно человеку а не машине или оптимизатору(суперкомпилятору). Вообще-же, я думаю, за оптимизацией в runtime — будущее.
Re[11]: Суперкомпиляторы
От: GlebZ Россия  
Дата: 15.05.09 08:29
Оценка:
Здравствуйте, IT, Вы писали:

VD>>ОК. Возьмем линк. Что там можно оптимизировать если запрос должен в рантайме превратиться в SQL?

IT>Получаемый SQL. Правда непонятно зачем там суперкомпиляция, несложных эвристик вполне хватает.
А теперь попробуем представить насколько увеличится быстродействие если вместо генерации будет использоваться кэшируемое значение, что собственно делается в каждой уважаемой БД. 50 раз нагрести можно?
Суперкомпилятор — может это сделать автоматически при том, что ты общаешься с нормальными читабельными сырцами.
Re[13]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.05.09 11:36
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>Так в C# версии проблем с промежуточными списками вроде как и нет. Там проблема в другом — код в котором много комбинаторов сам по себе ленивый, а средств для оптимизации такой ленивости в компиляторах strict языков по понятным причинам меньше, чем в GHC.


Я думаю, что проблема там в том, что создается множество промежуточных объектов. Использование итераторов приводит к этому на раз. Где-то пробигали варианты Парсека написанные на Немерле. Там вместо итераторов использовались лямбды. Правда, там для получения конца строки используется метод Substring(), но это легко лечится.
Можно провести сравнения.

K>В том треде варианты на OCaml и F# также сливали Хаскелю.


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

Лучше скажи, сколько они сливают? Не уж-то 50 процентов?

В прочем, в любом случае такой код никто в реальной жизни использовать не будет.

VD>>2. Не верю! Не верю, что в 500. Даже не верю, что в 10 раз медленее, если алгоритмически они эквивалентны.


K>Алгоритмически они не совсем эквивалентны. Вариант, переписаный с Хаскеля один-в-один вообще не работал — переполнял стек, так что в некоторых местах рекурсия заменена на автоматы на yield return. Но я думаю, что соответствие в общем случае достаточно хорошее, а если это не так, то неплохо было бы показать где именно проблемы.


Не, так дело не пойдет. Доказывать корректность результатов должен тот, то их предлагает.

K>Я то всего навсего попрытался показать, что комбинаторы могут обходиться гораздо дроже, чем в десятки процентов и еденицы раз. Согласен, что у моего обоснования есть изъяны, но в общем случае, мое утверждение лучше обосновано, чем Ваше, которое никак не доказано и даже не проиллюстрировано.


Дык это уже не совсем комбинаторы. Это еще и наворот на итераторах. В прочем, убедил. Таким образом можно что-угодно замедлить . Вот только это и получается частный случай неразумного выбора алгоритмов.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.05.09 11:46
Оценка: -2
Здравствуйте, Sinclair, Вы писали:

S>Тебе дали ссылку. Прямо здесь есть всё, что нужно.


Прокрутил страницу 5 раз (вниз-вверх) ничего не обнаружил. Можно цитату?
Я читал научную работу где эксперементы ставились на ML-е. Там выигрышь был от нулевого до 3-х раз. Ни о каких 50 разах речи даже не шло.

S>Конкретный пример: берём преобразование Фурье. Не нарошно пессимизированную версию, а честное FFT для комплексных чисел, работающее с N=2^K для любого R.


В задницу твои фурье. Они в библиотеках должны лежать. Это называется подтасовка фактов. Нормальное исследование должно брать ординарный код и изменять процент его ускорения после оптимизации.

S>Затем суперкомпилируем его для N=4 (а реальные программы, как правило, редко преобразовывают чанки разной длины). Получаем ускорение в 20 раз:

S>

Empirically, in Java, this gives a roughly 20 times speedup over the generic FFT. Similar results are obtained for larger n. For instance, the supercompiled FFT for an input series of length 16 may be obtained at the URL http://www.supercompilers.com/Fft.java.res16.html.


Уже 20 для частного случая. Это более реалистично.
Так что там на счет 50% в общем случае?

S>Оттуда же на близкую тебе тему:

S>

Similarly, if one is writing a language interpreter, there is no need to hack one's interpreter to make it maximally efficient for the specific grammar one needs interpreted. Rather, one can write the language interpreter in a simple, general and maintainable way, and let the supercompiler do the specialization of the interpreter for a given grammar. This is an area in which significant experimentation with the Java supercompiler is going on right now. On a cursory consideration, it looks like a pure program specialization application, but when one studies the actual code of language interpreters, one realizes that program specialization will not solve the majority of code inefficiencies, so that a fuller supercompilation approach is required. Experimentation in this domain is going on currently, focusing on popular scripting languages such as XSLT, Perl and Tcl.

S>Перевод нужен?

Да, переведи выделенный фрагмент. Плюс переведи реальную цифру ускорения интерпретатора.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[12]: Суперкомпиляторы
От: thesz Россия http://thesz.livejournal.com
Дата: 15.05.09 12:17
Оценка: +1
S>>Конкретный пример: берём преобразование Фурье. Не нарошно пессимизированную версию, а честное FFT для комплексных чисел, работающее с N=2^K для любого R.
VD>В задницу твои фурье. Они в библиотеках должны лежать. Это называется подтасовка фактов. Нормальное исследование должно брать ординарный код и изменять процент его ускорения после оптимизации.

SPECfp с тобой не согласен.

Там в исходниках часто лежит BLAS, который также надо преобразовывать и параллелить.

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

У тебя заведомо выигрышная позиция, завидую.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[14]: Суперкомпиляторы
От: thesz Россия http://thesz.livejournal.com
Дата: 15.05.09 12:18
Оценка: :))
VD>В прочем, в любом случае такой код никто в реальной жизни использовать не будет.

Завидую снова. Теперь твоему знакомству с реальной жизнью, какой мне не встретить вовеки.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[14]: Суперкомпиляторы
От: thesz Россия http://thesz.livejournal.com
Дата: 15.05.09 12:24
Оценка: -1
T>>Это ограничение придумано тобой только что.
T>>Я не вижу причин, по которым не...
VD>А ты разберись в том о чем идет речь и увидишь. В кратце, linq выдает AST которое уже в рантайме преобразуется в SQL.

Что не противоречит моим словам.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[13]: Суперкомпиляторы
От: vdimas Россия  
Дата: 15.05.09 12:53
Оценка: +1
Здравствуйте, Klapaucius, Вы писали:

K>Алгоритмически они не совсем эквивалентны. Вариант, переписаный с Хаскеля один-в-один вообще не работал — переполнял стек, так что в некоторых местах рекурсия заменена на автоматы на yield return. Но я думаю, что соответствие в общем случае достаточно хорошее, а если это не так, то неплохо было бы показать где именно проблемы.


сразу навскидку char.IsDigit и int.Parse(charVar.ToString())
Re[13]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.05.09 16:14
Оценка:
Здравствуйте, thesz, Вы писали:

T>SPECfp с тобой не согласен.


Кому нужен SPECfp на Яве?

T>Там в исходниках часто лежит BLAS, который также надо преобразовывать и параллелить.


Можно тоже самое но русскими словами?

T>Так что ты сейчас снова выдумал какие-то интересные тебе критерии и пытаешься заставить собеседника удовлетворить их.


Ты уже достал.

T>У тебя заведомо выигрышная позиция, завидую.


Да, я принципиально не верю в чудеса. На практике вместо 50 раз будет 1-2, в в большинстве случаев ~0.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[14]: Суперкомпиляторы
От: VoidEx  
Дата: 15.05.09 16:17
Оценка: :)
Здравствуйте, VladD2, Вы писали:

VD>Да, я принципиально не верю в чудеса. На практике вместо 50 раз будет 1-2, в в большинстве случаев ~0.

~0 обоснуешь?
Re[12]: Суперкомпиляторы
От: IT Россия linq2db.com
Дата: 15.05.09 18:03
Оценка:
Здравствуйте, GlebZ, Вы писали:

IT>>Получаемый SQL. Правда непонятно зачем там суперкомпиляция, несложных эвристик вполне хватает.

GZ>А теперь попробуем представить насколько увеличится быстродействие если вместо генерации будет использоваться кэшируемое значение, что собственно делается в каждой уважаемой БД. 50 раз нагрести можно?
GZ>Суперкомпилятор — может это сделать автоматически при том, что ты общаешься с нормальными читабельными сырцами.

Конкретно, в случае Linq 2 SQL кеширование результатов генерации не делается. Но сделать это можно. Проблема в том, что простого ключа для сгенерированного компилятором ExpressionTree нет и быть не может. Деревья каждый раз строятся по новой и могут отличаться передаваемыми в запрос параметрами, которые могут представлять собой другие поддеревья. Так же дерево может строиться динамически. Для сравнения деревьев в кеше необходимо последовательно сравнивать исходное дерево с тем, что у нас в кеше. При этом два разных дерева могут считаться одинаковыми, если они отличаются, например, значениями передаваемых запросу параметров.

Суперкомпилятор может это сделать автоматически или я очень сильно в этом сомневаюсь?
Если нам не помогут, то мы тоже никого не пощадим.
Re[13]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.05.09 18:18
Оценка:
Здравствуйте, IT, Вы писали:

IT>Суперкомпилятор может это сделать автоматически или я очень сильно в этом сомневаюсь?


Суперкомпиляция не может в рантайме сделать ничего.

Это просто подход оптимизации кода заключающийся в переписывании кода. С его помощью можно "изводить" ФВП и замыкания в простых случаях. Например, можно сделать так чтобы "xs.Map(x => x.Y)" переписывался бы в цикл.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[14]: Суперкомпиляторы
От: IT Россия linq2db.com
Дата: 15.05.09 18:40
Оценка:
Здравствуйте, VladD2, Вы писали:

IT>>Суперкомпилятор может это сделать автоматически или я очень сильно в этом сомневаюсь?

VD>Суперкомпиляция не может в рантайме сделать ничего.

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

VD>Это просто подход оптимизации кода заключающийся в переписывании кода. С его помощью можно "изводить" ФВП и замыкания в простых случаях. Например, можно сделать так чтобы "xs.Map(x => x.Y)" переписывался бы в цикл.


Чем это круче применения соответствующих эвристик?
Если нам не помогут, то мы тоже никого не пощадим.
Re[14]: Суперкомпиляторы
От: thesz Россия http://thesz.livejournal.com
Дата: 15.05.09 22:07
Оценка: 6 (1) -1
T>>SPECfp с тобой не согласен.
VD>Кому нужен SPECfp на Яве?

SPECfp — это бенчмарк такой. Он построен на реальном коде. В отличии от того, что пытаешься навязать ты (всем ходить ровно! FFT лежать в библиотеке!).

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

И компьютерная система должна эффективно и автоматически выполнить этот код. А если не автоматически, то это задаётся отдельными ключами.

Вот это — подход настоящих, уважаемых бенчмарков. Твой же подход его отвергает.

Я думаю, что не стоит обращать внимание на твои требования, они высосаны из пальца.

T>>Там в исходниках часто лежит BLAS, который также надо преобразовывать и параллелить.

VD>Можно тоже самое но русскими словами?

BLAS: http://www.netlib.org/blas/

Это то, что по-твоему, должно лежать в библиотеке. А в жизни таскается с исходным кодом.

T>>Так что ты сейчас снова выдумал какие-то интересные тебе критерии и пытаешься заставить собеседника удовлетворить их.

VD>Ты уже достал.

Не мог никак. Я далеко нахожусь.

T>>У тебя заведомо выигрышная позиция, завидую.

VD>Да, я принципиально не верю в чудеса. На практике вместо 50 раз будет 1-2, в в большинстве случаев ~0.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.5943

Это вариант супероптимизатора. Берётся программа, накладывается шаблон, получается другая программа.

Если ты прочитаешь, то увидишь, что они могут делать и замену алгоритма на более быстрый (и менее точный) по требованию пользователя.

Ускорение значительно.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[7]: Суперкомпиляторы
От: Константин Россия  
Дата: 15.05.09 22:59
Оценка:
Здравствуйте, Sinclair, Вы писали:

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


VD>>Чудес не бывает, чтобы получить выигрыш в 50 раз нужно исходно иметь огромные алгоритмические проблемы и искусственный интеллект который их исправит.

S>Да ладно. Никакого предела ускорению программ путём суперкомпиляции нету. Привожу простой пример: делаем разложение чисел на простые множители.
S>Обычный компилятор компиляет алгоритм, который получает O(exp(N)).

S>Суперкомпилятор запускает этот алгоритм на первом миллионе чисел и строит таблицу.

S>В итоге, для чисел в пределах первого миллиона результат суперкомпилированной программы работает за O(1). Поделив время работы первого варианта для достаточно большого числа K на это O(1), можно получить ускорение и в миллион раз. Никаких фундаментальных проблем нет.

Утверждение об ускорении в 50 (100,200,...) раз очевидное жульничество.
Сценарий 1. Приложение считает разложение чисел от 1 до 10. Суперкомпилированный вариант работает в 1000 раз медленней за счёт времени общения с базой данных подсчитанных разложений, которая живёт на серверах google, так как у нас на жёстком диске столько места нет.
Сценарий 2. Приложение считает разложение чисел от 1 до 100000. Суперкомпилированный вариант работает в 1000 раз быстрей
Сценарий 3. Приложение считает разложение чисел вида 2^{10000...000}. Разницы нет. Вот только грузится суперкомпилированный вариант чуть дольше, так как суперкомпилятор влинковал таблицу с 10^10 предвычисленными разложениями в exe.
Re[12]: Суперкомпиляторы
От: Sinclair Россия https://github.com/evilguest/
Дата: 17.05.09 13:43
Оценка:
Здравствуйте, VladD2, Вы писали:
VD>Прокрутил страницу 5 раз (вниз-вверх) ничего не обнаружил. Можно цитату?
Я привел.
VD>Я читал научную работу где эксперементы ставились на ML-е. Там выигрышь был от нулевого до 3-х раз. Ни о каких 50 разах речи даже не шло.

VD>В задницу твои фурье. Они в библиотеках должны лежать.

Оно и так лежит в библиотеке. Вопрос в том, насколько обобщенный код библиотеки можно ускорить, заточив под твой частный случай.
VD>Это называется подтасовка фактов. Нормальное исследование должно брать ординарный код и изменять процент его ускорения после оптимизации.
Это ординарный код. Что тебе не нравится?

VD>Уже 20 для частного случая. Это более реалистично.

VD>Так что там на счет 50% в общем случае?
Никто не обещал 50 раз для общего случая. Это ты слишком невнимательно читаешь. Доказательство отсутствия универсального оптимизатора, ускоряющего любую программу, входит в програму детского сада для программистовю

VD>Да, переведи выделенный фрагмент. Плюс переведи реальную цифру ускорения интерпретатора.

Реальной цифры ускорения интерпретатора там нет.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[8]: Суперкомпиляторы
От: Sinclair Россия https://github.com/evilguest/
Дата: 17.05.09 13:43
Оценка:
Здравствуйте, Константин, Вы писали:

К>Утверждение об ускорении в 50 (100,200,...) раз очевидное жульничество.

К>Сценарий 1. Приложение считает разложение чисел от 1 до 10. Суперкомпилированный вариант работает в 1000 раз медленней за счёт времени общения с базой данных подсчитанных разложений, которая живёт на серверах google, так как у нас на жёстком диске столько места нет.
Сколько места? Домашнее задание: оценить размер базы данных с разложениями чисел от 1 до 1e6.

К>Сценарий 2. Приложение считает разложение чисел от 1 до 100000. Суперкомпилированный вариант работает в 1000 раз быстрей


К>Сценарий 3. Приложение считает разложение чисел вида 2^{10000...000}. Разницы нет. Вот только грузится суперкомпилированный вариант чуть дольше, так как суперкомпилятор влинковал таблицу с 10^10 предвычисленными разложениями в exe.

Насколько дольше? Домашнее задание: ознакомиться с алгоритмами работы загрузчиков в современных ОС; оценить влияние размера екзешника на время загрузки. Домашнее задание повышенной сложности: прочитать статью про суперкомпиляцию и понять, что суперкомпиляция не сводится к построению линейных таблиц для первых N значений. Понять, что в сценарии 3, когда приложение раскладывает исключительно степени двойки, суперкомпилятор это обнаружит, и оставит таблицу достаточно компактной.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[15]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 17.05.09 22:52
Оценка:
Здравствуйте, IT, Вы писали:

VD>>Это просто подход оптимизации кода заключающийся в переписывании кода. С его помощью можно "изводить" ФВП и замыкания в простых случаях. Например, можно сделать так чтобы "xs.Map(x => x.Y)" переписывался бы в цикл.


IT>Чем это круче применения соответствующих эвристик?


Дык "это" даже не обсуждает эвристики. Это просто общая идея, что программу можно ускорить если автоматически переписать ее заменив менее эффективные куски более эффективными.

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

Сказочные 50, и тем более, 500 раз это желаемое выдаваемое за действительное. Разы — это уже замечательно. Программы которые можно оптимизировать в десятки или сотни раз — это чудовищно не эффективные программы. Такие еще поискать надо.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: Конкретный пример
От: VladD2 Российская Империя www.nemerle.org
Дата: 17.05.09 22:58
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Второй хороший конкретный пример — паттерн-матчер Nemerle строится методом "partial evaluation" — т.е. из наивного "дерева решений" во вренмя компиляции таким способом убирают все "лишние" тесты ( ML pattern match compilation and partial evaluation (1996)).

Z>Автор алгоритма (Sestoft) — соавтор книги Partial Evaluation and Automatic Program Generation, доступной свободно.

Это немного другой (нежели суперкомпиляция) подход. Здесь есть четкий алгоритм решения конкретной задачи. Та же фигня с построителями парсеров. И совсем другое дело оптимизировать любой код универсальными средствами. Тут выигрыша в десятки, и тем более, сотри раз достичь будет практически не реально.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[15]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 17.05.09 23:01
Оценка:
Здравствуйте, thesz, Вы писали:

T>Завидую снова. Теперь твоему знакомству с реальной жизнью, какой мне не встретить вовеки.


Что с тебя взять? Ты же фанатик.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[15]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 17.05.09 23:05
Оценка:
Здравствуйте, VoidEx, Вы писали:

VD>>Да, я принципиально не верю в чудеса. На практике вместо 50 раз будет 1-2, в в большинстве случаев ~0.

VE>~0 обоснуешь?

Элементарно. В коде просто не будет паттернов которые запрограмирован изводить суперкомпилятор.

С удовольствием послушаю обоснования 50-кратного (в общем случае) ускорения.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[15]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 17.05.09 23:07
Оценка:
Здравствуйте, thesz, Вы писали:

T>SPECfp — это бенчмарк такой. Он построен на реальном коде. В отличии от того, что пытаешься навязать ты (всем ходить ровно! FFT лежать в библиотеке!).


Ну, так ты поделишься информацией о том, что демонстрируют тесты SPECfp для среднего ява-прогроммиста? Или ты не в курсе какой софт пишут на яве?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[16]: Суперкомпиляторы
От: VoidEx  
Дата: 17.05.09 23:12
Оценка: :)
Здравствуйте, VladD2, Вы писали:

VD>Элементарно. В коде просто не будет паттернов которые запрограмирован изводить суперкомпилятор.


VD>С удовольствием послушаю обоснования 50-кратного (в общем случае) ускорения.


А, т.е. 50-кратное ускорение — это в 51 раз быстрее?
Re[13]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 17.05.09 23:19
Оценка:
Здравствуйте, Sinclair, Вы писали:

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

VD>>Прокрутил страницу 5 раз (вниз-вверх) ничего не обнаружил. Можно цитату?
S>Я привел.

Ты говорил о 50-кратном увеличении производительности в общем случае. Тут речь идет о 20-тикратном в частном, причем никаому не нужном на практике (быстрое преобразование Фурье, это не самое часто что пишут на яве, првда?).
Так о чем ты ведешь речь?

VD>>В задницу твои фурье. Они в библиотеках должны лежать.

S>Оно и так лежит в библиотеке. Вопрос в том, насколько обобщенный код библиотеки можно ускорить, заточив под твой частный случай.

Вот это и должно быть заботой библиотеки. Пусть там SSE использует, динамическую компиляцию или мемоизацию результатов. А затачивать компилятор под конеретный, частный случай не очень то разумно. Слишком много трудозатрат при не очень-то большом выигрыше. Фурье то может в 20 раз и ускорится, вот сама программа — нет.

VD>>Это называется подтасовка фактов. Нормальное исследование должно брать ординарный код и изменять процент его ускорения после оптимизации.

S>Это ординарный код. Что тебе не нравится?

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

VD>>Уже 20 для частного случая. Это более реалистично.

VD>>Так что там на счет 50% в общем случае?
S>Никто не обещал 50 раз для общего случая. Это ты слишком невнимательно читаешь. Доказательство отсутствия универсального оптимизатора, ускоряющего любую программу, входит в програму детского сада для программистовю

Ну, что толку от ускорения специально подобранного случая, да еще и на совершенно синтетическом тесте?

VD>>Да, переведи выделенный фрагмент. Плюс переведи реальную цифру ускорения интерпретатора.

S>Реальной цифры ускорения интерпретатора там нет.

Я тебе на это и намекал. И знаешь почему? Да потому, что чудес не бывает и 50 раз там не будет ни за что. И знаешь почему? Да потому, что это будет несколько быстрее чем аналогичная программа скомпилированная в маш.код.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[17]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 17.05.09 23:27
Оценка: :)
Здравствуйте, VoidEx, Вы писали:

VD>>С удовольствием послушаю обоснования 50-кратного (в общем случае) ускорения.


VE>А, т.е. 50-кратное ускорение — это в 51 раз быстрее?


Ты что курил?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[18]: Суперкомпиляторы
От: VoidEx  
Дата: 17.05.09 23:36
Оценка:
Здравствуйте, VladD2, Вы писали:

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


VD>>>С удовольствием послушаю обоснования 50-кратного (в общем случае) ускорения.


VE>>А, т.е. 50-кратное ускорение — это в 51 раз быстрее?


VD>Ты что курил?


Всю жизнь думал, что если объектив имеет 5-кратное увеличение, то он увеличивает в 5 раз.
А теперь ещё раз слушаем обоснование про 0-кратное ускорение (скорость исходной программы на ноль помочь умножить?)
Re[19]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 17.05.09 23:45
Оценка:
Здравствуйте, VoidEx, Вы писали:

VE>Всю жизнь думал, что если объектив имеет 5-кратное увеличение, то он увеличивает в 5 раз.

VE>А теперь ещё раз слушаем обоснование про 0-кратное ускорение (скорость исходной программы на ноль помочь умножить?)

Цитирую свои слова:
http://rsdn.ru/forum/message/3391962.1.aspx
Автор: VoidEx
Дата: 15.05.09

Да, я принципиально не верю в чудеса. На практике вместо 50 раз будет 1-2, в в большинстве случаев ~0.

Что в них не ясно? Или просто захотелось поговорить?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[16]: Суперкомпиляторы
От: Курилка Россия http://kirya.narod.ru/
Дата: 18.05.09 04:26
Оценка:
Здравствуйте, VladD2, Вы писали:

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


VD>>>Да, я принципиально не верю в чудеса. На практике вместо 50 раз будет 1-2, в в большинстве случаев ~0.

VE>>~0 обоснуешь?

VD>Элементарно. В коде просто не будет паттернов которые запрограмирован изводить суперкомпилятор.


Странно, согласно математике, чтобы ускорение в 0 раз получить, надо чтобы после суперкомпиляции код выполнялся бесконечно долго
0 != 1
Re[9]: Суперкомпиляторы
От: Константин Россия  
Дата: 18.05.09 08:54
Оценка:
Здравствуйте, Sinclair, Вы писали:

К>>Сценарий 1. Приложение считает разложение чисел от 1 до 10. Суперкомпилированный вариант работает в 1000 раз медленней за счёт времени общения с базой данных подсчитанных разложений, которая живёт на серверах google, так как у нас на жёстком диске столько места нет.

S>Сколько места? Домашнее задание: оценить размер базы данных с разложениями чисел от 1 до 1e6.

Домашнее задание: оценить размер базы данных с разложениями чисел от 1 до 10^20. Предположим суперкомпилятор посчитал (интересно как ), что это будет оптимально для ускорения в 10^10 раз.

К>>Сценарий 3. Приложение считает разложение чисел вида 2^{10000...000}. Разницы нет. Вот только грузится суперкомпилированный вариант чуть дольше, так как суперкомпилятор влинковал таблицу с 10^10 предвычисленными разложениями в exe.

S>Насколько дольше?
S>Домашнее задание: ознакомиться с алгоритмами работы загрузчиков в современных ОС; оценить влияние размера екзешника на время загрузки.
Не знаю. Но где моё обещанное ускорение в 50, 10^6 раз?

S>Домашнее задание повышенной сложности: прочитать статью про суперкомпиляцию и понять, что суперкомпиляция не сводится к построению линейных таблиц для первых N значений.

Я называю жульничеcтвом твой пример, который не имеет никакого отношения к суперкомпиляции. Ты же предложил вычисление первых n чисел.

S>Понять, что в сценарии 3, когда приложение раскладывает исключительно степени двойки, суперкомпилятор это обнаружит, и оставит таблицу достаточно компактной.

Откуда он узнает, что я ему буду скармливать только степени двойки?
Re[10]: Суперкомпиляторы
От: Aikin Беларусь kavaleu.ru
Дата: 18.05.09 09:05
Оценка:
Здравствуйте, Константин, Вы писали:

S>>Понять, что в сценарии 3, когда приложение раскладывает исключительно степени двойки, суперкомпилятор это обнаружит, и оставит таблицу достаточно компактной.

К>Откуда он узнает, что я ему буду скармливать только степени двойки?
А разобраться в теме можно перед тем как в спор вступать?

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

Без дополнительной информации суперкомилятор может только исправить ошибки программиста либо поработать продвинутым, заточенным под задачу, но все же компилятором.




Даже убогая статья в вики пестрит этим:

Для суперкомпиляции хорошо подходят те програмы, которые используют стандартные библиотеки с открытым исходным кодом. Суперкомпилятор переписывает этот стандартный код, делая его эффективным для конкретных задач конкретной создаваемой программы, а также переписывает программу, чтобы более эффективно обращаться к суперкомпилированным процедурам.

Суперкомпилятор может помочь, если программа меняет приёмы своей работы по определённым параметрам. Например, предположим, что программа написана для общего случая и может работать по-разному при разных форматах базы данных. Если заранее известно, какая база данных будет использована, суперкомпиляция сделает программу намного эффективнее.


СУВ, Aikin
Re[16]: Суперкомпиляторы
От: thesz Россия http://thesz.livejournal.com
Дата: 18.05.09 09:16
Оценка: -1
T>>SPECfp — это бенчмарк такой. Он построен на реальном коде. В отличии от того, что пытаешься навязать ты (всем ходить ровно! FFT лежать в библиотеке!).

VD>Ну, так ты поделишься информацией о том, что демонстрируют тесты SPECfp для среднего ява-прогроммиста? Или ты не в курсе какой софт пишут на яве?


И измеряемый по SPECfp тоже.

Ещё раз повторю мой тезис.

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

Всё.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[17]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.05.09 11:38
Оценка: +1 -1
Здравствуйте, Курилка, Вы писали:

К>Странно, согласно математике, чтобы ускорение в 0 раз получить, надо чтобы после суперкомпиляции код выполнялся бесконечно долго

К>0 != 1

Больше не нашлось занятия нежели докапываться до слов?
Смысл сказанного был не ясен?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[17]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.05.09 11:44
Оценка: -2
Здравствуйте, thesz, Вы писали:

T>И измеряемый по SPECfp тоже.


Вот иди и почитай то на что даешь ссылки.

T>Ещё раз повторю мой тезис.


T>Практика проведения испытаний вычислительных комплексов (компилятор и вычислительная система) включает в себя и обработку (возможно, устаревшего или измененного) библиотечного кода.


T>Всё.


Засунь куда по дальше свои тезисы не относящиеся к делу.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[18]: Суперкомпиляторы
От: thesz Россия http://thesz.livejournal.com
Дата: 18.05.09 13:40
Оценка:
T>>И измеряемый по SPECfp тоже.

VD>Вот иди и почитай то на что даешь ссылки.


T>>Ещё раз повторю мой тезис.


T>>Практика проведения испытаний вычислительных комплексов (компилятор и вычислительная система) включает в себя и обработку (возможно, устаревшего или измененного) библиотечного кода.


T>>Всё.


VD>Засунь куда по дальше свои тезисы не относящиеся к делу.


Только после снятия тобой требования о нахождении FFT в библиотеке.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[14]: Суперкомпиляторы
От: Klapaucius  
Дата: 18.05.09 16:06
Оценка:
Здравствуйте, vdimas, Вы писали:

V>сразу навскидку char.IsDigit и int.Parse(charVar.ToString())


Не понимаю, в чем пойнт повторить сообщение, на которое я уже ответил
Автор: Klapaucius
Дата: 15.05.09
в другом форуме?
... << RSDN@Home 1.2.0 alpha 4 rev. 1110>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[14]: Суперкомпиляторы
От: Klapaucius  
Дата: 18.05.09 16:06
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Я думаю, что проблема там в том, что создается множество промежуточных объектов.


Ну это-то как раз очевидно.

VD>Использование итераторов приводит к этому на раз.


Только итераторы тут непричем, эти "промежуточные" объекты — замыкания лямбд. Итераторы там использованы в незначительном количестве и потому, в основном, что рекурсия переполняет стек.

VD>Где-то пробигали варианты Парсека написанные на Немерле. Там вместо итераторов использовались лямбды. Правда, там для получения конца строки используется метод Substring(), но это легко лечится.

VD>Можно провести сравнения.

Ну так там так и есть — просто ситуация с Substring уже вылечена.

VD>Лучше скажи, сколько они сливают? Не уж-то 50 процентов?


Haskell — 16.83 мб/c на ГГц
OCaml (быстрый) — 8.0
F# (монадический) — 2.34
OCaml (монадический) — 1.9
C# (оптимизированный) — 0.75
C# (первоначальный) — 0.06

Т.е. разница везде в разы, а не на проценты. Учитывая то, что на настоящий момент этот компилятор Хаскеля уже допотопный.

VD>В прочем, в любом случае такой код никто в реальной жизни использовать не будет.


Ну с той скоростью, которую дает C# — естественно. А с той скоростью, что дает GHC — может и будет.

VD>Не, так дело не пойдет. Доказывать корректность результатов должен тот, то их предлагает.


И каким образом это доказательство должно выглядеть? Я написал настолько аналогичный (и работающий при этом) код, насколько сумел. Это и есть мое доказательство — если я ошибся — пусть мне покажут где.

VD>Дык это уже не совсем комбинаторы. Это еще и наворот на итераторах.


Да нет там никаких особенных наворотов на итераторах.

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


В том и дело, что алгоритм один — а разница существенная.
... << RSDN@Home 1.2.0 alpha 4 rev. 1110>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[15]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.05.09 16:52
Оценка:
Здравствуйте, Klapaucius, Вы писали:

VD>>В прочем, в любом случае такой код никто в реальной жизни использовать не будет.


K>Ну с той скоростью, которую дает C# — естественно. А с той скоростью, что дает GHC — может и будет.


Если скорость важна, то разумный человек не будет использовать комбинаторный пасер вообще. Или напишет вручную, или сгенерирует с помощью построителей парсеров. Это по любому будет быстрее.

K>И каким образом это доказательство должно выглядеть? Я написал настолько аналогичный (и работающий при этом) код, насколько сумел. Это и есть мое доказательство — если я ошибся — пусть мне покажут где.


Я не настолько знаком с Хаскелем, чтобы проверять соответствие алгоритмов на нем.

K>Да нет там никаких особенных наворотов на итераторах.


Так удали их оттуда.

K>В том и дело, что алгоритм один — а разница существенная.


Вот в этом я не вполне уверен. Возможно как-то влияет ленивость хаскеля и он не выполняет некоторые действия. Возможно еще что-то...
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[15]: Суперкомпиляторы
От: vdimas Россия  
Дата: 18.05.09 17:23
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>Не понимаю, в чем пойнт повторить сообщение, на которое я уже ответил
Автор: Klapaucius
Дата: 15.05.09
в другом форуме?


быстрее отвечать надо
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[15]: Суперкомпиляторы
От: SmbdRsdn2  
Дата: 18.05.09 23:39
Оценка:
Здравствуйте, Klapaucius, Вы писали:


K>Haskell — 16.83 мб/c на ГГц

K>OCaml (быстрый) — 8.0
K>F# (монадический) — 2.34
K>OCaml (монадический) — 1.9
K>C# (оптимизированный) — 0.75
K>C# (первоначальный) — 0.06

Не подскажете, где взять вариант для F#?
Re[16]: Суперкомпиляторы
От: Klapaucius  
Дата: 19.05.09 09:00
Оценка:
Здравствуйте, SmbdRsdn2, Вы писали:

SR>Не подскажете, где взять вариант для F#?


Здесь
Автор: Schade
Дата: 02.03.08
... << RSDN@Home 1.2.0 alpha 4 rev. 1110>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[16]: Суперкомпиляторы
От: Klapaucius  
Дата: 19.05.09 09:00
Оценка:
Здравствуйте, VladD2, Вы писали:

K>>Ну с той скоростью, которую дает C# — естественно. А с той скоростью, что дает GHC — может и будет.

VD>Если скорость важна, то разумный человек не будет использовать комбинаторный пасер вообще. Или напишет вручную, или сгенерирует с помощью построителей парсеров. Это по любому будет быстрее.

Первое: К чему эти крайности? Случаи когда скорость вообще никакого значения не имеет и когда ради скорости нужно жертвовать всем как раз редки. Чаще всего скорость должна быть просто достаточной.
Главное: Мы говорим не о применимости комбинаторных парсеров на практике. Мы говорим о том, насколько дорого обходятся ФВП.
В данном случае комбинаторный парсер — просто бенчмарк, который показывает, что без специальных оптимизаций скорость будет существенно деградировать по мере увеличения "функциональности" кода.

K>>И каким образом это доказательство должно выглядеть? Я написал настолько аналогичный (и работающий при этом) код, насколько сумел. Это и есть мое доказательство — если я ошибся — пусть мне покажут где.

VD>Я не настолько знаком с Хаскелем, чтобы проверять соответствие алгоритмов на нем.

В таком случае, как я могу что-то доказать?

K>>Да нет там никаких особенных наворотов на итераторах.

VD>Так удали их оттуда.

Трудно удалить то, чего нет. Люк Хобан в своем фреймворке все итераторы (очень простые) сразу же форсирует и мемоизирует — в некоторых случаях может и зря — но чаще всего совершенно оправдано — без этого там асимптотика алгоритма серьезно изменилась бы в худшую сторону. Один из немногих итераторов, которые я использовал — эта замена кода на комбинаторах:
Numbers = Rep1(Number);

Потому, что таким кодом парсер просто переполняет все что может и падает.
Впечатление о том, что там много "наворотов на итераторах" создается потому, что linq query используется в качестве do-нотации, так как работает для любых монад — для парсеров в данном случае. Стоит внимательнее присмотреться и будет понятно, что никаких "наворотов на итераторах" там нет.

VD>Возможно как-то влияет ленивость хаскеля и он не выполняет некоторые действия.


Естественно. Код ленивый и там и там, просто в Haskell ленивость поддерживается лучше. Т.е. чем "функциональнее" код — тем быстрее он работает в Haskell по сравнению с F#, OCaml, C#.
... << RSDN@Home 1.2.0 alpha 4 rev. 1110>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[17]: Суперкомпиляторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 19.05.09 14:49
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>Первое: К чему эти крайности? Случаи когда скорость вообще никакого значения не имеет и когда ради скорости нужно жертвовать всем как раз редки. Чаще всего скорость должна быть просто достаточной.


Так и есть. Только парсинг обычно используется для создания компиляторов или интерпретатров ЯП. И скорость парсинга становится весьма важным фактором. Ведь быстрее парсер, бысрее компилятора и интеграция с IDE. А раз так, то выше интерактивность разработки на новом языке.

Я не утверждаю, что это самый важный фактор, но это один из важных факторов.

K>Главное: Мы говорим не о применимости комбинаторных парсеров на практике. Мы говорим о том, насколько дорого обходятся ФВП.


Я согласен, что они не бесплатны. Но я не уверен, что этот пример показателен.

K>В данном случае комбинаторный парсер — просто бенчмарк, который показывает, что без специальных оптимизаций скорость будет существенно деградировать по мере увеличения "функциональности" кода.


Дык я как раз и привел устранение ВФП и замыканий, как пример области где спер-компиляция была бы весьма кстати. Только ждать от этого 50 (и тем более 500) раз в общем случае не стоит. В лучшем случае скорость всей программы увеличится в разы. Но и это уже было бы не плохо.
Тут важна даже не сама скорость, а отстутствие платы за абстракцию. Если Fold, Map и т.п. в большинстве случаев случаев превратится в циклы, то их можно будет использовать в большем числе мест. А это уже плюс.

K>В таком случае, как я могу что-то доказать?


Нужно попытаться вычленить то что по твоему мнению является проблемой и попытаться сравнить только эти аспекты. Задача не простая, так как синтетические тесты проще оптимизируются. Но подъемная.

Как вариант привести вместе каждую функцию, чтобы было проще сравнивать.

В общем, старые добрые научные методы исследования .

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


Итераторы всегда можно заменить на косвенный вызов (указатели на функции).

K>Впечатление о том, что там много "наворотов на итераторах" создается потому, что linq query используется в качестве do-нотации, так как работает для любых монад — для парсеров в данном случае. Стоит внимательнее присмотреться и будет понятно, что никаких "наворотов на итераторах" там нет.


Ну, а кто гарантирует, что проблемы вызваны делегатами, а не итераторами? А без этого все рассуждения довольно бессмысленны. Мы можем констатировать, что код на Шарпе не эффективный. Но не можем ничего сказать конкретно.

K>Естественно. Код ленивый и там и там, просто в Haskell ленивость поддерживается лучше. Т.е. чем "функциональнее" код — тем быстрее он работает в Haskell по сравнению с F#, OCaml, C#.


Не "чем функциональнее", а "чем больше он полагается на ленивость". В прочем было бы странно если бы в компиляторах самого функционального языка не было бы сделано оптимизаций для функциональшины.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[14]: Суперкомпиляторы
От: Sinclair Россия https://github.com/evilguest/
Дата: 20.05.09 11:08
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Ты говорил о 50-кратном увеличении производительности в общем случае.

А можно цитату, где я это говорил? Я говорил о том, что в частных случаях ускорение в 50 раз возможно безо всяких чудес. Еще раз повторяю: для общего случая добиться гарантированной оптимизации в приципе невозможно. Доказательство этого строится аналогично доказательству невозможности вечного двигателя, и точно так же не требует анализа конкретного оптимизатора. Поэтому лично мне непонятно, зачем мы вообще об этом говорим.

VD>Вот это и должно быть заботой библиотеки.

Непонятно, каким образом предполагается это сделать. У библиотеки банально нет данных про то, с какими параметрами ее будут вызывать.

VD>А затачивать компилятор под конеретный, частный случай не очень то разумно.

Компилятор под конкретный случай никто затачивать и не собирается. Под конкретный случай затачивается программа, причем не вручную, а автоматически.
Непонятно твоё нежелание прочитать пятистраничную статью.

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

Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[10]: Суперкомпиляторы
От: Sinclair Россия https://github.com/evilguest/
Дата: 20.05.09 11:12
Оценка:
Здравствуйте, Константин, Вы писали:


К>Домашнее задание: оценить размер базы данных с разложениями чисел от 1 до 10^20. Предположим суперкомпилятор посчитал (интересно как ), что это будет оптимально для ускорения в 10^10 раз.

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

К>Не знаю. Но где моё обещанное ускорение в 50, 10^6 раз?

На месте.

К>Я называю жульничеcтвом твой пример, который не имеет никакого отношения к суперкомпиляции. Ты же предложил вычисление первых n чисел.

Ну как это не имеет. Это один из частных случаев суперкомпиляции.

К>Откуда он узнает, что я ему буду скармливать только степени двойки?

Из процесса суперкомпиляции, который состоит в исполнении программы. И из этого процесса видно, какие ветки кода вызываются, а какие нет. Если интересно — почитай введение в суперкомпиляцию, ссылку здесь давали, там всё написано очень подробно.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[11]: Суперкомпиляторы
От: CreatorCray  
Дата: 20.05.09 13:22
Оценка:
Здравствуйте, Sinclair, Вы писали:

К>>Откуда он узнает, что я ему буду скармливать только степени двойки?

S>Из процесса суперкомпиляции, который состоит в исполнении программы. И из этого процесса видно, какие ветки кода вызываются, а какие нет. Если интересно — почитай введение в суперкомпиляцию, ссылку здесь давали, там всё написано очень подробно.

Хм. Что то мне это напоминает такой байан как

Profile-guided Optimization (PGO) improves application performance by reorganizing code layout to reduce instruction-cache problems, shrinking code size, and reducing branch mispredictions. PGO provides information to the compiler about areas of an application that are most frequently executed. By knowing these areas, the compiler is able to be more selective and specific in optimizing the application.

PGO consists of three phases or steps.

Step one is to instrument the program. In this phase, the compiler creates and links an instrumented program from your source code and special code from the compiler.

Step two is to run the instrumented executable. Each time you execute the instrumented code, the instrumented program generates a dynamic information file, which is used in the final compilation.

Step three is a final compilation. When you compile a second time, the dynamic information files are merged into a summary file. Using the summary of the profile information in this file, the compiler attempts to optimize the execution of the most heavily traveled paths in the program.

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[12]: Суперкомпиляторы
От: Курилка Россия http://kirya.narod.ru/
Дата: 20.05.09 14:32
Оценка:
Здравствуйте, CreatorCray, Вы писали:

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


К>>>Откуда он узнает, что я ему буду скармливать только степени двойки?

S>>Из процесса суперкомпиляции, который состоит в исполнении программы. И из этого процесса видно, какие ветки кода вызываются, а какие нет. Если интересно — почитай введение в суперкомпиляцию, ссылку здесь давали, там всё написано очень подробно.

CC>Хм. Что то мне это напоминает такой байан как

CC>

CC>Profile-guided Optimization (PGO)...


Сдаётся мне, что суперкомпиляция Турчина побоянистей будет (вроде в 70-е он начал этим заниматься), а до него ещё можно Футамуру спомнить (как Дэн Пипони недавно вспоминал) и смешанные вычисления Ершова.
Правда разница между PGO и выше приведёнными подходами, что PGO — вещь статистическая (насколько я понимаю), тогда как суперкомиляция и подобные подходы оперируют исходным кодом.
Re[13]: Суперкомпиляторы
От: CreatorCray  
Дата: 20.05.09 14:43
Оценка:
Здравствуйте, Курилка, Вы писали:

К>Сдаётся мне, что суперкомпиляция Турчина побоянистей будет (вроде в 70-е он начал этим заниматься), а до него ещё можно Футамуру спомнить (как Дэн Пипони недавно вспоминал) и смешанные вычисления Ершова.

Так то теория а PGO уже достаточно давно практика.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[12]: Суперкомпиляторы
От: thesz Россия http://thesz.livejournal.com
Дата: 20.05.09 14:51
Оценка:
К>>>Откуда он узнает, что я ему буду скармливать только степени двойки?
S>>Из процесса суперкомпиляции, который состоит в исполнении программы. И из этого процесса видно, какие ветки кода вызываются, а какие нет. Если интересно — почитай введение в суперкомпиляцию, ссылку здесь давали, там всё написано очень подробно.
CC>Хм. Что то мне это напоминает такой байан как
CC>

CC>Profile-guided Optimization (PGO)


Nope. Суперкомпилятор может вообще убрать обработку определённых вариантов входных данных процесса, а PGO может только уменьшить их влияние на производительность.

Суперкомпиляция не отменяет последующего PGO, да и сама может использовать результаты прогонов.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[13]: Суперкомпиляторы
От: FR  
Дата: 20.05.09 15:40
Оценка: +1
Здравствуйте, thesz, Вы писали:

T>Nope. Суперкомпилятор может вообще убрать обработку определённых вариантов входных данных процесса, а PGO может только уменьшить их влияние на производительность.


T>Суперкомпиляция не отменяет последующего PGO, да и сама может использовать результаты прогонов.


Ну PGO в нектором смысле тоже разновидность суперкомпиляции.
Re[14]: Суперкомпиляторы
От: Sinclair Россия https://github.com/evilguest/
Дата: 21.05.09 09:00
Оценка:
Здравствуйте, FR, Вы писали:

FR>Ну PGO в нектором смысле тоже разновидность суперкомпиляции.

Совершенно верно — они все близкие родственники: PGO, supercompilation, hotspotting.
Основное отличие SC от HS и PGO, как я понял — в том, что она пытается доказать несколько более широкий класс утверждений. То есть PGO и HS занимаются [iспекулятивной[/i] оптимизацией, основываясь на наблюдаемой статистике. А SC пытается устранить гарантированно недостижимые ветки кода с учетом глобальной информации.
Рассмотрим вот такой пример кода:

private Test()
{
  ITest test = new SpecificTest();
  Console.WriteLn(test.Check(8));
}
public class SpecificTest: ITest
{
  public int Check(int a)
  {
    if (a%2 == 0)
      return a+1
    else
      return a/2;
  }
}

Безо всякой помощи профайлера, достойный компилятор может вывести точный тип переменной test, устранить виртуальность, выполнить инлайнинг, провести constant propagation, выбросить unreachable code и свести программу к Console.WriteLn(4). В управляемом случае действия, кроме первых двух, переносятся на JIT.
Возьмем более интересный случай:
private Test(Type t)
{
  ITest test = (ITest)Activator.CreateInstance(t);
  Console.WriteLn(test.Check(8));
}

Здесь классическому компилятору делать нечего. Hotspotting или PGO могут обнаружить, что как правило в test попадает SpecificTest, и впендюрить спекулятивный инлайнинг с guard-ом. Типа вот такого:
private Test(Type t)
{
  if(t.GetType() == typeof(SpecificTest)
    Console.WriteLn(4);
  else
  {
    ITest test = (ITest)Activator.CreateInstance(t);
    Console.WriteLn(test.Check(8));
  }
}

Для того, чтобы PGO помогло совсем устранить else-ветку, этот код должен быть заинлайнен туда, откуда вызывается метод Test(), и там уже надо выполнять локальную оптимизацию с учетом constant propagation и прочими чудесами науки и техники. SC, по идее, имеет больше возможностей на эту тему, т.к. старается собирать глобальную статистику (а не просто локальные счётчики посещаемости строчек). В остальном она до боли похожа на PGO — опять исполнение программы под супервизором, наблюдение за поведением и сбор данных.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[4]: Суперкомпиляторы
От: Sergei Romanenko Россия http://pat.keldysh.ru/~roman/
Дата: 08.06.09 09:45
Оценка:
Здравствуйте, Красин, Вы писали:

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


DS>>Для Явы делают суперкомпилятор. Пишут, что увеличивает скорость до 50 раз.


К>Ссылочку можно? Я пока нашел эту, с указанием "The Java Supercompiler Version 1 is scheduled for completion in late 2003." без какой-либо ссылки на скачку и эту, где предлагается скачать альфа-версию, датированную 2008 годом (причем, судя по CHANGELOG, за последние 5 лет там поменялось всего несколько строк).


Можно почитать вот этот тред по поводу состояния дел с Java-суперкомпилятором: Java-суперкомпилятор
Re: Веб-ресурсы, связанные с суперкомпиляцией
От: Sergei Romanenko Россия http://pat.keldysh.ru/~roman/
Дата: 08.06.09 10:26
Оценка: 92 (9)
Здравствуйте, DSblizzard, Вы писали:

DS>1) Сколько времени и памяти занимает суперкомпиляция по сравнению с обычной компиляцией? Насколько больше по размеру программа после суперкомпиляции?

DS>2) Говорят, частичные вычисления не дружат с побочными эффектами. Насчет суперкомпиляции это тоже верно?
DS>3) Как вы думаете, почему суперкомпиляторы не входили в мэйнстрим и до сих пор бы не вошли, если бы этим не занялся сам Турчин? Только из-за сложности реализации?

На такие вопросы в двух словах ответить невозможно... Поэтому, я решил создать блог


и в нём попытаться написать о состоянии дел с суперкомпиляции. (Включая и такие подробности, о которых обычно умалчивают в "научных" статьях.) Пока что, в этот блог послания отправлял только я, но у блога несколько "авторов", и желающие в нём что-то выставить — приглашаются.

Есть возможность записываться и в "друзья" блога (по-английски это называется followers). Для этого вверху надо кликнуть по надписи "follow blog". После этого можно будет отслеживать, что происходит в блоге через Google Reader.

Также существует и группы


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

Другой вопрос: а есть ли возможность "пощупать" суперкомпиляторы "вживую"? Чтобы у "простого народа" была возможность "потыкать ломиком" в суперкомпиляторы, мы (я + Илья Ключников), выставили через веб-интерфейс на растерзание публике два суперкомпилятора


Первый из них (SPSC) обрабатывает программы на функциональном языке первого порядка (не ленивом), а второй (HOSC) — на ленивом функциональном языке с функциями высших порядков. Веб-приложения, через которые доступны эти суперкомпиляторы, находятся здесь:


Можно посмотреть заранее заготовленные задания на суперкомпиляцию, а можно добавить и свои задания. Для этого требуется иметь Гугл-аккаунт и сделать Sign in в веб-приложения.

В Гугл-коде также выставлены и исходные тексты специализатора (частичного вычислителя) Unmix:


Версия работает, если её запускать через Guile (одна из реализаций Scheme). Но сайт проекта должным образом пока не оформлен (в вики ещё нет ни одной страницы). Но среди исходных текстов есть текстовые файлы, которые содержат кое-какую документацию.
Re[2]: Веб-ресурсы, связанные с суперкомпиляцией
От: Sergei Romanenko Россия http://pat.keldysh.ru/~roman/
Дата: 11.09.09 09:44
Оценка: 17 (3)
Здравствуйте, Sergei Romanenko, Вы писали:

SR>Другой вопрос: а есть ли возможность "пощупать" суперкомпиляторы "вживую"? Чтобы у "простого народа" была возможность "потыкать ломиком" в суперкомпиляторы, мы (я + Илья Ключников), выставили через веб-интерфейс на растерзание публике два суперкомпилятора



Кстати, для желающих поковыряться в исходных текстах.

SPSC = "a Simple Supercompiler", минималистский суперкомпилятор.

SPSC Lite — это минималистская версия минималистского суперкомпилятора SPSC. Может
быть полезна для изучения основных алгоритмов суперкомпиляции и как
исходная точка для экспериментирования с суперкомпиляцией.

В настоящий момент имеются 4 версии SPSC Lite на следующих языках:

суперкомпилятор суперкомпиляция scala haskell python ruby
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.