1. 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...
2. RE: Translated w/ 2.4 CRASH
- Posted by kbochert at copper.net
Jun 27, 2003
On 27 Jun 2003 at 20:32, Andy Serpa wrote:
> >
>
> 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...
>
Do you have the source? You might try
increasing the extra bytes allocated for sequences.
When I saw the same slowdown on Bach, I discovered that adding
32 bytes to the allocation solved the problem.
I have no idea why!
It may just move the slowdown to a higher threshold.
I have had no problems, but I don't generally do large
allocations.
I think I can post the fix in the form of:
file:function -- change x to y.
But I will first give Rob a chance to object or comment.
I would like to see someone give this fix a workout.
Regards
Karl Bochert
3. RE: Translated w/ 2.4 CRASH
> >
> Do you have the source? You might try
> increasing the extra bytes allocated for sequences.
> When I saw the same slowdown on Bach, I discovered that adding
> 32 bytes to the allocation solved the problem.
> I have no idea why!
> It may just move the slowdown to a higher threshold.
> I have had no problems, but I don't generally do large
> allocations.
> I think I can post the fix in the form of:
> file:function -- change x to y.
> But I will first give Rob a chance to object or comment.
>
> I would like to see someone give this fix a workout.
>
Nope, no source. I would have no idea what I'm looking at with the
source. If you want to send me a modified interpreter, I'll try it
out...
4. RE: Translated w/ 2.4 CRASH
- Posted by kbochert at copper.net
Jun 27, 2003
On 27 Jun 2003 at 21:21, Andy Serpa wrote:
>
>
> > Do you have the source? You might try
> > increasing the extra bytes allocated for sequences.
> > When I saw the same slowdown on Bach, I discovered that adding
> > 32 bytes to the allocation solved the problem.
> > I have no idea why!
> > It may just move the slowdown to a higher threshold.
> > I have had no problems, but I don't generally do large
> > allocations.
> > I think I can post the fix in the form of:
> > file:function -- change x to y.
> > But I will first give Rob a chance to object or comment.
> >
> > I would like to see someone give this fix a workout.
> >
>
> Nope, no source. I would have no idea what I'm looking at with the
> source. If you want to send me a modified interpreter, I'll try it
> out...
>
Unfortunately, the only modified interpreter I have is Bach (2.0),
and my old 2.3 source is in an unbuildable state.
Perhaps some third party could translate my fix into
a modified interpreter?
Karl Bochert
5. RE: Translated w/ 2.4 CRASH
>
> Computer storage heirarchies (on-chip cache, secondary cache, main
> memory,
> swap area on disk) try to retain the most recently used
> information in fast memory, while pushing the rest out to slower memory.
> This tends to work fine for code, since programs spend a lot of time in
> small loops, but it often breaks down badly where
> a program is repeatedly sweeping through huge arrays of data
> from beginning to end. Instead of fetching most values
> from fast memory, you might end up fetching most from slow memory.
> This can be disasterous for performance.
>
> I've seen programs suddenly lose a few orders of magnitude of
> performance when their memory requirements exceeded some threshold.
>
>
That makes sense since the tree is partitioning up a big data set and
will need more or less random access to the set. However, the problem
still only occurs w/ 2.4, although the first iteration in 2.3 takes a
lot longer...
6. RE: Translated w/ 2.4 CRASH
- Posted by rforno at tutopia.com
Jun 28, 2003
I recall having tried Ackermann's function in 2.3 without problem.
Regards.
----- Original Message -----
From: Andy Serpa <ac at onehorseshy.com>
Subject: Translated w/ 2.4 CRASH
>
>
> 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.
>
> 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?
>
>
>
> TOPICA - Start your own email discussion group. FREE!
>
>
