Optimized C++

Description

"Proven techniques for heightened performance"--Cover. Copyright Table of Contents Preface Apology for the Code in This Book Using Code Examples Conventions Used in This Book Chapter 1. An Overview of Optimization Optimization Is Part of Software Development Optimization Is Effective It’s OK to Optimize A Nanosecond Here, a Nanosecond There Summary of Strategies for Optimizing C++ Code Use a Better Compiler, Use Your Compiler Better Use Better Algorithms Use Better Libraries Reduce Memory Allocation and Copying Remove Computation Use Better Data Structures Increase Concurrency Optimize Memory Management Summary Chapter 2. Computer Behavior Affecting Optimization Lies C++ Believes About Computers The Truth About Computers Memory Is Slow Memory Is Not Accessed in Bytes Some Memory Accesses Are Slower than Others Memory Words Have a Big End and a Little End Memory Has Finite Capacity Instruction Execution Is Slow Making Decisions Is Hard for Computers There Are Multiple Streams of Program Execution Calling into the Operating System Is Expensive C++ Tells Lies Too All Statements Are Not Equally Expensive Statements Are Not Executed in Order Summary Chapter 3. Measure Performance The Optimizing Mindset Performance Must Be Measured Optimizers Are Big Game Hunters The 90/10 Rule Amdahl’s Law Perform Experiments Keep a Lab Notebook Measure Baseline Performance and Set Goals You Can Improve Only What You Measure Profile Program Execution Time Long-Running Code “A Little Learning” About Measuring Time Measuring Time with Computers Overcoming Measurement Obstacles Create a Stopwatch Class Time Hot Functions in a Test Harness Estimate Code Cost to Find Hot Code Estimate the Cost of Individual C++ Statements Estimate the Cost of Loops Other Ways to Find Hot Spots Summary Chapter 4. Optimize String Use: A Case Study Why Strings Are a Problem Strings Are Dynamically Allocated Strings Are Values Strings Do a Lot of Copying First Attempt at Optimizing Strings Use Mutating String Operations to Eliminate Temporaries Reduce Reallocation by Reserving Storage Eliminate Copying of String Arguments Eliminate Pointer Dereference Using Iterators Eliminate Copying of Returned String Values Use Character Arrays Instead of Strings Summary of First Optimization Attempt Second Attempt at Optimizing Strings Use a Better Algorithm Use a Better Compiler Use a Better String Library Use a Better Allocator Eliminate String Conversion Conversion from C String to std::string Converting Between Character Encodings Summary Chapter 5. Optimize Algorithms Time Cost of Algorithms Best-Case, Average, and Worst-Case Time Cost Amortized Time Cost Other Costs Toolkit to Optimize Searching and Sorting Efficient Search Algorithms Time Cost of Searching Algorithms All Searches Are Equal When n Is Small Efficient Sort Algorithms Time Cost of Sorting Algorithms Replace Sorts Having Poor Worst-Case Performance Exploit Known Properties of the Input Data Optimization Patterns Precomputation Lazy Computation Batching Caching Specialization Taking Bigger Bites Hinting Optimizing the Expected Path Hashing Double-Checking Summary Chapter 6. Optimize Dynamically Allocated Variables C++ Variables Refresher Storage Duration of Variables Ownership of Variables Value Objects and Entity Objects C++ Dynamic Variable API Refresher Smart Pointers Automate Ownership of Dynamic Variables Dynamic Variables Have Runtime Cost Reduce Use of Dynamic Variables Create Class Instances Statically Use Static Data Structures Use std::make_shared Instead of new Don’t Share Ownership Unnecessarily Use a “Master Pointer” to Own Dynamic Variables Reduce Reallocation of Dynamic Variables Preallocate Dynamic Variables to Prevent Reallocation Create Dynamic Variables Outside of Loops Eliminate Unneeded Copying Disable Unwanted Copying in the Class Definition Eliminate Copying on Function Call Eliminate Copying on Function Return Copy Free Libraries Implement the “Copy on Write” Idiom Slice Data Structures Implement Move Semantics Nonstandard Copy Semantics: A Painful Hack std::swap(): The Poor Man’s Move Semantics Shared Ownership of Entities The Moving Parts of Move Semantics Update Code to Use Move Semantics Subtleties of Move Semantics Flatten Data Structures Summary Chapter 7. Optimize Hot Statements Remove Code from Loops Cache the Loop End Value Use More Efficient Loop Statements Count Down Instead of Up Remove Invariant Code from Loops Remove Unneeded Function Calls from Loops Remove Hidden Function Calls from Loops Remove Expensive, Slow-Changing Calls from Loops Push Loops Down into Functions to Reduce Call Overhead Do Some Actions Less Frequently What About Everything Else? Remove Code from Functions Cost of Function Calls Declare Brief Functions Inline Define Functions Before First Use Eliminate Unused Polymorphism Discard Unused Interfaces Select Implementation at Compile Time with Templates Eliminate Uses of the PIMPL Idiom Eliminate Calls into DLLs Use Static Member Functions Instead of Member Functions Move Virtual Destructor to Base Class Optimize Expressions Simplify Expressions Group Constants Together Use Less-Expensive Operators Use Integer Arithmetic Instead of Floating Arithmetic Double May Be Faster than Float Replace Iterative Computations with Closed Forms Optimize Control Flow Idioms Use switch Instead of if-elseif-else Use Virtual Functions Instead of switch or if Use No-Cost Exception Handling Summary Chapter 8. Use Better Libraries Optimize Standard Library Use Philosophy of the C++ Standard Library Issues in Use of the C++ Standard Library Optimize Existing Libraries Change as Little as Possible Add Functions Rather than Change Functionality Design Optimized Libraries Code in Haste, Repent at Leisure Parsimony Is a Virtue in Library Design Make Memory Allocation Decisions Outside the Library When in Doubt, Code Libraries for Speed Functions Are Easier to Optimize than Frameworks Flatten Inheritance Hierarchies Flatten Calling Chains Flatten Layered Designs Avoid Dynamic Lookup Beware of ‘God Functions’ Summary Chapter 9. Optimize Searching and Sorting Key/Value Tables Using std::map and std::string Toolkit to Improve Search Performance Make a Baseline Measurement Identify the Activity to Be Optimized Decompose the Activity to Be Optimized Change or Replace Algorithms and Data Structures Using the Optimization Process on Custom Abstractions Optimize Search Using std::map Use Fixed-Size Character Array Keys with std::map Use C-Style String Keys with std::map Using Map’s Cousin std::set When the Key Is in the Value Optimize Search Using the Header Key/Value Table for Search in Sequence Containers std::find(): Obvious Name, O(n) Time Cost std::binary_search(): Does Not Return Values Binary Search Using std::equal_range() Binary Search Using std::lower_bound() Handcoded Binary Search Handcoded Binary Search using strcmp() Optimize Search in Hashed Key/Value Tables Hashing with a std::unordered_map Hashing with Fixed Character Array Keys Hashing with Null-Terminated String Keys Hashing with a Custom Hash Table Stepanov’s Abstraction Penalty Optimize Sorting with the C++ Standard Library Summary Chapter 10. Optimize Data Structures Get to Know the Standard Library Containers Sequence Containers Associative Containers Experimenting with the Standard Library Containers std::vector and std::string Performance Consequences of Reallocation Inserting and Deleting in std::vector Iterating in std::vector Sorting std::vector Lookup with std::vector std::deque Inserting and Deleting in std::deque Iterating in std::deque Sorting std::deque Lookup with std::deque std::list Inserting and Deleting in std::list Iterating in std::list Sorting std::list Lookup with std::list std::forward_list Inserting and Deleting in std::forward_list Iterating in std::forward_list Sorting std::forward_list Lookup in std::forward_list std::map and std::multimap Inserting and Deleting in std::map Iterating in std::map Sorting std::map Lookup with std::map std::set and std::multiset std::unordered_map and std::unordered_multimap Inserting and Deleting in std::unordered_map Iterating in std::unordered_map Lookup with std::unordered_map Other Data Structures Summary Chapter 11. Optimize I/O A Recipe for Reading Files Create a Parsimonious Function Signature Shorten Calling Chains Reduce Reallocation Take Bigger Bites—Use a Bigger Input Buffer Take Bigger Bites—Read a Line at a Time Shorten Calling Chains Again Things That Didn’t Help Writing Files Reading from std::cin and Writing to std::cout Summary Chapter 12. Optimize Concurrency Concurrency Refresher A Walk Through the Concurrency Zoo Interleaved Execution Sequential Consistency Races Synchronization Atomicity C++ Concurrency Facilities Refresher Threads Promises and Futures Asynchronous Tasks Mutexes Locks Condition Variables Atomic Operations on Shared Variables On Deck: Future C++ Concurrency Features Optimize Threaded C++ Programs Prefer std::async to std::thread Create as Many Runnable Threads as Cores Implement a Task Queue and Thread Pool Perform I/O in a Separate Thread Program Without Synchronization Remove Code from Startup and Shutdown Make Synchronization More Efficient Reduce the Scope of Critical Sections Limit the Number of Concurrent Threads Avoid the Thundering Herd Avoid Lock Convoys Reduce Contention Don’t Busy-Wait on a Single-Core System Don’t Wait Forever Rolling Your Own Mutex May Be Ineffective Limit Producer Output Queue Length Concurrency Libraries Summary Chapter 13. Optimize Memory Management C++ Memory Management API Refresher The Life Cycle of Dynamic Variables Memory Management Functions Allocate and Free Memory New-Expressions Construct Dynamic Variables Delete-Expressions Dispose of Dynamic Variables Explicit Destructor Calls Destroy Dynamic Variables High-Performance Memory Managers Provide Class-Specific Memory Managers Fixed-Size-Block Memory Manager Block Arena Adding a Class-Specific operator new() Performance of the Fixed-Block Memory Manager Variations on the Fixed-Block Memory Manager Non-Thread Safe Memory Managers Are Efficient Provide Custom Standard Library Allocators Minimal C++11 Allocator Additional Definitions for C++98 Allocator A Fixed-Block Allocator A Fixed-Block Allocator for Strings Summary Index About the Author Colophon