Brian,

Thanks for your response. I realize that the cost will be very application-dependent, which is why I'm seeking other's practical experience programming with these techniques, particularly for stacked monad transformers involving simple monads (e.g. for interpreted languages). 

I can relay a little of my own practical experience in writing a monadic parser for a character-oriented grammar -- it is not practical. The performance was at least an order-of-magnitude worse than the yacc-based parser I later wrote. (Although the idea I was just pointed at of using metaocaml for this would seem to offer the best of both worlds: http://www.cas.mcmaster.ca/~carette/publications/scp_metamonads.pdf)

Warren


On Jun 21, 2008, at 7:32 PM, Brian Hurt wrote:



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