23 Jan 22:08 2013

## Space leaks in function that uses Data.Vector.Mutable

Andrey Yankin <yankin013 <at> gmail.com>

2013-01-23 21:08:28 GMT

2013-01-23 21:08:28 GMT

Hi!

I have a "low-level" function for insertion element into mutable vector. It looks like this:

place :: (PrimMonad m) =>

MV.MVector (PrimState m) (Int, t) -> (Int, t) -> Int -> m ()

place v max <at> (val1,_) i = place' i

where

place' i = do

let j = i - 1

if j < 0

then return ()

else do

curr <at> (val2, _) <- MV.unsafeRead v j -- <<<<<

if val2 > val1

then do

MV.unsafeWrite v j max

MV.unsafeWrite v i curr

place' j

else return ()

It searches a right place for the i-th element, moving it towards beginningI have a "low-level" function for insertion element into mutable vector. It looks like this:

place :: (PrimMonad m) =>

MV.MVector (PrimState m) (Int, t) -> (Int, t) -> Int -> m ()

place v max <at> (val1,_) i = place' i

where

place' i = do

let j = i - 1

if j < 0

then return ()

else do

curr <at> (val2, _) <- MV.unsafeRead v j -- <<<<<

if val2 > val1

then do

MV.unsafeWrite v j max

MV.unsafeWrite v i curr

place' j

else return ()

Time profiling says this:

COST CENTRE MODULE %time %alloc ticks bytes

place.place' Main 40.1 77.1 9167 12169223232

And heap profiling says that most of allocations are for Int and (,).

PS Emergence of this piece of code is a long story. Originally I was trying to solve Project Euler's problem 411. But now it is a different issue.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe