[Haskell-cafe] Performance Problem with Typeable

Michael D. Adams mdmkolbe at gmail.com
Wed May 13 17:57:08 EDT 2009


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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: CastSpeed.hs
Type: text/x-haskell
Size: 1024 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20090513/8288fe5f/CastSpeed.bin


More information about the Haskell-Cafe mailing list