前言　　xvii

第 1章　優(yōu)化概述　　1

1.1　優(yōu)化是軟件開發(fā)的一部分　　2

1.2　優(yōu)化是高效的　　3

1.3　優(yōu)化是沒有問題的　　3

1.4　這兒一納秒，那兒一納秒　　5

1.5　C 代碼優(yōu)化策略總結(jié)　　5

1.5.1　用好的編譯器并用好編譯器　　6

1.5.2　使用更好的算法　　7

1.5.3　使用更好的庫　　8

1.5.4　減少內(nèi)存分配和復(fù)制　　9

1.5.5　移除計算　　9

1.5.6　使用更好的數(shù)據(jù)結(jié)構(gòu)　　9

1.5.7　提高并發(fā)性　　10

1.5.8　優(yōu)化內(nèi)存管理　　10

1.6　小結(jié)　　10

第 2章　影響優(yōu)化的計算機行為　　11

2.1　C 所相信的計算機謊言　　12

2.2　計算機的真相　　12

2.2.1　內(nèi)存很慢　　13

2.2.2　內(nèi)存訪問并非以字節(jié)為單位　　13

2.2.3　某些內(nèi)存訪問會比其他的更慢　　14

2.2.4　內(nèi)存字分為大端和小端　　14

2.2.5　內(nèi)存容量是有限的　　15

2.2.6　指令執(zhí)行緩慢　　16

2.2.7　計算機難以作決定　　16

2.2.8　程序執(zhí)行中的多個流　　16

2.2.9　調(diào)用操作系統(tǒng)的開銷是昂貴的　　18

2.3　C 也會說謊　　18

2.3.1　并非所有語句的性能開銷都相同　　18

2.3.2　語句并非按順序執(zhí)行　　18

2.4　小結(jié)　　19

第3章　測量性能　　20

3.1　優(yōu)化思想　　21

3.1.1　必須測量性能　　21

3.1.2　優(yōu)化器是獵人　　21

3.1.3　90/10規(guī)則　　22

3.1.4　阿姆達爾定律　　23

3.2　進行實驗　　24

3.2.1　記實驗筆記　　26

3.2.2　測量基準性能并設(shè)定目標　　26

3.2.3　你只能改善你能夠測量的　　28

3.3　分析程序執(zhí)行　　28

3.4　測量長時間運行的代碼　　30

3.4.1　一點關(guān)于測量時間的知識　　30

3.4.2　用計算機測量時間　　35

3.4.3　克服測量障礙　　41

3.4.4　創(chuàng)建stopwatch類　　44

3.4.5　使用測試套件測量熱點函數(shù)　　48

3.5　評估代碼開銷來找出熱點代碼　　48

3.5.1　評估獨立的C 語句的開銷　　49

3.5.2　評估循環(huán)的開銷　　49

3.6　其他找出熱點代碼的方法　　51

3.7　小結(jié)　　51

第4章　優(yōu)化字符串的使用：案例研究　　53

4.1　為什么字符串很麻煩　　53

4.1.1　字符串是動態(tài)分配的　　54

4.1.2　字符串就是值　　54

4.1.3　字符串會進行大量復(fù)制　　55

4.2　嘗試優(yōu)化字符串　　56

4.2.1　使用復(fù)合賦值操作避免臨時字符串　　57

4.2.2　通過預(yù)留存儲空間減少內(nèi)存的重新分配　　57

4.2.3　消除對參數(shù)字符串的復(fù)制　　58

4.2.4　使用迭代器消除指針解引　　59

4.2.5　消除對返回的字符串的復(fù)制　　59

4.2.6　用字符數(shù)組代替字符串　　60

4.3　嘗試優(yōu)化字符串　　62

4.3.1　使用更好的算法　　62

4.3.2　使用更好的編譯器　　64

4.3.3　使用更好的字符串庫　　64

4.3.4　使用更好的內(nèi)存分配器　　67

4.4　消除字符串轉(zhuǎn)換　　69

4.4.1　將C字符串轉(zhuǎn)換為std::string　　69

4.4.2　不同字符集間的轉(zhuǎn)換　　70

4.5　小結(jié)　　70

第5章　優(yōu)化算法　　71

5.1　算法的時間開銷　　72

5.1.1　情況的時間開銷　　74

5.1.2　攤銷時間開銷　　74

5.1.3　其他開銷　　75

5.2　優(yōu)化查找和排序的工具箱　　75

5.3　高效查找算法　　75

5.3.1　查找算法的時間開銷　　75

5.3.2　當n很小時，所有算法的時間開銷都一樣　　76

5.4　高效排序算法　　77

5.4.1　排序算法的時間開銷　　77

5.4.2　替換在情況下性能較差的排序算法　　77

5.4.3　利用輸入數(shù)據(jù)集的已知特性　　78

5.5　優(yōu)化模式　　78

5.5.1　預(yù)計算　　79

5.5.2　延遲計算　　80

5.5.3　批量處理　　80

5.5.4　緩存　　80

5.5.5　特化　　81

5.5.6　提高處理量　　81

5.5.7　提示　　81

5.5.8　優(yōu)化期待路徑　　82

5.5.9　散列法　　82

5.5.10　雙重檢查　　82

5.6　小結(jié)　　82

第6章　優(yōu)化動態(tài)分配內(nèi)存的變量　　83

6.1　C 變量回顧　　84

6.1.1　變量的存儲期　　84

6.1.2　變量的所有權(quán)　　86

6.1.3　值對象與實體對象　　86

6.2　C 動態(tài)變量API回顧　　88

6.2.1　使用智能指針實現(xiàn)動態(tài)變量所有權(quán)的自動化　　90

6.2.2　動態(tài)變量有運行時開銷　　92

6.3　減少動態(tài)變量的使用　　92

6.3.1　靜態(tài)地創(chuàng)建類實例　　92

6.3.2　使用靜態(tài)數(shù)據(jù)結(jié)構(gòu)　　93

6.3.3　使用std::make_shared 替代new 表達式　　97

6.3.4　不要無謂地共享所有權(quán)　　97

6.3.5　使用“主指針”擁有動態(tài)變量　　98

6.4　減少動態(tài)變量的重新分配　　99

6.4.1　預(yù)分配動態(tài)變量以防止重新分配　　99

6.4.2　在循環(huán)外創(chuàng)建動態(tài)變量　　99

6.5　移除無謂的復(fù)制　　100

6.5.1　在類定義中禁止不希望發(fā)生的復(fù)制　　101

6.5.2　移除函數(shù)調(diào)用上的復(fù)制　　102

6.5.3　移除函數(shù)返回上的復(fù)制　　103

6.5.4　免復(fù)制庫　　105

6.5.5　實現(xiàn)寫時復(fù)制慣用法　　106

6.5.6　切割數(shù)據(jù)結(jié)構(gòu)　　106

6.6　實現(xiàn)移動語義　　107

6.6.1　非標準復(fù)制語義：痛苦的實現(xiàn)　　107

6.6.2　std::swap()：“窮人”的移動語義　　108

6.6.3　共享所有權(quán)的實體　　109

6.6.4　移動語義的移動部分　　109

6.6.5　更新代碼以使用移動語義　　110

6.6.6　移動語義的微妙之處　　 111

6.7　扁平數(shù)據(jù)結(jié)構(gòu)　　113

6.8　小結(jié)　　113

第7章　優(yōu)化熱點語句　　115

7.1　從循環(huán)中移除代碼　　116

7.1.1　緩存循環(huán)結(jié)束條件值　　117

7.1.2　使用更高效的循環(huán)語句　　117

7.1.3　用遞減替代遞增　　118

7.1.4　從循環(huán)中移除不變性代碼　　118

7.1.5　從循環(huán)中移除無謂的函數(shù)調(diào)用　　119

7.1.6　從循環(huán)中移除隱含的函數(shù)調(diào)用　　121

7.1.7　從循環(huán)中移除昂貴的、緩慢改變的調(diào)用　　123

7.1.8　將循環(huán)放入函數(shù)以減少調(diào)用開銷　　123

7.1.9　不要頻繁地進行操作　　124

7.1.10　其他優(yōu)化技巧　　126

7.2　從函數(shù)中移除代碼　　126

7.2.1　函數(shù)調(diào)用的開銷　　126

7.2.2　簡短地聲明內(nèi)聯(lián)函數(shù)　　129

7.2.3　在使用之前定義函數(shù)　　129

7.2.4　移除未使用的多態(tài)性　　130

7.2.5　放棄不使用的接口　　130

7.2.6　用模板在編譯時選擇實現(xiàn)　　133

7.2.7　避免使用PIMPL慣用法　　134

7.2.8　移除對DDL的調(diào)用　　135

7.2.9　使用靜態(tài)成員函數(shù)取代成員函數(shù)　　136

7.2.10　將虛析構(gòu)函數(shù)移基類中　　136

7.3　優(yōu)化表達式　　137

7.3.1　簡化表達式　　137

7.3.2　將常量組合在一起　　138

7.3.3　使用更高效的運算符　　139

7.3.4　使用整數(shù)計算替代浮點型計算　　139

7.3.5　雙精度類型可能會比浮點型更快　　140

7.3.6　用閉形式替代迭代計算　　141

7.4　優(yōu)化控制流程慣用法　　142

7.4.1　用switch替代if-else　if-else　　142

7.4.2　用虛函數(shù)替代switch 或if　　143

7.4.3　使用無開銷的異常處理　　144

7.5　小結(jié)　　145

第8章　使用更好的庫　　146

8.1　優(yōu)化標準庫的使用　　146

8.1.1　C 標準庫的哲學(xué)　　147

8.1.2　使用C 標準庫的注意事項　　147

8.2　優(yōu)化現(xiàn)有庫　　149

8.2.1　改動越少越好　　149

8.2.2　添加函數(shù)，不要改動功能　　150

8.3　設(shè)計優(yōu)化庫　　150

8.3.1　草率編碼后悔多　　150

8.3.2　在庫的設(shè)計上，簡約是一種美德　　151

8.3.3　不要在庫內(nèi)分配內(nèi)存　　152

8.3.4　若有疑問，以速度為準　　152

8.3.5　函數(shù)比框架更容易優(yōu)化　　152

8.3.6　扁平繼承層次關(guān)系　　153

8.3.7　扁平調(diào)用鏈　　153

8.3.8　扁平分層設(shè)計　　153

8.3.9　避免動態(tài)查找　　154

8.3.10　留意“上帝函數(shù)”　　155

8.4　小結(jié)　　156

第9章　優(yōu)化查找和排序　　157

9.1　使用std::map和std::string的鍵值對表　　158

9.2　改善查找性能的工具箱　　159

9.2.1　進行一次基準測量　　160

9.2.2　識別出待優(yōu)化的活動　　160

9.2.3　分解待優(yōu)化的活動　　160

9.2.4　修改或替換算法和數(shù)據(jù)結(jié)構(gòu)　　161

9.2.5　在自定義抽象上應(yīng)用優(yōu)化過程　　162

9.3　優(yōu)化std::map的查找　　163

9.3.1　以固定長度的字符數(shù)組作為std::map的鍵　　163

9.3.2　以C風(fēng)格的字符串組作為鍵使用std::map　　164

9.3.3　當鍵就是值的時候，使用map的表親std::set　　166

9.4　使用頭文件優(yōu)化算法　　167

9.4.1　以序列容器作為被查找的鍵值對表　　168

9.4.2　std::find()：功能如其名，O(n)時間開銷　　169

9.4.3　std::binary_search()：不返回值　　169

9.4.4　使用std::equal_range()的二分查找　　170

9.4.5　使用std::lower_bound()的二分查找　　170

9.4.6　自己編寫二分查找法　　171

9.4.7　使用strcmp()自己編寫二分查找法　　172

9.5　優(yōu)化鍵值對散列表中的查找　　173

9.5.1　使用std::unordered_map進行散列　　173

9.5.2　對固定長度字符數(shù)組的鍵進行散列　　174

9.5.3　以空字符結(jié)尾的字符串為鍵進行散列　　175

9.5.4　用自定義的散列表進行散列　　176

9.6　斯特潘諾夫的抽象懲罰　　177

9.7　使用C 標準庫優(yōu)化排序　　178

9.8　小結(jié)　　179

第 10章　優(yōu)化數(shù)據(jù)結(jié)構(gòu)　　181

10.1　理解標準庫容器　　181

10.1.1　序列容器　　182

10.1.2　關(guān)聯(lián)容器　　182

10.1.3　測試標準庫容器　　183

10.2　std::vector與std::string　　187

10.2.1　重新分配的性能影響　　188

10.2.2　std::vector中的插入與刪除　　188

10.2.3　遍歷std::vector　　190

10.2.4　對std::vector排序　　191

10.2.5　查找std::vector　　191

10.3　std::deque　　191

10.3.1　std::deque中的插入和刪除　　193

10.3.2　遍歷std::deque　　194

10.3.3　對std::deque 的排序　　194

10.3.4　查找std::deque　　194

10.4　std::list　　194

10.4.1　std::list中的插入和刪除　　196

10.4.2　遍歷std::list中　　197

10.4.3　對std::list排序　　197

10.4.4　查找std::list　　197

10.5　std::forward_list　　198

10.5.1　std::forward_list中的插入和刪除　　199

10.5.2　遍歷std::forward_list　　199

10.5.3　對std::forward_list排序　　199

10.5.4　查找std::forward_list　　199

10.6　std::map與std::multimap　　199

10.6.1　std::map中的插入和刪除　　200

10.6.2　遍歷std::map　　202

10.6.3　對std::map排序　　202

10.6.4　查找std::map　　203

10.7　std::set與std::multiset　　203

10.8　std::unordered_map與std::unordered_multimap　　204

10.8.1　std::unordered_map中的插入與刪除　　206

10.8.2　遍歷std::unordered_map　　207

10.8.3　查找std::unordered_map　　207

10.9　其他數(shù)據(jù)結(jié)構(gòu)　　208

10.10　小結(jié)　　209

第 11章　優(yōu)化I/O　　210

11.1　讀取文件的秘訣　　210

11.1.1　創(chuàng)建一個吝嗇的函數(shù)簽名　　211

11.1.2　縮短調(diào)用鏈　　213

11.1.3　減少重新分配　　213

11.1.4　更大的吞吐量——使用更大的輸入緩沖區(qū)　　215

11.1.5　更大的吞吐量——一次讀取一行　　216

11.1.6　再次縮短函數(shù)調(diào)用鏈　　217

11.1.7　無用的技巧　　218

11.2　寫文件　　219

11.3　從std::cin讀取和向std::cout中寫入　　220

11.4　小結(jié)　　220

第 12章　優(yōu)化并發(fā)　　221

12.1　復(fù)習(xí)并發(fā)　　222

12.1.1　并發(fā)概述　　222

12.1.2　交叉執(zhí)行　　226

12.1.3　順序一致性　　226

12.1.4　競爭　　227

12.1.5　同步　　228

12.1.6　原子性　　228

12.2　復(fù)習(xí)C 并發(fā)方式　　230

12.2.1　線程　　230

12.2.2　promise和future　　231

12.2.3　異步任務(wù)　　233

12.2.4　互斥量　　234

12.2.5　鎖　　235

12.2.6　條件變量　　236

12.2.7　共享變量上的原子操作　　238

12.2.8　展望未來的C 并發(fā)特性　　240

12.3　優(yōu)化多線程C 程序　　241

12.3.1　用std::async替代std::thread　　242

12.3.2　創(chuàng)建與核心數(shù)量一樣多的可執(zhí)行線程　　243

12.3.3　實現(xiàn)任務(wù)隊列和線程池　　244

12.3.4　在單獨的線程中執(zhí)行I/O　　245

12.3.5　沒有同步的程序　　245

12.3.6　移除啟動和停止代碼　　247

12.4　讓同步更加高效　　248

12.4.1　減小臨界區(qū)的范圍　　248

12.4.2　限制并發(fā)線程的數(shù)量　　249

12.4.3　避免驚群　　250

12.4.4　避免鎖護送　　250

12.4.5　減少競爭　　250

12.4.6　不要在單核系統(tǒng)上繁忙等待　　251

12.4.7　不要永遠等待　　252

12.4.8　自己設(shè)計互斥量可能會低效　　252

12.4.9　限制生產(chǎn)者輸出隊列的長度　　252

12.5　并發(fā)庫　　253

12.6　小結(jié)　　254

第 13章　優(yōu)化內(nèi)存管理　　255

13.1　復(fù)習(xí)C 內(nèi)存管理器API　　255

13.1.1　動態(tài)變量的生命周期　　256

13.1.2　內(nèi)存管理函數(shù)分配和釋放內(nèi)存　　256

13.1.3　new表達式構(gòu)造動態(tài)變量　　259

13.1.4　delete表達式處置動態(tài)變量　　261

13.1.5　顯式析構(gòu)函數(shù)調(diào)用銷毀動態(tài)變量　　262

13.2　高性能內(nèi)存管理器　　263

13.3　提供類專用內(nèi)存管理器　　264

13.3.1　分配固定大小內(nèi)存的內(nèi)存管理器　　265

13.3.2　內(nèi)存塊分配區(qū)　　267

13.3.3　添加一個類專用new()運算符　　269

13.3.4　分配固定大小內(nèi)存塊的內(nèi)存管理器的性能　　270

13.3.5　分配固定大小內(nèi)存塊的內(nèi)存管理器的變化形式　　270

13.3.6　非線程安全的內(nèi)存管理器是高效的　　271

13.4　自定義標準庫分配器　　271

13.4.1　C 11分配器　　273

13.4.2　C 98分配器的其他定義　　274

13.4.3　一個分配固定大小內(nèi)存塊的分配器　　278

13.4.4　字符串的分配固定大小內(nèi)存塊的分配器　　279

13.5　小結(jié)　　281

作者介紹　　282

封面介紹　　282