Timing Functions
I'm putting together a script to gather run-time stats for some functions I'm working with, and I'm having a terrible time. My strategy is to evaluate a function a number of times and compute the difference between the elapsed CPU time before and after the repeated calls.
timeNReps :: (a -> b) -> a -> Int -> FilePath -> IO () timeNReps func arg reps fileName = do t0 <- System.CPUTime.getCPUTime runNReps func arg reps t1 <- System.CPUTime.getCPUTime appendFile fileName ((showMS (t1 - t0)) ++ "\n") where showMS n = show (n `quot` 1000000000)
showMS just converts the pico-second result into milli-seconds and stringifies it. runNReps is an IO program (do sequence) that is intended to call the function and tail-call itself a given number of times:
runNReps :: (Int -> a) -> Int -> Int -> IO () runNReps f x todo | todo > 0 = do let junk = (f x) runNReps f x (todo - 1) | otherwise = return (())
Apparently runNReps doesn't apply f to x at all! I've called my test function with a suitable argument from top level (within ghci) and it takes ~20 sec. wall time to return; when I evaluate "runNReps test arg 1" it returns immediately. When I use this within my timing script I get timing output that indicates that calls for all args between 1 and 50 take about the same (very small) amount of time, but I know, both from theory and experiments in Scheme versions, that my test function's complexity is exponential in its arg. I'm using GHC 6.0.1 under Mandrake 9.1 on a 1.8 GHz Pentium box with 256MB RAM. Any idea where I'm going wrong? -- Bill Wood bill.wood@acm.org
On Mon, 17 Jan 2005 10:48:18 -0600, jekwtw
I'm putting together a script to gather run-time stats for some functions I'm working with, and I'm having a terrible time. My strategy is to evaluate a function a number of times and compute the difference between the elapsed CPU time before and after the repeated calls.
timeNReps :: (a -> b) -> a -> Int -> FilePath -> IO () timeNReps func arg reps fileName = do t0 <- System.CPUTime.getCPUTime runNReps func arg reps t1 <- System.CPUTime.getCPUTime appendFile fileName ((showMS (t1 - t0)) ++ "\n") where showMS n = show (n `quot` 1000000000)
showMS just converts the pico-second result into milli-seconds and stringifies it.
runNReps is an IO program (do sequence) that is intended to call the function and tail-call itself a given number of times:
runNReps :: (Int -> a) -> Int -> Int -> IO () runNReps f x todo | todo > 0 = do let junk = (f x) runNReps f x (todo - 1) | otherwise = return (())
Haskell is a non-strict language which means that 'junk' wont be evaluated since it's not necessary for the function to terminate. Check 'replicateM_' from Control.Monad.
runNReps :: Int -> IO a -> IO () runNReps = replicateM_
-- Friendly, Lemmih
Hi Bill, You know, Haskell is so smart that it realised that you want to measure it and therefore it performs very good -- NO, I am just kidding! Welcome to lazy programming! The thing is, that you don't force the evaluation of the result of you function f. Therefore you program doesn't bother to do anything. The way around is not easy in any case. You have basically two choices: a) force the evaluation inside runNReps, b) or collect the results and force the evaluation in timeNReps. The forcing can be done via seq or maybe print or whatever seems appropriate. Please note that seq is just force "Weak Head Normal Form", which means basically that just the top-most contructor is evaluated (to be not _|_). Btw: runNReps doesn't need to be in the IO Monad I came up with the following version:
timeNReps :: (Show b) => (a -> b) -> a -> Int -> FilePath -> IO () timeNReps func arg reps fileName = do t0 <- getCPUTime let results = map (func) $ take reps $ repeat arg putStrLn $ "Produced String of length " ++ (show $ length $ show results) t1 <- getCPUTime appendFile fileName ((showMS (t1 - t0)) ++ "\n") where showMS n = show (n `quot` 1000000000)
I hope it helped.
Cheers,
Georg
On Mon, 17 Jan 2005 10:48:18 -0600, jekwtw
I'm putting together a script to gather run-time stats for some functions I'm working with, and I'm having a terrible time. My strategy is to evaluate a function a number of times and compute the difference between the elapsed CPU time before and after the repeated calls.
timeNReps :: (a -> b) -> a -> Int -> FilePath -> IO () timeNReps func arg reps fileName = do t0 <- System.CPUTime.getCPUTime runNReps func arg reps t1 <- System.CPUTime.getCPUTime appendFile fileName ((showMS (t1 - t0)) ++ "\n") where showMS n = show (n `quot` 1000000000)
showMS just converts the pico-second result into milli-seconds and stringifies it.
runNReps is an IO program (do sequence) that is intended to call the function and tail-call itself a given number of times:
runNReps :: (Int -> a) -> Int -> Int -> IO () runNReps f x todo | todo > 0 = do let junk = (f x) runNReps f x (todo - 1) | otherwise = return (())
Apparently runNReps doesn't apply f to x at all! I've called my test function with a suitable argument from top level (within ghci) and it takes ~20 sec. wall time to return; when I evaluate "runNReps test arg 1" it returns immediately. When I use this within my timing script I get timing output that indicates that calls for all args between 1 and 50 take about the same (very small) amount of time, but I know, both from theory and experiments in Scheme versions, that my test function's complexity is exponential in its arg.
I'm using GHC 6.0.1 under Mandrake 9.1 on a 1.8 GHz Pentium box with 256MB RAM.
Any idea where I'm going wrong?
-- Bill Wood bill.wood@acm.org
-- ---- Georg Martius, Tel: (+49 34297) 89434 ---- ------- http://www.flexman.homeip.net ---------
Many thanks to both Georg and Lemmih. Actually, I had considered laziness, but I didn't pursue it enough. I tried one version of runNReps in which I passed (f x) as an additional arg; when that didn't work, a little thought convinced me that laziness was doing me in. I also tried another approach, which was to "use" the function evaluation, but that didn't work either (note: I know (f x) can not be the empty list for values of x I'm interested in, but I don't think Haskell does, unless it's *really* smart :-) :
runNReps :: (Int -> [a]) -> Int -> Int -> IO () runNReps f x todo | todo > 0 = do let junk = (f x) if null junk then return (()) else runNReps f x (todo - 1) | otherwise = return (())
Ideas? Again, many thanks, -- Bill Wood bill.wood@acm.org
Hi Bill,
please note that "null list" just forces the first cell to be evaluated. I.e. the list (x: xs), just x is evaluated, but not xs. That means, that just the code in you function is evaluated that is really required for x.
If your return type is a list, then you might get away with determining the length, but again it will not force the inside of each cell. The only way to force full evaluation is the DeepSeq class, see [1]. In case you can show your type you can also do that, but it will warp you results obviously.
Regards,
Georg
[1] http://www.mail-archive.com/haskell@haskell.org/msg15819.html
On Mon, 17 Jan 2005 14:21:00 -0600, jekwtw
Many thanks to both Georg and Lemmih. Actually, I had considered laziness, but I didn't pursue it enough. I tried one version of runNReps in which I passed (f x) as an additional arg; when that didn't work, a little thought convinced me that laziness was doing me in. I also tried another approach, which was to "use" the function evaluation, but that didn't work either (note: I know (f x) can not be the empty list for values of x I'm interested in, but I don't think Haskell does, unless it's *really* smart :-) :
runNReps :: (Int -> [a]) -> Int -> Int -> IO () runNReps f x todo | todo > 0 = do let junk = (f x) if null junk then return (()) else runNReps f x (todo - 1) | otherwise = return (())
Ideas?
Again, many thanks,
-- Bill Wood bill.wood@acm.org
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
-- ---- Georg Martius, Tel: (+49 34297) 89434 ---- ------- http://www.flexman.homeip.net ---------
participants (3)
-
Georg Martius -
jekwtw -
Lemmih