Optimized C++

Table of Contents

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