cwhitley@mole.gnu.ai.mit.edu (Cecil H. Whitley) (04/25/91)
Hi,
I am having some trouble with xlisp 2.1 tc. I compiled the source
using tc++ 1.0 and it apparently runs fine. The problem comes up when
I try to use a recursive function. I wrote a recursive version
of factorial with one parameter x. On the 53 iteration it runs out
of argument stack space. Did I compile it wrong? I used the
makefile that came with the source. The only other possibility is
the differences between tc 2.0 and tc++ 1.0.
Any suggestions of where to look would be appriciated.
Cecil
cwhitley@mole.ai.mit.edu
|
cwhitley@gnu.ai.mit.edutoma@sail.LABS.TEK.COM (Tom Almy) (04/25/91)
In article <15243@life.ai.mit.edu> cwhitley@mole.gnu.ai.mit.edu (Cecil H. Whitley) writes: >Hi, >I am having some trouble with xlisp 2.1 tc. [...] The problem comes up when >I try to use a recursive function. [...] On the 53 iteration it runs out >of argument stack space. Did I compile it wrong? You did it right. That's all the depth you get. Its all a funtion of the compilation constants EDEPTH and ADEPTH, and the stack size (_stklen) specified for Turbo-C. Here is a report on this and other tuning factors that I posted in January 1989. If you are running XLISP that has passed through my hands, then the situation is much improved over the distribution, but you may want to change the constants: ************** The following problems apply, in part, to XLISP running on any system. In my case, I am running on an 80386, MS-DOS system (with PharLap DOS Extender being used for native 80386 operation). I had noticed that the distributed (Turbo-C) version of XLISP would crash upon "too much" recursion, rather than give an error. I discovered that the default stack size (4k, I believe) was used, and the size of argument stack (ADEPTH in xlisp.h) and evaluation stack (EDEPTH) were far bigger than could ever be utilized. Also, the argument stack would overflow well before the evaluation stack when using a large program stack. Setting EDEPTH The growth of the system (C language) stack roughly parallels that of the evaluation stack. For a simple recursive function of the form "(defun foo (...) (cond (..(foo ..))))" seven evaluation stack cells are used per recursion. With an 8086 style compiler, roughly 200 bytes are used on the system stack per recursion, while in the 80386 environment 270 are used (I would expect a 68000 would be about the same as an 80386). Thus, there should be 28 or 38 bytes per cell. With the default EDEPTH of 2000, which allows 280 deep recursion, an 8086 compiler needs a stack of 56k bytes, while an 80386 (or 68000?) needs 76000 bytes. Considering the scarcity of avalailable memory under MSDOS, EDEPTH should probably be reduced instead in this environment! With a stack size of 16k, EDEPTH could be set to 580, allowing about 80 deep recursion. Setting ADEPTH With the above simple recursive function, the argument stack grows at the rate of 6 + #arguments per recursion, or typically the same rate as the evaluation stack. Heavy use of local variables in an iterative program will cause the argument stack to grow much faster. Yet the default ADEPTH value is 1000, or half of EDEPTH! ADEPTH should be at least as large as EDEPTH! Performance Measurement ;;;;; NOTE: THIS IS VERY DATED. ALL OF THE COMPILERS ARE IMPROVED, AND ;;;;; I'VE ACHIEVED PERFORMANCE ENHANCEMENTS IN THE CODE!!! ;;;;; IN THE 16 BIT WORLD, THE ZORTECH 2.1 COMPILER DOES BEST, FOLLOWED ;;;;; BY THE BORLAND C++ 2.0 (AS A C COMPILER). THE METAWARE COMPILER ;;;;; STILL IS BEST FOR 32 BIT OPERATION. I compared XLISP 2.0 compiled under 5 different compilers. In each case, compiler options were used to specify floating point coprocessor, maximum speed optimizations, word aligned data, and most advanced processor (80386, 80286, in that order). During execution, the minimum system configuration was used, allowing maximum memory (of 8 megabytes) to be used by XLISP. The execution time measured was of a program which plays a game of akalah with itself (as good as any benchmark I would guess). Compiler executable maximum stack used execution size nodes per recursion time Turbo 1.5 123878 40640 202 83.5 sec Zortech 1.07 137806 40640 204 85 Microsoft 5.0 141536 36640 200 86.5 Microway NDP 1.4e (80386) 200888 + stack 594640 248 58.5 Metaware HighC 1.4 (80386) 203275 592640 268 57.5 Notes: Turbo-C compiled without a hitch (after all, that was how it was distributed). Zortech (was Datalight) would not compile xldmem.c with optimization (compiler bug reported). The Zortech compiler choked on some expressions where types did not match (this is actually good). Microsoft optimization had to be disabled to generate a working executable. Microway did not provide longjmp support (I had to write it in assembler), and their "shell escape" code could not be used because it gave unresolved routines in the linker. Microway also didn't provide a primitive DOS call mechanism, so I had to write the keyboard/display primitives in assembler. Only the Microway compiler would compile the sources without warnings. Metaware didn't provide a "shell escape" call, so I wrote one which I also used for Microway. The primitive DOS call mechanism was different than that of the three 8086 compilers. Like Zortech, this compiler was finicky about types matching, and choked on several modules. Metaware allows turning off allignment, which drops the size of nodes from 12 to 10 bytes. In this case, the maximum nodes jumps to 708,640, and execution time goes up to 59.5 seconds. Draw your own conclusions. -- Tom Almy toma@sail.labs.tek.com Standard Disclaimers Apply