book

C++ High Performance - Second Edition

by Björn Andrist, Viktor Sehr

December 2020

Intermediate to advanced

544 pages

12h 45m

English

Packt Publishing

Read now

Unlock full access

Who this book is forWhat this book coversGet the most out of this bookDownload the example code filesDownload the color imagesConventions usedGet in touchReviews
Why C++?Zero-cost abstractionsProgramming languages and machine code abstractionsAbstractions in other languagesThe zero-overhead principlePortabilityRobustnessC++ of todayC++ compared with other languagesCompeting languages and performanceNon-performance-related C++ language featuresValue semanticsConst correctnessObject ownershipDeterministic destruction in C++Avoiding null objects using C++ referencesDrawbacks of C++Libraries and compilers used in this bookSummary
Automatic type deduction with the auto keywordUsing auto in function signaturesForwarding the return type using decltype(auto)Using auto for variablesA const referenceA mutable referenceA forwarding referencePractices for ease of useConst propagation for pointersMove semantics explainedCopy-construction, swap, and moveCopy-constructing an objectResource acquisition and the rule of fiveNamed variables and rvaluesDefault move semantics and the rule of zeroRule of zero in a real code baseA common pitfall – moving non-resourcesApplying the && modifier to class member functionsDon't move when copies are elided anywayPass by value when applicableCases where pass-by-value is not applicableMoving constructor parametersDesigning interfaces with error handlingContractsClass invariantsMaintaining contractsError handlingProgramming error or runtime error?Programming errors (bugs)Recoverable runtime errorsFunction objects and lambda expressionsThe basic syntax of a C++ lambdaThe capture clauseCapture by reference versus capture by valueSimilarities between a lambda and a classInitializing variables in captureMutating lambda member variablesCapture allAssigning C function pointers to lambdasLambda typesLambdas and std::functionImplementing a simple Button class with std::functionPerformance consideration of std::functionGeneric lambdasSummary
Asymptotic complexity and big O notationGrowth ratesAmortized time complexityWhat to measure and how?Performance propertiesSpeedup of execution timePerformance countersPerformance testing — best practicesKnowing your code and hot spotsInstrumentation profilersSampling profilersMicrobenchmarkingAmdahl's lawPitfalls of microbenchmarkingA microbenchmark exampleSummary
The properties of computer memoryThe standard library containersSequence containersVectors and arraysDequeList and forward_listThe basic_stringAssociative containersOrdered sets and mapsUnordered sets and mapsContainer adaptorsPriority queuesUsing viewsAvoiding copies with string_viewEliminating array decay with std::spanSome performance considerationsBalancing between complexity guarantees and overheadKnowing and using the appropriate API functionsParallel arraysSummary
Introducing the standard library algorithmsEvolution of the standard library algorithmsSolving everyday problemsIterating over a sequenceGenerating elementsSorting elementsFinding elementsFinding using binary searchTesting for certain conditionsCounting elementsMinimum, maximum, and clampingIterators and rangesIntroducing iteratorsSentinel values and past-the-end iteratorsRangesIterator categoriesFeatures of the standard algorithmsAlgorithms do not change the size of the containerAlgorithms with output require allocated dataAlgorithms use operator==() and operator<() by defaultCustom comparator functionsConstrained algorithms use projectionsAlgorithms require move operators not to throwAlgorithms have complexity guaranteesAlgorithms perform just as well as C library function equivalentsWriting and using generic algorithmsNon-generic algorithmsGeneric algorithmsData structures that can be used by generic algorithmsBest practicesUsing the constrained algorithmsSorting only for the data you need to retrieveUse casesPerformance evaluationUse standard algorithms over raw for-loopsExample 1: Readability issues and mutable variablesExample 2: Unfortunate exceptions and performance problemsExample 3: Exploiting the standard library optimizationsAvoiding container copiesSummary
The motivation for the Ranges libraryLimitations of the Algorithm libraryUnderstanding views from the Ranges libraryViews are composableRange views come with range adaptorsViews are non-owning ranges with complexity guaranteesViews don't mutate the underlying containerViews can be materialized into containersViews are lazy evaluatedViews in the standard libraryRange viewsGenerating viewsTransforming views Sampling viewsUtility viewsRevisiting std::string_view and std::spanThe future of the Ranges librarySummary
Computer memoryThe virtual address spaceMemory pagesThrashingProcess memoryStack memoryHeap memoryObjects in memoryCreating and deleting objectsPlacement newThe new and delete operatorsMemory alignmentPaddingMemory ownershipHandling resources implicitlyContainersSmart pointersUnique pointerShared pointerWeak pointerSmall object optimizationCustom memory managementBuilding an arenaA custom memory allocatorUsing polymorphic memory allocatorsImplementing a custom memory resourceSummary
Introduction to template metaprogrammingCreating templatesUsing integers as template parametersProviding specializations of a templateHow the compiler handles a template functionAbbreviated function templatesReceiving the type of a variable with decltypeType traitsType trait categoriesUsing type traitsProgramming with constant expressionsConstexpr functions in a runtime contextDeclaring immediate functions using constevalThe if constexpr statementComparison with runtime polymorphismExample of the generic modulus function using if constexprChecking programming errors at compile timeUsing assert to trigger errors at runtimeUsing static_assert to trigger errors at compile timeConstraints and conceptsAn unconstrained version of a Point2D templateGeneric interfaces and bad error messagesA syntactic overview of constraints and conceptsDefining new conceptsConstraining types with conceptsFunction overloadingA constrained version of the Point2D templateAdding constraints to your codeConcepts in the standard libraryReal-world examples of metaprogrammingExample 1: creating a generic safe cast functionExample 2: hash strings at compile timeThe advantages of the compile-time hash sum calculationImplementing and verifying a compile-time hash functionConstructing a PrehashedString classEvaluating PrehashedStringEvaluating get_bitmap_resource() with PrehashedStringSummary
Representing optional values with std::optionalOptional return valuesOptional member variablesAvoiding empty states in enumsSorting and comparing std::optionalFixed size heterogenous collectionsUsing std::pairThe std::tupleAccessing the members of a tupleIterating std::tuple membersUnrolling the tupleAccessing tuple elementsThe variadic template parameter packDynamically sized heterogenous collectionsThe std::variantException safety of std::variantVisiting variantsHeterogenous collections using variantAccessing the values in our variant containerGlobal function std::get()Some real-world examplesExample 1: projections and comparison operatorsExample 2: reflectionMaking a class reflect its membersC++ libraries that simplify reflectionUsing reflectionConditionally overloading global functionsTesting reflection capabilitiesSummary

Introducing lazy evaluation and proxy objectsLazy versus eager evaluationProxy objectsAvoiding constructing objects using proxy objectsComparing concatenated strings using a proxyImplementing the proxyThe rvalue modifierAssigning a concatenated proxyPerformance evaluationPostponing sqrt computationsA simple two-dimensional vector classThe underlying mathematicsImplementing the LengthProxy object Comparing lengths with LengthProxy Calculating length with LengthProxyPreventing the misuse of LengthProxyPerformance evaluationCreative operator overloading and proxy objectsThe pipe operator as an extension methodThe pipe operatorSummary
Understanding the basics of concurrencyWhat makes concurrent programming hard?Concurrency and parallelismTime slicingShared memoryData racesExample: A data race Avoiding data racesMutexDeadlockSynchronous and asynchronous tasksConcurrent programming in C++The thread support libraryThreadsThread statesJoinable threadProtecting critical sectionsAvoiding deadlocksCondition variablesReturning data and handling errorsTasksAdditional synchronization primitives in C++20Using latchesUsing barriersSignalling and resource counting using semaphoresAtomic support in C++The lock-free propertyAtomic flagsAtomic wait and notifyUsing shared_ptr in a multithreaded environmentAtomic referencesThe C++ memory modelInstruction reorderingAtomics and memory ordersLock-free programmingExample: A lock-free queuePerformance guidelinesAvoid contentionAvoid blocking operationsNumber of threads/CPU coresThread prioritiesThread affinityFalse sharingSummary
A few motivating examplesThe coroutine abstractionSubroutines and coroutinesExecuting subroutines and coroutines on the CPUCPU registers, instructions, and the stackCall and returnSuspend and resumeStackless versus stackful coroutinesPerformance costMemory footprintContext switchingWhat you have learned so farCoroutines in C++What's included in standard C++ (and what's not)?What makes a C++ function a coroutine?A minimal but complete exampleThe coroutine return objectThe promise typeAwaitable typesPassing our coroutine aroundAllocating the coroutine stateAvoiding dangling referencesPassing parameters to coroutinesMember functions that are coroutinesLambdas that are coroutinesGuidelines to prevent dangling referencesHandling errorsCustomization pointsGeneratorsImplementing a generatorUsing the Generator classSolving generator problemsAn iterator implementationA solution using the Ranges libraryConclusionA real-world example using generatorsThe problemDelta encodingPerformanceSummary
Awaitable types revisitedThe implicit suspend pointsImplementing a rudimentary task typeHandling return values and exceptionsResuming an awaiting coroutineSupporting void tasksSynchronously waiting for a task to completeImplementing sync_wait()Implementing SyncWaitTaskTesting asynchronous tasks with sync_wait()Wrapping a callback-based APIA concurrent server using Boost.AsioImplementing the serverRunning and connecting to the serverWhat we have achieved with the server (and what we haven't)Summary
The importance of parallelismParallel algorithmsEvaluating parallel algorithmsAmdahl's law revisitedImplementing parallel std::transform()Naive implementationDivide and conquerImplementing parallel std::count_if()Implementing parallel std::copy_if()Approach 1: Use a synchronized write positionApproach 2: Split the algorithm into two partsPerformance evaluationParallel standard library algorithmsExecution policiesSequenced policyParallel policyUnsequenced policyParallel unsequenced policyException handlingAdditions and changes to parallel algorithmsstd::accumulate() and std::reduce()std::for_each()Parallelizing an index-based for-loopCombining std::for_each() with std::views::iota()Simplifying construction via a wrapperExecuting algorithms on the GPUSummary

Content preview from C++ High Performance - Second Edition

14 Parallel Algorithms

The previous chapters have focused on how to introduce concurrency and asynchrony in our programs by using threads and coroutines. This chapter focuses on parallel execution of independent tasks, which is related to but distinct from concurrency.

In earlier chapters, I stressed that I prefer standard library algorithms over handcrafted for-loops. In this chapter, you will see some great advantages of using standard library algorithms with the execution policies introduced with C++17.

This chapter is not going to go in depth into theories of parallelizing algorithms or parallel programming in general, as these subjects are far too complex to cover in a single chapter. Also, there are a multitude of books on this subject. ...