cost of monads

cost of monads

[Warren Harris]

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.

I know that the real answer here is "profile it and find out"... but I  
thought that asking for other's experience might be a good first step.  
Perhaps someone can offer a technique to make this work well, or a  
word of caution on why this should be avoided. I realize that most of  
the monad work happens in haskell (and I sometimes feel that I'm  
reinventing the wheel -- although it's very educational!), but I'd  
prefer to stick with ocaml if possible.

Warren


(* -*- Mode: Caml; tab-width: 4; indent-tabs-mode: nil -*- *)
(******************************************************************************)

module type MONAD =
sig
   type 'a t
   val return : 'a -> 'a t
   val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
end

module type ID_MONAD =
sig
   type 'a t
   val return : 'a -> 'a t
   val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
   val run : 'a t -> 'a
end

module IdM : ID_MONAD =
struct
   type 'a t = 'a
   let return a = a
   let (>>=) m f = f m
   let run a = a
end

(******************************************************************************)

module type STATE_MONAD =
sig
   type 'a t
   val return : 'a -> 'a t
   val (>>=) : 'a t -> ('a -> 'b t) -> 'b t

   type s
   type 'a m
   val lift : 'a m -> 'a t
   val run : 'a t -> s -> 'a m
   val gets : s t
   val puts : s -> unit t
end

module type STATE = sig type s end

module StateT(M:MONAD)(S:STATE) : STATE_MONAD with type s = S.s =
struct
   type 'a m = 'a M.t
   type s = S.s
   type 'a t = s -> ('a * s) M.t
   let return a s = M.return (a, s)
   let (>>=) m f s = M.(>>=) (m s) (fun (a, s) -> f a s)

   let lift m s = M.(>>=) m (fun a -> M.return (a,s))
   let run m s = M.(>>=) (m s) (fun (a, _) -> M.return a)
   let gets s = M.return (s, s)
   let puts s _ = M.return ((), s)
end

(******************************************************************************)

module type KMONAD =
sig
   type 'a t
   val return : 'a -> 'a t
   val (>>=) : 'a t -> ('a -> 'b t) -> 'b t

   type 'a m
   type ans
   val lift : 'a m -> 'a t
   val run : ans t -> ans m
   val callcc : (('a -> 'b t) -> 'a t) -> 'a t
end

module type K = sig type ans end

module KMonadT(M:MONAD)(K:K) : KMONAD with type ans = K.ans =
struct
   type ans = K.ans
   type 'a m = 'a M.t
   type 'a t = ('a m -> ans m) -> ans m
   let lift m k = k m
   let return a k = k (M.return a)
   let (>>=) m f k = m (fun am -> M.(>>=) am (fun a -> f a k))
   let run m = m (fun a -> a)
   let callcc f k = f (fun a _ -> return a k) k
end

(******************************************************************************)

Re: [Caml-list] cost of monads

[David Teller]

If you're interested, I'm currently putting the last touch on a paper
dealing with monads in OCaml -- including some benchmarks. I'll share
the data once I'm done with the writing.

Cheers,
 David


On Sat, 2008-06-21 at 11:23 -0700, 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.
> 
> I know that the real answer here is "profile it and find out"... but I  
> thought that asking for other's experience might be a good first step.  
> Perhaps someone can offer a technique to make this work well, or a  
> word of caution on why this should be avoided. I realize that most of  
> the monad work happens in haskell (and I sometimes feel that I'm  
> reinventing the wheel -- although it's very educational!), but I'd  
> prefer to stick with ocaml if possible.
> 
> Warren

> 
-- 
David Teller
 Security of Distributed Systems
  http://www.univ-orleans.fr/lifo/Members/David.Teller
 Angry researcher: French Universities need reforms, but the LRU act
brings liquidations. 

Re: [Caml-list] cost of monads

[Brian Hurt]

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

Re: [Caml-list] cost of monads

[Warren Harris]

[-- Attachment #1: Type: text/plain, Size: 2866 bytes --]

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
>


[-- Attachment #2: Type: text/html, Size: 3242 bytes --]