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 [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
