|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, its 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.
Whats 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 doesnt 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 thats enough to give you the idea. Its 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:
With each iteration youll 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, Ive learned that given current processors and compiler technology, data recursion isnt going to get me any big wins; and yes, that was news to me. Thats 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 wont hold still for you, but fortunately you can run fast enough to keep up if you just keep at it.
Depths within depths indeed!
In the next chapter, well build a BSP-tree compiler, and after that, well 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 http://www.qualia.com/bspfaq/. Its set up in the familiar Internet Frequently Asked Questions (FAQ) style, and is very good stuff.
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|