15
$\begingroup$

I was just reviewing the Mathematica benchmark code linked from the Julia language home page http://julialang.org/. The stated goal of the benchmarks is to test the performance of specific algorithms, expressed in a reasonable idiom in each language, and all languages use the same algorithm.

In particular, the Fibonacci benchmarks are all recursive, and the Mathematica code reads

ClearAll[fib];
fib = Compile[{{n, _Integer}}, 
    If[n < 2, n, fib[n - 1] + fib[n - 2]],
    CompilationTarget -> "WVM"
];

Now, dynamic programming is certainly a reasonable idiom in Mathematica:

fib[n_Integer]:= fib[n]= If[n < 2, n, fib[n - 1] + fib[n - 2]]

and this dynamic uncompiled code will be much faster than the benchmark code, especially for large n (unless the WVM compiler is smart enough to do automatic memoization).

The test only computes fib[20] and it would be most interesting to try say fib[100] in the various languages (the times for R, MATLAB, and OCTAVE are excessive even for n=20).

It would also be useful, I think, for better coding of all the benchmark examples, if someone has the time and energy ...

$\endgroup$
  • 5
    $\begingroup$ You know that self-answering is not at all frowned upon? ;-) $\endgroup$ – Yves Klett Jun 9 '14 at 7:46
  • 1
    $\begingroup$ One could interpret this as a question along the lines "Do people have input on better Mathematica coding of examples in ...?" $\endgroup$ – Daniel Lichtblau Jun 9 '14 at 15:45
  • 2
    $\begingroup$ It looks like everything is using Compile. I wouldn't write code like this for the benchmark. Even if in some cases the compiled code is faster, it is not natural for Mathematica. I'd only use Compile in cases when it's clearly the best approach, e.g. the mandelbrot test. I did write a set of Mathematica benchmarks when Julia was first made public, but I got lazy at the quicksort and stopped there. I hacve the rest, should dig them up. $\endgroup$ – Szabolcs Jun 9 '14 at 17:13
  • 1
    $\begingroup$ never understood why Fibonacci code (like factorials) are always expressed recursively when linearly implementing the algorithm is pretty simple and straightforward $\endgroup$ – warren Mar 3 '17 at 17:22
  • 1
    $\begingroup$ @Szabolcs In Julia it is also easy to memoize (you need a package, github.com/JuliaCollections/Memoize.jl). It could be interesting to compare memoized implementations. $\endgroup$ – becko Dec 5 '18 at 16:27
12
$\begingroup$

I wrote the code in question... It is pretty much a line for line port of the Julia version of the benchmark:

Julia:

fib(n) = n < 2 ? n : fib(n-1) + fib(n-2)

Mathematica:

fib = Compile[{{n, _Integer}},
    If[n < 2, n, fib[n - 1] + fib[n - 2]],
    CompilationTarget -> "WVM" 
    (* WVM is faster than C in this case because of the recursive calls *)
];

It was never intended it to be an example of idiomatic Mathematica code. I did however actively chose not to use memoization because the benchmark states: "all languages use the same algorithm".

On my use of Compile: Since the code is very procedural it was very amenable to use with Compile. Most of the time it was as simple as wrapping the functions with Compile. I do recognize that it is sort of gaming the benchmark and perhaps it should have been excluded.

I am open to doing a rewrite of the code that does things in a more idiomatic style if there is any interest but I doubt the people over at Julia really care much.

(Sorry this isn't just a comment. I don't have the reputation to make comments)

Edit: I just tested the more idiomatic:

ClearAll[fib];
fib[0] = 0;
fib[1] = 1;
fib[n_] := fib[n - 1] + fib[n - 2];

It turns out this is only about 3 times slower than the WVM compiled version.

$\endgroup$
  • $\begingroup$ Fair enough. But...for some reason I did not find the fib Julia code at the linked-to site. Could you show that? (Or at least tell me where I should have been looking.) $\endgroup$ – Daniel Lichtblau Jan 11 '15 at 20:31
  • 2
    $\begingroup$ The fib code can be found here: github.com/JuliaLang/julia/blob/master/test/perf/micro/perf.jl Code for the other benchmarks is in the /julia/test/perf/micro/ folder: github.com/JuliaLang/julia/tree/master/test/perf/micro $\endgroup$ – MBryn Jan 11 '15 at 20:41
  • $\begingroup$ Thanks. Also, if I understand the result, the WVM-interpreted flavor is a couple of orders of magnitude slower than a from-scratch C-compiled code? I'm seeing a bit under .01 sec for fib[20] and around 4.5 sec for fib[34]. $\endgroup$ – Daniel Lichtblau Jan 11 '15 at 21:09
  • $\begingroup$ Yes. According to the table on julialang.org the WVM fib function is 163.43 times slower than the C version. $\endgroup$ – MBryn Jan 11 '15 at 21:55
  • $\begingroup$ It's worth pointing out that Roman E. Maeder gave ten progressively faster programs to compute Fibonacci numbers to illustrate optimization techniques applicable to other problems as well in Fibonacci on the Fast Track <mathematica-journal.com/issue/v1i3/tutorials/maeder/index.html> back in 1991. $\endgroup$ – TheDoctor Dec 19 '18 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.