headers
Andrey Yankin | 23 Jan 2013 22:08
Picon

Space leaks in function that uses Data.Vector.Mutable

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 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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Permalink | Reply |
headers
Johan Tibell | 24 Jan 2013 00:03
Picon
Gravatar

Re: Space leaks in function that uses Data.Vector.Mutable

Hi!

You have to look outside the place function, which is strict enough. I
would look for a call to unsafeWrite that doesn't evaluate it's
argument before writing it into the vector. Perhaps you're doing
something like:

    MV.unsafeWrite (i + 1, ...)

Since tuples are lazy the i + 1 will be stored as a thunk. I recommend doing:

    data DescriptiveName a = DescriptiveName {-# UNPACK #-} !Int a

and using a

    MV.MVector (PrimState m) (DescriptiveName t)

if speed is really of the essence.

Aside: You can't optimize place slightly by:

 * Making it strict in val1, and
 * Making it inline.

The reason you want it to inline* is that's the function is
polymorphic and inlining it at a call site when you know if you're
working in IO and ST will improve performance.

Here's the slightly optimized version:

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 ()
{-# INLINE place #-}

* It should be enough to write two SPECIALIZE pragmas, one for IO and
one for ST, but GHC doesn't seem to like that for some reason:

/tmp/Test.hs:24:1: Warning:
    RULE left-hand side too complicated to desugar
      (place  <at>  (ST s)  <at>  t ($fPrimMonadST  <at>  s ($fMonadST  <at>  s))) `cast` ...

/tmp/Test.hs:25:1: Warning:
    RULE left-hand side too complicated to desugar
      (place  <at>  IO  <at>  t $fPrimMonadIO) `cast` ...

Cheers,
Johan
Permalink | Reply |

Gmane