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.

Что в них не ясно? Или просто захотелось поговорить?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.