Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, VoidEx, Вы писали:
VD>>>Да, я принципиально не верю в чудеса. На практике вместо 50 раз будет 1-2, в в большинстве случаев ~0. VE>>~0 обоснуешь?
VD>Элементарно. В коде просто не будет паттернов которые запрограмирован изводить суперкомпилятор.
Странно, согласно математике, чтобы ускорение в 0 раз получить, надо чтобы после суперкомпиляции код выполнялся бесконечно долго
0 != 1
Здравствуйте, 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, когда приложение раскладывает исключительно степени двойки, суперкомпилятор это обнаружит, и оставит таблицу достаточно компактной.
Откуда он узнает, что я ему буду скармливать только степени двойки?
Здравствуйте, Константин, Вы писали:
S>>Понять, что в сценарии 3, когда приложение раскладывает исключительно степени двойки, суперкомпилятор это обнаружит, и оставит таблицу достаточно компактной. К>Откуда он узнает, что я ему буду скармливать только степени двойки?
А разобраться в теме можно перед тем как в спор вступать?
Ты говоришь суперкомпилятору, что будешь работать только со степенями двойки и на основании этих данных произойдет суперкомпиляция.
Без дополнительной информации суперкомилятор может только исправить ошибки программиста либо поработать продвинутым, заточенным под задачу, но все же компилятором.
Для суперкомпиляции хорошо подходят те програмы, которые используют стандартные библиотеки с открытым исходным кодом. Суперкомпилятор переписывает этот стандартный код, делая его эффективным для конкретных задач конкретной создаваемой программы, а также переписывает программу, чтобы более эффективно обращаться к суперкомпилированным процедурам.
Суперкомпилятор может помочь, если программа меняет приёмы своей работы по определённым параметрам. Например, предположим, что программа написана для общего случая и может работать по-разному при разных форматах базы данных. Если заранее известно, какая база данных будет использована, суперкомпиляция сделает программу намного эффективнее.
T>>SPECfp — это бенчмарк такой. Он построен на реальном коде. В отличии от того, что пытаешься навязать ты (всем ходить ровно! FFT лежать в библиотеке!).
VD>Ну, так ты поделишься информацией о том, что демонстрируют тесты SPECfp для среднего ява-прогроммиста? Или ты не в курсе какой софт пишут на яве?
Практика проведения испытаний вычислительных комплексов (компилятор и вычислительная система) включает в себя и обработку (возможно, устаревшего или измененного) библиотечного кода.
Всё.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, Курилка, Вы писали:
К>Странно, согласно математике, чтобы ускорение в 0 раз получить, надо чтобы после суперкомпиляции код выполнялся бесконечно долго К>0 != 1
Больше не нашлось занятия нежели докапываться до слов?
Смысл сказанного был не ясен?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Вот иди и почитай то на что даешь ссылки.
T>Ещё раз повторю мой тезис.
T>Практика проведения испытаний вычислительных комплексов (компилятор и вычислительная система) включает в себя и обработку (возможно, устаревшего или измененного) библиотечного кода.
T>Всё.
Засунь куда по дальше свои тезисы не относящиеся к делу.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
T>>И измеряемый по SPECfp тоже.
VD>Вот иди и почитай то на что даешь ссылки.
T>>Ещё раз повторю мой тезис.
T>>Практика проведения испытаний вычислительных комплексов (компилятор и вычислительная система) включает в себя и обработку (возможно, устаревшего или измененного) библиотечного кода.
T>>Всё.
VD>Засунь куда по дальше свои тезисы не относящиеся к делу.
Только после снятия тобой требования о нахождении FFT в библиотеке.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, VladD2, Вы писали:
VD>Я думаю, что проблема там в том, что создается множество промежуточных объектов.
Ну это-то как раз очевидно.
VD>Использование итераторов приводит к этому на раз.
Только итераторы тут непричем, эти "промежуточные" объекты — замыкания лямбд. Итераторы там использованы в незначительном количестве и потому, в основном, что рекурсия переполняет стек.
VD>Где-то пробигали варианты Парсека написанные на Немерле. Там вместо итераторов использовались лямбды. Правда, там для получения конца строки используется метод Substring(), но это легко лечится. VD>Можно провести сравнения.
Ну так там так и есть — просто ситуация с Substring уже вылечена.
VD>Лучше скажи, сколько они сливают? Не уж-то 50 процентов?
Т.е. разница везде в разы, а не на проценты. Учитывая то, что на настоящий момент этот компилятор Хаскеля уже допотопный.
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
Здравствуйте, Klapaucius, Вы писали:
VD>>В прочем, в любом случае такой код никто в реальной жизни использовать не будет.
K>Ну с той скоростью, которую дает C# — естественно. А с той скоростью, что дает GHC — может и будет.
Если скорость важна, то разумный человек не будет использовать комбинаторный пасер вообще. Или напишет вручную, или сгенерирует с помощью построителей парсеров. Это по любому будет быстрее.
K>И каким образом это доказательство должно выглядеть? Я написал настолько аналогичный (и работающий при этом) код, насколько сумел. Это и есть мое доказательство — если я ошибся — пусть мне покажут где.
Я не настолько знаком с Хаскелем, чтобы проверять соответствие алгоритмов на нем.
K>Да нет там никаких особенных наворотов на итераторах.
Так удали их оттуда.
K>В том и дело, что алгоритм один — а разница существенная.
Вот в этом я не вполне уверен. Возможно как-то влияет ленивость хаскеля и он не выполняет некоторые действия. Возможно еще что-то...
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, 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
Здравствуйте, Klapaucius, Вы писали:
K>Первое: К чему эти крайности? Случаи когда скорость вообще никакого значения не имеет и когда ради скорости нужно жертвовать всем как раз редки. Чаще всего скорость должна быть просто достаточной.
Так и есть. Только парсинг обычно используется для создания компиляторов или интерпретатров ЯП. И скорость парсинга становится весьма важным фактором. Ведь быстрее парсер, бысрее компилятора и интеграция с IDE. А раз так, то выше интерактивность разработки на новом языке.
Я не утверждаю, что это самый важный фактор, но это один из важных факторов.
K>Главное: Мы говорим не о применимости комбинаторных парсеров на практике. Мы говорим о том, насколько дорого обходятся ФВП.
Я согласен, что они не бесплатны. Но я не уверен, что этот пример показателен.
K>В данном случае комбинаторный парсер — просто бенчмарк, который показывает, что без специальных оптимизаций скорость будет существенно деградировать по мере увеличения "функциональности" кода.
Дык я как раз и привел устранение ВФП и замыканий, как пример области где спер-компиляция была бы весьма кстати. Только ждать от этого 50 (и тем более 500) раз в общем случае не стоит. В лучшем случае скорость всей программы увеличится в разы. Но и это уже было бы не плохо.
Тут важна даже не сама скорость, а отстутствие платы за абстракцию. Если Fold, Map и т.п. в большинстве случаев случаев превратится в циклы, то их можно будет использовать в большем числе мест. А это уже плюс.
K>В таком случае, как я могу что-то доказать?
Нужно попытаться вычленить то что по твоему мнению является проблемой и попытаться сравнить только эти аспекты. Задача не простая, так как синтетические тесты проще оптимизируются. Но подъемная.
Как вариант привести вместе каждую функцию, чтобы было проще сравнивать.
В общем, старые добрые научные методы исследования .
K>Трудно удалить то, чего нет. Люк Хобан в своем фреймворке все итераторы (очень простые) сразу же форсирует и мемоизирует — в некоторых случаях может и зря — но чаще всего совершенно оправдано — без этого там асимптотика алгоритма серьезно изменилась бы в худшую сторону.
Итераторы всегда можно заменить на косвенный вызов (указатели на функции).
K>Впечатление о том, что там много "наворотов на итераторах" создается потому, что linq query используется в качестве do-нотации, так как работает для любых монад — для парсеров в данном случае. Стоит внимательнее присмотреться и будет понятно, что никаких "наворотов на итераторах" там нет.
Ну, а кто гарантирует, что проблемы вызваны делегатами, а не итераторами? А без этого все рассуждения довольно бессмысленны. Мы можем констатировать, что код на Шарпе не эффективный. Но не можем ничего сказать конкретно.
K>Естественно. Код ленивый и там и там, просто в Haskell ленивость поддерживается лучше. Т.е. чем "функциональнее" код — тем быстрее он работает в Haskell по сравнению с F#, OCaml, C#.
Не "чем функциональнее", а "чем больше он полагается на ленивость". В прочем было бы странно если бы в компиляторах самого функционального языка не было бы сделано оптимизаций для функциональшины.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Ты говорил о 50-кратном увеличении производительности в общем случае.
А можно цитату, где я это говорил? Я говорил о том, что в частных случаях ускорение в 50 раз возможно безо всяких чудес. Еще раз повторяю: для общего случая добиться гарантированной оптимизации в приципе невозможно. Доказательство этого строится аналогично доказательству невозможности вечного двигателя, и точно так же не требует анализа конкретного оптимизатора. Поэтому лично мне непонятно, зачем мы вообще об этом говорим.
VD>Вот это и должно быть заботой библиотеки.
Непонятно, каким образом предполагается это сделать. У библиотеки банально нет данных про то, с какими параметрами ее будут вызывать.
VD>А затачивать компилятор под конеретный, частный случай не очень то разумно.
Компилятор под конкретный случай никто затачивать и не собирается. Под конкретный случай затачивается программа, причем не вручную, а автоматически.
Непонятно твоё нежелание прочитать пятистраничную статью.
VD>Это специально подобранная программа демонстрирующая нужные результаты. Вот пусть тот же компилятор Явы перекомпилируют и сравнят его скорость со скоростью не оптимизированного варианта. Тогда это будет интересно. А то мне как то ни горяче, ни холодно от того как ускоряется Фурье, если мой код не ускоряется.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
К>Домашнее задание: оценить размер базы данных с разложениями чисел от 1 до 10^20. Предположим суперкомпилятор посчитал (интересно как ), что это будет оптимально для ускорения в 10^10 раз.
Вот давай сначала обоснуем это предположение, а потом будем оценивать. Потому что с тем же успехом можно напредполагать вообще любую херню про поведение суперкомпилятора, а потом из нее выводить всё что угодно.
К>Не знаю. Но где моё обещанное ускорение в 50, 10^6 раз?
На месте.
К>Я называю жульничеcтвом твой пример, который не имеет никакого отношения к суперкомпиляции. Ты же предложил вычисление первых n чисел.
Ну как это не имеет. Это один из частных случаев суперкомпиляции.
К>Откуда он узнает, что я ему буду скармливать только степени двойки?
Из процесса суперкомпиляции, который состоит в исполнении программы. И из этого процесса видно, какие ветки кода вызываются, а какие нет. Если интересно — почитай введение в суперкомпиляцию, ссылку здесь давали, там всё написано очень подробно.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, 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.
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, Sinclair, Вы писали:
К>>>Откуда он узнает, что я ему буду скармливать только степени двойки? S>>Из процесса суперкомпиляции, который состоит в исполнении программы. И из этого процесса видно, какие ветки кода вызываются, а какие нет. Если интересно — почитай введение в суперкомпиляцию, ссылку здесь давали, там всё написано очень подробно.
CC>Хм. Что то мне это напоминает такой байан как CC>
CC>Profile-guided Optimization (PGO)...
Сдаётся мне, что суперкомпиляция Турчина побоянистей будет (вроде в 70-е он начал этим заниматься), а до него ещё можно Футамуру спомнить (как Дэн Пипони недавно вспоминал) и смешанные вычисления Ершова.
Правда разница между PGO и выше приведёнными подходами, что PGO — вещь статистическая (насколько я понимаю), тогда как суперкомиляция и подобные подходы оперируют исходным кодом.
Здравствуйте, Курилка, Вы писали:
К>Сдаётся мне, что суперкомпиляция Турчина побоянистей будет (вроде в 70-е он начал этим заниматься), а до него ещё можно Футамуру спомнить (как Дэн Пипони недавно вспоминал) и смешанные вычисления Ершова.
Так то теория а PGO уже достаточно давно практика.
), что это будет оптимально для ускорения в 10^10 раз.
