18

I have a codebase that is "needlessly" polymorphic in that almost every function is polymorphic in some way (why not, when you can?), but the end program uses functions with only a handful of concrete types. I've started spending some time throwing in SPECIALIZE and INLINABLE pragmas to try to bring down the performance cost of all this polymorphism, but with the size of my code it's pretty hit and miss. Is there a way to tell from profiling how much time is spent "doing the the things polymorphism needs" at runtime, for each function?

(Note: I've asked this question without knowing if such a thing is even technically possible or if "the things polymorphism needs" is well-defined enough).

gspr
  • 11,144
  • 3
  • 41
  • 74
  • 1
    Why are you focusing on polymorphism? Give the program a reasonable workload, [*get some stack samples*](http://stackoverflow.com/a/378024/23771), and find out what matters. – Mike Dunlavey Jul 18 '12 at 12:08
  • @MikeDunlavey: Two reasons: 1) It's interesting for me to learn how to control the downsides of polymorphism in Haskell. 2) Since my code is heavily polymorphic, but at the end uses only a few concrete types, I suspect I can get some nearly free performance gains by properly specializing some of the polymorphic functions. (As for your link, I was hoping to learn of a way to do what I describe through GHC's ordinary profiling facilities). – gspr Jul 18 '12 at 12:20
  • I'll also add that I'm not really *focusing* on polymorphism. Daniel Fischer's comments on [this answer](http://stackoverflow.com/questions/11537170/why-the-recursive-list-is-so-slow-in-haskell/11537241#11537241) got me thinking more about doing something with the performance penalties related to polymorphism, and I realized I had problems attacking my rather large code and that I'd really like GHC's profiler to come help me. Hence the question :-) – gspr Jul 18 '12 at 12:26
  • "why not, when you can?" Because, as the users guide says (6.2): "Overloaded functions are not your friend: Haskell's overloading (using type classes) is elegant, neat, etc., etc., but it is death to performance if left to linger in an inner loop." But how to find where it really hurts, I know nothing better than benchmarking, profiling and reading the core (yay for -ddump-simpl). Digging through the core is of course a royal pain with a large code base. – Daniel Fischer Jul 18 '12 at 13:36
  • Yeah I should've said "disregarding performance, why not, when you can?". I guess I'm looking to have my cake and eat it too, but if the profiler is able to tell the time spent doing "polymorphism bookkeeping", then one could write all the polymorphic code one wants, and then go in and specialize afterwards precisely where it's needed. If possible, this sounds to me like a wonderful way to cake. – gspr Jul 18 '12 at 13:53

1 Answers1

8

The process of determining costs is:

  • Construct a benchmark - with criterion, or some other measurement tool
  • Profile - with ghc's profiling support
  • Read the core - with ghc-core, if the performance causes are not obvious

Typically you will identify some operation that is too slow; compile with profiling and determine precisely which components are costly, and then inspect the code to optimize it (e.g. by specializing data structures or functions, changing algorithms, or making other changes).

For performance critical work you will then go and inspect the Core to see if micro-tuning the compiler can help.

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
  • Am I correct in thinking this means that there isn't a way for GHC's profiler to specifically tell me how much time is spent "bookkeeping for polymorphism"? This could be a stupid question for all I know, since I have little idea how polymorphism is actually done in Haskell, but what I'm thinking about is analogous to the profiler's "%GC time" statistic, except for "polymorphism bookkeeping" for function so-and-so (if that at all makes sense). – gspr Jul 18 '12 at 14:23
  • 7
    With the exception of type class methods, there really isn't any cost to polymorphism. Rather there's opportunity cost, that is the compiler could have generated better code for specific types if they had been fixed in advance. Depending on the functions in use, sometimes setting a monomorphic type is no more efficient than a polymorphic variant. As to type classes, the profiler may be able to help. If a profiling report indicates a great deal of time spent in a class method, you may consider marking that method as INLINE. But reading core is probably your best bet for optimizing this. – John L Jul 18 '12 at 14:37
  • @JohnL: Oh, OK, then I seems hard to get what I want from profiling. I always thought polymorphism in Haskell essentially involved some kind of run-time/call-time choices of alternative functions to call. To my naive self that seemed like something you could measure during profiling and hence know where to target your specializations. If you can make your comment an answer, I'll accept it :-) – gspr Jul 18 '12 at 14:41
  • 4
    Typeclass functions add an extra dictionary parameter, parametrically polymorphic functions generate code that works on any kind of object, by representing data in a universal format (as a closure). Only type class dictionaries will show up in the profiler. – Don Stewart Jul 18 '12 at 14:45
  • 1
    Accepted Don Stewart's answer in light of his illuminating comment. – gspr Jul 18 '12 at 15:04
  • Eh. The OP almost certainly wants to be reading the GHC core, which will show you where dictionaries are getting passed around and where they're getting optimized away. That's really the place to learn these details. – Louis Wasserman Jul 19 '12 at 12:14
  • @LouisWasserman: I was (overly optimistically it seems) hoping GHC could automatically give me a profiler measurement of how much time is spent looking up in and working with these dictionaries, and in which functions these costs occur. – gspr Jul 20 '12 at 15:57