But fib is a great benchmark for blog posts. You can write a naive implementation in your least-favorite language, and write a simple iterative implementation in your favorite language, and your favorite language will always win! And that's the most important part of benchmarking, who wins!

Edit: did anyone replying to this post (other than dons) actually read the linked paper?

Indeed, no other benchmark is:

* so accessible to the naive -- anyone can understand fib!

* has so many ways to implement it -- each in different complexity classes!

* is so perfect for language pissing contests on the intertubes.

Endless fun!

A much better idea is to contribute programs to the Great Shootout, http://shootout.alioth.debian.org/u64/benchmark.php?test=all...

fib does present an interesting problem. Any language worth its weight should be able to express the problem in such a way that it can perform

  1) quickly, 
  2) iteratively (tail-recursion)
  3) succinctly.

Not that many languages can do that.

Tail recursion for two recursive steps per invocation? I don't think so.

(Hint: the "naive" implementation of fib that I refer to above is "fib (x + 1) = fib x + fib (x - 1)".)

What are you saying exactly? That fib shouldn't be defined in terms of tail recursion? Of course it doesn't have to be. But it's also the moment that you realize that for loops are entirely unnecessary and broken since they aren't composable the way functions are.

Iteration and tail recursion are orthogonal. Yes, you can implement iteration in terms of function application. But no, the results of benchmarking "fib" won't make your favorite version win.

Doesn't seem that interesting -

http://shootout.alioth.debian.org/gp4/benchmark.php?test=rec...

Heh, no, the most important part about of benchmarking is collecting data so that people can make informed judgements about what language to use on a particular project. Put all those silly benchmarks together and you get a rough sense of how well a language performs.

I started learning Lisp specifically because I saw that SBCL could hold it's own against C, C++, Java, Haskell. A dynamic, interactive language that fast? Unbelievable.

These days I'd much rather use a language that gives me the full power of the REPL and performs just as well pixel-pushing as it does with web programming.

Read it. Honestly the paper is mostly a critique of functional programmers resting on their laurels for too long.

"Hey guys, our tail-recursive fib is just as fast as a for loop in C"

"Yeah that is pretty cool. But uh, we're simulating millions of particles in huge blocks of contiguous memory using C++. Your cons cells are too slow for that."

"Optimizing iteration over our list data structure? Uh ... catch you later."

Anyways good read and it's great that Haskell continues to take performance very seriously without abandoning expressive capability.

I can't tell from your post, but remember: this paper is from 1993.

That we still today have Ruby vs Lisp posts with fib(n) as the test is pathetic.

And as a Haskell guy, I'm going to call out anyone trying to use fibonacci to measure things, even though GHC is kicking butt.

Don't forget that there's also an O(1) closed form solution (and in fact you can derive a closed form solution for any linear recurrence relation: http://en.wikipedia.org/wiki/Recurrence_relation).

This is more useful though for things like calculating the size of a mortgage balance after N repayments.

I came to HN because CiteSeer is down and I couldn't get work done. Then I see CiteSeer on the front page of HN: my mistress killed my wife :-(

Watch it, buddy. Your mistress is your wife (in VR gear), and she's out to nail your two-timing butt.

(Short-story plot by Jeffrey Archer, in an old paperback I absentmindedly read a while ago.)

I have read the paper before, and it's certainly right -- but Gabriel never claimed that the fib benchmark was anything other than a microbenchmark of certain aspects of a system.

For example, when discussing the TAK microbenchmark, he says:

> When called on the above arguments, TAK makes 63,609 function calls and performs 47,706 subtractions by 1. The result of the function is 7. The depth of recursion is never greater than 18. No garbage collection takes place in the MacLisp version of this function because small fixnums are used.

(See http://www.dreamsongs.com/Files/Timrep.pdf)

With such a precise description of what the benchmark tests, it's obvious (a) that it's a microbenchmark, but also (b) that it does indicate the speed of certain combinations of operations.

So I don't think that the title of this article is actually the takeaway message from that paper. Microbenchmarks like the Gabriel benchmarks are around for a reason.

I just made a similar complaint over at Reddit. Maybe interesting, maybe not. http://www.reddit.com/r/programming/comments/b5v64/tired_of_...

The real reason why it's such a poor example is that it's contrived. If you honestly wanted to determine arbitrary elements from the Fibonacci series you would calculate them using a closed form expression that runs in O(1) (wiki Fibonacci sequence for examples).

Similarly, factorial is often a poor example problem because it's almost always completely unnecessary to tweak the performance of any algorithm for real world inputs. 13! is larger than an unsigned 32-bit int can hold, and 21! is larger than an unsigned 64-bit int can hold. The amount of performance gain you'd get from shaving down a loop or recursive call that ran at most 20 times is inconsequential in the vast majority of cases. Indeed, a simple recursive or iterative method is probably more efficient than even a lookup table method in most cases.

As example problems to see how people think through issues of iteration vs. recursion, efficiency, and performance these are ok problems but as real-world benchmarks for any kind of coding style they are terribly artificial.

The closed form solution isn't O(1). It's Ω(2^N) since the number of digits in the output is Θ(2^N).

On the most prevalent electronic computers of our time the closed form solution is effectively constant-time if the output is bounded to be within the limits of a 32 or 64 bit integer.