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
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
I've opened a ticket for this
(http://hackage.haskell.org/trac/ghc/ticket/3245), but someone else
will have to do the investigation into the problem.
Michael D. Adams
On Thu, May 14, 2009 at 10:59 AM, 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
participants (2)
-
Michael D. Adams -
Simon Peyton-Jones