Opened 10 years ago

Closed 10 years ago

#3245 closed merge (fixed)

Quadratic slowdown in Data.Typeable

Reported by: guest Owned by: igloo
Priority: normal Milestone: 6.12 branch
Component: libraries (other) Version: 6.10.1
Keywords: Cc:
Operating System: Linux Architecture: x86
Type of failure: Runtime performance bug Test Case: perf/should_run/T3245
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Data.Typeable has a significant asymptotic performance problem. 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

Attachments (2)

CastSpeed.hs (1.0 KB) - added by guest 10 years ago.
Example code showing performance problem
TypeOfSpeed.hs (947 bytes) - added by guest 10 years ago.
Example code showing performance problem with typeOf

Download all attachments as: .zip

Change History (8)

Changed 10 years ago by guest

Attachment: CastSpeed.hs added

Example code showing performance problem

comment:1 Changed 10 years ago by guest

Type: bugrun-time performance bug

Changed 10 years ago by guest

Attachment: TypeOfSpeed.hs added

Example code showing performance problem with typeOf

comment:2 Changed 10 years ago by guest

As demonstration that the slowness in the cast is from the typeOf call see the attached TypeOfSpeed.hs.

Example run:

$ ghc --make -O3 TypeOfSpeed.hs
[1 of 1] Compiling Main             ( TypeOfSpeed.hs, TypeOfSpeed.o )
Linking TypeOfSpeed ...
$ ./TypeOfSpeed 20000
count1
Result: 20000
Time(sec): 9.998e-3
Result: 20000
Time(sec): 2.0e-3
Result: 20000
Time(sec): 2.0e-3

count2
Result: 20000
Time(sec): 1.455779
Result: 20000
Time(sec): 1.414784
Result: 20000
Time(sec): 1.415785

comment:3 Changed 10 years ago by igloo

difficulty: Unknown
Milestone: 6.12 branch

Thanks for the report

comment:4 Changed 10 years ago by simonmar

Type of failure: Runtime performance bug

comment:5 Changed 10 years ago by simonpj

Owner: set to igloo
Test Case: perf/should_run/T3245
Type: bugmerge

Excellent point. Fixed by

Fri Dec 18 15:51:17 GMT 2009  simonpj@microsoft.com
  * Fix Trac #3245: memoising typeOf
  
  The performance bug in #3245 was caused by computing the typeRep
  once for each call of typeOf, rather than once for each dictionary
  contruction.  (Computing TypeReps is reasonably expensive, because
  of the hash-consing machinery.)
  
  This is readily fixed by putting the TypeRep construction outside
  the lambda.  (Arguably GHC might have worked that out itself,
  but it involves floating something between a type lambda and a
  value lambda, which GHC doesn't currently do. If it happens a lot
  we could fix that.)

    M ./Data/Typeable.hs -29 +52

See Note [Memoising typeOf] in Typeable.hs which explains a bit more.

I added a regression test too.

I suppose we could merge this to the 6.12 branch, for the next patch release.

Simon

comment:6 Changed 10 years ago by igloo

Resolution: fixed
Status: newclosed

Merged

Note: See TracTickets for help on using tickets.