Comments 43
UFO just landed and posted this here
Подскажите шрифт на первом изображении?
P.S. Ubuntu font?
P.S. Ubuntu font?
Очень серьезная работа!
К сожалению python не оптимизирует хвостовую рекурсию, поэтому созрел вопрос, а если применить ваш декоратор к такому коду, он произведет оптимизацию?
К сожалению python не оптимизирует хвостовую рекурсию, поэтому созрел вопрос, а если применить ваш декоратор к такому коду, он произведет оптимизацию?
def f(n):
if n == 0:
return
n-=1
print n
f(n)
Нет, моя библиотека, к сожалению, не умеет оптимизировать рекурсивные функции. Однако, в Интернете я видел проекты по написанию других декораторов, которые, также анализируя байт-код, оптимизируют конкретно случай хвостовой рекурсии. Можно поискать по словам «python tail recursion decorator»: goo.gl/CHhkZh
Посчитать сумму геометрической прогрессии можно и по формуле за константное сразу :)
В формуле есть возведение в степень, поэтому за константное не получится.
А, да, сорри. Но всё-равно, если вбить в питон школьную формулу, а не писать цикл, то получится быстро
Если вы позволяете применять логарифмы/экспоненты для (*;pow) то можно возвести в степень и за констаное время (логарифм, *, экспонента).
Конечно, если логарифм и экспоненту считает сопроцессор за одну операцию. В случае длинной арифметики — время log(n).
Конечно, если логарифм и экспоненту считает сопроцессор за одну операцию. В случае длинной арифметики — время log(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? Язык всё-таки не слишком быстрый, любые оптимизации его — это очень здорово.
По ссылке можно найти презентации с подробным описанием изменений, которые они сделали в интерпретаторе: 1, 2. Там же сравнивается эффективность WPython по сравнению с классическим интерпретатором CPython.
Мне кажется, что в основной код CPython это не внесли, так как было сделано очень много внутренних изменений в интерпретаторе, которые его значительно усложнили. Возможно, это привело к каким-то проблемам, из-за которого слиять проекты было затруднительно.
Мне кажется, что в основной код CPython это не внесли, так как было сделано очень много внутренних изменений в интерпретаторе, которые его значительно усложнили. Возможно, это привело к каким-то проблемам, из-за которого слиять проекты было затруднительно.
RSA2048 раскладывается на множители за час?)
Спасибо за статью!
Простите, асимптота — это не кривая, а ось, к которой кривая приближается. Поэтому «изменяется асимптотически» — это линейная функция или вообще константа (то есть вообще НЕ изменяется). Наверное, Вы не это имели в виду?
Далее вы увидите, что эта оптимизация может ускорять программу не в определённое количество раз, а асимптотически.
Простите, асимптота — это не кривая, а ось, к которой кривая приближается. Поэтому «изменяется асимптотически» — это линейная функция или вообще константа (то есть вообще НЕ изменяется). Наверное, Вы не это имели в виду?
Вычислительную сложность алгоритма нередко коротко называют «асимптотика». В словосочетании «изменяется асимптотически» я имел в виду то, что в результате оптимизации изменяется эта самая сложность алгоритма (далее идут рассуждения про асимптотику O(n) в одном случае и асимптотику O(log n) в другом).
при увеличении размера входных данных вклад постоянных множителей и слагаемых низших порядков, фигурирующих в выражении для точного времени работы, становится крайне незначительным.
ru.wikipedia.org/wiki/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C#.D0.90.D1.81.D0.B8.D0.BC.D0.BF.D1.82.D0.BE.D1.82.D0.B8.D1.87.D0.B5.D1.81.D0.BA.D0.B0.D1.8F_.D1.81.D0.BB.D0.BE.D0.B6.D0.BD.D0.BE.D1.81.D1.82.D1.8C
— то есть ровно противоположный тезис от того, который Вы хотели показать? Или я Вас не понял, в связи с чем, собственно, и переспрашиваю.
Асимптотическое приближение — стремится к нулю при бесконечности и минус бесконечности. Асимптотическое изменение — линейно или константно (в декартовой СК — отсутствует). ru.wikipedia.org/wiki/%D0%90%D1%81%D0%B8%D0%BC%D0%BF%D1%82%D0%BE%D1%82%D0%B0
Далее вы увидите, что эта оптимизация может ускорять программу не в определённое количество раз, а асимптотически.
Определенное количество раз — линейная функция, асимптотическое ускорение — в одном понимании отсутствует вовсе, в другом — стремится к нулю, верно?
За убитую карму спасибо большое тем, кто ее убил. Всего-то переспросил по теме, для понимания. Что с хабром?... :(
Оптимизация не ускоряет программу в определённое количество раз, а вообще изменяет сложность алгоритма, используемого в ней. Таким образом, меняется вид зависимости времени работы от входных данных (обратите внимание, линия на графике после оптимизации имеет другой вид, соответствующий функции, растущей более медленно).
Понятие «асимптоты» тут, грубо говоря, ни при чём, речь только про сложность алгоритма. Вот ещё статья с хабра на эту тему.
Понятие «асимптоты» тут, грубо говоря, ни при чём, речь только про сложность алгоритма. Вот ещё статья с хабра на эту тему.
За убитую карму спасибо большое тем, кто ее убил. Всего-то переспросил по теме, для понимания. Что с хабром?.. :(Вашу карму не трогал, но могу предположить, что программисту нельзя не знать про вычислительную сложность алгоритмов, и про то, что именно называется асимптотикой.
До чегож красивый кусок кода в начале статьи. Прям смотрю и словно соловьи поют.
Раз уж упомянуты Nuitka и Cython, то можно вспомнить и про shedskin.
Вы про ускорение вычислений числа Фибоначчи для привлечения внимания написали? Таки зачем-то у меня оно не работает. Без декоратора ваш пример с картинки отрабатывает (для 10^5) за 0.210с а с декоратором за 0.215. Замедление на лицо, но не ускорение.
Если написать тот же самый код, что и на картинке, для n = 10^5 скрипт с тривиальным алгоритмом у меня работает за 0,2 с, а скрипт с оптимизацией — за 0,05 с. То есть, оптимизация ускоряет программу в 4 раза.
Вы уверены, что правильно измеряли время выполнения? В вашем случае разница между временем так мала (в пределах погрешности), что вы могли, например, случайно запускать один и тот же файл.
Вы уверены, что правильно измеряли время выполнения? В вашем случае разница между временем так мала (в пределах погрешности), что вы могли, например, случайно запускать один и тот же файл.
Интересный подход и интересная статья, спасибо. Хотя (и это уже заметили в обсуждении) терминология в статье немного нетрадиционная.
Если по сути, то вот такой вопрос: есть ли возможность из cpmoptimize выдавать диагностику? Т.е. в случаях, если не удалось оптимизировать конкретный цикл, то куда-нибудь пишется сообщение, почему (какие переменные помешали, настройки лимита циклов, несделанная функциональность и т.п.). Конечно, можно запускать с strict = True и ловить исключения, но часто хочется получить отчёт по всей программе в целом, не прерывая её работу, например, если вместе с профилировщиком запускать, чтобы понять, а какие циклы вообще стоит оптимизировать. Примерно так делается в компиляторах в автопараллелизаторах кода на C/C++/Fortran.
Если по сути, то вот такой вопрос: есть ли возможность из cpmoptimize выдавать диагностику? Т.е. в случаях, если не удалось оптимизировать конкретный цикл, то куда-нибудь пишется сообщение, почему (какие переменные помешали, настройки лимита циклов, несделанная функциональность и т.п.). Конечно, можно запускать с strict = True и ловить исключения, но часто хочется получить отчёт по всей программе в целом, не прерывая её работу, например, если вместе с профилировщиком запускать, чтобы понять, а какие циклы вообще стоит оптимизировать. Примерно так делается в компиляторах в автопараллелизаторах кода на C/C++/Fortran.
Я попробовал реализовать то, о чём вы написали.
Теперь можно применять декоратор строкой @cpmoptimize(verbose=sys.stderr), тогда он будет логгировать, в каких функциях какие циклы он оптимизировал, что пропустил из-за iters_limit, а что оптимизировать не смог. В последнем случае выводятся достаточно подробные сообщения о причинах того, что оптимизация не удалась.
Новую версию можно установить с github'а.
Теперь можно применять декоратор строкой @cpmoptimize(verbose=sys.stderr), тогда он будет логгировать, в каких функциях какие циклы он оптимизировал, что пропустил из-за iters_limit, а что оптимизировать не смог. В последнем случае выводятся достаточно подробные сообщения о причинах того, что оптимизация не удалась.
Новую версию можно установить с github'а.
Выглядит круто и неожиданно! А вы думали реализовать подобный трансформатор, например, для LLVM? Это сразу приведёт к прогрессу для многих языков программирования. Плюс, там не надо угадывать типы переменных, всё известно.
Возможно ли автоматическое аннотироване подходящих функций?
Допустим, в контексте того же LLVM. На этапе, когда все основные оптимизации (вроде выноса инвариантного кода за цикл) уже выполнены, но код ещё не векторизован — оптимизатор может попробовать оценить пригодность метода для каждого очевидного цикла…
Ещё круче может оказаться применимость для JVM или V8 — их JIT-компилятор уже умеет анализировать циклы и применяет loop unrolling для «небольших» циклов. Я могу представить, что туда можно дописать «else» и попробовать оценить применимость вашей опимизации к тому циклу.
// Просто мне кажется непродуктивным, что вы вынуждены решать уже решённые проблемы вроде вывода типов или других промежуточных оптимизаций, которые уже давно решены вне Python
Допустим, в контексте того же LLVM. На этапе, когда все основные оптимизации (вроде выноса инвариантного кода за цикл) уже выполнены, но код ещё не векторизован — оптимизатор может попробовать оценить пригодность метода для каждого очевидного цикла…
Ещё круче может оказаться применимость для JVM или V8 — их JIT-компилятор уже умеет анализировать циклы и применяет loop unrolling для «небольших» циклов. Я могу представить, что туда можно дописать «else» и попробовать оценить применимость вашей опимизации к тому циклу.
// Просто мне кажется непродуктивным, что вы вынуждены решать уже решённые проблемы вроде вывода типов или других промежуточных оптимизаций, которые уже давно решены вне Python
Скажите, а вы рассматривали случаи, когда такой подход наоборот замедлит программу? Поясню. Оптимизируется вычисление выражения
где матрица
Можно представить себе случай, когда эта матрица разрежена. Пусть, для простоты, в каждой ее строке имеется
Далее, если бы мы выполняли последовательное умножение вектора на матрицу, то нам понадобилось бы
Посмотрим теперь, сколько умножений потребуется при возведении
1) всего матричных произведений
2) каждое произведение — это
Итого получаем
Ясно, что величина K должна быть достаточно большой, чтобы получить хоть какой-то выигрыш для задач подобного рода. Не говоря уже о том, что коэффициенты матрицы, возведенной в степень, скорее всего потребуют использования длинной арифметики для обеспечения устойчивости вычислений (да и вообще приемлемой точности), что еще более замедлит процесс.
Словом, интуитивно мне кажется, что такой подход применим лишь для небольших размерностей вектора состояния, когда неважно, заполнена матрица или разрежена. И я бы не рискнул применять эту оптимизацию для длинных циклов. Хотя на примере Фибоначчи вроде бы все хорошо, но там на таких порядках в любом случае необходима длинная арифметика.
b = (A^k)u,
где матрица
A имеет размерность NxN.Можно представить себе случай, когда эта матрица разрежена. Пусть, для простоты, в каждой ее строке имеется
M << N ненулевых элементов. В общем случае возведение этой матрицы в степень превратит ее в заполненную. Далее, если бы мы выполняли последовательное умножение вектора на матрицу, то нам понадобилось бы
K*N*M умножений (будем считать только их). Посмотрим теперь, сколько умножений потребуется при возведении
A в степень K:1) всего матричных произведений
log K2) каждое произведение — это
N^3 умножений. Пусть используется что-то вроде алгоритма Штрассена, тогда N^{log 7}.Итого получаем
(log K)*(N^{log 7})Ясно, что величина K должна быть достаточно большой, чтобы получить хоть какой-то выигрыш для задач подобного рода. Не говоря уже о том, что коэффициенты матрицы, возведенной в степень, скорее всего потребуют использования длинной арифметики для обеспечения устойчивости вычислений (да и вообще приемлемой точности), что еще более замедлит процесс.
Словом, интуитивно мне кажется, что такой подход применим лишь для небольших размерностей вектора состояния, когда неважно, заполнена матрица или разрежена. И я бы не рискнул применять эту оптимизацию для длинных циклов. Хотя на примере Фибоначчи вроде бы все хорошо, но там на таких порядках в любом случае необходима длинная арифметика.
Такие случаи автором рассматривались, и именно потому автором введен параметр iters_limit. С длинной арифметикой тоже никаких проблем — там, где она начинает требоваться, ответ все равно без нее не получить.
Если же вдруг для представления ответа не требуется длинной арифметики — то все промежуточные вычисления можно проводить в кольце вычетов. Жаль только, автоматически до такого додуматься сложно.
Если же вдруг для представления ответа не требуется длинной арифметики — то все промежуточные вычисления можно проводить в кольце вычетов. Жаль только, автоматически до такого додуматься сложно.
А есть ли что-то общее у этой библиотеки и у проекта polly.llvm.org? Я детально не смотрел, но вроде и там, и там используется arbitrary precision math.
Sign up to leave a comment.
Автоматическая оптимизация алгоритмов с помощью быстрого возведения матриц в степень