[erlang-questions] Preventing Recursion from Crashing Me...

[Richard Carlsson]

David Lloyd wrote:
> I rather quickly discovered that:
> 
> factorial(0) -> 1;
> factorial(N) -> N * factorial(N-1).
> 
> % math1:factorial(1000000).
> 
> ...was able to take sufficient resources that I only just managed to 
> send a ctrl+alt+break (I'm running Gnome/JDS on Solaris SXCE b72 on a 
> Intel Quad Core E6600 with 4Gb of memory).
> 
> Apart from not using naive fibonacci ( :P ) is there a way to prevent 
                              ^factorial
> erlang from running away with such processes?

The recursion in itself is not a problem (try changing * to +), but when
you get up to really huge numbers, almost all the CPU time is being spent
inside the bignum-arithmetic routines. These are implemented in C, and for
obvious performance reasons they do not check for signals, and the Erlang
process cannot be rescheduled in the middle of such an operation, so you
may well have problems interrupting the process in a pathological case
like this.

When I tested this, I noticed that the print-formatting in the shell
actually takes quite a long time. On my desktop machine, _computing_
factorial(10000) takes a fraction of a second, but printing it takes
almost a full second in itself. factorial(100000) takes about 35 seconds
to compute, and one minute 25 seconds to format (the result is many screen
pages). The formatting time is actually spent in the built-in function
integer_to_list(N), so there may be reason to look at whether this is
inefficiently implemented also for smaller numbers.

Computing factorial(1000000), on my 1GB desktop Pentium 4 used 100% of one
"cpu" (hyperthreaded, not multicore) for more than 20 minutes before I
killed the job (no problem using ctrl-G and "kill" in the shell), with peak
memory usage of no more than 30 MB, and the OS (Windows) remained
responsive. I don't really understand how Erlang could hog your 4GB
Quad-core machine executing the above program.

     /Richard