Здравствуйте, VladD2, Вы писали:
VD>Суперкомпиляция полезна, например, для уничтожения замыканий и лямбд, путем замены их на циклы, в тех случаях когда это возможно, и путем инлайнинга. VD>Это даст ощутимый выигрыш. Но этот выигрыш будет варьироваться от десятых долей процента до нескольких раз. Он никогда не достигнет 50 раз! Точнее сказать, надо написать просто чудовищно не реалистичную программу забитую комбинаторами, чтобы достичь этих 50 раз. В реальной жизни такого не встречается.
Написать "программу забитую комбинаторами" совсем не сложно. Здесь
очень простой комбинаторный парсер на 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
очень простой комбинаторный парсер на C#, который работает в примерно в 500 раз медленнее, чем комбинаторный парсер на Хаскеле безо всякой суперкомпиляции
1. В Хаскеле (в некотрых компиляторах) применяется аналог суперкомпиляции "дедеревизация".
2. Не верю! Не верю, что в 500. Даже не верю, что в 10 раз медленее, если алгоритмически они эквивалентны.
K>- просто в C# почти совсем нет оптимизаций для функциональщины. Где-то рядом есть улучшенный варинат, который в 25 раз медленнее парсера на Хаскеле, что примерно соответствует обсуждаемым здесь порядкам ускорения.
Это гадание на кофейной гуще. Сначала нужно доказать алгоритмическую эквивалентность, а потом уже обсуждать преимущества и недостатки оптимизаций.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, IT, Вы писали:
VD>>ОК. Возьмем линк. Что там можно оптимизировать если запрос должен в рантайме превратиться в SQL?
IT>Получаемый SQL. Правда непонятно зачем там суперкомпиляция, несложных эвристик вполне хватает.
Скажу даже больше. Суперкомпиляция тут вообще ничего не даст, так как она будет оптимизировать код генерирующий SQL, а не SQL. Так что оптимизировать нужно алгоритмы, а не генерируемый код.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, GlebZ, Вы писали:
VD>>Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга. GZ>a)Это неверный подход изначально. Ускорять можно не алгоритм, а реализацию.
На счет "ускорить реализацию". Синклер предлагал оптимизировать алгоритм путем автоматического создания таблицы решений для некоторых значений входных параметров. Это, по-твоему, не алгоритмическая оптимизация?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
очень простой комбинаторный парсер на C#, который работает в примерно в 500 раз медленнее, чем комбинаторный парсер на Хаскеле безо всякой суперкомпиляции — просто в C# почти совсем нет оптимизаций для функциональщины. Где-то рядом есть улучшенный варинат, который в 25 раз медленнее парсера на Хаскеле, что примерно соответствует обсуждаемым здесь порядкам ускорения.
Кстати, подумай, что может сделать суперкомпилятор если программист для прсинга регулярной грамматики (которой является разбор числа) использует рекурсивный нисходящий парсер с бэктрэкингом но без мемоизации?
Самая разумная оптимизация тут будет использовать регулярные выражения (оптимально если их движок создают ДКА). Задача при этом еще и проще получится.
Никакая суперкомпиляция до этого не додумается.
Устранение комбинаторов позволит повысить скорость вычислений, но экспненциального характера алгоритма она не уберет.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Если это известно, то это можно захардкодить. Причем получится даже проще.
О, Боже! Слышу ли я это от сторонника метапрограммирования и написания как можно меньшего кода руками?
Здравствуйте, 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)
Здравствуйте, VoidEx, Вы писали:
VD>>Если это известно, то это можно захардкодить. Причем получится даже проще. VE>О, Боже! Слышу ли я это от сторонника метапрограммирования и написания как можно меньшего кода руками?
Метапрограммирование — это средство автоматизировать процесс хардкодинга.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
IT>>Получаемый SQL. Правда непонятно зачем там суперкомпиляция, несложных эвристик вполне хватает. VD>Скажу даже больше. Суперкомпиляция тут вообще ничего не даст, так как она будет оптимизировать код генерирующий SQL, а не SQL.
Это ограничение придумано тобой только что.
Я не вижу причин, по которым не...
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, 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>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, 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
Здравствуйте, VladD2, Вы писали:
VD>>>Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга. GZ>>a)Это неверный подход изначально. Ускорять можно не алгоритм, а реализацию. Ты предлагаешь оптимизировать генеренный машиной код. Если он написан человеком, то чаще может быть оптимизирован(как в рамках суперкомпиляции, так и без оной) GZ>>б)В случае если есть неиспользуемые AST-tree ноды, то зачем из создавать? Не проще ли пропустить? VD>Я привел пример алгоритма который давно известно как реализовать весьма эффективно. И будучи эффективно реализованным его хрена два соптимизируешь.
Прооверквотю —
1) алгоритм написанный человеком неоптимален потому что он должен быть прежде всего понятен самому человеку. Такой оптимизацией занимаются все компиляторы
2) Для человека важна формализация парсируемого языка. Для оптимизатора важно то, что непротиворечивость результатов для потребляющих компонентов. Поэтому, если часть формализации неиспользуется, то ее вполне можно опустить.
Это к слову об оптимизации LL(1).
VD>ОК. Возьмем линк. Что там можно оптимизировать если запрос должен в рантайме превратиться в SQL?
А если не должен? При глобальном анализе доступно не только что нужно исполнять, но и как будут использоваться результаты. Одно кэширование повторяющихся выборок вполне может дать результат в те же 50 раз. Вопрос только в том, что выполнение в оперативе и так быстро.
VD>На счет "ускорить реализацию". Синклер предлагал оптимизировать алгоритм путем автоматического создания таблицы решений для некоторых значений входных параметров. Это, по-твоему, не алгоритмическая оптимизация?
Ну вместо алгоритм Штуцера назовешь это кэширующий алгоритм Штуцера. Любое действие можно описать алгоритмом. Но понятие алгоритм — нужно человеку а не машине или оптимизатору(суперкомпилятору). Вообще-же, я думаю, за оптимизацией в runtime — будущее.
Здравствуйте, IT, Вы писали:
VD>>ОК. Возьмем линк. Что там можно оптимизировать если запрос должен в рантайме превратиться в SQL? IT>Получаемый SQL. Правда непонятно зачем там суперкомпиляция, несложных эвристик вполне хватает.
А теперь попробуем представить насколько увеличится быстродействие если вместо генерации будет использоваться кэшируемое значение, что собственно делается в каждой уважаемой БД. 50 раз нагрести можно?
Суперкомпилятор — может это сделать автоматически при том, что ты общаешься с нормальными читабельными сырцами.
Здравствуйте, Klapaucius, Вы писали:
K>Так в C# версии проблем с промежуточными списками вроде как и нет. Там проблема в другом — код в котором много комбинаторов сам по себе ленивый, а средств для оптимизации такой ленивости в компиляторах strict языков по понятным причинам меньше, чем в GHC.
Я думаю, что проблема там в том, что создается множество промежуточных объектов. Использование итераторов приводит к этому на раз. Где-то пробигали варианты Парсека написанные на Немерле. Там вместо итераторов использовались лямбды. Правда, там для получения конца строки используется метод Substring(), но это легко лечится.
Можно провести сравнения.
K>В том треде варианты на OCaml и F# также сливали Хаскелю.
Дык, хаскель действительно заточен под комбинаторы. Там на эту оптимизацию положиле добрых 10 лет жизни не одного человека.
Лучше скажи, сколько они сливают? Не уж-то 50 процентов?
В прочем, в любом случае такой код никто в реальной жизни использовать не будет.
VD>>2. Не верю! Не верю, что в 500. Даже не верю, что в 10 раз медленее, если алгоритмически они эквивалентны.
K>Алгоритмически они не совсем эквивалентны. Вариант, переписаный с Хаскеля один-в-один вообще не работал — переполнял стек, так что в некоторых местах рекурсия заменена на автоматы на yield return. Но я думаю, что соответствие в общем случае достаточно хорошее, а если это не так, то неплохо было бы показать где именно проблемы.
Не, так дело не пойдет. Доказывать корректность результатов должен тот, то их предлагает.
K>Я то всего навсего попрытался показать, что комбинаторы могут обходиться гораздо дроже, чем в десятки процентов и еденицы раз. Согласен, что у моего обоснования есть изъяны, но в общем случае, мое утверждение лучше обосновано, чем Ваше, которое никак не доказано и даже не проиллюстрировано.
Дык это уже не совсем комбинаторы. Это еще и наворот на итераторах. В прочем, убедил. Таким образом можно что-угодно замедлить . Вот только это и получается частный случай неразумного выбора алгоритмов.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, 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>Перевод нужен?
Да, переведи выделенный фрагмент. Плюс переведи реальную цифру ускорения интерпретатора.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
S>>Конкретный пример: берём преобразование Фурье. Не нарошно пессимизированную версию, а честное FFT для комплексных чисел, работающее с N=2^K для любого R. VD>В задницу твои фурье. Они в библиотеках должны лежать. Это называется подтасовка фактов. Нормальное исследование должно брать ординарный код и изменять процент его ускорения после оптимизации.
SPECfp с тобой не согласен.
Там в исходниках часто лежит BLAS, который также надо преобразовывать и параллелить.
Так что ты сейчас снова выдумал какие-то интересные тебе критерии и пытаешься заставить собеседника удовлетворить их.
У тебя заведомо выигрышная позиция, завидую.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
T>>Это ограничение придумано тобой только что. T>>Я не вижу причин, по которым не... VD>А ты разберись в том о чем идет речь и увидишь. В кратце, linq выдает AST которое уже в рантайме преобразуется в SQL.
Что не противоречит моим словам.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Если нам не помогут, то мы тоже никого не пощадим.
. Вот только это и получается частный случай неразумного выбора алгоритмов.
