1. 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?
2. Re: Translated w/ 2.4 CRASH
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.
> 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.
Regards,
Rob Craig
Rapid Deployment Software
http://www.RapidEuphoria.com
3. Re: Translated w/ 2.4 CRASH
Andy Serpa wrote:
> Aha... gotta get that XP one of these days. This ME is driving me crazy
> for lots of other reasons...
Well, I just tried ack(3, 10) and it ran out of stack
space on XP with Watcom, but was ok with Borland.
(3, 9) worked with both. OPTION STACK=400000 made (3, 10)
work with Watcom too.
So I guess XP has stack limits too.
I've added a note to the Translator docs about this.
> 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.
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.
Regards,
Rob Craig
Rapid Deployment Software
http://www.RapidEuphoria.com
4. Re: Translated w/ 2.4 CRASH
kbochert at copper.net 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.
That's ok with me. Post your fix.
I assume you mean the parameters that control
how much extra space is reserved when a sequence
is appended-to. Increasing that value could speed up certain
code by quite a bit, while wasting some memory
in other situations.
Regards,
Rob Craig
Rapid Deployment Software
http://www.RapidEuphoria.com
5. Re: Translated w/ 2.4 CRASH
- Posted by kbochert at copper.net
Jun 27, 2003
On 27 Jun 2003 at 18:37, Robert Craig wrote:
>
>
> kbochert at copper.net 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.
>
> That's ok with me. Post your fix.
> I assume you mean the parameters that control
> how much extra space is reserved when a sequence
> is appended-to. Increasing that value could speed up certain
> code by quite a bit, while wasting some memory
> in other situations.
>
Always the tradeoffs. Thats one reason why I would like
to have others try it.
Its very simple:
in alloc.c::NewS1()
change:
EMalloc(sizeof(struct s1) + (size+1) * sizeof(object));
To:
EMalloc(sizeof(struct s1) + (size+9) * sizeof(object));
The extra allocation (36 bytes vs 4) seems to have a sharp
threshold -- increasing to 28 bytes say, seemed to have little effect,
but that could easily be because of the specific test program.
(I could almost imagine a 'with bigmem' option for those who
must have the speed at the expense of space)
Karl Bochert
