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@haskell.org [mailto:haskell-cafe-bounces@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@gmail.com