Recursion on REXX/2 
Author Message
 Recursion on REXX/2



I have found a problem with REXX recursion on OS/2.  I'm
using classic REXX for portability to machines not yet
running OREXX.  Hopefully someone can offer a suggestion.

Recently I had need to sort a large (circa ten thousand
values) word list as part of a web indexing routine I've
written.  When an insertion sort proved too slow, I wrote
a poor man's B-tree handler.  Given that the incoming data
is a fairly good approximation of random order, I did not
add balancing logic and assumed that the tree would more or
less balance itself.

My insertion algorithm works perfectly and I have succeeded
in building B-trees of many thousands of entries in memory.
Unfortunately, the "walk the tree" extraction algorithm was
easiest to implement using recursion, and therein lies the
problem.  My code worked perfectly on test datasets up to
around 4500 unique entries, but on my live data it fails
part way through with a "control stack overflow".  From my
assembly language background I gather that this means I
recursed too deeply for the interpreter to handle, and in
fact my call traceback had about 30 or so entries.  It looks
as if my tree for this particular dataset was unbalanced
rather badly.

For the short term, I chose to rewrite the extract using a
nonrecursive algorithm and I have the code working.  But I
really liked the recursive method and if I could get it
working, I would go back and use it.  The recursive call is
a very "clean" algorithm and very intuitive to read and
maintain, whereas the nastiness that replaced it has to keep
state variable information in globals (yech!) to avoid
following the same branches more than once.

My questions, then, are these:

1.  Can I control the size of the internal stack of REXX/2?
    My machine has 40 meg of RAM and plenty of swap, so if I
    need to allocate ten meg of stack, so be it.

2.  Clearly my tree is "deeper" than it needs to be for this
    number of items.  Anyone got a good balancing algorithm
    for which they'd like to share pseudocode?

3.  The data that I actually sort is really just a value and
    a numeric index into a set of arrays containing the record
    fields.  When I extract, I need to pass these to the routine
    that gets called to process each outbound record.  This means
    that although my BTREE_EXTRACT() function is a PROCEDURE, I
    have to EXPOSE all these stems and they are large.  I would
    think that an EXPOSE global would not be replicated on the
    call stack internally, but am I wrong in this assumption?

4.  Guru question:  I also know how to write REXX callable C
    functions.  If I implement this in C, will I run into the
    same problem?  I've never gotten that deeply into REXX's
    stack mechanism with DLL-called functions before.  Anyone
    care to comment on this issue?

Thanks for any comments, suggestions, or advice!

------------------------------------------------------------------
You cannot get high from   | Scott D. Courtney, Sr. Telecomm Analyst
Ethernet, even by sniffing | The Timken Company (Canton, Ohio, USA)
the cut end of a cable.    | *** Web Site (Timken internal only) ***
     -- Dogbert            | http://www.*-*-*.com/ ~courtney



Sat, 28 Aug 1999 03:00:00 GMT  
 Recursion on REXX/2

On Tuesday, 97/03/11, "Scott D. Courtney" wrote to All about
"Recursion on REXX/2" as follows:

C> 1.  Can I control the size of the internal stack of REXX/2?

No, you cannot adjust the stack.

C> 2.  Clearly my tree is "deeper" than it needs to be for this
C>     number of items.  Anyone got a good balancing algorithm
C>     for which they'd like to share pseudocode?

Use Sedgewick's variant of Quicksort; it's non-recursive.
Alternatively, several freeware/shareware extension DLL's have sort
functions. I use REXXLIB for sorting stems.

C> 3.  The data that I actually sort is really just a value and
C>     a numeric index into a set of arrays containing the record
C>     fields.  When I extract, I need to pass these to the routine
C>     that gets called to process each outbound record.  This means
C>     that although my BTREE_EXTRACT() function is a PROCEDURE, I
C>     have to EXPOSE all these stems and they are large.  I would
C>     think that an EXPOSE global would not be replicated on the
C>     call stack internally, but am I wrong in this assumption?

A global reference should not take up stack space, but the mere fact
that you are calling causes contexts to be saved (pushed) and restored
(popped) upon return.

C> 4.  Guru question:  I also know how to write REXX callable C
C>     functions.  If I implement this in C, will I run into the
C>     same problem?  I've never gotten that deeply into REXX's
C>     stack mechanism with DLL-called functions before.  Anyone
C>     care to comment on this issue?

This is one of the nastiest features of the internals of the OS/2
Classic REXX interpreter. No matter how big a stack you pass it, it
replaces that stack with its own and all extension DLL's and
sub-commnad handlers have to live with that limited stack. My
speculation is that REXX does not use stack probes and so it replaces
a potentially sparse stack with a fully committed one. I hope this is
fixed in Object REXX, but I somehow doubt IBM would address such a
'techie' issue as this.

The most efficacious work-around is to have the extension DLL do its
processing in another thread that has a stack large enough to deal
with the data being handled.

Regards

Dave
<Team PL/I>

 * KWQ/2 1.2i * Bring back the snakes! Ireland was better off Pagan.
--
Please remove the '$' in the from line before reply via email.
Anti-UCE filter in operation.



Sun, 29 Aug 1999 03:00:00 GMT  
 Recursion on REXX/2

Quote:

> On Tuesday, 97/03/11, "Scott D. Courtney" wrote to All about
> "Recursion on REXX/2" as follows:

> C> 1.  Can I control the size of the internal stack of REXX/2?

> No, you cannot adjust the stack.

I was afraid of that.  Never hurts to ask, though.

Quote:

> C> 2.  Clearly my tree is "deeper" than it needs to be for this
> C>     number of items.  Anyone got a good balancing algorithm
> C>     for which they'd like to share pseudocode?

> Use Sedgewick's variant of Quicksort; it's non-recursive.
> Alternatively, several freeware/shareware extension DLL's have sort
> functions. I use REXXLIB for sorting stems.

The problem is I need to do more than just sort a single stem.
The stem elements are indices into other stems, and I need to
sort on the indirect reference.  I haven't seen any sort utility
that is able to do this.

[....]

Quote:
> A global reference should not take up stack space, but the mere fact
> that you are calling causes contexts to be saved (pushed) and restored
> (popped) upon return.

That's what I figured.  But either their stack is miniscule, or their
call overhead is tremendous!  I was only nested a couple dozen levels.

Quote:

> C> 4.  Guru question:  I also know how to write REXX callable C
> C>     functions.  If I implement this in C, will I run into the
> C>     same problem?  I've never gotten that deeply into REXX's
> C>     stack mechanism with DLL-called functions before.  Anyone
> C>     care to comment on this issue?

> This is one of the nastiest features of the internals of the OS/2
> Classic REXX interpreter. No matter how big a stack you pass it, it
> replaces that stack with its own and all extension DLL's and
> sub-commnad handlers have to live with that limited stack.
[....]
> The most efficacious work-around is to have the extension DLL do its
> processing in another thread that has a stack large enough to deal
> with the data being handled.

That's a pretty interesting thought.  I need synchronous behavior, but
what about creating a thread in my DLL, with a very large stack, then
just pausing the main thread until the subthread finishes?  It's ugly
but it might work.

I am seriously considering rewriting this thing in Java anyway, which
may make the whole point moot.  It's working well as-is but I want
to distribute it on the network.  Yes, I know of NetREXX and will
take a good look at it, too.

Thanks for the suggestions and information.

------------------------------------------------------------------
You cannot get high from   | Scott D. Courtney, Sr. Telecomm Analyst
Ethernet, even by sniffing | The Timken Company (Canton, Ohio, USA)
the cut end of a cable.    | *** Web Site (Timken internal only) ***
     -- Dogbert            | http://www.ctnvm.inside.tkr/~courtney



Tue, 07 Sep 1999 03:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. RECURSION RECURSION RECURSION ... AAARRGGHHHH

2. Regina RExx and recursion?

3. Tail recursion and complete recursion?

4. REXX in WINDOWS/REXX Add-ins/VISUAL REXX ????

5. calling Non-Rexx DLLs from REXX with RXU

6. Porting from REXX on VM to Object REXX on AIX or W2000

7. for help about vispro rexx and Object REXX

8. Porting an OS/2 Rexx to Regina Rexx

9. Calling Rexx from Rexx

10. Rexx-Mode.el, Rexx syntax support for Gnu-Emacs(1/1)

11. Object REXX: incompatibility with T-REXX ?

12. Rexx or Obj-Rexx for web programming?

 

 
Powered by phpBB® Forum Software