I''ve already got the BSP thing going, but how do you walk through it without recursion?..I''m sure I could design some type of nightmare, but I''d rather hear it from someone who''s done it..anyone?.. "Like all good things, it starts with a monkey.."

Um... why would you want to?

I''m assuming you''re trying to display your tree or something. I guess you could do it by throwing everything you find into a linked list (or an array if you have a finite known number of nodes) but quite honestly walking through a binary tree without recursion is going to be what I would term "really freaking painful".

-fel

In order to program any binary tree traversal without explicit recursion (not just a BSP), you need to manually maintain a stack. One way is to maintain a resizable array of pointers to nodes. Then for node traversal, keep going down the one side of the nodes, and whenever you transition off that side of a node, put the node at the end of the array. When you reach a node that you can no longer traverse from on that side, get the last node in the array, remove it, and process the node on that node''s other side, again traversing down the original direction.

I was afraid of that..here''s a quote from an inspiring SoapBox post:

////////////////////////////
Want to know why we get so many annoying newbie questions? Because the newbies do not have any foundation of knowledge to even attempt to create a game as simple as Pong. There are questions about DirectX from people who can''t even understand the object model exposed by C++ and/or COM. Posts about optimization problems from those who can''t even code a non-recursive in-order traversal of a binary tree.
////////////////////////////
Posted By: msn@glue.umd.edu

My engine runs just fine, but if there''s an easy, efficient method of non-recursively walking the BSP that gives a big performance boost, naturally I want to know about it
BTW I am No Newbie..
I''m lead engine programmer with a top-notch software R&D team, and I''ve never SEEN an efficient BSP-based engine that DIDN''T use recursion..obviously I''ve been in the dark about things

It''s a real shame that msn@glue.umd.edu sounds like such a dick, otherwise I''d probably ask him directly..



"Like all good things, it starts with a monkey.."

To be honest I kind of thought the whole point of using recursion is that if you can manage to get it working it''s the fastest, most elegant, and shortest (code-length-wise) way of doing whatever it is you''re trying to do.

I''d be curious too if someone could come up with a traversal of a binary tree not using recursion that somehow buys you something. Can''t really imagine what it would buy you to be honest, since it would probably have to be rather long, and you''re going to have to visit every node regardless so it wouldn''t speed it up any probably. It probably couldn''t be more efficient, because it''s really efficient to do recursion on BSP trees due to the fact that you''re actually technically queueing the information you''re reading but you''re queueing it on the stack itself in the form of information held in temporarily paused functions, and I can''t imagine coming up with anything more efficient than that.

-fel

We had a fairly lengthy discussion of this in a thread about a month back. I was strongly fighting for the side of recursion. Well, a lot of code flew around, and it turns out that for a lot of recursive problems, the non-recursive solution executes faster. Calls to recursive functions do take some time. I think if one were to implement an inline stack, one could probably get some performance gain. It would have to be profiled experimentally, but that was the outcome of the discussion. I was pretty disappointed, since recursion is so elegant & nifty. Oh well.

quote: Original post by monkeyman
It's a real shame that msn@glue.umd.edu sounds like such a dick, otherwise I'd probably ask him directly..

That email doesn't work anymore... U of MD deleted my account when I graduated .

Anywho, doing a non-recursive inorder traversal of a BSP tree with full optimizations turned on in VC6 will not run noticeably faster than a regular recursive traversal. The VC compiler has some impressive optimization algorithms, and will optimize the tail recursion into a simple loop.[1]

But, for the sake of completeness, here's some pseudocode:

    struct Node{    Node* left;    Node* right;    T data;};void WalkInorder( Node* root ){    Node* stack[]; //allocate this however you want.    Node* iter = stack;    *iter++ = 0;    Node* curr = root;    while( curr )    {        while( curr )        {            *iter++ = curr;            curr = curr->left;        }        if( *--iter )        {            ProcessNode( *iter );            curr = *iter->right;        }    }};  

Note that for a BSP, you'll need to muck around so that you traverse down the correct side. That's left up as an exercise to the reader however

MSN

[1] Zen of Graphics Programming, 2nd edition. Check here for a possibly better implementation of a non-recursive inorder tree traversal.


Edited by - msn12b on December 1, 2000 7:17:32 PM

Gee, you don''t sound like such a dick after all

The pseudocode definitely helped, I see what you''re saying
now..I have never seen a better example of putting pointer
arithmetic to work..I''ll have to try that..

I know recursion can be an evil thing in high-performance apps, but I hadn''t seen an alternative to the BSP walk until now..I hadn''t considered the pointer math..now I shall take over the world >

Thanks for answering my post despite my comments

You are the man

"Like all good things, it starts with a monkey.."

quote: Original post by felisandria
To be honest I kind of thought the whole point of using recursion is that if you can manage to get it working it''s the fastest, most elegant, and shortest (code-length-wise) way of doing whatever it is you''re trying to do.

Provided, of course, that the algorithm is particularly amenable to recursive solutions. Consider, for example, that tic-tac-toe problem that just came up.

quote:
I''d be curious too if someone could come up with a traversal of a binary tree not using recursion that somehow buys you something. Can''t really imagine what it would buy you to be honest, since it would probably have to be rather long, and you''re going to have to visit every node regardless so it wouldn''t speed it up any probably. It probably couldn''t be more efficient, because it''s really efficient to do recursion on BSP trees due to the fact that you''re actually technically queueing the information you''re reading but you''re queueing it on the stack itself in the form of information held in temporarily paused functions, and I can''t imagine coming up with anything more efficient than that.

-fel

For argument''s sake, let''s consider the recursive implementation of a function independent binary tree traversal on a pipelined MIPS processor (the latter because I don''t want arguments on the relative merits of the x86 instruction cycle length, encoding, etc.)
It''s function prototype would probably looks something like:
void Traverse(Node * root, int (*fp)(Node *));

The register convention for the MIPS processor imply that the arguments are passed through the registers. So probably $a0 and $a1 will receive the node pointer and the function pointer. However because this is a recursive function we''ll need to store these values on the stack. Minimally you''d need, for every function call, to push the Node pointer, the function pointer, and the return address on the stack every time, for the recursive implementation. Thankfully, we can probably get away with not pushing the stack or frame pointers.

Now we''re going to do something vaguely evil and start constructing an iterative traversal of the tree using the stack as our stack. We''ll dive into assembly, but we still have to obey certain register conventions if we want this code to play happily with other code. (for example, that nice function that we got as an argument)

First things first. We notice that the function pointer doesn''t change for any of the invocations of the recursive call. So upon entry to our new function, we move the function pointer to $s0. And because we call a function from this function we also need to store the return address. Let''s stick it on the stack. We''ll place a sentinal value of zero at the current location of the stack pointer. Every time we encounter a new node, we decrement the stack pointer and place the node on the stack. And everytime can no longer left traverse, we pop a node from the stack, stopping when we hit our sentinal.

Assembly pseduo-code, for the recursive function:

$sp = $sp - 12 // stack stuff$sp[12] = $s0$sp[8]  = $s1$sp[4]  = $ra$s0 = $a0$s1 = $a1$t0 = $a0[0]  // node->leftbez $t0, skip1 // if node->left traverse left  $a0 = $t0  jal SELF  // recurse on leftskip1:$a0 = $s0jal $s1     // perform function$a0 = $s0[4]  // node->rightbez $a0, skip2 // if node->right traverse right  $a1 = $s1  jal SELF  // recurse on rightskip2:$ra = $sp[4]$s0 = $sp[12]$s1 = $so[8]$sp = $sp + 12jre $ra 

Assembly pseudo-code, for the iterative function:

$sp = $sp - 16$sp[16] = $s0 // store $s vars$sp[12] = $s3$sp[8] = $ra  // store return address$sp[4] = 0    // install sentinal$s0 = $a1  // fp$s3 = $a0  // node addressbez $s3, returnouter:  $sp[0] = $s3  // push current node on stack  $sp = $sp - 4  $s3 = $s3[0]  // current node = node->left  bnez $s3, outer  // repeat while not zeroinner:  $sp = $sp + 4 // pop node from stack  $s3 = $sp[0]  bez $s3, return // reached sentinal, so return  $a0 = $s3  // process node  jal $s0  $s3 = $s3[4] // current node = node->right  bnez $s3, outer  b innerreturn:$ra = $sp[4]$s0 = $sp[12]$s3 = $sp[8]$sp = $sp - 12jre $ra 

It may be hard to see, but the memory motion in the latter case is much lower. Everytime the recursive function is called three items are placed on the stack, and on exit three items are popped from the stack. In the iterative function whenever the stack is accessed (aside from entry/exit) only one load/store is called. So it''s overall more cache friendly. And because we use the stack as our stack, no additional memory allocation overhead is incurred either. Also, when performing the actual traversals, fewer instructions are needed in the iterative method. i.e. the number of instructions in the loop is smaller than the number of instructions in the recursive funciton.

quote: Original post by Stoffel

We had a fairly lengthy discussion of this in a thread about a month back. I was strongly fighting for the side of recursion. Well, a lot of code flew around, and it turns out that for a lot of recursive problems, the non-recursive solution executes faster. Calls to recursive functions do take some time. I think if one were to implement an inline stack, one could probably get some performance gain. It would have to be profiled experimentally, but that was the outcome of the discussion. I was pretty disappointed, since recursion is so elegant & nifty. Oh well.

Uhh, I believe the end result of the above mentioned discussion was that a truly native recursive function will save you maybe 6% or so if implemented iteratively, assuming there is no actual work to do on each node. If you actually have to do work at each node (welcome to the real world, people), then your savings drops to something possibly significantly less than 6%.