[Haskell] Re: Profiling Feedback to Optimize Memoization Caching

[apfelmus at quantentunnel.de]

Tom Hawkins wrote:
> After programming in Haskell for about a year now, I have found it
> allows we to quickly develop initial programs; thanks to the
> expressiveness of the language and type system.  But due to
> performance concerns, I typically have to restructure the initial
> program, guided by profiling, to reduce time or memory consumption.
> Many times, this refactoring process helps illuminate a better
> strategic approach to the program.  But very often, only a few
> inefficient functions need to be equipped with memoization.
> 
> I can certainly speed up these functions with explicit memoization,
> usually by threading a Map or Set through the recursive decent.  But
> doing so always degrades the legibility of the original function.  Are
> there any tools to automate this process, so as not to clutter the
> code with "Have-I-been-here-before?" tests and supporting data
> structures?  To what extent do Haskell compilers use memoization?  Is
> there any way to guide automatic memoization?
>
> Also, do any compilers use profiling data to enable or re-adjust
> memoization caches of the worst offenders?  In ECAD, we would call
> this an in-place optimization (IPO).

Memoization and lazy evaluation go hand in hand. Unless you need to do
different things depending on the answer of the question
"Have-I-been-here-before?" (most prominent example: depth first search),
it is unlikely that you need to carry around a Data.Map at all. It can
be filled "statically" by a circular program.

Anyway, the ultimate way to exploit sharing of sub-computations and
pruning search tree is to use equational reasoning. IMHO, the following
talk and paper make a good introduction:

   Richard Bird. How to Write a Functional Pearl.
   ICFP 2006
   http://icfp06.cs.uchicago.edu/bird-talk.pdf

   Graham Hutton. The countdown problem.
   Journal of Functional Programming, 12(6):609-616, November 2002
   http://www.cs.nott.ac.uk/~gmh/countdown.pdf


Regards,
apfelmus