Коротко — как понять и исправить «пожирающий память» факториал в ленивом Haskell.
1) Что обычно происходит (математически)
- Рекуррентно: $$fact(0)=1,fact(n)=n\cdot fact(n-1).$$ - При использовании аккумулятора без принудительной оценки накопляется $O(n)$ отложенных вычислений (thunks), что даёт рост памяти и частые GC.
2) Как проанализировать использование памяти
- Соберите программу с профилированием:
- `ghc -O2 -prof -fprof-auto -rtsopts Main.hs`
- Запустите с RTS-опциями:
- `./Main +RTS -s` — суммарная статистика (allocs, max residency, GC).
- `./Main +RTS -hc` — heap profile по cost-centres, создаст `Main.hp`.
- `./Main +RTS -hy` — heap profile по типам объектов (Thunk/Closure/…).
- `./Main +RTS -p` — временное профилирование (создаёт `.prof`).
- Преобразуйте профиль: `hp2ps -c Main.hp` → .ps график.
- Для событий GC/параллелизма: компиляция с `-eventlog` и просмотр в ThreadScope.
- Что искать в профиле: большие блоки типа `Thunk` или накопление памяти в функции-аккумуляторе.
3) Типичные исправления (строгость и хвостовая рекурсия)
- Пример проблемы (хвостовая рекурсия, но без strict — возможны thunks):
code:
factorialTR :: Integer -> Integer
factorialTR n = go n 1
where
go 0 acc = acc
go k acc = go (k-1) (k * acc)
- Сделать аккумулятор строгим:
a) BangPatterns:
code:
{-# LANGUAGE BangPatterns #-}
go 0 !acc = acc
go k !acc = go (k-1) (k * acc)
b) seq:
code:
go k acc =
let acc' = k * acc
in acc' `seq` go (k-1) acc'
c) Использовать готовую строгую свёртку:
code:
import Data.List (foldl')
factorial n = foldl' (*) 1 [1..n]
- Для небольших чисел рассмотрите `Int` (машинный тип) вместо `Integer` — это уменьшит аллокации, но может переполниться. Для больших чисел учтите, что сам `Integer` выделяет память для больших результатов.
4) Дополнительные инструменты/параметры компилятора
- Включайте `-O2`.
- Опции вроде `-funbox-strict-fields`, `{-# UNPACK #-}` для структур данных, если храните большие числовые поля.
- Для критичной скорости/памяти — использовать unboxed типы (`Int#`, `Word#`) или библиотеки с примитивами.
- Проверяйте Core (`-ddump-simpl`) чтобы убедиться, что оптимизации сделали вашу функцию строгой/хвостовой.
5) Короткий чек-лист
- Получить профиль: компиляция с `-prof` + запуск `+RTS -s -hc/-hy`.
- Найти, где накапливаются `Thunk`/объекты.
- Сделать аккумулятор строгим (BangPatterns/seq/foldl').
- Пересобрать с `-O2` и перепрофилировать.
- При необходимости перейти на более низкоуровневые/неупакованные типы.
Итог: основной приём — обнаружить источники отложенных вычислений через профилировщик и убрать их, сделав аккумулятор/операции строгими (BangPatterns/seq/foldl'), при необходимости заменить типы на более компактные или использовать unboxed представление.