Re: [isabelle] 64-bit Java is 6x faster than 32-bit for a recursive fibonacci



On Thu, 15 May 2014, Gottfried Barrow wrote:

On 14-05-15 11:23, Gottfried Barrow wrote:
 fun fib (n:int) = (if (n < 2) then n else (fib(n - 1) + fib(n - 2)));

Knowing nothing about concurrency, naively, this looks to me like it would be a perfect candidate, since there are two calls to fib.

This kind of example is generally called "micro benchmark". It is fun to play with it, but hardly relevant in practice. There are so many side-conditions to take into account in a real application, to say if it is fast or not. E.g. proper integer arithmetic depends on the libray that does that in the background, while machine integers are not integers at all.

Just from the parallelization standpoint, the above is relatively difficult to get performance from, and not just heat up all cores to give you a warm feeling. You would have to do quite smart organization of the evaluation. Some language frameworks try to do that for you, but in general you have to do it yourself -- again depending on many side-conditions of the overall application.


It bugs me that when calculating fib(42), the Java process only works 25% of my CPU.

Here is a version for Isabelle/ML that uses approx. 0% of CPU:

ML {*
  fun fib2 f0 f1 n = if n = 1 then f1 else fib2 f1 (f0 + f1) (n - 1);
  fun fib n = if n = 0 then 1 else fib2 0 1 n;
*}

See also http://www.cs.northwestern.edu/academics/courses/110/html/fib_rec.html which happened to be the first page Google spit out on this well-known exercise for freshmen.

To keep this on-track for isabelle-users, I propose that you make a small formalization in Isabelle/HOL to relate the two implementations.


	Makarius




This archive was generated by a fusion of Pipermail (Mailman edition) and MHonArc.