Size: a a a

Compiler Development

2021 February 27

RB

Rustem B. in Compiler Development
источник
2021 February 28

IJ

Igor 🐱 Jirkov in Compiler Development
Коллеги, а у кого есть примеры работающих в популярных компиляторах оптимизаций таких, которые понижают класс сложности программы?
источник

IJ

Igor 🐱 Jirkov in Compiler Development
скажем. понижающую O(n) до O(log(n)) когда мы в цикле умножаем вектор на матрицу
источник

H

Hirrolot in Compiler Development
Igor 🐱 Jirkov
скажем. понижающую O(n) до O(log(n)) когда мы в цикле умножаем вектор на матрицу
источник

M

MaxGraey in Compiler Development
Igor 🐱 Jirkov
скажем. понижающую O(n) до O(log(n)) когда мы в цикле умножаем вектор на матрицу
Начнем с того, что умножение вектора на матрицу - это O(m * n) или O(n^2) если ранг матрицы равен длине вектора. Произведение двух квадратных матриц это соответственно O(n^3) или O(m*n*p) если колличества столбцов / строк разняться.

Можно ли это ускорить в общем случае? Можно сделать некоторые оптимизации в полигедральной модели. Ну например сделать loop tiling что улучшить когеренность кеша, векторизировать все это. Ну и пожалй все.

Можно ли это ассимптотически улучшить? В теории можно, если матрица сильно разраженная, но компилятор об этом не догадается.
Можно разбить на блоки и перемножать по-блочно (не путать с тайлизацией)

Можно пойти еще дальше. На сколько мне известно наиболее быстрый вот этот модифицированный алгоритм Копперсмита-Винограда сводящий перемножение матриц из O(n^3) к субкубическому O(n^2.373)
https://people.csail.mit.edu/virgi/matrixmult-f.pdf
источник

M

MaxGraey in Compiler Development
Насчет оптимизаций компилятора. Я знаю только что LLVM умеет сворачивать некоторые циклы в которых находит арифметическую сумму до собственно аналитической формылы подсчета для такой суммы или произведения
источник

IJ

Igor 🐱 Jirkov in Compiler Development
MaxGraey
Начнем с того, что умножение вектора на матрицу - это O(m * n) или O(n^2) если ранг матрицы равен длине вектора. Произведение двух квадратных матриц это соответственно O(n^3) или O(m*n*p) если колличества столбцов / строк разняться.

Можно ли это ускорить в общем случае? Можно сделать некоторые оптимизации в полигедральной модели. Ну например сделать loop tiling что улучшить когеренность кеша, векторизировать все это. Ну и пожалй все.

Можно ли это ассимптотически улучшить? В теории можно, если матрица сильно разраженная, но компилятор об этом не догадается.
Можно разбить на блоки и перемножать по-блочно (не путать с тайлизацией)

Можно пойти еще дальше. На сколько мне известно наиболее быстрый вот этот модифицированный алгоритм Копперсмита-Винограда сводящий перемножение матриц из O(n^3) к субкубическому O(n^2.373)
https://people.csail.mit.edu/virgi/matrixmult-f.pdf
речь не совсем об этом, а о том, что вместо умножения на матрицу 1000 раз можно возвести матрицу в 1000 степень быстрее, чем за 1000 умножений
источник

IJ

Igor 🐱 Jirkov in Compiler Development
это классический трюк с помощью которого можно считать фибоначчи быстрее. чем за линию
источник

RP

Roman Proskuryakov in Compiler Development
Igor 🐱 Jirkov
Коллеги, а у кого есть примеры работающих в популярных компиляторах оптимизаций таких, которые понижают класс сложности программы?
РЕФАЛ
источник

DF

Dollar Føølish in Compiler Development
MaxGraey
Насчет оптимизаций компилятора. Я знаю только что LLVM умеет сворачивать некоторые циклы в которых находит арифметическую сумму до собственно аналитической формылы подсчета для такой суммы или произведения
+++
источник

DF

Dollar Føølish in Compiler Development
Всегда угорал с этой фичи
источник

DF

Dollar Føølish in Compiler Development
Интересно кто додумался ее впилить
источник

AZ

Alexander Zaitsev in Compiler Development
Dollar Føølish
Интересно кто додумался ее впилить
ну а почему бы и нет - времени компилятора не жалко :)
источник

DF

Dollar Føølish in Compiler Development
Ну потому что это как ускорение от лто , работать всегда будет только на хелловолдах
источник

DF

Dollar Føølish in Compiler Development
Нужен более системный подход
источник

DF

Dollar Føølish in Compiler Development
В случае со сворачиванием прогрессий не знаю , но в случае с лто - полнопрограммная оптимизация
источник

AZ

Alexander Zaitsev in Compiler Development
Dollar Føølish
Ну потому что это как ускорение от лто , работать всегда будет только на хелловолдах
вот про LTO уже интереснее
источник

DF

Dollar Føølish in Compiler Development
Whole program optimization / дефункционализация и иже с ними
источник

LA

Liber Azerate in Compiler Development
Dollar Føølish
В случае со сворачиванием прогрессий не знаю , но в случае с лто - полнопрограммная оптимизация
У LLVM есть ведь ещё полиэдральные оптимизации циклов, не знаю, насколько живые. Как раз об этом
источник

M

MaxGraey in Compiler Development
Igor 🐱 Jirkov
речь не совсем об этом, а о том, что вместо умножения на матрицу 1000 раз можно возвести матрицу в 1000 степень быстрее, чем за 1000 умножений
А можно по-подробнее, потому что A * B = exp(log(A) + log(B)) возможно только для квадратных матрицах это раз и удовлетворяет условию X*Y = Y*X это два
источник