replicateM space leak with lists
See mater ticket #1168
Summary
base:Control.Monad.replicateM
uses too much memory when m a = [a]
and the arguments are not small.
Steps to reproduce
import Control.Monad (replicateM)
shapes bias p =
[ s
| m <- [0 .. p]
, s <- replicateM (fromInteger m + 2) [1 .. p]
, p == sum (zipWith (*) (map (bias +) s) (tail s))
]
main = mapM_ (print . length . shapes 0) [1..10]
uses 500MB after 1min wall-clock time, and eventually gets OOM-killed on a 32GB desktop.
Expected behavior
Run to completion using small constant space.
Probable cause
liftA2 (:) f (loop (cnt - 1))
retaining in memory the result of the recursive call to use for each element of the list f
, which at top level has size (length f)^(n - 1)
.
Possible solution
I wrote an alternative implementation solves this for me in my use case, very happy to donate it to this project but I don't know:
- whether it is more frugal for all
m
- whether it is correct for all
m
, or even form = []
- whether it is faster for all
m
.
It is certainly much more complicated than the current implementation, and I don't know fully how/why it works so effectively.
{-# LANGUAGE ApplicativeDo #-}
replicateM' :: Applicative m => Int -> m a -> m [a]
replicateM' n ls = go n (pure id)
where
go n fs
| n <= 0 = do
f <- fs
pure (f [])
| otherwise = go (n - 1) gs
where
gs = do
f <- fs
l <- ls
pure (f . (l:))
Unfortunately I don't have resources at the moment to spend on researching/verifying/proving points 1,2,3 above; I imagine this task would be much easier for a ghc developer who would be familiar with the process involved in swapping the implementation and running the test suite?
More details including heap profile graphs at https://mathr.co.uk/blog/2022-06-25_fixing_replicatem_space_leak.html
Environment
- GHC version used: 8.8.4
- Operating System: Debian Bullseye
- System Architecture: amd64
$ apt-cache policy ghc
ghc:
Installed: 8.8.4-2
Candidate: 8.8.4-2
Version table:
*** 8.8.4-2 990
990 http://ftp.uk.debian.org/debian bullseye/main amd64 Packages
100 /var/lib/dpkg/status
Note: I don't think the replicateM implementation has changed since base-4.13.0.0.