What’s on the CD-ROM The companion CD-ROM includes all of the source code published as numbered listings in the text of the book, plus compiled executables of many of the demos. In ad- dition, you’ll find the following extras on the CD: The classic Zen Timer code profiling tool, in both executable and source code format. a\ 4 Exclusive! The text of Michael’s long out of print 1989 cult classic Zen of @ AsS6T373ibLlya nguage, plus scans of all 1 OOt technical figures. ant essays from Michael’s ongoing work in game develop- g for the first time in book form. :nts, descriptions, copyrights, installation, limita- ‘n. Hardware Platform: An Intel PC. Note that some code is processor-specific. To run all code you must have at least a Pentium processor. Wimiws 95 or NT. . Black Book Abrash Michael Albany, NY Belmont, CA Bonn Boston Clnclnnatl Detrolt Johannesburg London Madrld Melbourne Mexlco C I N~ew York Paris Slngapore Tokyo Toronto Washlngton Publisher Keith Weiskamp Project Editor Denise Constantine Production Proiect Coordinator Kim Eoff Compositor Rob Mauhar Cover Artist and Cover Design Anthony Stock Proofreaders JefKellum and Meredith Brittain Indexer Caroline Parks CD-ROM Development Robert Clarfield Michael Abrashs Graphics Programming Black Book, Special Edition 1-57610-174-6 Copyright 0 1997 by The Coriolis Group, Inc. All rights reserved. This book may not be duplicated in any way without the express written consent of the publisher, excepti n the form of brief excerpts or quotations fort he purposes of review. The information contained herein is ftohre personal use of the reader and may not be incorporated in any commercial programs, other books, databases, or any kind of software without written consent of the publisher. Making copies of this book or any portion for any purpose other than your own is a violation of United States copyright laws. Limits of Liability and Disclaimer of Warranty The author and publisher of this book have used their best effortsin preparing the book and the programs contained in it. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. Thaeu thor and publisher maken o warranty of any kind, expressed or implied, with regatrod these programs or the documenta- tion contained in this book. The author and publisher shall notb e liable in the event of incidental or consequential dam- ages in connection with, or arising out tohfe, furnishing, performance, our se of the programs, associated instructions,a nd/or claims of productivity gains. Tiademarks Trademarked names appear throughout this book. Rather than list the names and entities that own the trademarks or inserat trademark symbol withe ach mention of the trademarked name, the publisher states thati t is using the names for editorialp urposes only and to the benefit of the trademark owner, with no intention of infringing upon that trademark. The Coriolis Group, Inc. An International Thomson Publishing Company 14455 N. Hayden Road, Suite 220 Scottsdale, Arizona 85260 602/483-0192 FAX 602/483-0193 http://www.coriolis.com Printed in the United States of America 109876543 Acknowledgments Because this bookw as written over many yearsi, n many different settings, an un- usually large number of people have played a part in making this book possible. First and foremost, thanks (yet again) to Jeff Duntemann for getting this book started, doing thed irty work, and keeping things on track and everyone’s spirits up. Thanks to Dan Illowsky for not only contributing ideas and encouragement, but also getting me started writing articles long ago, when I lacked the confidence to do it on my own-and for teaching me how to handle the business end of things. Thanks to Will Fastie for giving me my first crack at writing for a large audience in the long-gone but still-missed PC Tech Journal, and for showing me how much fun it could be in his even longer-vanished but genuinely terrific col- umn in Creative Computing (the most enjoyable single columnI have ever read in a computer magazine; I used to haunt the mailbox around the beginning of the month justt o see whatW ill had to say). Thanks to Robert Keller, Erin O’Connor, Liz Oakley, Steve Bakaern, d the rest of the cast oft housands that made PJa uniquely fun magazine-especiallyE rin, who did more thana nyone tot each me the proper use of English language. (To this day, Erin will still patiently explain to me when one should use “that” andw hen one should use “which”e ven though eight years of instruction on this and related topics have left no discernible imprint on my brain.) Thanks toJ on Erickson, Tami Zemel, Monica Berga,n d ther est of the DDJ crew for excellent, professional editing, and forjusbt eing great people. Thanks to the Coriolis gangf or their tireless hard work: JefDf untemann andK eith Weiskamp on the editorial and publishing side, and Brad Grannis, Rob Mauhar, and Kim Eoffwho handled art,d esign, and layout. Thanks to JiMm ischel who did a terrific job testing code for the book and putting thec ode disk together. Thanks to Jack Tseng, for teaching me a lot about graphics hardware, and even more about how much difference hard work can make. Thanks J tooh n Cockerham, David Stafford, Terje Mathisen,t he BitMan, Chris Hecker, Jim Mackraz, MeLlvainft te, JohnN avas, Phil Coleman, Anton TruenfeJlosh, n Carmack,J ohn Miles,J ohn Bridges, Jim Kent, Hal Hardenberg, Dave Miller, Steve Levy, Jack DaviDs, uane Strong, Daev Rohr, Bill Weber, Dan Gochnauer, Patrick Milligan, Tom Wilson, the people in the ibm.pc/ fast.code topic on Bix, and all the rest of you who haveb een so generous with your ideas and suggestions. I’ve done my best to acknowledge contributors by name in this book, but if yourn ame is omitted, my apologies, and consider yourself thanked; this bookc ould not have happened without you.A nd, of course, thanks to Shaya nd Emily for their generous patience with my passion for writing and computers. And, finally, thanks to the readers of my articles and to you, the reader of this book. You are, after all, the ultimate reason why I write, and I hope you learn as much and have as much fun reading this book as I did writing it! Michael Abrash ([email protected]) Bellevue, Washington, 1997 To Shay . C o n t e n t s Foreword xxxi Introduction xxxiii Part I 1 Chapter 1 The Best Optimizer Is between YouEr ars 3 The Human Element of Code Optimization 5 Understanding High Performance 6 When Fast Isn't Fast 6 Rules for Building High-Performance Code 7 Know Where You 're Going 8 Make a Big Map 8 Make Lots of Little Maps 8 Know the Ta'tory 12 Know When It Matters 13 AlwaysC onsidert he Alternatives 14 Know How to Turn Ont he Juice 16 Where We've Been, What We've Seen 19 WhereW e'reG oing 19 ' Chapter 2 A World Apart 21 The Unique Nature of Assembly Language Optimization 23 Instructions: The Individual versus the Collective 23 Assembly Is Fundamentally Different 25 Transfwmation Inefficiencies 25 Self-Rliance 27 vi i Knowledge 27 The FlexibleM ind 28 Where to Begm ? 30 Chapter 3 Assume Nothing 31 Understanding and Using the Zen Timer 33 The Costs of Ignorance 34 The Zen Timer 35 The Zen Timer Is a Means, Not an End 42 Starting the Zen Timer 43 Time and the PC 43 Stopping the Zen Timer 46 ReportingT iming Results4 7 Notes on the Zen Timer 48 A Sample Use of the Zen Timer 49 The Long-Period Zen Timer 53 Stoppingt he Clock 54 Example Use of the Long-Period Zen Timer 66 Using the Zen Timer from C 69 Watch Out for Optimizing Assemblers! 71 Further Reading 72 Armed with the Zen Timq Onward and Upward 72 Chapter 4 In theL air of theC ycle-Eaters 75 How the PC Hardware Devours CodeP erformance 77 Cycle-Eaters 78 The Nature of Cycle-Eaters 78 The 8088’sA ncestral Cycle-Eaters 79 The 8-Bit Bus Cycle-Eater 79 The Impact of the 8-Bit Bus Cycle-Eater 82 What to Do about the 8-Bit Bus Cycle-Eater? 83 The Prefetch Queue Cycle-Eater 86 Official Execution Times Are Only Part of the Story 87 There Is No Such Beast as a True Instruction Execution Time 88 Approximating OverallE xecutionT imes 93 What to Do abotuhP t er efetcQh u euC ey cle-Eater? 93 Holding Upt he 8088 94 Contents Dynamic RAM Refresh: The Invisible Hand 95 How DRAM Refresh Works in the PC 95 The Impact of DRAM Refresh 97 What to Do About the DRAM Refresh Cycle-Eater? 98 Wait States 99 The Display Adapter Cycle-Eater 101 The Impact of the DisplayA dapter Cycle-Eater 104 What to Do about the Display Adapter Cycle-Eater? 107 Cycle-Eaters: A Summary 108 What Does It All Mean? 108 Chapter 5 Crossing the Border 1 1 1 Searching Files with Restartable Blocks 113 Searchingf or Text 114 Avoiding the String Trap 115 Brute-Force Techniques 115 Using memchr() 116 Making a Search Restartable 11 7 Interpreting Where the Cycles Go 121 Knowing When Assembly Is Pointless 122 Always Look Where Execution Is Going 123 Chapter 6 LookingP asFt aceV alue 125 How Machine Instructions May Do More Than You Think 127 Memory Addressing and Arithmetic 128 Math via Memory Addressing 130 The Wonders of LEA on the 386 131 Multiplication with LEA Using Non-Powers ofTwo 132 Chapter 7 Local Optimization 135 Optimizing Halfway between Algorithms and Cycle Counting 137 When LOOP Is a Bad Idea 138 The Lessons of LOOP andJ CXZ 139 Avoiding LOOPS of Any Stripe 140