[Haskell-cafe] Space leaks in function that uses Data.Vector.Mutable

[Andrey Yankin]

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@(val1,_) i = place' i
 where
  place' i = do
    let j = i - 1
    if j < 0
    then return ()
    else do
      curr@(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 beginning
. Surprisingly, it works, but is slow.

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 (,).

I think, binding of unsafeRead to curr and val might allocate my Precious
memory more than, maybe, it is needed.

Am I right? Is it some strictness that I need? Is there anything I can do
in this situation? Or should I look outside of this function?

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130124/1780d2f9/attachment.htm>