Отказ от ответственности: я мало знаю о конвейере компиляции ghc, но я надеюсь узнать о нем больше в этом посте, например, если сравнение императивного и функционального имеет отношение к компиляции кода.
Как вы знаете, развертывание цикла сокращает количество итераций в цикле за счет дублирования кода внутри него. Это повышает производительность, поскольку уменьшает количество переходов (и связанных с ними штрафов) и AFAIR, создает большие блоки кода, оставляя место для лучшего Регистрация переименования оптимизация.
Мне было интересно, может ли быть эквивалент Loop Unrolling для функционального программирования? Можем ли мы «развернуть» функцию, открыть/расширить ее определение, чтобы сначала уменьшить количество вызовов указанной функции и/или создать большие фрагменты кода, а затем оставить место для дополнительных оптимизаций переписывания кода (таких как переименование регистров или некоторые FP). эквивалент)?
Что-то, что могло бы «развернуть» или «расширить» определение функции, используя, например, оценку функции (возможно, в сочетании с некоторой тактикой), чтобы найти компромисс между пространством и временем.
Пример того, что я имел в виду:
map1 _ [] = []
map1 f (x:xs) = (f x): map f xs
развернулся бы
map2 _ [] = []
map2 f (x:x1:xs) = (f x):(f x1):map2 f xs
map2 f (x:xs) = (f x): map2 f xs
Еще раз:
map4 _ [] = []
map4 f (x:x1:x2:x3:xs) = (f x):(f x1):(f x2):(f x3):map4 f xs
map4 f (x:x1:x2:xs) = (f x):(f x1):(f x2):map4 f xs
map4 f (x:x1:xs) = (f x):(f x1):map4 f xs
map4 f (x:xs) = (f x): map4 f xs
В игре две вещи: несколько случаев map4 (и последующие тесты в списке) могут снизить производительность, или уменьшение количества вызовов map4 улучшит производительность. Может быть, это могло бы уменьшить некоторые постоянные накладные расходы, создаваемые ленивой оценкой?
Кажется, написать тест для этого несложно, поэтому после определения критерия для развертывания этого что у меня есть:
Problem size 5*10^6
map 105.4 ms
map2 93.34 ms
map4 89.79 ms
Problem size 1*10^7
map 216.3 ms
map2 186.8 ms
map4 180.1 ms
Problem size 5*10^7
map 1050 ms
map2 913.7 ms
map4 899.8 ms
Что ж, кажется, раскрутка подействовала^1! map4 работает на 16% быстрее.
Тогда время для вопросов:
- Обсуждалось ли это раньше? Что-то подобное уже реализовано?
- Действительно ли уменьшенное количество оценок map4 улучшает скорость?
- Можно ли это автоматизировать?
- Могу ли я оценить по частям? т.е.: если (f x) полностью оценено, полностью оценить все до (f x4).
- Любая другая форма такого рода развертывания вступает в игру?
- К чему может привести инфляция размера функции?
- Любые недостатки, почему это не очень хорошая идея?
1: Я также развернул fib, так как такого рода оптимизация также имела бы место в этой форме, но прирост производительности заключается в обмане (очень) плохого алгоритма.
O2
приводит к тому, что все они дают одинаковые результаты. Развертывание не уменьшает количество переходников (еслиmap f (x:xs)
производит один, то же самое делает иf x:map f xs
). Я не уверен, что еще может быть затронуто. - person user2407038   schedule 02.10.2013