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 4. Optimize String Use: A Case Study

A few can touch the magic string, and noisy fame is proud to win them: Alas for those that never sing, but die with all their music in them!”

Oliver Wendell Holmes, “The Voiceless” (1858)

The C++ std::string class templates are among the most used features of the C++ standard library. For instance, an article in the Google Chromium developer forum stated that std::string accounted for half of all calls to the memory manager in Chromium. Any frequently executed code that manipulates strings is fertile ground for optimization. This chapter uses a discussion of optimizing string handling to illustrate recurring themes in optimization.

Why Strings Are a Problem

Strings are simple in concept, but quite subtle to implement efficiently. The particular combination of features in std::string interact in ways that make an efficient implementation almost impossible. Indeed, at the time this book was written, several popular compilers provided std::string implementations that were non-conforming in various ways.

Furthermore, the behavior of std::string has been changed over the years to keep up with changes in the C++ standard. This means that a conforming std::string implementation from a C++98 compiler may not behave the same way as a std::string implementation after C++11.

Strings have some behaviors that make them expensive to use, no matter the implementation. They are dynamically allocated, they behave as values in expressions, ...