book

Optimized C++

by Kurt Guntheroth

April 2016

Intermediate to advanced

388 pages

11h 5m

English

O'Reilly Media, Inc.

Read now

Unlock full access

Apology for the Code in This BookUsing Code ExamplesConventions Used in This Book
Optimization Is Part of Software DevelopmentOptimization Is EffectiveIt’s OK to OptimizeA Nanosecond Here, a Nanosecond ThereSummary of Strategies for Optimizing C++ CodeUse a Better Compiler, Use Your Compiler BetterUse Better AlgorithmsUse Better LibrariesReduce Memory Allocation and CopyingRemove ComputationUse Better Data StructuresIncrease ConcurrencyOptimize Memory ManagementSummary
Lies C++ Believes About ComputersThe Truth About ComputersMemory Is SlowMemory Is Not Accessed in BytesSome Memory Accesses Are Slower than OthersMemory Words Have a Big End and a Little EndMemory Has Finite CapacityInstruction Execution Is SlowMaking Decisions Is Hard for ComputersThere Are Multiple Streams of Program ExecutionCalling into the Operating System Is ExpensiveC++ Tells Lies TooAll Statements Are Not Equally ExpensiveStatements Are Not Executed in OrderSummary
The Optimizing MindsetPerformance Must Be MeasuredOptimizers Are Big Game HuntersThe 90/10 RuleAmdahl’s LawPerform ExperimentsKeep a Lab NotebookMeasure Baseline Performance and Set GoalsYou Can Improve Only What You MeasureProfile Program ExecutionTime Long-Running Code“A Little Learning” About Measuring TimeMeasuring Time with ComputersOvercoming Measurement ObstaclesCreate a Stopwatch ClassTime Hot Functions in a Test HarnessEstimate Code Cost to Find Hot CodeEstimate the Cost of Individual C++ StatementsEstimate the Cost of LoopsOther Ways to Find Hot SpotsSummary
Why Strings Are a ProblemStrings Are Dynamically AllocatedStrings Are ValuesStrings Do a Lot of CopyingFirst Attempt at Optimizing StringsUse Mutating String Operations to Eliminate TemporariesReduce Reallocation by Reserving StorageEliminate Copying of String ArgumentsEliminate Pointer Dereference Using IteratorsEliminate Copying of Returned String ValuesUse Character Arrays Instead of StringsSummary of First Optimization AttemptSecond Attempt at Optimizing StringsUse a Better AlgorithmUse a Better CompilerUse a Better String LibraryUse a Better AllocatorEliminate String ConversionConversion from C String to std::stringConverting Between Character EncodingsSummary
Time Cost of AlgorithmsBest-Case, Average, and Worst-Case Time CostAmortized Time CostOther CostsToolkit to Optimize Searching and SortingEfficient Search AlgorithmsTime Cost of Searching AlgorithmsAll Searches Are Equal When n Is SmallEfficient Sort AlgorithmsTime Cost of Sorting AlgorithmsReplace Sorts Having Poor Worst-Case PerformanceExploit Known Properties of the Input DataOptimization PatternsPrecomputationLazy ComputationBatchingCachingSpecializationTaking Bigger BitesHintingOptimizing the Expected PathHashingDouble-CheckingSummary
C++ Variables RefresherStorage Duration of VariablesOwnership of VariablesValue Objects and Entity ObjectsC++ Dynamic Variable API RefresherSmart Pointers Automate Ownership of Dynamic VariablesDynamic Variables Have Runtime CostReduce Use of Dynamic VariablesCreate Class Instances StaticallyUse Static Data StructuresUse std::make_shared Instead of newDon’t Share Ownership UnnecessarilyUse a “Master Pointer” to Own Dynamic VariablesReduce Reallocation of Dynamic VariablesPreallocate Dynamic Variables to Prevent ReallocationCreate Dynamic Variables Outside of LoopsEliminate Unneeded CopyingDisable Unwanted Copying in the Class DefinitionEliminate Copying on Function CallEliminate Copying on Function ReturnCopy Free LibrariesImplement the “Copy on Write” IdiomSlice Data StructuresImplement Move SemanticsNonstandard Copy Semantics: A Painful Hackstd::swap(): The Poor Man’s Move SemanticsShared Ownership of EntitiesThe Moving Parts of Move SemanticsUpdate Code to Use Move SemanticsSubtleties of Move SemanticsFlatten Data StructuresSummary
Remove Code from LoopsCache the Loop End ValueUse More Efficient Loop StatementsCount Down Instead of UpRemove Invariant Code from LoopsRemove Unneeded Function Calls from LoopsRemove Hidden Function Calls from LoopsRemove Expensive, Slow-Changing Calls from LoopsPush Loops Down into Functions to Reduce Call OverheadDo Some Actions Less FrequentlyWhat About Everything Else?Remove Code from FunctionsCost of Function CallsDeclare Brief Functions InlineDefine Functions Before First UseEliminate Unused PolymorphismDiscard Unused InterfacesSelect Implementation at Compile Time with TemplatesEliminate Uses of the PIMPL IdiomEliminate Calls into DLLsUse Static Member Functions Instead of Member FunctionsMove Virtual Destructor to Base ClassOptimize ExpressionsSimplify ExpressionsGroup Constants TogetherUse Less-Expensive OperatorsUse Integer Arithmetic Instead of Floating ArithmeticDouble May Be Faster than FloatReplace Iterative Computations with Closed FormsOptimize Control Flow IdiomsUse switch Instead of if-elseif-elseUse Virtual Functions Instead of switch or ifUse No-Cost Exception HandlingSummary
Optimize Standard Library UsePhilosophy of the C++ Standard LibraryIssues in Use of the C++ Standard LibraryOptimize Existing LibrariesChange as Little as PossibleAdd Functions Rather than Change FunctionalityDesign Optimized LibrariesCode in Haste, Repent at LeisureParsimony Is a Virtue in Library DesignMake Memory Allocation Decisions Outside the LibraryWhen in Doubt, Code Libraries for SpeedFunctions Are Easier to Optimize than FrameworksFlatten Inheritance HierarchiesFlatten Calling ChainsFlatten Layered DesignsAvoid Dynamic LookupBeware of ‘God Functions’Summary
Key/Value Tables Using std::map and std::stringToolkit to Improve Search PerformanceMake a Baseline MeasurementIdentify the Activity to Be OptimizedDecompose the Activity to Be OptimizedChange or Replace Algorithms and Data StructuresUsing the Optimization Process on Custom AbstractionsOptimize Search Using std::mapUse Fixed-Size Character Array Keys with std::mapUse C-Style String Keys with std::mapUsing Map’s Cousin std::set When the Key Is in the ValueOptimize Search Using the <algorithm> HeaderKey/Value Table for Search in Sequence Containersstd::find(): Obvious Name, O(n) Time Coststd::binary_search(): Does Not Return ValuesBinary Search Using std::equal_range()Binary Search Using std::lower_bound()Handcoded Binary SearchHandcoded Binary Search using strcmp()Optimize Search in Hashed Key/Value TablesHashing with a std::unordered_mapHashing with Fixed Character Array KeysHashing with Null-Terminated String KeysHashing with a Custom Hash TableStepanov’s Abstraction PenaltyOptimize Sorting with the C++ Standard LibrarySummary

Get to Know the Standard Library ContainersSequence ContainersAssociative ContainersExperimenting with the Standard Library Containersstd::vector and std::stringPerformance Consequences of ReallocationInserting and Deleting in std::vectorIterating in std::vectorSorting std::vectorLookup with std::vectorstd::dequeInserting and Deleting in std::dequeIterating in std::dequeSorting std::dequeLookup with std::dequestd::listInserting and Deleting in std::listIterating in std::listSorting std::listLookup with std::liststd::forward_listInserting and Deleting in std::forward_listIterating in std::forward_listSorting std::forward_listLookup in std::forward_liststd::map and std::multimapInserting and Deleting in std::mapIterating in std::mapSorting std::mapLookup with std::mapstd::set and std::multisetstd::unordered_map and std::unordered_multimapInserting and Deleting in std::unordered_mapIterating in std::unordered_mapLookup with std::unordered_mapOther Data StructuresSummary
A Recipe for Reading FilesCreate a Parsimonious Function SignatureShorten Calling ChainsReduce ReallocationTake Bigger Bites—Use a Bigger Input BufferTake Bigger Bites—Read a Line at a TimeShorten Calling Chains AgainThings That Didn’t HelpWriting FilesReading from std::cin and Writing to std::coutSummary
Concurrency RefresherA Walk Through the Concurrency ZooInterleaved ExecutionSequential ConsistencyRacesSynchronizationAtomicityC++ Concurrency Facilities RefresherThreadsPromises and FuturesAsynchronous TasksMutexesLocksCondition VariablesAtomic Operations on Shared VariablesOn Deck: Future C++ Concurrency FeaturesOptimize Threaded C++ ProgramsPrefer std::async to std::threadCreate as Many Runnable Threads as CoresImplement a Task Queue and Thread PoolPerform I/O in a Separate ThreadProgram Without SynchronizationRemove Code from Startup and ShutdownMake Synchronization More EfficientReduce the Scope of Critical SectionsLimit the Number of Concurrent ThreadsAvoid the Thundering HerdAvoid Lock ConvoysReduce ContentionDon’t Busy-Wait on a Single-Core SystemDon’t Wait ForeverRolling Your Own Mutex May Be IneffectiveLimit Producer Output Queue LengthConcurrency LibrariesSummary
C++ Memory Management API RefresherThe Life Cycle of Dynamic VariablesMemory Management Functions Allocate and Free MemoryNew-Expressions Construct Dynamic VariablesDelete-Expressions Dispose of Dynamic VariablesExplicit Destructor Calls Destroy Dynamic VariablesHigh-Performance Memory ManagersProvide Class-Specific Memory ManagersFixed-Size-Block Memory ManagerBlock ArenaAdding a Class-Specific operator new()Performance of the Fixed-Block Memory ManagerVariations on the Fixed-Block Memory ManagerNon-Thread Safe Memory Managers Are EfficientProvide Custom Standard Library AllocatorsMinimal C++11 AllocatorAdditional Definitions for C++98 AllocatorA Fixed-Block AllocatorA Fixed-Block Allocator for StringsSummary

Content preview from Optimized C++

Chapter 10. Optimize Data Structures

A thing of beauty is a joy forever

John Keats (1818)

If you have never stopped to marvel at the container classes of the C++ standard library (formerly the Standard Template Library, or STL), perhaps you should do so now. At the time it was introduced into the draft C++ standard in 1994, Stepanov’s Standard Template Library was the first reusable library of efficient containers and algorithms. Prior to the STL, every project developed its own linked list and binary tree implementations, possibly adapting source code from other users. C has no equivalent. Standard library containers have allowed many programmers to forget their algorithms and data structures classes and choose exclusively from the standard library’s menu of prebuilt containers for the past 20 years.

Get to Know the Standard Library Containers

There are many things to like about the C++ standard library containers, such as uniform naming and a consistent notion of iterators for traversing the containers. But for optimization purposes, some properties are especially important. These include:

Big-O performance guarantees for the cost of insertion and deletion
Amortized constant-time cost of appending to sequence containers
Ability to finely control the dynamic memory allocated by the container

The C++ standard library containers seem almost similar enough that they can be substituted for one another, notwithstanding their obviously different implementations. But this ...