Thats it! Thanks a lot. I do not even need forceOutput, because I
perform a bottom-up analysis. And the timeline I got looks sooo
great (perfect polynomial behavior :-))
Best regards,
Steffen
2007/5/20, Matthew Brecknell
Steffen Mazanek:
I have written a function f, that performs a quite complex operation on its argument. Furthermore I have another function genInput that takes a number and constructs an argument for f of this size.
What I want now is a list [(n,time)] that gives me for every size of input n the time, f needs to compute this input.
How can I do this? I have found the module Time and tried diffClockTimes, but I ever got zero as a delta.
Lazy evaluation makes it tricky to measure exactly the computation you want to measure. You are probably measuring the time it takes to construct a single unevaluated thunk on the heap. If that's the case, you need to add strictness annotations to force the computation you want to measure. However, you need to take care to ensure that:
(a) the entire computation you want to measure is forced between your start/stop timer samples, and (b) no other computations are incidentally forced between your start/stop timer samples.
So, given a pure function f :: Input -> Output, you can write (untested):
import System.CPUTime
ftimer :: Int -> IO Integer ftimer n = do input <- return $! forceInput $ genInput n -- (b) t0 <- getCPUTime return $! forceOutput $ f input -- (a) t1 <- getCPUTime return (t1-t0)
I've marked the lines which (I think) ensure the conditions described above. Note the use of "return $!" to sequence the pure computations at the appropriate points in the IO computation.
The purpose of the forcing functions (forceInput :: Input -> Input) and (forceOuput :: Output -> Output) is to ensure there are no unevaluated thunks in values of type Input and Output, respectively. This is necessary because "seq" only forces values to Weak Head Normal Form (WHNF), which means it only goes as far as the top-level data constructor. The implementations of these functions will depend on the definitions of those types, so you'll need to give more details of the types if you want help with that.
Here are some (untested) examples of forcing functions to get you started.
-- Forcing a trivial data type is a no-op. forceInt :: Int -> Int forceInt = id
-- To force a list, force both the spine and the values. forceIntList :: [Int] -> [Int] forceIntList l = foldr seq l l
-- Some data types for illustration. data Foo = Foo Int Bar Baz data Bar = Bar Int data Baz = Baz !Int
-- Forcing evaluation inside a data constructor. forceBar :: Bar -> Bar forceBar b@(Bar i) = i `seq` b
-- This has already been forced by the strictness annotation in the data definition. forceBaz :: Baz -> Baz forceBaz = id
-- Elide forceInt and forceBaz, since they are no-ops. forceFoo :: Foo -> Foo forceFoo f@(Foo i b z) = i `seq` forceBar b `seq` z `seq` f
-- This time, forcing the list values is non-trivial. forceFooList :: [Foo] -> [Foo] forceFooList = forceGenericList forceFoo
-- To force lists generically, we need to be told how to force the values. forceGenericList :: (a -> a) -> [a] -> [a] forceGenericList vf l = foldr (seq.vf) l l
I hope that helps.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: steffen.mazanek@unibw.de