Re: speed versus C

[Anton Moscal <msk@post.tepkom.ru>]

On Tue, 5 Oct 1999, Gerd Stolpmann wrote:

> On Sun, 03 Oct 1999, Jan Brosius wrote:
> >Hi, is there anything known about the efficiency of compiled Ocaml code
> >compared with C/C++
> 
> A good comparision of the low-level features of Ocaml and C are my
> implementations of the cryptographic algorithms Blowfish and DES. Such
> algorithms do many integer calculations, bit shifting, and array lookups, i.e.
> tasks where C is perfect, and Ocaml is not designed for. The manually optimized
> algorithms are 8 to 10 times slower than the C counterparts, and a factor of 2
> can be explained with Ocaml's problems when computing with 32 bit numbers. To
> get around this, all 32 bit calculations are simulated by doing them on two 16
> bit halves. If such problems do not play a role, Ocaml is at most 4 to 5 times
> slower than C.

Assignment to array element can be very ineffictive in O'Caml due to the
following reasons:

1)O'Caml uses generational GC. Any pointer storing not to fresh memory
must be protected by write barrier. In O'Caml this means that if
type of array elements isn't unboxed type (int, char, bool, simple
enumeration or float), than a.(i) <- x implementation calls `modify'
function, which takes about 20-30 commands. 

for example:
----------------------
let rec test (a:int array) f = function 
   0 -> a
 | n -> 
   for i = 0 to Array.length a - 1 do a.(i) <- f a.(i) done;
   test a f (n-1);;

test (Array.create 1000 0) succ 20000;;
----------------------
runs 4.5 time faster than
----------------------
let rec test a f = function 
   0 -> a
 | n -> 
   for i = 0 to Array.length a - 1 do a.(i) <- f a.(i) done;
   test a f (n-1);;

test (Array.create 1000 0) succ 20000;;
----------------------
(on native code compiler for x86)

2) access to polymorphic array elements not very effective due
to special representation of the float arrays (polymorphic code 
test type of array and use different code for float/non-float
cases).

Good way to improve efficiency in such cases - suppress needless
polymorphism by type constaints.

Anton