[clean-list] Re: Memory usage in recursion

[Fabien Todescato]

Dear Richard and Eddy,

I am presently using Clean to implement processing of
automatically-generated electronic CAD data, and the average size of my
input files is about 512kb, up to several Mb. I have implemented a =
compiler
with a hand-written state machine for the lexer, and am using a variant =
of
the parser combinators taken from [Koop98] for the parser. For streams =
of up
to several hundred thousands tokens the parser behaves nicely, but =
beyond my
Clean program crashes and tweaking the size of the stack doesn't seem =
to
have any effect at all (I allocated 128Mb of stack to the same effect, =
on a
1Gb machine). It seems that beyond 1Mb of stack nothing changes... I
therefore suspect a problem in the management of the stacks, although =
it
becomes apparent only in extreme cases... I will have to find a =
workaround
and consider reimplementing my parser combinators for large inputs...

As Richard said, the stack is theoretically the best place to put data
because allocating and deallocating is so cheap, but in practice it may
cause troubles as it seems that we cannot have a stack with a size =
beyond
1Mb - observation to be confirmed -.

[Koop98]	Efficient Parser Combinators
		Pieter Koopman, Rinus Plasmeijer
		Downloadable from the Clean Home Page.

Best regards, Fabien TODESCATO

-----Message d'origine-----
De : Eddy Van Esch [mailto:eva@xpeqt.com]
Envoy=E9 : mardi 21 novembre 2000 08:52
=C0 : Richard A. O'Keefe
Cc : clean-list@cs.kun.nl
Objet : [clean-list] Re: Memory usage in recursion


Hi Richard,
Thanks for clearing up a few things.
I thought that recursion always used the stack. Of course, if a tail =
call
is only a jump there couldn't be any problem. I didn't know that.
My concern was that the stack size is determined by the programmer and
wasn't changed by the run time system. So if the stack size would be =
fixed,
a program could run out of stack space. While if it would use the heap, =
the
system could use all of its virtual memory....
But it seems that I have been worrying over nothing..:-)
Kind regards =20
Eddy

At 11:46 21-11-00 +1300, you wrote:
>	As I understand from the Clean tutorial "Functional programming in
Clean",
>	Clean uses quite a lot of recursion to implement certain functions.
>
>Any good book about functional programming will make clear the =
difference
>between "body" calls and "tail" calls; tail calls are effectively =
jumps.
>
>	What I know from other languages is that recursion usually makes
>	extensive use of the stack.  When the code is assembled you
>	usually see a number of 'pushes' and 'pops' to store and
>	retrieve data on the stack.
>
>There need not be any stack at all; Simula 67 put "stack frames" on =
the
>garbage collected heap, and at least some functional languages do that =
to
>this day (which makes it easier to implement concurrency).  Even those
>language implementations that do use a stack do NOT commonly use =
pushes
>or pops for that purpose.  C compilers don't.  The Quintus Prolog =
compiler
>certainly didn't.
>
>	As you all know the danger is that the depth of recursion
>	depends on the data to be processed by the function in question.
>	Usually you don't know in advance what the 'size' of the data
>	will be and you don't know exactly how deep the recursion will
>	be.  As a result of this, a 'stack overflow' can occur.
>
>Danger?  In the case of tail recursion, the depth of recursion could =
be
>a hundred million million billion and the stack depth could still be =
zero.
>But if data _do_ have to be saved on the stack, they have to be saved
>_somewhere_.  Why is running out of stack space thought to be worse
>than running out of space anywhere else?  It's only language
implementations
>such as old MS-DOS C compilers that artificially limited the stack =
size to
>64 kB that had any special problem with this.  If you have 64MB of =
data to
>store and 64MB of memory to put it in, why should you *care* whether =
the
>place it's put is called "stack", "heap", or something else?  For what =
it's
>worth, the stack is probably the cheapest place to put anything, =
because
>it's likely to be reclaimed quickly and cheaply.
>=09
>	Is this also the case in Clean or is the data storage during
recursion
>	handled in a different way?
>
>You don't need to know.  There isn't any special problem.
>

_______________________________________________
clean-list mailing list
clean-list@cs.kun.nl
http://www.cs.kun.nl/mailman/listinfo/clean-list