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. 

	The factor is likely much worse than two. Doing multiple precision
arithmetic, the factor is two, but even specially optimised simulations
of 32 bit ints by 16 bit ones often involve a more than two
instructions,
and this impacts cache performance severely in tight loops.


> As already pointed out, Ocaml is not designed for such problems, and this
> slow-down factor is an upper limit. 

	That depends on what kinds of data structures you are working with.
Ocaml has some problems requiring many things to be initialised
unnecessarily.
Also, where the library lacks certain facilities, it is occasionally
harder to provide efficient data structures than in C. These problems
are not intrinsic to ocaml, but can be solved by carefully considered
extension
of the standard library.

	There is also a problem with finalisation, which is not supported
by the garbage collector (at the user level): savings made using GC
to reduce code complexity and (possibly) enhance performance can go down
the
drain compared with manual memory management if finalisation is
required.

>The typical application will have a speed
> which is comparable with C/C++ solutions, as there are a number of advantages:
> 
> - The recursive data types of Ocaml are often more problem-oriented than
>   "imperative" data structures. 

	I don't think it is entirely reasonably to claim this; I find that
the 'imperative' data structures are more generally applicable.
Singly linked immutable lists are a special case well supported by ocaml
(and most other functional languages) but their performance is abysmal
for applications for which they are not suited.

>   Consider you want to fill an (C) array with an
>   unknown number of elements. The typical solution puts the elements into the
>   array until it is full, and then enlarges the array by reallocating new
>   memory. If you use the Ocaml lists instead, you do not have this problem. Of
>   course, you can program linked lists in C, too, but they are not as
>   convenient as arrays are, so many people avoid them. 

	This may be true in C, but it is NOT true in C++, in which the
Standard Template Library supports efficient data structures of various
kinds including lists and arrays (vectors).

> - OCaml code expresses the same with fewer lines of code, so it is possible to
>   write more complicated solutions, and to prefer a more sophisticated approach
>   over the straight-forward solution.

	I agree.  Furthermore, make times are very fast, to the point
that very rapid prototyping is possible, yet such code will perform
well even before tuning,  or native code generation.

	In particular, I think that higher order functions simplify coding
enormously, and reduce program size significantly; but variants and
matching are also likely to be faster than the 'hand coded' C/C++
equivalents,
and far more likely to be correct.

> - Memory management is much better; but this counts only for long-running
>   applications. Many C/C++ programs only "malloc" and do not "free", so the
>   time consumption of these functions isn't a problem.

	I do not think 'micky mouse' programs that fail to release
memory are worth considering here. C++ memory management can be
very difficult to get both correct and efficient, and sometimes
implementation details invade the program structure.

	However, C++ allows finalisation and ocaml doesn't,
which is a serious problem in ocaml when it is needed.

	I would very much like to see some discussion by ocaml experts
(not me!) leading to a standard solution to this problem, probably
a combination of some ocaml library code, some changes to the 
garbage collector to ensure efficiency, and some requirements
on the client. I need to call python __del__ methods on classes 
_immediately_ when they become unreferenced, and _some time or other_
when they become otherwise unreachable. 

	A technique for doing this using a strong array of objects,
a weak array of symbols for them, and a map recording symbolic
dependencies will work, but maintaining these data structures
is likely to be difficult to get right, will
obscure the currently clean code (both these problems would probably be
alievated with Haskell style monads), and will duplicate a lot of the
work
which the existing efficient collector does, and do so inefficiently.
I am not happy with this solution. Python uses reference counting,
which is reasonably fast, provides synchronous finalisation, but fails
to handle circular references: I would like to obtain better performance
_and_ handle circular references. This could be done for C Python
using the Boehm collector.

-- 
John Skaller, mailto:skaller@maxtal.com.au
1/10 Toxteth Rd Glebe NSW 2037 Australia
homepage: http://www.maxtal.com.au/~skaller
downloads: http://www.triode.net.au/~skaller