The Fibonacci implementation here:

http://github.com/raganwald/homoiconic/blob/master/2008-12-1...

Does a pretty quick job using plain-old-old-ruby (POOR Implementation):

    time ruby /Users/raganwald/Desktop/matrix_fib.rb   102334155

    real    0m0.012s
    user    0m0.007s
    sys     0m0.004s

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!"

Neat hack, but needless, and besides that, irrelevant: the author didn't really care about the fibonacci sequence. He cared about function calls and additions.

See Performance and Evaluation of Lisp Systems, http://www.dreamsongs.com/Files/Timrep.pdf, for more discussions of the nature of benchmarks.

Thank you, I am aware that the author was deliberately picking a "most pessimum" algorithm as a benchmark. I am not commenting on the nature of benchmarks, but rather on the relative importance of algorithms and implementations.

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.

OK, but the implementation layer is just another layer of algorithms, except that you have somewhat less control over it. I notice your code uses inject, which is coded in C rather than Ruby -- as are many parts of POOR where C offers better performance.

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?

> 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...

Smalltalk Agents had no "primitives." (Read, no methods written in C.) The JIT was deemed good enough that everything could be written in Smalltalk. VisualWorks still has primitives, but a surprising number of things are written in Smalltalk, like Dictionary lookup.

Heh, sure. I would note however that implementation speed conditions the kinds of algorithms you write. You can't really do realtime audio processing in Ruby -- so implementation performance limits the scope of your project.

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.

That basically uses dynamic programming, which is "cheating". (It is a linear time algorithm instead of exponential!) Different compilers will almost always just give us constant factor improvements. Smarter algorithms will always beat that, but sometimes a smart algorithm with a slow compiler still isn't fast enough.

I don't think the matrix algorithm is linear, in other words I don't think fib(40) takes exactly twice as long to compute as fib(20). I think it's faster than linear, because it converts the multiplications to exponentiation and then takes advantage of composeability such that fib(40) should require on the order of one more operation than fib(20).

I think that means it's order log 2 n, but perhaps you HN folks can correct my poor math skills.

The site is down now, but from looking at wikipedia, you are probably right. (Sorry, I just glanced at the way they were using the matrix before, and assumed they did n matrix multiplies to calculate fib(n)) I think you are also right about the complexity, though people would usually just write log(n) since log(a*b)=log(a)+log(b).

Sorry, I didn't mean log (2n), I meant (log sub 2) n. Or in other words, the computation times is proportional to the number of binary bits in n.

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.

One of the beautiful things about JRuby is that for performance-intensive code, you can drop to Java instead of dropping to C. Java's almost as fast, and a whole heck of a lot nicer to program in.

If Surinx is able to produce Java-like speeds, that means that you never have to drop out to a different language at all. That's pretty awesome, and it would open up a whole new world to Ruby programmers.

I hope some of this work gets pushed into JRuby. I'll take 5x speed boosts any day, constant factor or not.

> ... fib(40) in only 7 seconds on current MLVM (OpenJDK7 + invokedynamic and other tidbits), a five-fold improvement over JRuby's fastest mode (jruby --fast).

I was going to say, "damn, that's it? that's pretty slow" until I realized:

   $ time python fib.py 40
   102334155

   real    1m43.363s
   user    1m36.824s
   sys     0m0.577s

It may be the fact that I have a ton of stuff running on my machine right now, but still.

Does fib.py use psyco? If not, that does still seem slow. Standard numerical benchmarks indicate that c or fortran or whatever should have a much larger speed advantage relative to regular python than 40/163. E.g. on the n-body benchmark here:

http://shootout.alioth.debian.org/u32/benchmark.php?test=nbo...

Python is about 65 times slower than c/c++/java/fortran/scala.

No, it doesn't use psyco. If it did, I'd expect it to be faster of course.

I just rewrote it in C though:

   $ time ./fib 40 
   102334155
   real    0m3.063s
   user    0m2.912s
   sys     0m0.014s

Which makes the python version something like 35x slower in wall clock time.

I just tried it with psyco. I get about 103 seconds with normal python and about 4 seconds with psyco. (Including the imports.)

Or you could simply make your python code tail-recursive:

  $ time python fib.py 40
  102334155

  real	0m0.013s
  user	0m0.000s
  sys	0m0.010s

Then you are testing two different things, and if you use tail recursion even Ruby 1.9 still runs it faster than Python.

  # 400
  $ time ruby fib.rb

  real	0m0.017s
  user	0m0.010s
  sys	0m0.006s
  
  # 400
  $ time python fib.py 

  real	0m0.023s
  user	0m0.011s
  sys	0m0.011s

Of course you can, but that's not going to work when you run out of stack space. The point of my stupid benchmark was to write the equivalent ruby code, and then the equivalent C code, forgetting the fact that there's a much more optimal way to do it (e.g. write it in scheme with tail calls).

> was to write the equivalent ruby code,

that should have stated "equivalent python code"

Python does not do tail call optimization.

Whether it does tail call optimization is a different question than whether you can write the algorithm in a tail-recursive manner, though.

Yes, but without the optimization, how would it help? Am I just being a n00b?

Writing it tail-recursively forces you to switch from the O(2^n) algorithm (which has two recursive calls; you can't put both into tail position) to a more efficient algorithm. You could also write the more-efficient algorithm without tail recursion, of course.

No, you're not being a n00b. It'll help because the stack usage will grow linearly as opposed to quadratically, as in the case of the naive solution. You'll still overflow the stack without the optimization.

One thing to remember about a lot of JVM language benchmarks is that they include the startup time for the JVM. Java code running on a pre-warmed JVM is significantly faster, and for short programs can be faster by an order of magnitude (or two).

For a good example, check out Nailgun (http://martiansoftware.com/nailgun/background.html).

I never stop being impressed by Charles (the JRuby lead dev)... remind me to ship a case of the Sierra Nevada Hefeweitzen to Engine Yard.

The best thing is that this will likely percolate into JRuby, and it bodes well for JRuby performance on JVMs that support invokeDynamic (not sure if OpenJDK does yet...)

You are reminded to ship a case of the Sierra Nevada Hefeweitzen to Engine Yard.

Boo is a similar project with Python and .NET:

http://boo.codehaus.org/

There are so many (new) languages for the JVM; its becoming a curse of plenty! (Not complaining.) Its a great platform, and invokedynamic will usher in a whole new generation of languages.

Lets just hope the Java 7 actually happens given the change of ownership, and I would love to see John Rose's call for programmatic access from Java (http://blogs.sun.com/jrose/entry/jsr_292_support_in_javac) realized. (ASM is great stuff, but I'll admit that its not a great joy to use for me.)

Or you could just use Groovy.