From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.5 required=5.0 tests=AWL,HTML_10_20,HTML_MESSAGE autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 28749BBAF for ; Sun, 22 Jun 2008 21:02:17 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AkoBAIc+XkjRVcitc2dsb2JhbACCPDePNkMBDAMEBAkPBZZxgy0 X-IronPort-AV: E=Sophos;i="4.27,685,1204498800"; d="scan'208,217";a="14370711" Received: from wf-out-1314.google.com ([209.85.200.173]) by mail3-smtp-sop.national.inria.fr with ESMTP; 22 Jun 2008 21:02:15 +0200 Received: by wf-out-1314.google.com with SMTP id 24so1824955wfg.15 for ; Sun, 22 Jun 2008 12:02:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:cc:message-id:from:to :in-reply-to:content-type:mime-version:subject:date:references :x-mailer; bh=Xg9KxZu5OwZnO3MPVK7vhmC4bK9QfStfFpx689/V9Lw=; b=XQThzzbgSUsFEEQzUNj5i+FhnRczNqJb/T5/6QSAvVhJI81Fr16iwNDRKM3UNMsfq5 i4JOvPxUI/f1hIfVqcgsfIgVvKRWxfm5UPb1VrKU2iuiCncUeNDcECcNBfC7HP0dcJl4 M/94JNXfmxSRIviWQgt1rTkiWrwRtM2jqt+gc= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=cc:message-id:from:to:in-reply-to:content-type:mime-version:subject :date:references:x-mailer; b=hKt1+EWpwidSfrrXGuIS1dOuL+B9aXrJHxujh9t9zPYzrfrxQq2m5XdVLbvpQQYtYm MqrbZB5g89C6/xhnJCJvAid9DES6FX51/PEFkkfI8gjbmZ6VO1KPvaLxTZbliLaVa3HI BpKr4433liI+0S37h5fwaCWwDdQ3l7LNeoneg= Received: by 10.142.238.9 with SMTP id l9mr3051783wfh.125.1214161334866; Sun, 22 Jun 2008 12:02:14 -0700 (PDT) Received: from timesink.local ( [98.210.196.241]) by mx.google.com with ESMTPS id 28sm7911496wfg.15.2008.06.22.12.02.13 (version=TLSv1/SSLv3 cipher=RC4-MD5); Sun, 22 Jun 2008 12:02:14 -0700 (PDT) Cc: caml-list@yquem.inria.fr Message-Id: From: Warren Harris To: Brian Hurt In-Reply-To: Content-Type: multipart/alternative; boundary=Apple-Mail-1--369070459 Mime-Version: 1.0 (Apple Message framework v924) Subject: Re: [Caml-list] cost of monads Date: Sun, 22 Jun 2008 12:02:10 -0700 References: <3822B729-FD99-429E-8150-CEAA57E4D84F@gmail.com> X-Mailer: Apple Mail (2.924) X-Spam: no; 0.00; monads:01 transformers:01 monads:01 monadic:01 parser:01 parser:01 metaocaml:01 ocaml:01 abstraction:01 transformers:01 inlining:01 semantics:01 vaguely:01 monadic:01 metaocaml:01 --Apple-Mail-1--369070459 Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit 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 > --Apple-Mail-1--369070459 Content-Type: text/html; charset=US-ASCII Content-Transfer-Encoding: quoted-printable http://www.cas.mcmaster.ca/~carette/publications/scp_metamonads.pdf)

Warren


O= n 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


= = --Apple-Mail-1--369070459--