RE: Translated w/ 2.4 CRASH
Robert Craig wrote:
>
>
> Andy Serpa wrote:
> > Ackermann's function crashes when translated!
> >
> > function ack(integer m, integer n)
> > if m = 0 then
> > return n+1
> > end if
> >
> > if n = 0 then
> > return ack(m-1,1)
> > end if
> > return ack(m-1,ack(m,n-1))
> > end function
> >
> > object x
> >
> > x = ack(3,8)
> >
> >
> > Works fine in the interpreter -- x = 2045. But translated and it
> > crashes on my system with both Watcom & Borland (2.4 beta translator).
> > It crashes outright -- no ex.err at all. It doesn't crash with a lower
> > argument, like (3,7).
> >
> > I assume something to do with excession recursion? I am no longer
> > set-up for translating with 2.3 so I don't know if it is a 2.4 thing,
> > but it seems likely.
>
> Ackermann is *the* classic example of a simple function that
> uses an enormous number of levels of recursion.
> From what I just read on the Web somewhere, the number of levels
> of recursion goes up as 2 to the power n. Your example uses a couple
> of thousand levels of calls. The Euphoria interpreter
> automatically grows the call stack (until all memory is used up).
> Compiled languages, like C, normally have a fixed-size call stack,
> although I thought that Windows could grow the stack. On my XP
> machine this example works fine, but on ME it crashes.
> With WATCOM, I can make it work on ME too, by editing
> "objfiles.lnk" and adding the directive:
> OPTION STACK=100000
> With Borland, it works for me on ME without adding
> any stack directive.
>
Aha... gotta get that XP one of these days. This ME is driving me crazy
for lots of other reasons...
> > By the way, regarding the last problem I reported with a slowdown when
> > recycling a lot of memory -- I discovered a few of my other programs are
> >
> > victim to that as well, especially when using recursive algorithms --
> > they take longer and longer every time they recurse. Maybe it is part
> > of the same problem here?
>
> I don't think recursion has much to do with it.
> Your examples seem to all use hundreds of thousands,
> if not millions of floating-point numbers. They also
> do lots of appends and concatenations to sequences
> of many different sizes. This results in a system heap
> that is huge and fragmented. I believe the poor performance
> stems from that. I don't see any obvious bug
> in Euphoria, in terms of correctness or performance.
>
> In the future I'll take another look at all this,
> to see if there is a better overall algorithm for
> handling extreme cases like yours.
>
There seems to be a definite threshold for encountering these allocation
problems. In my latest example, I am building "decision trees"
recursively. (The data is all integers, by the way.) Works fine most of
the time, but if the size of the data set is over a certain size, it
gets slower & slower. The thing is, it seems to just be the act of
loading the data into memory in the first place that does it. (That once
loaded just sits there.) Even if I set it to only use a small fraction
of the data it still gets slower after loading in the big file. The
main problem with this problem is the fact that it gets slower & slower,
which means before long it basically comes to a stop. With 2.3, certain
algorithms would take a while to get started but then each iteration
would stay a constant speed after that. If you're willing the pay the
price at the beginning, it is still usable. But if it gets
progressively slower you're just screwed. With the decision trees, I
switched the algorithm to a non-recursive one that didn't use nested
sequences. It lowered the amount of the progressive delay by quite a
bit, but didn't eliminate it...
|
Not Categorized, Please Help
|
|
