See Performance and Evaluation of Lisp Systems, http://www.dreamsongs.com/Files/Timrep.pdf, for more discussions of the nature of benchmarks.
You may find it irrelevant to the author's point, others may find it an interesting byway to follow in a larger conversation. Or not.
The point of Duby/Juby is to give us _more_ control over these algorithms by dragging them out of the base implementation language and into Ruby. Why should inject be written in C or Java?
I agree with your point and bless you with a mighty upmod. One of my peeves about inject being written in C is that there is very little pressure to make Ruby fast enough that inject could be written in Ruby. So who cares? Well, if you want to make your own language feature that is like inject but not inject, your feature will be 100x slower.
So making Ruby fast enough that Ruby can be implemented in Ruby is a huge win for metaprogrammers :-)
> Now it is not correct to say that Matz does not use Ruby. He does, and so he does eat his own dog food. And for the domains where he uses Ruby, he has optimized Ruby to be a useful tool. But since he doesn’t use Ruby to build Ruby, he does not have the same incentive to tune Ruby for the purpose of building languages.
http://weblog.raganwald.com/2006/11/significance-of-meta-cir...
I know, because I hack on Guile ;-) Fortunately in this case we come in at about 20 seconds. But there's a long way to go. I'm tired of the "slow language" question, and of having to drop down to C to do even modest number crunching.
And by "drop down to C", I really mean anything that's not written in the HLL (Scheme in my case) -- I'm less and less interested even by C libraries providing Scheme functions.
I think that means it's order log 2 n, but perhaps you HN folks can correct my poor math skills.
The algorithm is remarkably simple. Given that fib(40) can be extracted from:
40
[ 1 1 ]
[ 1 0 ]
The simplest implementation, as you surmise, is to do 40 matrix multiplications. I don't think that part is dynamic. the dynamic part comes in observing that n^40 = (n^20)^2. This can be followed downward recursively: n^20 = (n^10)^2, n^10 = (n^5)^2, n^5 = (n^2)^2 * n and n^2 = n * n.So... The actual matrix multiplication is much slower than a simple bignum multiplication, but there are only six such operations to perform.
http://github.com/raganwald/homoiconic/blob/master/2008-12-1...
Does a pretty quick job using plain-old-old-ruby (POOR Implementation):
That doesn't mean we shouldn't welcome implementation improvements, but in my lifetime the quest for a "sufficiently smart compiler" that will do away with thinking programmers has enjoyed only modest success.Append: This is not a criticism of Charles' amazing work dragging Ruby into the 1980s and designing Ruby-like languages for the JVM. If asked to choose between algorithm improvements and implementation improvements, I answer "Yes!"