Re: [Caml-list] cost of monads

[Brian Hurt <bhurt@spnz.org>]

On Sat, 21 Jun 2008, Warren Harris wrote:

> I'm considering writing a moderate sized program with high performance needs 
> in a monad / monad transformer style in ocaml. Although I believe that this 
> abstraction will offer me benefits in hiding some complexity, some of the 
> monad transformers I would like to "stack" are quite simple (e.g. a 
> state-transition monad), and I'm concerned that my program will be paying a 
> high performance cost due to high function call overhead -- ones which cannot 
> be optimized away due to module boundaries.

The performance hit of monads are two-fold: 1) generally, bind requires an 
allocation, and 2) functorization and partial application defeat inlining, 
and require more expensive call semantics (basically, you end up having to 
call caml_applyn where normally you'd just directly call, or even jump to, 
the function in question).

How much of a penalty this is depends upon how often the monad layer is 
invoked, or how much work is performed per bind.  If the cost of a bind 
is, say, 10 clocks, and on average you're doing a bind every 20 clocks, 
that's a huge hit- perfomance just dropped by a factor of 50%.  But if you 
only bind every 200 clocks, then it's only a 5% hit, and it is much less a 
big deal.  I pull these numbers out of me rear end, but they're probably 
vaguely close to correct.

The point is that it's impossible to generally state what the performance 
hit of monads are, because that's dependent upon how they're used.

For performance-sensitive code, I'd probably stay away from higher level 
abstractions.  On the other hand, I'd also consider how performance 
sensitive the code really is- we programmers have a bad habit of wanting 
to assume that all code needs to be tuned to within an inch of it's life- 
but the reality is hardly any code needs to be tuned at all (witness the 
popularity of languages like Ruby, Python, and PHP- all of which make Java 
look like greased lightning).

Brian