Version française
Home     About     Download     Resources     Contact us    
Browse thread
RE: [Caml-list] @, List.append, and tail recursion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Brian Hurt <brian.hurt@q...>
Subject: RE: [Caml-list] @, List.append, and tail recursion
On Fri, 31 Jan 2003, Harrison, John R wrote:

> How about the following policy?
> 
>   Don't place any limit on stack growth
> 
> The stack, like the heap, should be capable of expanding to
> fill all available memory. I don't know much about the OS issues
> involved in stack extension, but some such policy seems preferable
> to building in a hard limit.

We need some way to find infinitely recursive functions.  The hard limit 
is a good idea.  Especially considering some OSs (Linux) do not deal well 
with OOM errors.  Linux freely over commits memory- allowing you to 
"allocate" way more memory than exists.  When you first touch the memory 
is when the memory is really allocated.  And if the memory isn't there to 
be allocated, it segfaults.  In practice, this means that when you run out 
of memory on Linux, random processes start to segfault.  Including 
possibly init.

I agree this is a bad design decision.  It is, however, how Linux works.

In fact, I'd argue that the hard limit is too large.  I'd put the limit 
somewhere between 1024 and 8192 deep.  If you are doing O(n) recursion, 
I'd rather find out about it sooner rather than later- it's a lot more 
likely to be hit in testing that way, and fixed.  Note that I'm thinking 
here of the maximum *number* of levels, not the maximum stack size.

Or settable either in the runtime environment, or by the program itself 
(Sys.set_stack_limit()?).

> 
> Users would then be free to write relatively inefficient and
> stack-hungry recursive functions, 

Actually, recursion seems to be very cheap- the recursive append function 
is signifigantly faster than the reversing append, and almost as fast as 
the set_cdr function.

> and at least the implementation
> would do its best to carry recursions as far as possible. The only
> reason I can see for placing a limit on the stack size is that users
> become aware of trivially looping recursions more quickly. But this
> doesn't seem a particularly strong argument.

I like becoming aware of problems in my code as quickly as possible.  It 
lets me fix them quicker.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners