transpose still leaks
Summary
My recent change to transpose
was too fragile. Whoops!
I now have a proper fix and a test, but I don't currently have things set up on my side to integrate the test, so I could use some help. Here's the fix:
transpose :: [[a]] -> [[a]]
transpose [] = []
transpose ([] : xss) = transpose xss
transpose ((x : xs) : xss) = combine x hds xs tls
where
(hds,tls) = unzip [(hd, tl) | hd : tl <- xss]
combine x h xs t = (x:h) : transpose (xs:t)
{-# NOINLINE combine #-}
The combine
function ensures that we allocate the tls
selector thunk before we reach the tail of the result. Otherwise, GHC wants to do something like (x:h) : let tls = ... in ...
, which is no good at all.
Here's the test:
import Data.List (transpose, foldl')
thingy :: [[[Int]]]
thingy = [ [[1],[2]], [[1..10^7], [3]]]
thingy2 :: [[[Int]]]
thingy2 = [ [[1],[2]], [[3], [2..10^7+1]]]
main = do
htr : ttr <- pure $ L.transpose thingy
print $ foldl' (+) 0 . head . tail $ htr
print ttr
htr2 : ttr2 <- pure $ L.transpose thingy2
print $ foldl' (+) 0 . head . tail . head $ ttr2
print htr2
Maximum residency should be quite low. I get 44,504 bytes, but anything under 200,000 should be fine. With the original transpose
implementation, residency jumps to over 354,000,000 and the test goes slow as molasses.
The test works with or without optimization, but we need to be sure to run it with optimization to make sure the optimizer doesn't muck anything up.