1) Сколько времени и памяти занимает суперкомпиляция по сравнению с обычной компиляцией? Насколько больше по размеру программа после суперкомпиляции?
2) Говорят, частичные вычисления не дружат с побочными эффектами. Насчет суперкомпиляции это тоже верно?
3) Как вы думаете, почему суперкомпиляторы не входили в мэйнстрим и до сих пор бы не вошли, если бы этим не занялся сам Турчин? Только из-за сложности реализации?
Программировать сложно. Но не программировать еще сложнее.
Здравствуйте, DSblizzard, Вы писали:
DS>3) Как вы думаете, почему суперкомпиляторы не входили в мэйнстрим и до сих пор бы не вошли, если бы этим не занялся сам Турчин? Только из-за сложности реализации?
Здравствуйте, DSblizzard, Вы писали:
DS>Для Явы делают суперкомпилятор. Пишут, что увеличивает скорость до 50 раз.
Ссылочку можно? Я пока нашел эту, с указанием "The Java Supercompiler Version 1 is scheduled for completion in late 2003." без какой-либо ссылки на скачку и эту, где предлагается скачать альфа-версию, датированную 2008 годом (причем, судя по CHANGELOG, за последние 5 лет там поменялось всего несколько строк).
Здравствуйте, DSblizzard, Вы писали:
DS>1) Сколько времени и памяти занимает суперкомпиляция по сравнению с обычной компиляцией? Насколько больше по размеру программа после суперкомпиляции? DS>2) Говорят, частичные вычисления не дружат с побочными эффектами. Насчет суперкомпиляции это тоже верно? DS>3) Как вы думаете, почему суперкомпиляторы не входили в мэйнстрим и до сих пор бы не вошли, если бы этим не занялся сам Турчин? Только из-за сложности реализации?
Просветите меня что это такое, с чем едят и зачем надо?
Здравствуйте, Tom, Вы писали:
DS>>1) Сколько времени и памяти занимает суперкомпиляция по сравнению с обычной компиляцией? Насколько больше по размеру программа после суперкомпиляции?
… Tom>Просветите меня что это такое, с чем едят и зачем надо?
Здравствуйте, VladD2, Вы писали:
VD>Чудес не бывает, чтобы получить выигрыш в 50 раз нужно исходно иметь огромные алгоритмические проблемы и искусственный интеллект который их исправит.
Да ладно. Никакого предела ускорению программ путём суперкомпиляции нету. Привожу простой пример: делаем разложение чисел на простые множители.
Обычный компилятор компиляет алгоритм, который получает O(exp(N)).
Суперкомпилятор запускает этот алгоритм на первом миллионе чисел и строит таблицу.
В итоге, для чисел в пределах первого миллиона результат суперкомпилированной программы работает за O(1). Поделив время работы первого варианта для достаточно большого числа K на это O(1), можно получить ускорение и в миллион раз. Никаких фундаментальных проблем нет.
Нужно просто понимать, что речь идет о частичных вычислениях. А они применимы далеко не всегда — если нужно раскладывать числа за пределами первого миллиона, вторая программа будет ничуть не лучше первой.
Так что всё, что может сделать суперкомпилятор — это
а) устранить заведомо избыточную обобщённость (типична для суперумных библиотек на все случаи жизни, которые реально в конкретной программе используются в небольшом количестве сценариев)
б) провести спекулятивное устранение обобщённости (с этим сложнее, потому что нужно знать распределение значений входных параметров. И если в нём нет особенных неравномерностей, то ничего интересного суперкомпилятор не даст)
В принципе, на локальном уровне этим уже занимаются современные компиляторы, особенно для неуправляемых языков. Суперкомпиляторы претендуют на глобальный уровень, только и всего.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Да ладно. Никакого предела ускорению программ путём суперкомпиляции нету. Привожу простой пример: делаем разложение чисел на простые множители. S>Обычный компилятор компиляет алгоритм, который получает O(exp(N)).
То есть исходно мы имеем супер-нееэффективный алгоритм и путем его переписывания в эффективный получаем значительное ускорение?
Поделись тем как такой подход можно обобщить. Иначе это и есть частный случай.
S>Суперкомпилятор запускает этот алгоритм на первом миллионе чисел и строит таблицу. S>В итоге, для чисел в пределах первого миллиона результат суперкомпилированной программы работает за O(1). Поделив время работы первого варианта для достаточно большого числа K на это O(1), можно получить ускорение и в миллион раз. Никаких фундаментальных проблем нет.
Гы-гы. Кремлевский мечтатель. Представим что у алгоритма есть 10 параметров или 2 но с очень большими значениями. В итоге мы получаем или многомерную структуру неопределенного размера стремящуюся к бесконечности, или двухмерную но тоже вылезающую за память компьюетра.
В общем, это все мечты. Если алгоритм исходно оптимальный, то никакие суперкомпиляторы его не ускорят (а замедлить могут).
Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга.
S>Нужно просто понимать, что речь идет о частичных вычислениях. А они применимы далеко не всегда — если нужно раскладывать числа за пределами первого миллиона, вторая программа будет ничуть не лучше первой.
Нужно понимать, что частные оптимизации мало интересны, так как устанешь затачивать под них компилятор.
То что ты описал влет оптимизируется путем тупой мемоизации (в том же Немерле — это ровно один атрибут на метод повесть).
S>Так что всё, что может сделать суперкомпилятор — это S>а) устранить заведомо избыточную обобщённость (типична для суперумных библиотек на все случаи жизни, которые реально в конкретной программе используются в небольшом количестве сценариев) S>б) провести спекулятивное устранение обобщённости (с этим сложнее, потому что нужно знать распределение значений входных параметров. И если в нём нет особенных неравномерностей, то ничего интересного суперкомпилятор не даст)
S>В принципе, на локальном уровне этим уже занимаются современные компиляторы, особенно для неуправляемых языков. Суперкомпиляторы претендуют на глобальный уровень, только и всего.
Ну, и как добиться ускорения в 50 раз?
Я вижу только один способ — писать чудовищно бездарный код и очень умный компилятор.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга.
a)Это неверный подход изначально. Ускорять можно не алгоритм, а реализацию. Ты предлагаешь оптимизировать генеренный машиной код. Если он написан человеком, то чаще может быть оптимизирован(как в рамках суперкомпиляции, так и без оной)
б)В случае если есть неиспользуемые AST-tree ноды, то зачем из создавать? Не проще ли пропустить?
S>>Нужно просто понимать, что речь идет о частичных вычислениях. А они применимы далеко не всегда — если нужно раскладывать числа за пределами первого миллиона, вторая программа будет ничуть не лучше первой. VD>Нужно понимать, что частные оптимизации мало интересны, так как устанешь затачивать под них компилятор.
Аднако в этом весь смысл. Правда никто и не говорит что в данный момент суперкомпиляторы есть кул. С наполнением алгоритмами оптимизации туговато... Во многом эти алгоритмы NP-задачи. Sinclair — правду молвит о проблеме нынешней применимости.
VD>То что ты описал влет оптимизируется путем тупой мемоизации (в том же Немерле — это ровно один атрибут на метод повесть).
Это не оптимизация. Это декларативное указание алгоритма выполнения
VD>Ну, и как добиться ускорения в 50 раз? VD>Я вижу только один способ — писать чудовищно бездарный код и очень умный компилятор.
Если посмотреть на обобщенности современных библиотек, которые умеют все, и гладить и вышивать, частные случаи подобной оптимизации — возможны. Ну к примеру, оптимизировать Linq to entities запросы. Другой вопрос — нужны ли если производительность в подавляющем случае достаточна?
Здравствуйте, 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>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
VD>>То что ты описал влет оптимизируется путем тупой мемоизации (в том же Немерле — это ровно один атрибут на метод повесть). S>Нет, не всё. Речь же не просто о перечислении значений параметров. К примеру, если известно, что параметром некоторого floating-point алгоритма всегда будут целые числа, то частенько можно его подкрутить так, чтобы он был быстрее. Никакая мемоизация тут не спасёт.
Здравствуйте, 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-я и паттер-матчинга. Где можно его уже применяют. А в общем случае проекты вроде суперкомпиляторов для Явы просто дохнут ничем не закончившись. По всей видимости выхлоп не соответствует ожиданиям и авторы холодеют к данному подходу.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, GlebZ, Вы писали:
VD>>Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга. GZ>a)Это неверный подход изначально. Ускорять можно не алгоритм, а реализацию. Ты предлагаешь оптимизировать генеренный машиной код. Если он написан человеком, то чаще может быть оптимизирован(как в рамках суперкомпиляции, так и без оной) GZ>б)В случае если есть неиспользуемые AST-tree ноды, то зачем из создавать? Не проще ли пропустить?
Я привел пример алгоритма который давно известно как реализовать весьма эффективно. И будучи эффективно реализованным его хрена два соптимизируешь.
GZ>Аднако в этом весь смысл. Правда никто и не говорит что в данный момент суперкомпиляторы есть кул. С наполнением алгоритмами оптимизации туговато... Во многом эти алгоритмы NP-задачи. Sinclair — правду молвит о проблеме нынешней применимости.
Это все мечтания. Я не спорю, что для некоторых задач (вроде переписывания замыканий и ФВП в циклы) суперкомпиляция отличный алгоритм оптимизации, но никаких 50 раз в общем случае дабиться не получится. Это просто выдумки. Разы будет уже хорошо. Да и то в частном случае.
VD>>То что ты описал влет оптимизируется путем тупой мемоизации (в том же Немерле — это ровно один атрибут на метод повесть). GZ>Это не оптимизация. Это декларативное указание алгоритма выполнения
Синклер привел примет того, что отлично оптимизируется этим метдом. Я ответил, что для данного случая есть в тысячи раз более простое решение.
VD>>Ну, и как добиться ускорения в 50 раз? VD>>Я вижу только один способ — писать чудовищно бездарный код и очень умный компилятор. GZ>Если посмотреть на обобщенности современных библиотек, которые умеют все, и гладить и вышивать, частные случаи подобной оптимизации — возможны. Ну к примеру, оптимизировать Linq to entities запросы. Другой вопрос — нужны ли если производительность в подавляющем случае достаточна?
ОК. Возьмем линк. Что там можно оптимизировать если запрос должен в рантайме превратиться в SQL?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
