Суперкомпиляция

Суперкомпиляция — специальная техника оптимизации алгоритмов, основанная на знании конкретных входных данных алгоритма. Суперкомпилятор принимает исходный код алгоритма плюс некоторые данные о входных параметрах и возвращает новый исходный код, который исполняет свою задачу на этих данных быстрее или является лучше исходного алгоритма по каким-то другим показателям. Очень часто под суперкомпиляцией неверно понимают глобальную оптимизацию программы, то есть эквивалентные преобразования программы, которые улучшают выбранные показатели исполнения (скорость работы, требуемая память, размер и т. п.), из-за чего технология суперкомпиляции очень мало распространена, а сама идея имеет невысокую оценку в профессиональном сообществе.

Автор этой техники — российский и американский учёный Валентин Турчин.

Основная идея

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

Например, пусть исходный алгоритм — вычисление квадрата числа: square(x) => x * x. Для x = 0 можно получить более короткий и более быстрый вариант алгоритма, который просто возвращает ноль: square(0) => 0.

Равенство аргумента функции константе — только частный и самый простой вариант данных для суперкомпиляции. Другими примерами могут служить четность/нечетность числа, конкретные или четные/нечетные размеры массива, знания о порядке элементов массива или коллекции.

Например, для случая сортировки массива целых чисел можно получить несколько алгоритмов для размеров массива в 0, 1, 2, 3 и т. д. элементов, — результирующие алгоритмы будут работать без циклов, сводиться к нескольким сравнениям и выполняться максимально эффективно.

Процедура суперкомпиляции заключается в следующих шагах:

1. исполнение исходного алгоритма над интересующими данными на некоторой метамашине с запоминанием всех произведенных вычислений;
2. свертка полученного списка вычислений таким образом, чтобы интересующие показатели алгоритма улучшились, а результат вычисления остался верным;
3. обратное преобразование списка вычислений в код нового алгоритма.

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

В отличие от классических методов оптимизации, суперкомпиляция может в разы улучшить показатели работы даже простых алгоритмов. Например, для программы консольной игры в крестики-нолики суперкомпилятор может упразднить все массивы и циклы в предположении, что используется игровое поле 3x3, а также все написанные классы и подпрограммы/функции, в результате чего получится одна монолитная функция.

История вопроса

В 1970-е годы Валентин Турчин, Андрей Климов и их коллеги в Институте прикладной математики разработали суперкомпилятор для языка РЕФАЛ. С 1998 года они работают над тем, чтобы использовать эти приёмы для языка Java.

Для суперкомпиляции хорошо подходят те программы, которые используют стандартные библиотеки с открытым исходным кодом. Суперкомпилятор переписывает этот стандартный код, делая его эффективным для конкретных задач конкретной создаваемой программы, а также переписывает программу, чтобы более эффективно обращаться к суперкомпилированным процедурам.

Суперкомпилятор может помочь, если программа меняет приёмы своей работы по определённым параметрам. Например, предположим, что программа написана для общего случая и может работать по-разному при разных форматах базы данных. Если заранее известно, какая база данных будет использована, суперкомпиляция сделает программу намного эффективнее.

См. также

• Смешанные вычисления — те же задачи и решение Андрея Петровича Ершова.

Источники

• Материал для пополнения статьи

Для улучшения этой статьи желательно?: Викифицировать статью. Проставив сноски, внести более точные указания на источники.