Previous Table of Contents Next

Things change when maximum optimization is selected, however: The performance of the two implementations becomes virtually identical! How can this be? Part of the answer is that the compiler does an amazingly good job with Listing 59.2. Most impressively, when compiling Listing 59.2, the compiler actually converts all right-subtree descents from code recursion to data recursion, by simply jumping back to the left-subtree handling code instead of recursively calling WalkTree(). This means that half the time Listing 59.4 has no advantage over Listing 59.2; in fact, it’s at a disadvantage because the code that the compiler generates for handling right-subtree descent in Listing 59.4 is somewhat inefficient, but the right-subtree code in Listing 59.2 is a marvel of code generation, at just 3 instructions.

What’s more, although left-subtree traversal is more efficient with data recursion than with code recursion, the advantage is only four instructions, because only one parameter is passed and because the compiler doesn’t bother setting up an EBP-based stack frame, instead it uses ESP to address the stack. (And, in fact, this cost could be reduced still further by eliminating the check for a NULL pNode at all but the top level.) There are other interesting aspects to what the compiler does with Listings 59.2 and 59.4 but that’s enough to give you the idea. It’s worth noting that the compiler might not do as well with code recursion in a more complex function, and that a good assembly language implementation could probably speed up Listing 59.4 enough to make it measurably faster than Listing 59.2, but not even close to being enough faster to be worth the effort.

The moral of this story (apart from it being a good idea to enable compiler optimization) is:

1.  Understand what you’re doing, through and through.
2.  Build a complete and consistent model in your head.
3.  Design from the principles that the model provides.
4.  Implement the design.
5.  Measure to learn what you’ve wrought.
6.  Go back to step 1 and apply what you’ve just learned.

With each iteration you’ll dig deeper, learn more, and improve your ability to know where and how to focus your design and programming efforts. For example, with the C compilers I used five to 10 years ago, back when I learned about the relative strengths and weaknesses of code and data recursion, and with the processors then in use, Listing 59.4 would have blown away Listing 59.2. While doing this chapter, I’ve learned that given current processors and compiler technology, data recursion isn’t going to get me any big wins; and yes, that was news to me. That’s good; this information saves me from wasted effort in the future and tells me what to concentrate on when I use recursion.

Assume nothing, keep digging deeper, and never stop learning and growing. The world won’t hold still for you, but fortunately you can run fast enough to keep up if you just keep at it.

Depths within depths indeed!

Surfing Amidst the Trees

In the next chapter, we’ll build a BSP-tree compiler, and after that, we’ll put together a rendering system built around the BSP trees the compiler generates. If the subject of BSP trees really grabs your fancy (as it should if you care at all about performance graphics) there is at this writing (February 1996) a World Wide Web page on BSP trees that you must investigate at It’s set up in the familiar Internet Frequently Asked Questions (FAQ) style, and is very good stuff.

Related Reading

Foley, J., A. van Dam, S. Feiner, and J. Hughes, Computer Graphics: Principles and Practice (Second Edition), Addison Wesley, 1990, pp. 555-557, 675-680.

Fuchs, H., Z. Kedem, and B. Naylor, “On Visible Surface Generation by A Priori Tree Structures,” Computer Graphics Vol. 17(3), June 1980, pp. 124-133.

Gordon, D., and S. Chen, “Front-to-Back Display of BSP Trees,” IEEE Computer Graphics and Applications, September 1991, pp. 79-85.

Naylor, B., “Binary Space Partitioning Trees as an Alternative Representation of Polytopes,” Computer Aided Design, Vol. 22(4), May 1990, pp. 250-253.

Previous Table of Contents Next

Graphics Programming Black Book © 2001 Michael Abrash