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 5. Optimize Algorithms

Time heals what reason cannot.

Seneca the Younger (c. 4 BC–65 AD)

If a program takes hours to run, when it needs to take seconds, the only optimization likely to be successful is to select a more efficient algorithm. Most optimizations improve performance by only a constant factor. Replacing an inefficient algorithm with a better-performing one is the only sure ticket to an order-of-magnitude improvement in performance.

Design of efficient algorithms is the topic of many whole computer science textbooks and numerous doctoral dissertations. There are specialist computer scientists who devote their careers to analysis of algorithms. There’s no way to cover the topic in a single short chapter. Instead, this chapter looks briefly at the time cost of algorithms, providing a guide to know when you’re in trouble.

I take a look at common searching and sorting algorithms, and present a toolkit for optimizing searching and sorting in existing programs. In addition to picking an algorithm that is optimal for unknown data, there are algorithms with exceptional performance on data that is sorted or nearly sorted, or that has other special properties.

Computer scientists study important algorithms and data structures because they are examples of how to optimize code. I have collected some important optimization techniques in the hope that the reader will come to recognize places where they can be applied.