[Haskell-cafe] Profiling, measuring time

Steffen Mazanek haskell at steffen-mazanek.de
Sun May 20 05:56:08 EDT 2007


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 <haskell at brecknell.org>:
>
> 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 at 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 at unibw.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070520/88286e01/attachment.htm


More information about the Haskell-Cafe mailing list