Здравствуйте, 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-я и паттер-матчинга. Где можно его уже применяют. А в общем случае проекты вроде суперкомпиляторов для Явы просто дохнут ничем не закончившись. По всей видимости выхлоп не соответствует ожиданиям и авторы холодеют к данному подходу.