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@(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.
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@(!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 () {-# 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 @ (ST s) @ t ($fPrimMonadST @ s ($fMonadST @ s))) `cast` ... /tmp/Test.hs:25:1: Warning: RULE left-hand side too complicated to desugar (place @ IO @ t $fPrimMonadIO) `cast` ... Cheers, Johan
participants (2)
-
Andrey Yankin -
Johan Tibell