System getting hang after running normal recursion program

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

System getting hang after running normal recursion program

ARUN P
Hi all,

I tried to run normal recursion program from erlang shell, the program
runs infinitely and it is doing addition of numbers. But its been
observed that soon after starting the program entire PC is getting hang.

My doubt is that, why my PC is getting hang. ? , if something is going
wrong, the erlang vm should be able to handle it, like in C if we run
some recursion program infinity, it will crash by throwing segmentation
fault error.

What will be happening in the VM if I run a normal recursion program in
erlang infinitely ?

What will be the behavior of erlang scheduler in this scenario ?

Can somebody please assist me on this issue.

Thanks in advance
Arun P.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: System getting hang after running normal recursion program

Ameretat Reith
In C your infinite recursion will cause infinite increase in stack
size (infinite number of return addresses and local variables that
should be remembered). There are some languages coming with
optimizations making you able to call functions infinitely as long as
the last line of code is same function call [1] or another function
call [2]. Erlang is of latter type so if last code of your recursion
function is another function call, there is no reason to terminate it.
Stack won't grow infinitely and Is perfectly fine to keep running.

1: https://en.wikipedia.org/wiki/Tail_call
2: http://erlang.org/pipermail/erlang-questions/2016-October/090663.html
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: System getting hang after running normal recursion program

ARUN P
In reply to this post by ARUN P

Hi Leandro,

Am aware about tail recursion in erlang, but here I am talking about recursion which is not tail recursive. Here is the code snippet;

start(N) ->
    N*start(N-1).

Here the function is not tail recursive and it is in an infinite loop. If run this function my system is getting hang. That why i got the doubt why it is making my system to hang and how the erlang scheduler will behave in this scenario.?

Regards,
Arun P.


On Saturday 07 October 2017 04:07 PM, Leandro Ostera wrote:
Hej Arun, hi.

Depending on your recursion, you may or may not be building up a stack that will at some point crash. I am unsure about how C compilers typically deal with tail-recursion, but tail call optimization is automatically performed in the Erlang VM for you.

From the Learn You Some Erlang book chapter on Recursion (http://learnyousomeerlang.com/recursion):

Note: tail recursion as seen here is not making the memory grow because when the virtual machine sees a function calling itself in a tail position (the last expression to be evaluated in a function), it eliminates the current stack frame. This is called tail-call optimisation (TCO) and it is a special case of a more general optimisation named Last Call Optimisation (LCO).

LCO is done whenever the last expression to be evaluated in a function body is another function call. When that happens, as with TCO, the Erlang VM avoids storing the stack frame. As such tail recursion is also possible between multiple functions. As an example, the chain of functions a() -> b(). b() -> c(). c() -> a(). will effectively create an infinite loop that won't go out of memory as LCO avoids overflowing the stack. This principle, combined with our use of accumulators is what makes tail recursion useful.


Hope this helps!

On Sat, Oct 7, 2017 at 9:03 AM Arun <[hidden email]> wrote:
Hi all,

I tried to run normal recursion program from erlang shell, the program
runs infinitely and it is doing addition of numbers. But its been
observed that soon after starting the program entire PC is getting hang.

My doubt is that, why my PC is getting hang. ? , if something is going
wrong, the erlang vm should be able to handle it, like in C if we run
some recursion program infinity, it will crash by throwing segmentation
fault error.

What will be happening in the VM if I run a normal recursion program in
erlang infinitely ?

What will be the behavior of erlang scheduler in this scenario ?

Can somebody please assist me on this issue.

Thanks in advance
Arun P.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: System getting hang after running normal recursion program

Pierpaolo Bernardi
In reply to this post by ARUN P

Il giorno 7 ottobre 2017, alle ore 14:14, Arun <[hidden email]> ha scritto:

>
>
>Hi Leandro,
>
>Am aware about tail recursion in erlang, but here I am talking about recursion which is not tail recursive. Here is the code snippet;
>
>start(N) ->
>    N*start(N-1).
>
>Here the function is not tail recursive and it is in an infinite loop. If run this function my system is getting hang. That why i got the doubt why it is making my system to hang and how the erlang scheduler will behave in this scenario.?

The numbers involved here grow very quickly. Your system is boggled down by the integer multiplications after a few hundred functions calls, much before the depth of recursion is a problem at all.

If you want to stress recursion depth, try 1+start(N-1), for example.


>
>Regards,
>Arun P.
>
>On Saturday 07 October 2017 04:07 PM, Leandro Ostera wrote:
>
>Hej Arun, hi.
>
>Depending on your recursion, you may or may not be building up a stack that will at some point crash. I am unsure about how C compilers typically deal with tail-recursion, but tail call optimization is automatically performed in the Erlang VM for you.
>
>From the Learn You Some Erlang book chapter on Recursion (http://learnyousomeerlang.com/recursion):
>
>Note: tail recursion as seen here is not making the memory grow because when the virtual machine sees a function calling itself in a tail position (the last expression to be evaluated in a function), it eliminates the current stack frame. This is called tail-call optimisation (TCO) and it is a special case of a more general optimisation named Last Call Optimisation (LCO).
>
>LCO is done whenever the last expression to be evaluated in a function body is another function call. When that happens, as with TCO, the Erlang VM avoids storing the stack frame. As such tail recursion is also possible between multiple functions. As an example, the chain of functions a() -> b(). b() -> c(). c() -> a(). will effectively create an infinite loop that won't go out of memory as LCO avoids overflowing the stack. This principle, combined with our use of accumulators is what makes tail recursion useful.
>
>Hope this helps!
>
>On Sat, Oct 7, 2017 at 9:03 AM Arun <[hidden email]> wrote:
>
>Hi all,
>I tried to run normal recursion program from erlang shell, the program
>runs infinitely and it is doing addition of numbers. But its been
>observed that soon after starting the program entire PC is getting hang.
>My doubt is that, why my PC is getting hang. ? , if something is going
>wrong, the erlang vm should be able to handle it, like in C if we run
>some recursion program infinity, it will crash by throwing segmentation
>fault error.
>What will be happening in the VM if I run a normal recursion program in
>erlang infinitely ?
>What will be the behavior of erlang scheduler in this scenario ?
>Can somebody please assist me on this issue.
>Thanks in advance
>Arun P.
>_______________________________________________
>erlang-questions mailing list
>[hidden email]
>http://erlang.org/mailman/listinfo/erlang-questions
>


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: System getting hang after running normal recursion program

Richard Carlsson-3
In reply to this post by ARUN P
Your small function has no way to terminate, and very quickly eats up your system RAM with its ever growing stack. The CPU load is not the problem.


        /Richard

2017-10-07 14:14 GMT+02:00 Arun <[hidden email]>:

Hi Leandro,

Am aware about tail recursion in erlang, but here I am talking about recursion which is not tail recursive. Here is the code snippet;

start(N) ->
    N*start(N-1).

Here the function is not tail recursive and it is in an infinite loop. If run this function my system is getting hang. That why i got the doubt why it is making my system to hang and how the erlang scheduler will behave in this scenario.?

Regards,
Arun P.


On Saturday 07 October 2017 04:07 PM, Leandro Ostera wrote:
Hej Arun, hi.

Depending on your recursion, you may or may not be building up a stack that will at some point crash. I am unsure about how C compilers typically deal with tail-recursion, but tail call optimization is automatically performed in the Erlang VM for you.

From the Learn You Some Erlang book chapter on Recursion (http://learnyousomeerlang.com/recursion):

Note: tail recursion as seen here is not making the memory grow because when the virtual machine sees a function calling itself in a tail position (the last expression to be evaluated in a function), it eliminates the current stack frame. This is called tail-call optimisation (TCO) and it is a special case of a more general optimisation named Last Call Optimisation (LCO).

LCO is done whenever the last expression to be evaluated in a function body is another function call. When that happens, as with TCO, the Erlang VM avoids storing the stack frame. As such tail recursion is also possible between multiple functions. As an example, the chain of functions a() -> b(). b() -> c(). c() -> a(). will effectively create an infinite loop that won't go out of memory as LCO avoids overflowing the stack. This principle, combined with our use of accumulators is what makes tail recursion useful.


Hope this helps!

On Sat, Oct 7, 2017 at 9:03 AM Arun <[hidden email]> wrote:
Hi all,

I tried to run normal recursion program from erlang shell, the program
runs infinitely and it is doing addition of numbers. But its been
observed that soon after starting the program entire PC is getting hang.

My doubt is that, why my PC is getting hang. ? , if something is going
wrong, the erlang vm should be able to handle it, like in C if we run
some recursion program infinity, it will crash by throwing segmentation
fault error.

What will be happening in the VM if I run a normal recursion program in
erlang infinitely ?

What will be the behavior of erlang scheduler in this scenario ?

Can somebody please assist me on this issue.

Thanks in advance
Arun P.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: System getting hang after running normal recursion program

Richard Carlsson-3
Exactly. Erlang processes manage their own stacks and reallocate and grow them as needed. This means that stacks can start out very small (like 2-4 k) and you can have millions of processes without running out of address space for stacks.


        /Richard

2017-10-07 15:23 GMT+02:00 Leandro Ostera <[hidden email]>:
@Richard, so there's no static stack limit, but rather the stack grows dynamically and the evaluation will be RAM-bound?

On Sat, Oct 7, 2017 at 3:04 PM Richard Carlsson <[hidden email]> wrote:
Your small function has no way to terminate, and very quickly eats up your system RAM with its ever growing stack. The CPU load is not the problem.


        /Richard

2017-10-07 14:14 GMT+02:00 Arun <[hidden email]>:

Hi Leandro,

Am aware about tail recursion in erlang, but here I am talking about recursion which is not tail recursive. Here is the code snippet;

start(N) ->
    N*start(N-1).

Here the function is not tail recursive and it is in an infinite loop. If run this function my system is getting hang. That why i got the doubt why it is making my system to hang and how the erlang scheduler will behave in this scenario.?

Regards,
Arun P.


On Saturday 07 October 2017 04:07 PM, Leandro Ostera wrote:
Hej Arun, hi.

Depending on your recursion, you may or may not be building up a stack that will at some point crash. I am unsure about how C compilers typically deal with tail-recursion, but tail call optimization is automatically performed in the Erlang VM for you.

From the Learn You Some Erlang book chapter on Recursion (http://learnyousomeerlang.com/recursion):

Note: tail recursion as seen here is not making the memory grow because when the virtual machine sees a function calling itself in a tail position (the last expression to be evaluated in a function), it eliminates the current stack frame. This is called tail-call optimisation (TCO) and it is a special case of a more general optimisation named Last Call Optimisation (LCO).

LCO is done whenever the last expression to be evaluated in a function body is another function call. When that happens, as with TCO, the Erlang VM avoids storing the stack frame. As such tail recursion is also possible between multiple functions. As an example, the chain of functions a() -> b(). b() -> c(). c() -> a(). will effectively create an infinite loop that won't go out of memory as LCO avoids overflowing the stack. This principle, combined with our use of accumulators is what makes tail recursion useful.


Hope this helps!

On Sat, Oct 7, 2017 at 9:03 AM Arun <[hidden email]> wrote:
Hi all,

I tried to run normal recursion program from erlang shell, the program
runs infinitely and it is doing addition of numbers. But its been
observed that soon after starting the program entire PC is getting hang.

My doubt is that, why my PC is getting hang. ? , if something is going
wrong, the erlang vm should be able to handle it, like in C if we run
some recursion program infinity, it will crash by throwing segmentation
fault error.

What will be happening in the VM if I run a normal recursion program in
erlang infinitely ?

What will be the behavior of erlang scheduler in this scenario ?

Can somebody please assist me on this issue.

Thanks in advance
Arun P.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions




_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: System getting hang after running normal recursion program

zxq9-2
In reply to this post by ARUN P
On 2017年10月07日 土曜日 17:44:00 Arun wrote:

> Hi Leandro,
>
> Am aware about tail recursion in erlang, but here I am talking about
> recursion which is not tail recursive. Here is the code snippet;
>
> start(N) ->
>      N*start(N-1).
>
> Here the function is not tail recursive and it is in an infinite loop.
> If run this function my system is getting hang. That why i got the doubt
> why it is making my system to hang and how the erlang scheduler will
> behave in this scenario.?

Infinite depth recursion will make your system run out of memory, not CPU. The call stack is just growing and growing and growing...

This has nothing to do with the schedulers at all -- they will behave the way they always would, but will be starved for things to do because your system will the thrashing (swapping in and out of virtual memory on disk in the common case).

The reason this slows the entire system down is because the WHOLE SYSTEM is now starved for memory and is thrashing, including your OS and anything else running. Eventually the size of the Erlang runtime will grow large enough that the system's OOM killer will terminate it and things will return to normal.

If you want to see this effect firsthand but much more quickly, turn off swap.

That said, deep recursion is occasionally the correct approach to take, particularly in problems where the natural solution is iterative and deep, and the depth is known to be finite (the shape of some trees, like filesystems, and certain cases of document or string processing).

-Craig
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: System getting hang after running normal recursion program

Dominic Morneau
In reply to this post by ARUN P
To add to the other replies, you can also set a heap size limit and have the VM kill your process if it grows too much:

1> erlang:process_flag(max_heap_size, 10000000).
#{error_logger => true,kill => true,size => 0}
2> Start = fun Start(N) -> N * Start(N - 1) end.
#Fun<erl_eval.30.99386804>
3> Start(1).

=ERROR REPORT==== 9-Oct-2017::11:59:38 ===
     Process:          <0.64.0>
     Context:          maximum heap size reached
     Max Heap Size:    10000000
     Total Heap Size:  15420698
     Kill:             true
     Error Logger:     true
     GC Info:          [{old_heap_block_size,5157867},
                        {heap_block_size,11347307},
                        {mbuf_size,0},
                        {recent_size,1308970},
                        {stack_size,1084478},
                        {old_heap_size,0},
                        {heap_size,4073388},
                        {bin_vheap_size,4},
                        {bin_vheap_block_size,46422},
                        {bin_old_vheap_size,0},
                        {bin_old_vheap_block_size,46422}]
** exception exit: killed
4>

Dominic

2017-10-07 21:14 GMT+09:00 Arun <[hidden email]>:

Hi Leandro,

Am aware about tail recursion in erlang, but here I am talking about recursion which is not tail recursive. Here is the code snippet;

start(N) ->
    N*start(N-1).

Here the function is not tail recursive and it is in an infinite loop. If run this function my system is getting hang. That why i got the doubt why it is making my system to hang and how the erlang scheduler will behave in this scenario.?

Regards,
Arun P.


On Saturday 07 October 2017 04:07 PM, Leandro Ostera wrote:
Hej Arun, hi.

Depending on your recursion, you may or may not be building up a stack that will at some point crash. I am unsure about how C compilers typically deal with tail-recursion, but tail call optimization is automatically performed in the Erlang VM for you.

From the Learn You Some Erlang book chapter on Recursion (http://learnyousomeerlang.com/recursion):

Note: tail recursion as seen here is not making the memory grow because when the virtual machine sees a function calling itself in a tail position (the last expression to be evaluated in a function), it eliminates the current stack frame. This is called tail-call optimisation (TCO) and it is a special case of a more general optimisation named Last Call Optimisation (LCO).

LCO is done whenever the last expression to be evaluated in a function body is another function call. When that happens, as with TCO, the Erlang VM avoids storing the stack frame. As such tail recursion is also possible between multiple functions. As an example, the chain of functions a() -> b(). b() -> c(). c() -> a(). will effectively create an infinite loop that won't go out of memory as LCO avoids overflowing the stack. This principle, combined with our use of accumulators is what makes tail recursion useful.


Hope this helps!

On Sat, Oct 7, 2017 at 9:03 AM Arun <[hidden email]> wrote:
Hi all,

I tried to run normal recursion program from erlang shell, the program
runs infinitely and it is doing addition of numbers. But its been
observed that soon after starting the program entire PC is getting hang.

My doubt is that, why my PC is getting hang. ? , if something is going
wrong, the erlang vm should be able to handle it, like in C if we run
some recursion program infinity, it will crash by throwing segmentation
fault error.

What will be happening in the VM if I run a normal recursion program in
erlang infinitely ?

What will be the behavior of erlang scheduler in this scenario ?

Can somebody please assist me on this issue.

Thanks in advance
Arun P.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions