Здравствуйте, Sinclair, Вы писали:

S>Да ладно. Никакого предела ускорению программ путём суперкомпиляции нету. Привожу простой пример: делаем разложение чисел на простые множители.
S>Обычный компилятор компиляет алгоритм, который получает O(exp(N)).

То есть исходно мы имеем супер-нееэффективный алгоритм и путем его переписывания в эффективный получаем значительное ускорение?

Поделись тем как такой подход можно обобщить. Иначе это и есть частный случай.

S>Суперкомпилятор запускает этот алгоритм на первом миллионе чисел и строит таблицу.
S>В итоге, для чисел в пределах первого миллиона результат суперкомпилированной программы работает за O(1). Поделив время работы первого варианта для достаточно большого числа K на это O(1), можно получить ускорение и в миллион раз. Никаких фундаментальных проблем нет.

Гы-гы. Кремлевский мечтатель. Представим что у алгоритма есть 10 параметров или 2 но с очень большими значениями. В итоге мы получаем или многомерную структуру неопределенного размера стремящуюся к бесконечности, или двухмерную но тоже вылезающую за память компьюетра.

В общем, это все мечты. Если алгоритм исходно оптимальный, то никакие суперкомпиляторы его не ускорят (а замедлить могут).

Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга.

S>Нужно просто понимать, что речь идет о частичных вычислениях. А они применимы далеко не всегда — если нужно раскладывать числа за пределами первого миллиона, вторая программа будет ничуть не лучше первой.

Нужно понимать, что частные оптимизации мало интересны, так как устанешь затачивать под них компилятор.

То что ты описал влет оптимизируется путем тупой мемоизации (в том же Немерле — это ровно один атрибут на метод повесть).

S>Так что всё, что может сделать суперкомпилятор — это
S>а) устранить заведомо избыточную обобщённость (типична для суперумных библиотек на все случаи жизни, которые реально в конкретной программе используются в небольшом количестве сценариев)
S>б) провести спекулятивное устранение обобщённости (с этим сложнее, потому что нужно знать распределение значений входных параметров. И если в нём нет особенных неравномерностей, то ничего интересного суперкомпилятор не даст)

S>В принципе, на локальном уровне этим уже занимаются современные компиляторы, особенно для неуправляемых языков. Суперкомпиляторы претендуют на глобальный уровень, только и всего.

Ну, и как добиться ускорения в 50 раз?
Я вижу только один способ — писать чудовищно бездарный код и очень умный компилятор.