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
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:
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;
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.
This archive was generated by a fusion of
Pipermail (Mailman edition) and