Spis treści

Optimized C++. Proven Techniques for Heightened Performance eBook -- spis treści

• Preface
  • Apology for the Code in This Book
  • Using Code Examples
  • Conventions Used in This Book
• 1. An Overview of Optimization
  • Optimization Is Part of Software Development
  • Optimization Is Effective
  • Its 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
• 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
• 3. Measure Performance
  • The Optimizing Mindset
    • Performance Must Be Measured
    • Optimizers Are Big Game Hunters
    • The 90/10 Rule
    • Amdahls 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
      • Precision, trueness, and accuracy
      • Measuring time
      • Measurement resolution
      • Measuring with several clocks
    • Measuring Time with Computers
      • Hardware evolution of tick counters
      • Wraparound
      • Resolution is not accuracy
      • Latency
      • Nondeterministic behavior
    • Overcoming Measurement Obstacles
      • Dont sweat the small stuff
      • Measure relative performance
      • Improve repeatability by measuring module tests
      • Tune performance with metrics
      • Improve accuracy by averaging many iterations
      • Reduce nondeterministic operating system behavior by raising priority
      • Nondeterminism happensget over it
    • 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
      • Estimate repeat count in nested loops
      • Estimate loops with variable repeat count
      • Recognize implicit loops
      • Recognize false loops
  • Other Ways to Find Hot Spots
  • Summary
• 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
      • Adopt a richer library for std::string
      • Use std::stringstream to avoid value semantics
      • Adopt a novel string implementation
    • Use a Better Allocator
  • Eliminate String Conversion
    • Conversion from C String to std::string
    • Converting Between Character Encodings
  • Summary
• 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
• 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
      • Automating ownership of dynamic variables
      • Shared ownership of dynamic variables is more expensive
      • std::auto_ptr versus container classes
    • Dynamic Variables Have Runtime Cost
  • Reduce Use of Dynamic Variables
    • Create Class Instances Statically
      • Create class member variables statically
    • Use Static Data Structures
      • Use std::array instead of std::vector
      • Create large buffers on the stack
      • Create linked data structures statically
      • Create binary trees in an array
      • Use a circular buffer instead of a deque
    • Use std::make_shared Instead of new
    • Dont 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 Mans Move Semantics
    • Shared Ownership of Entities
    • The Moving Parts of Move Semantics
    • Update Code to Use Move Semantics
    • Subtleties of Move Semantics
      • Moving instances into std::vector
      • Rvalue reference arguments are lvalues
      • Dont return an rvalue reference
      • Moving bases and members
  • Flatten Data Structures
  • Summary
• 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
      • Basic cost of function calls
      • Cost of virtual functions
      • Member function calls in derived classes
      • Cost of pointers to functions
      • Summary of function call costs
    • Declare Brief Functions Inline
    • Define Functions Before First Use
    • Eliminate Unused Polymorphism
    • Discard Unused Interfaces
      • Select interface implementation at link time
      • Select interface implementation at compile time
    • 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
      • Dont use exception specifications
  • Summary
• 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
• 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 Maps Cousin std::set When the Key Is in the Value
  • Optimize Search Using the <algorithm> 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
  • Stepanovs Abstraction Penalty
  • Optimize Sorting with the C++ Standard Library
  • Summary
• 10. Optimize Data Structures
  • Get to Know the Standard Library Containers
    • Sequence Containers
    • Associative Containers
    • Experimenting with the Standard Library Containers
      • Element data type
      • A note on designing the experiment
  • 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
      • Optimizing the check-and-update idiom
    • 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
• 11. Optimize I/O
  • A Recipe for Reading Files
    • Create a Parsimonious Function Signature
    • Shorten Calling Chains
    • Reduce Reallocation
    • Take Bigger BitesUse a Bigger Input Buffer
    • Take Bigger BitesRead a Line at a Time
    • Shorten Calling Chains Again
    • Things That Didnt Help
  • Writing Files
  • Reading from std::cin and Writing to std::cout
  • Summary
• 12. Optimize Concurrency
  • Concurrency Refresher
    • A Walk Through the Concurrency Zoo
    • Interleaved Execution
    • Sequential Consistency
    • Races
    • Synchronization
    • Atomicity
      • Atomicity by mutual exclusion
      • Atomic hardware operations
  • C++ Concurrency Facilities Refresher
    • Threads
    • Promises and Futures
    • Asynchronous Tasks
    • Mutexes
    • Locks
    • Condition Variables
    • Atomic Operations on Shared Variables
      • Memory fences
    • 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
    • Dont Busy-Wait on a Single-Core System
    • Dont Wait Forever
    • Rolling Your Own Mutex May Be Ineffective
    • Limit Producer Output Queue Length
  • Concurrency Libraries
  • Summary
• 13. Optimize Memory Management
  • C++ Memory Management API Refresher
    • The Life Cycle of Dynamic Variables
    • Memory Management Functions Allocate and Free Memory
      • operator new() implements allocation
      • operator delete() frees allocated memory
      • Memory management functions from the C library
    • New-Expressions Construct Dynamic Variables
      • Non-throwing new
      • Placement new performs placement without allocation
      • Custom placement new, the half-formed hinterland of allocation
      • Class-specific operator new() gives fine control of allocation
    • Delete-Expressions Dispose of Dynamic Variables
    • Explicit Destructor Calls Destroy Dynamic Variables
      • There is no explicit constructor call... Or is there?
  • 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
      • Performance of the fixed-block allocator
    • A Fixed-Block Allocator for Strings
      • Performance of the string allocator
  • Summary
• Index