[Haskell-cafe] Performance Problem with Typeable

[Simon Peyton-Jones]

Interesting.  Would anyone care to make a Trac ticket for this (with "perf bug" as  the ticket kind), and (if at all possible) do some investigation to see what is going on?

Many thanks

Simon

| -----Original Message-----
| From: haskell-cafe-bounces at haskell.org [mailto:haskell-cafe-bounces at haskell.org] On
| Behalf Of Michael D. Adams
| Sent: 13 May 2009 22:57
| To: Haskell Cafe
| Subject: [Haskell-cafe] Performance Problem with Typeable
|
| I'm not sure where this should be reported, but I think I've found a
| significant asymptotic performance problem with Data.Typeable.  In the
| attached code, sum2 runs much slower than either sum1 or sum3.  It
| should be linear but it seems to slow down quadratically (i.e.
| doubling "len" quadruples the time for sum2).  Here is an example run:
|
| $ ghc --make -O3 CastSpeed.hs
| $ ./CastSpeed 20000
| gsum1
| Result: 200010000
| Time(sec): 7.999e-3
| Result: 200010000
| Time(sec): 0.0
| Result: 200010000
| Time(sec): 1.0e-3
|
| gsum2
| Result: 200010000
| Time(sec): 1.483774
| Result: 200010000
| Time(sec): 1.477776
| Result: 200010000
| Time(sec): 1.523768
|
| gsum3
| Result: 200010000
| Time(sec): 5.999e-3
| Result: 200010000
| Time(sec): 0.0
| Result: 200010000
| Time(sec): 0.0
|
| The only difference between sum1 and sum2 is that sum2 wraps a
| singleton list around each element (i.e. the cast is to [Int] instead
| of Int).  The only difference between sum2 and sum3 is that sum3 uses
| an unchecked cast (unsafeCoerce) instead of a checked cast.  This
| problem seems to crop up only for those types which are made up of a
| type constructor applied to an argument (e.g. "[]" applied to "Int").
|
| Because of sum3 runs fast, I suspect that something is going wrong
| with the "typeOf" call in a checked cast, and because sum1 runs fast I
| suspect that what is going wrong is the call to appKey that is called
| from mkAppTy that is called from typeOfDefault that is called from the
| Typeable instance for [Int] (i.e. instance (Typeable1 s, Typeable a)
| => Typeable (s a)).  This is a bit of speculation and I don't have
| hard evidence for that being the source of the problems, but tests
| that I have run (not listed here) are strongly suggestive of appKey
| being the culprit.
|
| Michael D. Adams
| mdmkolbe at gmail.com