Re: [Ocaml-lib-devel] De-functor-ized Psqueue

[Brian H. <bri...@ql...>]

On Wed, 28 May 2003, Nicolas Cannasse wrote:

> > > I don't agree here :
> > > - BUT the internal next is most of the time "concatening" the next
> functions
> > > in a purely functional way, so for example after two Enum.maps and doing
> an
> > > Enum.iter, you'll have to check the None/Some three times !
> >
> > For Enum.iter this is correct.  However, for doing just about anything
> > else you need to try/catch the exception the same number of times you need
> > to check for None/Some.  And I would expect map and fold to be at least as
> > important as iter.
> 
> I don't think so... here's current Enum.map implementation :

Oh.  You're right- I forgot Enum.map was O(1).  I was mainly thinking of 
fold, and tossed map in as well without thinking about it.

> In this sequence, there is only 1 catch for the exception if you're using
> Enum.iter or 2 if you're using Enum.fold , and it does not depends of the
> number of maps / filters you have done ! Here will be a map with next
> returning 'a option :

Enum.fold has to set up an exception stack every time it calls next.  It 
only catches an exception once- but it has to set up the stack frame every 
single time.  And that costs.

> Exceptions are really cheap in ocaml, better than pattern matching since the
> caml stay unwinding is very efficient.

Attached are a pair of simple benchmarks I whipped up.  Basically, they 
compare the relative costs of raising an exception vr.s returing 
None/Some.  I checked the output, and compiling with "ocamlopt -o test 
test1.ml" (or 2, as the case may be) doesn't "overoptimize" the test.

The file called test1.ml uses exceptions, and runs in 2.18 seconds on my 
system.  The file called test2.ml uses Some/None, and runs in 1.3 seconds.  
Exceptions are fast.  Just not as fast as allocating a word of memory and 
taking a branch.  Playing around with the code a little bit leads me to 
beleive that 0.7 seconds are program overhead, so as an approximation, 
catching an exception is 2.5x as expensive as Some/None.  Rough 
approximation here.  But it's actually a lot closer than I would have 
guessed.

In either case, interface harmonization is a more important issue IMHO.  
The exported definition of next should not be any more complicated than:
    let next t = t.next ()

Brian