Efficient C/C++ Programming

Table of Listings
Foreword
Preface
Acknowledgments
1 Let's Get Small (and Fast): Introduction to Optimization
Deciding Whether to Optimize
Why Optimization is Necessary
Why Optimization is Often Neglected
Considering a Hardware Solution
Categories of Optimization
Finding the Critical Resource
Determining How Much Optimization Is Needed
A Real-Life Example
Summary
2 Hash, Cache and Crunch: A Supermarket Price Lookup System
Introduction
Up the Down Staircase
Some Random Musings
Hashing It Out
Divide and Conquer
Unite and Rule
Knowing When to Stop
Handling Subfile Overflow
Some Drawbacks of Hashing
Caching out Our Winnings
Heading for The Final Lookup
Saving Storage
The Code
Some User-Defined Types
Preparing to Access the Price File
Making a Hash of Things
Searching the File
Wrapping Around at EOF
Summary
Problems
3 Strips, Bits, And Sorts: A Mailing List System
Introduction
A First Approach
Saving Storage with Bitmaps
Increasing Processing Speed
The Law of Diminishing Returns
Strip Mining
Sorting Speed
The Distribution Counting Sort
Multicharacter Sorting
On the Home Stretch
The Code
Determining the Proper Buffer Size
Preparing to Read the Key File
Reading the Key File
Setting a Bit in a Bitmap
Allocate as You Go
Getting Ready to Sort
The Megasort Routine
Finishing Up
Performance
Back to the Future
Moral Support
Summary
Problems
4 Cn U Rd Ths Qkly?: A Data Compression Utility
Introduction
Huffman Coding
Half a Bit Is Better than One
Getting a Bit Excited
A Character Study
Keeping It in Context
Conspicuous Nonconsumption
Receiving the Message
The Code
A Loose Translation
Getting in on the Ground Floor
Gentlemen, Start Your Output
The Main Loop
Finding the Bottlenecks
Dead Slow Ahead
Getting the Correct Answer, Slowly
Some Assembly Is Required
Memories Are Made of This
Loop, De-Loop
Odd Man Out
Getting There Is Half the Fun
A Bunch of Real Characters
1994: A Space Odyssey?
Summary
Problems
5 Do You Need an Interpreter?
Introduction
Lost in Translation
Go FORTH and Multiply
What's in a Name?
The Impossible Dream
Floating Alone
386 Quick Avenue
Caveat Programmer
Timing Is Everything
Summary
Auxiliary Programs
Problems
6 Free at Last: A Customer Database Program with Variable-Length Records
Introduction
A Harmless Fixation
Checking out of the Hotel Procrustes
The Quantum File Access Method
A Large Array
Many Large Arrays
The Light at the End of the Tunnel
The Quantum File Header Record
The Itinerary
Let's Get Physical
A Logical Analysis
The Grab Bag
Taking It from the Top
Summary
Problems
7 OO, What an Algorithm Index and Key Access to Variable-Length Records
Introduction
Rewriting History
Warning: Overload
Hellot Operator?
An Auto-Loader
Type-Safety First
Hidden Virtues
Residence Permit
Punching the Time Clock
Getting Our Clocks Cleaned
Speed Demon
Virtual Perfection
Open Season
The Crown of Creation
Free the Quantum 16K!
One Size Fits All
Well-Founded Assertions
Running on Empty
Assembly Instructions Included
The Top and the Bottom
Where the Wild Goose Goes
Odd Man Out
The Code
Other Assembly Routines
Paying the Piper
Heavenly Hash
Just Another Link in the Chain
Relocation Assistance
Making a Quantum Leap
Persistence Pays Off
In Resplendent Array
Some Fine Details
Bigger and Better
The More, the Merrier
Summary
Problems
8 Mozart, No. Would You Believe Gershwin?
Introduction
Summary of Characteristics
Some Thoughts on the Future
Why Johnny Can't Estimate
Goodbye for Now
Suggested Approaches to Problems
Index