Sat May 19 22:56:11 EDT 2007

```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.

```