I recently wanted to calculate some binomial coefficients in Erlang, and so needed an implementation of the factorial function. No problem. The factorial function is the canonical illustration of how to define a recursive function in Erlang. It goes something like this:
fac(0) -> 1;
fac(N) -> N * fac(N-1).
I have to confess that definition has always bothered me because it is not tail recursive. And it only takes one more line to write a tail recursive version, just the way God intended:
fac1(N) -> fac1(N,1).
fac1(0,R) -> R;
fac1(N,R) -> fac1(N-1, N*R).
The advantage of fac1 over fac is that fac1 operates in constant space, while fac requires space linear in N. For large N one has to wonder whether fac's chain of deferred multiplications will overflow the stack. But is this really a problem? Just how large a value of N is required to overflow the stack? I decided to try to find out.
I ran some test cases: fac(1000), fac(10000), fac(50000). No stack overflow yet, but I could see it might get old waiting for the enormous answers to be computed and displayed. I decided to switch gears. To avoid suffering through monster integers, I modified the test. Rather than testing with fac, I settled on using the structurally similar function sum:
sum(0) -> 0;
sum(N) -> N + sum(N-1).
Just for grins, I decided to try the same thing in a couple of other languages. Here is sum in Clojure:
(defn sum [n]
(if (= n 0)
0
(+ n (sum (- n 1)))))
And here it is in Haskell, where I changed the spelling to summ to avoid a name collision with a Prelude function called sum:
summ 0 = 0
summ n = n + summ (n-1)
I was surprised by the results of my tests.
Just to build up the suspense, I'll pause to describe the test machine. It's a Dell T105, quad-core AMD Opteron, 8GB of ram, running Ubuntu Intrepid. Clojure is revision 1173, running on top of Java 1.6.0_10. Haskell is ghci 6.10.1, and Erlang is R12B-5.
On to the results. First up is Clojure:
user=> (sum 10000)
50005000
user=> (sum 20000)
200010000
user=> (sum 30000)
450015000
user=> (sum 40000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)
The stack overflow is just the sort of thing that makes me prefer fac1 over fac. Let's see what happens in Haskell.
*Main> summ 10000
50005000
*Main> summ 30000
450015000
*Main> summ 40000
800020000
*Main> summ 50000
1250025000
*Main> summ 75000
2812537500
*Main> summ 100000
5000050000
*Main> summ 150000
11250075000
*Main> summ 175000
*** Exception: stack overflow
Haskell, or rather ghci, did roughly four times better. It's probably worth pointing out that this is not really a comparison of the languages so much as a comparison of how the language implementations handle one very specific detail.
Here I need to point out that I am quite aware than both the Clojure and Haskell examples could be (and normally ought to be) modified so as not to blow the stack. My purpose here is to see what it takes to blow the stack. I want to blow the stack.
Time to see how the Erlang virtual machine fares. I stuck the sum function in a module called fac. No matter.
Eshell V5.6.5 (abort with ^G)
1> fac:sum(1000).
500500
2> fac:sum(10000).
50005000
3> fac:sum(50000).
1250025000
4> fac:sum(100000).
5000050000
5> fac:sum(200000).
20000100000
6> fac:sum(500000).
125000250000
7> fac:sum(1000000).
500000500000
8> fac:sum(5000000).
12500002500000
9> fac:sum(10000000).
50000005000000
10> fac:sum(50000000).
1250000025000000
11> fac:sum(100000000).
5000000050000000
12> fac:sum(200000000).
20000000100000000
At that point I went for broke, and tried to compute sum(1000000000). Maybe it would have worked eventually, but I killed it. My machine had gone nearly non-responsive, and I could hear my hard drive thrashing. Those disk sounds incline me to guess that when Erlang ran out of stack space, it moved the computation into virtual memory and soldiered on. Whatever the actual means, N=200,000,000 is pretty impressive. That's three orders of magnitude better than ghci or the jvm. Kudos to the authors of the Erlang virtual machine.
One final thought. In spite of what I saw here, I'll still go with the tail recursive version of the factorial function. It better satisfies my sense of aesthetics. But it's nice to know I don't have to.
Posts
Here’s how to implement sum in Clojure so it doesn’t give a stack overflow. loop/recur is the trick to avoid adding stack frames with each recursive call.
(defn sum [number]
(loop [n number result 0]
(if (zero? n) result (recur (dec n) (+ n result)))))
(println (sum 40000)) ; -> 800020000
February 19, 2009 @ 5:49 pm
Mark,
My whole purpose was to write code maximally vulnerable to a stack overflow, so I could get some idea when the overflow would occur. And I wanted to write pretty much the same code in all three languages.
On the other hand, I’m happy to show how NOT to trigger the overflow. I rewrote the Erlang version to be tail recursive (unnecessarily, as it turned out). The jvm does not properly support tail recursion, so I appreciate your taking the time to show how to do the right thing in Clojure.
My choice of Clojure was something of a back-handed compliment. I wanted to hammer on the jvm, but I don’t like writing java. Clojure to the rescue. Since I’m on the topic, let me say that I think Clojure is the best thing to happen to the jvm in a long time. Clojure beautifully combines the cool, the expressive, and the practical. I hope the wider lisp and java communities will rally behind Clojure and give it the audience it deserves. Anyone remotely interested in lisp, java, or concurrent programming should check out this screencast by Clojure’s author and benevolent dictatior, Rich Hickey.
drc
February 19, 2009 @ 7:34 pm
You should probably not benchmark the (naive) Haskell interpreter , when you’ve an optimising Haskell compiler next door. So, compiling it, how much stack do you want to burn?
main = print (summ 200000000)
summ 0 = 0
summ n = n + summ (n-1)
$ ghc -O2 –make A.hs
$ time ./A +RTS -K1G
Stack space overflow: current size 1000000000 bytes.
Use `+RTS -Ksize’ to increase it.
./A +RTS -K1G 2.87s user 2.05s system 96% cpu 5.111 total
Well, it will run till you’ve used a gig of stack.
Best to write it tail recusively, or use a library that will do that for you:
import Data.Array.Vector
main = print (sumU (enumFromToU 1 (200000000 :: Int)))
$ ghc -O2 –make A.hs
$ time ./A
20000000100000000
./A +RTS 0.26s user 0.00s system 100% cpu 0.262 total
February 20, 2009 @ 6:50 pm
Don,
Thanks for you comments. All three languages offered the option to compile; in all three cases I went with the corresponding interpreter instead. I wanted to see whether and when a deliberately naive use of recursion would blow the stack. It was curiosity and nothing more.
I appreciate your taking the time to show me how the code ought to be written, assuming one wants to avoid the overflow.
Let me take the opportunity to tell you that I am a huge fan of xmonad. For anyone who may not know it, xmonad is the most badass window manager in the world, and it is written entirely in Haskell.
I use xmonad at least eight hours a day, at least five days a week. It makes my life better. By my reckoning there are three indispensable pieces of software: emacs, ssh, and xmonad. Don is one of the authors of xmonad.
Don is also one of the authors of Real World Haskell. Even though the entire book is available free online, I recently bought a copy. It’s that good. I have read very little of it because I have entirely too much to do. But I did read enough to know it is THE book to get if you want to learn Haskell.
When I look at Haskell I see two things. The superficial one is stunningly elegant syntax. Beyond that is something more important. I see the language that has come closest to Backus’ dream of escaping the confines of the von Neumann architecture. I get the impression that Haskell done right is more like doing math than tinkering with abstract machines. Both are fun, but math’s track record as humanity’s most powerful and profound symbolic technology makes me think that Haskell and its offspring will have an important future.
drc
February 20, 2009 @ 11:38 pm