Есть ли оптимизация, похожая на развертывание цикла для функционального программирования?
Отказ от ответственности: я мало знаю о конвейере компиляции 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, так как такая оптимизация также должна происходить в такой форме, но выигрыш в производительности обманывает (очень) плохой алгоритм.
3 ответа
Вы компилировали с оптимизацией? Для меня с -O2нет никакой разницы между этими фрагментами: map1, map2, а также map4 побежал в 279, 267 и 285 мс, соответственно (и для сравнения, map сам пробежал за 278мс). Так что это похоже на шум измерений, а не на улучшение.
Тем не менее, вы могли бы взглянуть на этот плагин GHC, который, кажется, о развертывании цикла.
Грустно, но довольно верно, что чисто функциональные языки и императивные языки, как правило, имеют очень разные методы оптимизации. Например, вы можете захотеть взглянуть на слияние потоков и обезлесение - два метода, которые довольно аккуратны, но не очень хорошо переводят на императивные языки.
А что касается "каких-либо недоразумений по поводу того, почему это не очень хорошая идея?", Ну, я могу подумать об одном сразу же:
*Main> map succ (1:undefined)
[2*** Exception: Prelude.undefined
*Main> map4 succ (1:undefined)
*** Exception: Prelude.undefined
Во многих ситуациях хорошо сделать функцию более строгой, чтобы улучшить производительность, но здесь выигрыш в производительности мне не совсем понятен. map часто используется в зависимости от лени.
Наряду с уже упоминавшимся плагином ghc unrolling, на GHC trac есть страница, где обсуждается очистка / развертывание. Разделы "Открытые проблемы" и "Ссылки" являются особенно показательными источниками дальнейшего материала исследования.
Разворачивание петли - довольно неприятное оружие. Я бы никогда не хотел твоего
mapпример развернуться, например. Он полностью определяется распределением памяти для возвращенного списка и переходов в его ячейках. Неважно, есть ли у распределителя регистров что-то еще, над чем можно подумать. (Разворачивать ли свертку вроде
foldl' это, наверное, другой вопрос.)
GHC может разворачивать цикл путем встраивания рекурсивных функций. Но он изо всех сил пытается этого не делать: на самом деле он никогда не будет встраивать «прерыватели цикла» рекурсивной группы. В противном случае нет гарантии, что встраивание вообще прекратится. См. Раздел 4 «Секреты инлайнера GHC» .
GHC действительно применяет ограниченную форму отслаивания петель (или, скорее, частичное устранение избыточности) в своих
LiberateCase пройти (бежать с
-O2):
f :: (Int, Int) -> Int
f p = g [0..snd p]
where
g :: [Int] -> Int
g [] = 0
g (x:xs) = fst p + x + g xs
Здесь GHC выполнит одну итерацию цикла, чтобы получить
fst p проекция вне цикла и ссылка на распакованный
Int#вместо. Основной:
Lib.$wf
= \ (ww_sNF :: Int) (ww1_sNJ :: GHC.Prim.Int#) ->
case GHC.Enum.eftInt 0# ww1_sNJ of {
[] -> 0#;
: x_atE xs_atF ->
case ww_sNF of { GHC.Types.I# x1_aLW ->
case x_atE of { GHC.Types.I# y_aLZ ->
letrec {
$wg_sNB [InlPrag=NOUSERINLINE[2], Occ=LoopBreaker]
:: [Int] -> GHC.Prim.Int#
[LclId, Arity=1, Str=<S,1*U>, Unf=OtherCon []]
$wg_sNB
= \ (w_sNx :: [Int]) ->
case w_sNx of {
[] -> 0#;
: x2_Xud xs1_Xuf ->
case x2_Xud of { GHC.Types.I# y1_XMG ->
case $wg_sNB xs1_Xuf of ww2_sNA { __DEFAULT ->
GHC.Prim.+# (GHC.Prim.+# x1_aLW y1_XMG) ww2_sNA
}
}
}; } in
case $wg_sNB xs_atF of ww2_sNA { __DEFAULT ->
GHC.Prim.+# (GHC.Prim.+# x1_aLW y_aLZ) ww2_sNA
}
}
}
}