Version française
Home     About     Download     Resources     Contact us    
Browse thread
cost of monads
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Warren Harris <warrensomebody@g...>
Subject: Re: [Caml-list] cost of monads
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
>