Ocaml Fibonacci is faster compared to lisp/scheme

Learning
1

In my “ocaml-tests” just 46 fibonnaci number ocaml is the slowest.
-8 seconds for racket-scheme
-10 seconds for sbcl-lisp
-19 seconds for chicken-scheme
-28 seconds for ocaml
Source code,

Feel free to elaborate.

2

Do you test native code or bytecode?

3

Looking at ocaml_28/doit from your repository it seems you are compiling to bytecode. You should change the compiler to ocamlopt instead of ocamlc. On my machine the native version takes 4.4s while the bytecode version (the one you use) takes 30.7s.

2 Likes
4

Using flambda would probably cut it by another factor, too.

1 Like
5

I was surprised by this since as far as I know (which is not much) there is not a whole lot that flambda can optimize in this code (it’s just the naïve, textbook recursive Fibonacci function). And indeed the generated code is the same for 4.14 and 4.14+flambda.

1 Like
6

I lazily didn’t look at the code in question before commenting; I’ve just frequently (~always?) had great results with rubbing flambda on projects, and getting an NN% perf improvement over regular ocamlopt.

But in this case, you’re right, and I sit corrected :blush:

7

I’m honestly surprised racket had the fastest, not the slowest execution time. My impression of that language was it being horribly slow at everything. Turns out you could make it a fast executable. I tried installing raco and invoking it the same way you did to get an executable and take a look at it, but raco exe wasn’t even a subcommand. In any case, I’m interested in the performance of ocamlopt in this whole experiment.

8

This made rounds on HN a few years(?) back: GitHub - drujensen/fib: Performance Benchmark of top Github languages OCaml definitely holds its own.

9

I don’t know which version of Racket is being tested, but the Racket people rewrote their implementation on top of Chez Scheme recently, which is one of the most efficient Schemes out there, so I assume they do great on these kind of microbenchmarks (relatively to other Schemes). Racket’s own advanced runtime features (monitors, contracts etc.) add overhead when they are used, of course.

3 Likes
10

I believe that all three of the Lisp dialects here compile to machine code and have a reputation for being decently fast. (Some others, like the venerable CLISP, are interpreted or bytecode-compiled and deliver performance similar to many scripting languages.)

An additional explanation for the Lisp results may be the use of optional type annotations:

;; SBCL
(declaim
  (ftype
    (function (fixnum) fixnum) fib))

;; Chicken
(: fib (fixnum -> fixnum))

As for the Racket benchmark, the specific dialect is Typed Racket; here the annotations are used for both static type checks and optimization.

11

I fixed the title of your post. Feel free to understand what you’re measuring before posting.

6 Likes
12

Use ocamlopt -O3 and you will see a very different picture! And update your post accordingly!

13

For a C program -O3 is not faster compared to -O2.
Also why the difference in compilation to byte-code vs native-code.
Wouldn’t you expect compilation to native-code be slower but resulting in faster applications ?

14

Yes you expect that, and your git repository and your topic was comparing byte-code OCaml to other natively compiled language (or JIT compiled). For instance, racket scheme support both native code and JIT, and probably JIT as default because of the potential for optimizing for specific parameters of function.

15

FWIW, 64-bit floating point Fibonacci on Apple M2 gives surprising results: I get 29s for C compiled using clang -O2, 20s for OCaml compiled using ocamlopt -O3 and 12s for my own code.

16

You can also implement it like this:

let fib x =
  let rec loop fm1 fm2 i n =
    if i = n then
      fm1 + fm2
    else
      loop fm2 (fm1 + fm2) (succ i) n
  in
  if x <= 1 then 1
  else loop 1 1 2 x

And then just care that you are using a “real man’s compiler”.
I.e. one that implements tail-recursive optimization. :wink:

1 Like