1. Translated w/ 2.4 CRASH
- Posted by Andy Serpa <ac at onehorseshy.com> Jun 27, 2003
- 392 views
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
- Posted by Robert Craig <rds at RapidEuphoria.com> Jun 27, 2003
- 367 views
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
- Posted by Robert Craig <rds at RapidEuphoria.com> Jun 27, 2003
- 377 views
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
- Posted by Robert Craig <rds at RapidEuphoria.com> Jun 27, 2003
- 380 views
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
- 377 views
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