Optimized C++：Proven.Techniques.for.Heightened.Performance.2016.....pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：5.61M 资料格式：pdf 举报版权申诉

xinconan1992-9509413-4744300845154299867.pdf-第1页.png

第1页 / 共387页

xinconan1992-9509413-4744300845154299867.pdf-第2页.png

第2页 / 共387页

xinconan1992-9509413-4744300845154299867.pdf-第3页.png

第3页 / 共387页

xinconan1992-9509413-4744300845154299867.pdf-第4页.png

第4页 / 共387页

xinconan1992-9509413-4744300845154299867.pdf-第5页.png

第5页 / 共387页

xinconan1992-9509413-4744300845154299867.pdf-第6页.png

第6页 / 共387页

xinconan1992-9509413-4744300845154299867.pdf-第7页.png

第7页 / 共387页

xinconan1992-9509413-4744300845154299867.pdf-第8页.png

第8页 / 共387页

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

Optimized C++ PROVEN TECHNIQUES FOR HEIGHTENED PERFORMANCE Kurt Guntheroth

Optimized C++ Kurt Guntheroth Beijing Beijing Boston Boston Farnham Sebastopol Farnham Sebastopol Tokyo Tokyo

Optimized C++ by Kurt Guntheroth Copyright © 2016 Kurt Guntheroth. All rights reserved. Printed in the United States of America. Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472. O’Reilly books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles (http://safaribooksonline.com). For more information, contact our corporate/ institutional sales department: 800-998-9938 or corporate@oreilly.com. Indexer: Judy McConville Interior Designer: David Futato Cover Designer: Randy Comer Illustrator: Rebecca Demarest Editors: Meghan Blanchette and Andy Oram Acquisition Editor: Meghan Blanchette Production Editor: Nicole Shelby Copyeditor: Rachel Head Proofreader: Jasmine Kwityn April 2016: First Edition Revision History for the First Edition 2016-04-27: First Release See http://oreilly.com/catalog/errata.csp?isbn=9781491922064 for release details. The O’Reilly logo is a registered trademark of O’Reilly Media, Inc. Optimized C++, the cover image, and related trade dress are trademarks of O’Reilly Media, Inc. While the publisher and the author have used good faith efforts to ensure that the information and instructions contained in this work are accurate, the publisher and the author disclaim all responsibility for errors or omissions, including without limitation responsibility for damages resulting from the use of or reliance on this work. Use of the information and instructions contained in this work is at your own risk. If any code samples or other technology this work contains or describes is subject to open source licenses or the intellectual property rights of others, it is your responsibility to ensure that your use thereof complies with such licenses and/or rights. 978-1-491-92206-4 [LSI]

Everyone thanks their spouse for helping make a book possible. It’s trite, I know. My wife Renee Ostler made this book possible by giving me permission to take months off work, by giving me time and space to focus on writing, and by staying up late asking me ques‐ tions about optimizing C++ code, even though she wasn’t particularly engaged by the topic, just to show her support. She made this project important to her because it was important to me. No author could ask for more.

Table of Contents Preface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv 1. An Overview of Optimization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Optimization Is Part of Software Development 2 Optimization Is Effective 3 It’s OK to Optimize 3 A Nanosecond Here, a Nanosecond There 6 Summary of Strategies for Optimizing C++ Code 6 Use a Better Compiler, Use Your Compiler Better 7 Use Better Algorithms 8 Use Better Libraries 9 Reduce Memory Allocation and Copying 10 Remove Computation 11 Use Better Data Structures 12 Increase Concurrency 12 Optimize Memory Management 12 Summary 12 2. Computer Behavior Affecting Optimization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Lies C++ Believes About Computers 16 The Truth About Computers 17 Memory Is Slow 17 Memory Is Not Accessed in Bytes 18 Some Memory Accesses Are Slower than Others 19 Memory Words Have a Big End and a Little End 20 Memory Has Finite Capacity 20 Instruction Execution Is Slow 21 Making Decisions Is Hard for Computers 22 v

There Are Multiple Streams of Program Execution 22 Calling into the Operating System Is Expensive 24 C++ Tells Lies Too 24 All Statements Are Not Equally Expensive 24 Statements Are Not Executed in Order 25 Summary 26 3. Measure Performance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 The Optimizing Mindset 28 Performance Must Be Measured 28 Optimizers Are Big Game Hunters 29 The 90/10 Rule 29 Amdahl’s Law 31 Perform Experiments 32 Keep a Lab Notebook 34 Measure Baseline Performance and Set Goals 35 You Can Improve Only What You Measure 37 Profile Program Execution 37 Time Long-Running Code 40 “A Little Learning” About Measuring Time 40 Measuring Time with Computers 46 Overcoming Measurement Obstacles 54 Create a Stopwatch Class 58 Time Hot Functions in a Test Harness 62 Estimate Code Cost to Find Hot Code 63 Estimate the Cost of Individual C++ Statements 63 Estimate the Cost of Loops 64 Other Ways to Find Hot Spots 66 Summary 67 4. Optimize String Use: A Case Study. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Why Strings Are a Problem 69 Strings Are Dynamically Allocated 70 Strings Are Values 70 Strings Do a Lot of Copying 71 First Attempt at Optimizing Strings 72 Use Mutating String Operations to Eliminate Temporaries 74 Reduce Reallocation by Reserving Storage 74 Eliminate Copying of String Arguments 75 Eliminate Pointer Dereference Using Iterators 76 Eliminate Copying of Returned String Values 77 Use Character Arrays Instead of Strings 78 vi | Table of Contents

分享到：

赞收藏

资料库

Optimized C++：Proven.Techniques.for.Heightened.Performance.2016.....pdf

相关推荐

开发技术

热门标签

最新资料