OCaml and C math routines

OCaml and C math routines

[David McClain]

OCaml'ers... I would be very interested to hear your response to this!

|> From: -Zhong Shao
(shao-zhong@cs.yale.edu)

||> From: "Stephen T. Weeks" <sweeks@intertrust.com>
||> ...................
||> Even more impressive for the OCAML compiler is the fact that the
||> PLClub entry was compiled using separate compilation (please
||> correct me if I'm wrong) but the MLton entry was compiled whole
||> program (by necessity) and the SML/NJ entry was compiled whole
||> program (because it improves the speed).
||> 

>From what I know, for the floating-point intensive benchmarks, Ocaml
is faster than SML/NJ mainly because Ocaml directly calls the native,
C-based math library (which in turn is fine-tuned for the actual
processor).  SML/NJ, on the other hand, implements all of the math
library functions (e.g., cos, sin, tan) in ML itself (as part of the
SML basis). There is easily an order-of-magnitude difference between
these two implementations. You could try to measure a few such math
functions to find out.

>Members of the SML basis committee and the Ocaml group probably can
tell us the pros and cons of calling the native math library vs. having
it written in ML itself.


- DM

Re: OCaml and C math routines

[Xavier Leroy]

> OCaml'ers... I would be very interested to hear your response to this!

Here is a copy of the response I posted on comp.lang.ml:

Zhong Shao <shao@cs.yale.edu> writes:

> From what I know, for the floating-point intensive benchmarks, Ocaml
> is faster than SML/NJ mainly because Ocaml directly calls the native,
> C-based math library (which in turn is fine-tuned for the actual
> processor).  SML/NJ, on the other hand, implements all of the math
> library functions (e.g., cos, sin, tan) in ML itself (as part of the
> SML basis).

Thanks, Zhong, for this interesting piece of information.  I had no
idea that the SML Basis Library took such a "bare-bone" approach...

> Members of the SML basis committee and the Ocaml group probably can
> tell us the pros and cons of calling the native math library vs. having
> it written in ML itself.

Short answer: the idea of writing the math functions in ML itself
never even crossed my mind, and I can see absolutely no reason why one
would want to do so.

Longer answer: here are a bunch of reasons why calling the native math
library makes much more sense.

1- Availability: any Unix system, and any C compiler for other OS,
come with a math library conforming to ANSI (for the API) and IEEE
(for the semantics of the math operations).  So there are no
portability issues in using the native math library.

2- Correctness: floating-point arithmetic is surprisingly tricky.  These
native math libraries are widely used, in C and Fortran, by demanding
numerical users, so chances are that they are more correct than
anything we can write ourselves.  (And if they are not correct,
someone else gets to fix them, not us.)  Some of these libraries were
written by leading experts in the field (I'm thinking of Apple's SANE
library, which I believe was originally written by Prof. Kahan, one of
the biggest names in the area.)  So, I trust those libraries to be
more correct than anything I could write myself.

3- Speed: we can safely expect the native math library to be nearly
optimal in terms of performances, including processor-specific
optimizations, e.g. critical parts are written in assembly, exploiting
all resources of the target processor.  Sometimes, these libraries are
even written by the same people that designed the processor (I'm
thinking of Motorola's library for the Power PC).  So, I trust those
libraries to be faster than anything I could write myself.

4- Economy of means: implementors of ML have very limited human
resources, so it makes much more sense to interface with good existing
C libraries rather than redo everything from scratch.  In many areas,
it's not obvious to find good C libraries that do what we want, so
reimplementation in ML might be justified; but in the case of
floating-point math functions, I really don't see anything to hold
against the existing math libraries.  So, reimplementing exp() or sin()
myself would just be a waste of my time (and rather boring, in addition).

Now, I'd really love to hear from the SML Basis Library designers and
see what reason they can come up with to justify implementing the math
functions in ML.

- Xavier Leroy

-- 
Valid e-mail address (without the underscores): Xavier.Leroy@i_n_r_i_a.f_r
This is a protection against junk mail. Apologies for the inconvenience.
Home page: http://pauillac.inria.fr/~xleroy/

Re: OCaml and C math routines

[John R Harrison]

David McClain writes:

| OCaml'ers... I would be very interested to hear your response to this!

I guess I should comment, since I work closely with the people designing
math functions for various Intel architectures, and have even written a
few myself.

| Members of the SML basis committee and the Ocaml group probably can 
| tell us the pros and cons of calling the native math library vs. having
| it written in ML itself.

There are (at least) three things to consider in writing a good math
library function:

 * accuracy

 * speed

 * proper handling of exceptional cases

Getting good speed and accuracy together (or sometimes just one of them at
at a time) is often non-trivial. And even given a good basic design for the
core function, it's a serious amount of work to make all the peculiar
corner cases work sensibly, e.g. detecting overflow and underflow
correctly, behaving sensibly when unusual exceptions like "inexact" are
enabled, or even providing accurate answers when the rounding mode is not
the default of round-to-nearest or when trigonometric functions are applied
to huge arguments.

Besides, there's room for disagreement over what *should* be done in many
of the obscure cases. There's no IEEE standard for the transcendentals,
though C99 is establishing some sort of norm. In the absence of absolute
standards, there are hard trade-offs to be made between various desirable
characteristics.

So, on the one hand, it's ambitious bordering on hubristic for SML experts
who are not floating point specialists to reimplement all this stuff
themselves. On the other hand, it's certainly true that most available math
libraries have shortcomings in some area or another, so if the SML people
are able and determined enough, it would be possible in principle for them
to do better. For an idea of some of the techniques we've used at Intel in
recent math library work, you might look at the following:

  "The Computation of Transcendental Functions on the IA-64 Architecture"
  http://developer.intel.com/technology/itj/q41999/articles/art_5.htm

  "New Algorithms for Improved Transcendental Functions on IA-64"
  http://euler.ecs.umass.edu/paper/final/paper-118.ps

The original question seemed particularly focused on speed. In my
experience the really critical math functions tend to be coded in
assembler, simply because C compilers don't usually provide adequate
control or provide intrinsics to access special hardware features. For
less popular functions (like the cube root and Bessel functions), it's
common to use some portable C routines such as those in FDLIBM:

         http://www.netlib.org/fdlibm

There's certainly a case for having a similar library in ML, but the case
for using it as the default for important functions is more questionable.

Cheers,

John.

RE: OCaml and C math routines

[Dave Berry]

As a member of the SML Basis Library committee, my answer is quite simple.
The SML Basis Library is a specification, and does not specify that
mathematical functions should be implemented in ML.  For the most part, the
specification puts as few constraints as possible on implementations.  I'm
pretty certain that MLWorks implemented these functions in C.
 
Dave.