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