CODEWITHSUNDEEP
haskelldata-structuresmemory-leakssdl
fayong lin
fayong lin

Reputation: 224

Haskell Data.Vector, huge memory leak

I am trying to make a basic 2D engine with haskell and the SDL1.2 bindings (for fun, I am just learning). Ideally the world is to be procedurally generated, chunk by chunk, allowing free exploration.

Right now my chunk is composed of 200*200 tiles which I represent using a type:

Mat [Tile] = Vec.Vector (Vec.Vector [Tile])

and these functions:

fromMat :: [[a]] ->  Mat a
fromMat xs = Vec.fromList [Vec.fromList xs' | xs' <- xs]

(§) :: Mat a -> (Int, Int) -> a
v § (r, c) = (v Vec.! r) Vec.! c

I am using cyclic list of tiles in order to allow for sprite animation, and later for dynamic behaviour.

Each frame of the game loop, the program reads the part of the vector relevant to the current camera position, display the corresponding tiles and return a new vector in which every of these cyclic lists has been replaced by it's tail.

Here is the code responsible for this:

applyTileMat :: Chunk -> SDL.Surface -> SDL.Surface -> IO Chunk
applyTileMat ch src dest = 
  let m = chLand $! ch
      (x,y) = chPos ch
      wid = Vec.length (m Vec.! 0) - 1
      hei = (Vec.length m) - 1
      (canW,canH) = canvasSize ch in

  do sequence $ [ applyTile (head (m § (i,j))) (32*(j-x), 32*(i-y)) src dest | i <- [y..(y+canH)], j <- [x..(x+canW)]]
     m' <-sequence $ [sequence [(return $! tail (m § (i,j))) | j <- [0..wid]] | i <- [0..hei]] --weird :P
     return ch { chLand = fromMat m' }

the first sequence does the display part, the second one returns the new vector m'.

At first I was using the following comprehension to get m'

let !m' = [id $! [(tail $! (m § (i,j))) | j <- [0..wid]] | i <- [0..hei]]

but doing so results in ever increasing memory usage. I think it has to do with lazy evaluation preventing the data to be properly garbage collected, but I don't really understand why.

In this particular case, it doesn't really mater since I have to look at the whole vector. But I don't know how I should do if I wanted to only "update" part of my chunk each frame, thus making a new chunk with only part of the data from the previous one.

I am probably not using Data.Vector the way it's intended, but it's the simplest data structure I found with O(n) random access.

The whole code is there: https://github.com/eniac314/wizzard/blob/master/tiler.hs

Upvotes: 1

Views: 307

Answers (1)

Andr&#225;s Kov&#225;cs
Andr&#225;s Kov&#225;cs

Reputation: 30103

The problem is indeed that vectors are lazy in the elements. First, let's look at why your example doesn't work.

let !m' = [id $! [(tail $! (m § (i,j))) | j <- [0..wid]] | i <- [0..hei]]

The bang pattern in !m doesn't do much. All ! does is ensure that a variable is a constructor or a lambda, instead of a function application. Here !m can be discerned to be either an [] or a (:) without evaluating any elements. Similarly, the įd $!-s don't force any actual elements of the inner lists. 

return ch { chLand = fromMat m' }

fromMat is the next culprit. fromMat doesn't force the inner vectors, and also doesn't force the elements. As a result, references to old vectors stick around in the thunks indefinitely.

Often the correct solution is to import Control.DeepSeq, and use force or $!! to fully evaluate vectors. Unfortunately, we can't do that here because of the cyclic lists (trying to force one results in an infinite loop).

What we really need is a function that brings all the elements of a vector to weak head normal form:

whnfElements :: Vector a -> Vector a
whnfElements v = V.foldl' (flip seq) () v `seq` v

We can use this to define a strict map for vectors:

vmap' :: (a -> b) -> Vector a -> Vector b
vmap' f = whnfElements . V.map f

Now updating becomes:

update :: Mat [Tile] -> Mat [Tile]
update = (vmap' . vmap') tail

Upvotes: 3

Related Questions