Автоматическая оптимизация алгоритмов с помощью быстрого возведения матриц в степень

Подскажите шрифт на первом изображении?
P.S. Ubuntu font?

Очень серьезная работа!
К сожалению python не оптимизирует хвостовую рекурсию, поэтому созрел вопрос, а если применить ваш декоратор к такому коду, он произведет оптимизацию?

def f(n):
	if n == 0:
		return 
	n-=1
	print n
	f(n)

Посчитать сумму геометрической прогрессии можно и по формуле за константное сразу :)

Вообще данный подход очень напомнил так называему суперкомпиляцию.

Скажите, а в этом примере выноса константного выражения за цикл:

@cpmoptimize()
def f(n, k):
    res = 0
    for i in xrange(n):
        m = 3
        res += ((k ** m) & 676) + i
    return res

закралась опечатка, или действительно ваш декоратор не вынесет инструкцию m = 3 за пределы цикла?

@cpmoptimize()
def f(n, k):
    res = 0
    _const1 = (k ** m) & 676
    for i in xrange(n):
        m = 3
        res += _const1 + i
    return res

Если нет, то это же ошибка — вы возводите значение k в степень, задаваемую неинициализированной переменной. C учётом того, что переменная m в цикле не изменяется, логично и её выносить за пределы цикла.

WPython — модифицированный интерпретатор CPython 2.6.4 с более эффективной моделью байт-кода, умной системой сворачивания констант и переработанной виртуальной машиной.

Интересно, насколько эффективная там модель байт-кода, насколько переработана виртуальная машина и почему всё это добро не было внесено в общий код Python? Язык всё-таки не слишком быстрый, любые оптимизации его — это очень здорово.

Раз уж упомянуты Nuitka и Cython, то можно вспомнить и про shedskin.

Интересный подход и интересная статья, спасибо. Хотя (и это уже заметили в обсуждении) терминология в статье немного нетрадиционная.

Если по сути, то вот такой вопрос: есть ли возможность из cpmoptimize выдавать диагностику? Т.е. в случаях, если не удалось оптимизировать конкретный цикл, то куда-нибудь пишется сообщение, почему (какие переменные помешали, настройки лимита циклов, несделанная функциональность и т.п.). Конечно, можно запускать с strict = True и ловить исключения, но часто хочется получить отчёт по всей программе в целом, не прерывая её работу, например, если вместе с профилировщиком запускать, чтобы понять, а какие циклы вообще стоит оптимизировать. Примерно так делается в компиляторах в автопараллелизаторах кода на C/C++/Fortran.

Выглядит круто и неожиданно! А вы думали реализовать подобный трансформатор, например, для LLVM? Это сразу приведёт к прогрессу для многих языков программирования. Плюс, там не надо угадывать типы переменных, всё известно.

Возможно ли автоматическое аннотироване подходящих функций?
Допустим, в контексте того же LLVM. На этапе, когда все основные оптимизации (вроде выноса инвариантного кода за цикл) уже выполнены, но код ещё не векторизован — оптимизатор может попробовать оценить пригодность метода для каждого очевидного цикла…

Ещё круче может оказаться применимость для JVM или V8 — их JIT-компилятор уже умеет анализировать циклы и применяет loop unrolling для «небольших» циклов. Я могу представить, что туда можно дописать «else» и попробовать оценить применимость вашей опимизации к тому циклу.

// Просто мне кажется непродуктивным, что вы вынуждены решать уже решённые проблемы вроде вывода типов или других промежуточных оптимизаций, которые уже давно решены вне Python

Скажите, а вы рассматривали случаи, когда такой подход наоборот замедлит программу? Поясню. Оптимизируется вычисление выражения
b = (A^k)u,
где матрица A имеет размерность NxN.
Можно представить себе случай, когда эта матрица разрежена. Пусть, для простоты, в каждой ее строке имеется M << N ненулевых элементов. В общем случае возведение этой матрицы в степень превратит ее в заполненную.
Далее, если бы мы выполняли последовательное умножение вектора на матрицу, то нам понадобилось бы K*N*M умножений (будем считать только их).
Посмотрим теперь, сколько умножений потребуется при возведении A в степень K:
1) всего матричных произведений log K
2) каждое произведение — это N^3 умножений. Пусть используется что-то вроде алгоритма Штрассена, тогда N^{log 7}.
Итого получаем (log K)*(N^{log 7})

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

Для копилки компиляторов:
github.com/cosmo-ethz/hope
github.com/serge-sans-paille/pythran

А есть ли что-то общее у этой библиотеки и у проекта polly.llvm.org? Я детально не смотрел, но вроде и там, и там используется arbitrary precision math.