Во-первых, не пытайтесь понять производительность кода, скомпилированного GHC, используя что-либо кроме оптимизированной компиляции:
$ stack ghc -- -O2 Find.hs
$ ./Find +RTS -s
С флагом -O2 (и GHC версии 8.6.4) вашfind работает следующим образом:
16,051,544 bytes allocated in the heap
14,184 bytes copied during GC
44,576 bytes maximum residency (2 sample(s))
29,152 bytes maximum slop
0 MB total memory in use (0 MB lost due to fragmentation)
Однако это очень вводит в заблуждение. Ни одно из этого использования памяти не связано с циклом, выполняемым foldr. Скорее это все из-за использования в штучной упаковке Integers. Если вы переключитесь на обычный Ints, который компилятор может распаковать:
main = print $ find (\x -> x `mod` 2 == 0) [1::Int, 3..1000000]
^^^^^
, производительность памяти резко изменится и продемонстрирует истинную стоимость памяти foldr:
51,544 bytes allocated in the heap
3,480 bytes copied during GC
44,576 bytes maximum residency (1 sample(s))
25,056 bytes maximum slop
0 MB total memory in use (0 MB lost due to fragmentation)
Есливы тестируете findRec с Ints следующим образом:
main = print $ findRec (\x -> x `mod` 2 == 0) [1::Int, 3..1000000]
вы увидите гораздо худшую производительность памяти:
40,051,528 bytes allocated in the heap
14,992 bytes copied during GC
44,576 bytes maximum residency (2 sample(s))
29,152 bytes maximum slop
0 MB total memory in use (0 MB lost due to fragmentation)
, что, кажется, убедительно доказывает, что рекурсия должна бытьпредпочтительнее избегать foldr, но это тоже вводит в заблуждение. То, что вы видите здесь, это не стоимость памяти рекурсии, а скорее стоимость памяти для "построения списка".
Смотрите, foldr и выражение [1::Int, 3..1000000] оба включают некоторыемагия называется "список слияния". Это означает, что когда они используются вместе (то есть, когда foldr применяется к [1::Int 3..1000000]), можно выполнить оптимизацию, чтобы полностью исключить создание списка Haskell. Важно отметить, что код foldr, даже используя объединение списков, компилируется в рекурсивный код, который выглядит следующим образом:
main_go
= \ x ->
case gtInteger# x lim of {
__DEFAULT ->
case eqInteger# (modInteger x lvl) lvl1 of {
__DEFAULT -> main_go (plusInteger x lvl);
-- ^^^^^^^ - SEE? IT'S JUST RECURSION
1# -> Just x
};
1# -> Nothing
}
end Rec }
Таким образом, это объединение списков, а не «избегание рекурсии», которое делает find быстрее, чемfindRec.
Вы можете убедиться в этом, если учесть производительность:
find1 :: Int -> Maybe Int
find1 n | n >= 1000000 = Nothing
| n `mod` 2 == 0 = Just n
| otherwise = find1 (n+2)
main :: IO ()
main = print $ find1 1
Даже при использовании рекурсии список не создается (или не используется в штучной упаковке * 1047). *), поэтому он работает так же, как foldr версия:
51,544 bytes allocated in the heap
3,480 bytes copied during GC
44,576 bytes maximum residency (1 sample(s))
25,056 bytes maximum slop
0 MB total memory in use (0 MB lost due to fragmentation)
Итак, какие уроки можно взять домой?
- Всегда тестируйте код на Haskell, используя
ghc -O2,никогда GHCi или ghc без флагов оптимизации. - Менее 10% людей в любой ветке Reddit знают, о чем говорят.
foldr иногда может работать лучше, чем явная рекурсиякогда могут применяться специальные оптимизации, такие как слияние списков. - Но в общем случае явная рекурсия выполняется так же, как
foldr или другие специализированные конструкции. - Кроме того, оптимизация кода на Haskell является сложной задачей.
На самом деле, вот лучший (более серьезный) урок на дому. Особенно, когда вы начинаете работать с Haskell, приложите все возможные усилия, чтобы не думать об «оптимизации» вашего кода. Гораздо больше, чем любой другой язык, который я знаю, существует огромный разрыв между кодом, который вы пишете, и кодом, генерируемым компилятором, поэтому даже не пытайтесь выяснить это прямо сейчас. Вместо этого напишите код, который будет понятен, понятен и идиоматичен. Если вы попытаетесь выучить «правила» для высокопроизводительного кода сейчас, вы поймете их все неправильно и выучите действительно плохой стиль программирования за сделку.