Hacker News Reader

Comment by apgwoz | Hacker News Reader

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

View on HN

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.

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?

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.

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.

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

Reply on news.ycombinator.com