Re: speed versus C

From: Pierre Weis (
Date: Fri Oct 08 1999 - 11:56:29 MET DST

From: Pierre Weis <>
Message-Id: <>
Subject: Re: speed versus C
Date: Fri, 8 Oct 1999 11:56:29 +0200 (MET DST)
In-Reply-To: <99100800064700.23684@ice> from "Gerd Stolpmann" at Oct 7, 99 09:21:21 pm

> in Caml imperative programming should not be preferred because
> the compiled code is better, but because the algorithm demands it, i.e. there
> are many algorithms which work magnitudes better when programmed imperatively.
> Think of the thousands of books explaining array algorithms; there
> are often no functional counterparts that can compete.

 I think your message is right, except may be for this last sentence
that can just be unreliable urbian folklore.

 Let me give you a surprising counter-example: ``once upon a time'',
many people from the Caml team were teaching ``algorithmic and
programmation'' courses, and some were tired of (bubble | heap | merge
| shell | quick | insertion | selection | mecanographe | bogo)-sorts
algorithms written in imperative (C | Pascal | Ada | Caml)-style. So,
those hackers decided to have some fun writing the fastest (in place)
sorting algorithm for Caml vectors. After a while, and a careful
benchmark campaign, it turns out that the fastest program was so
simple and trivial that it was almost unfair: it started by building a
list from the vector's elements, then called the merge sort algorithm
of the standard library and stored back to the vector the elements of
the sorted list! What an interesting imperative programming style!

 This old experimental result may be wrong today, due for instance to
the new optimizations of the current Caml compiler or to new hardware
specificities. However it is interesting to remember this story, just
to know that imperative programming is not uniformely better than
functional programming, even for vector sorting algorithms (at least
in languages that support the two programming paradigms, such as
... euh, I mean in Caml :).

 In conclusion, use whatever style leads to the most readable and
provably correct program for the problem at hand. Then optimize this
correct program, if it is absolutely mandatory and if you have enough

Pierre Weis

INRIA, Projet Cristal,,

This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:26 MET