C++性能優化指南 C++性能优化指南

[美]柯爾特 甘瑟爾羅斯（Kurt Guntheroth）譯者:楊文軒

Kurt Guntheroth軟件開發工作近40年，C++代碼實用年齡20餘年。具有在Windows、Linux和嵌入式設備上的開發經驗。Kurt不是一個工作狂，他喜歡陪伴他的妻子和那四個活潑的兒子。Kurt居住在華盛頓州的西雅圖。

前言xvii 
第1章優化概述1 
1.1優化是軟件開發的一部分2 
1.2優化是高效的3 
1.3優化是沒有問題的3 
1.4這兒一納秒，那兒一納秒5 
1.5 C++代碼優化策略總結5 
1.5.1用好的編譯器並用好編譯器6 
1.5.2使用更好的算法7 
1.5.3使用更好的庫8 
1.5.4減少內存分配和復制9 
1.5.5移除計算9 
1.5.6使用更好的數據結構9 
1.5.7提高並發性10 
1.5.8優化內存管理10 
1.6小結10 

第2章影響優化的計算機行為11 
2.1 C++所相信的計算機謊言12 
2.2計算機的真相12 
2.2.1內存很慢13 
2.2.2內存訪問並非以字節為單位13 
2.2.3某些內存訪問會比其他的更慢14 
2.2.4內存字分為大端和小端14 
2.2.5內存容量是有限的15 
2.2. 6指令執行緩慢16 
2.2.7計算機難以作決定16 
2.2.8程序執行中的多個流16
2.2.9調用操作系統的開銷是昂貴的18 
2.3 C++也會說謊18 
2.3.1並非所有語句的性能開銷都相同18 
2.3.2語句並非按順序執行18 
2.4小結19 

第3章測量性能20 
3.1優化思想21 
3.1.1必須測量性能21 
3.1.2優化器是獵人21 
3.1.3 90/10規則22 
3.1.4阿姆達爾定律23 
3.2進行實驗24 
3.2.1記實驗筆記26 
3.2.2測量基準性能並設定目標26 
3.2.3你只能改善你能夠測量的28 
3.3分析程序執行28 
3.4測量長時間運行的代碼30 
3.4.1一點關於測量時間的知識30 
3.4.2用計算機測量時間35 
3.4. 3剋服測量障礙41 
3.4.4創建stopwatch類44 
3.4.5使用測試套件測量熱點函數48 
3.5評估代碼開銷來找出熱點代碼48 
3.5.1評估獨立的C++語句的開銷49 
3.5.2評估循環的開銷49 
3.6其他找出熱點代碼的方法51 
3.7小結51 

第4章優化字符串的使用：案例研究53
4.1為什麼字符串很麻煩53 
4.1.1字符串是動態分配的54 
4.1.2字符串就是值54 
4.1.3字符串會進行大量複製55 
4.2嘗試優化字符串56 
4.2.1使用複合賦值操作避免臨時字符串57 
4.2.2通過預留存儲空間減少內存的重新分配57 
4.2.3消除對參數字符串的複制58 
4.2.4使用迭代器消除指針解引59 
4.2.5消除對返回的字符串的複制59 
4.2.6用字符數組代替字符串60 
4.3嘗試優化字符串62 
4.3.1使用更好的算法62 
4.3.2使用更好的編譯器64 
4.3.3使用更好的字符串庫64 
4.3.4使用更好的內存分配器67 
4.4消除字符串轉換69 
4.4.1將C字符串轉換為std::string 69 
4.4.2不同字符集間的轉換70 
4.5小結70 

第5章優化算法71 
5.1算法的時間開銷72 
5.1.1情況的時間開銷74 
5.1.2攤銷時間開銷74 
5.1.3其他開銷75 
5.2優化查找和排序的工具箱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利用輸入數據集的已知特性78 
5.5優化模式78 
5.5.1預計算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優化期待路徑82 
5.5.9散列法82 
5.5.10雙重檢查82 
5.6小結82 

第6章優化動態分配內存的變量83 
6.1 C++變量回顧84 
6.1. 1變量的存儲期84 
6.1.2變量的所有權86 
6.1.3值對象與實體對象86 
6.2 C++動態變量API回顧88 
6.2.1使用智能指針實現動態變量所有權的自動化90 
6.2.2動態變量有運行時開銷92 
6.3減少動態變量的使用92 
6.3.1靜態地創建類實例92
6.3.2使用靜態數據結構93 
6.3.3使用std::make_shared替代new表達式97 
6.3.4不要無謂地共享所有權97 
6.3.5使用“主指針”擁有動態變量98 
6.4減少動態變量的重新分配99 
6.4.1預分配動態變量以防止重新分配99 
6.4.2在循環外創建動態變量99 
6.5移除無謂的複制100 
6.5.1在類定義中禁止不希望發生的複制101 
6.5.2移除函數調用上的複制102 
6.5.3移除函數返回上的複制103 
6.5.4免複製庫105 
6.5.5實現寫時復制慣用法106 
6.5.6切割數據結構106 
6.6實現移動語義107 
6.6.1非標準複製語義：痛苦的實現107 
6.6.2 std::swap()：“窮人”的移動語義108 
6.6.3共享所有權的實體109 
6.6.4移動語義的移動部分109 
6.6.5更新代碼以使用移動語義110 
6.6.6移動語義的微妙之處111 
6.7扁平數據結構113 
6.8小結113 

第7章優化熱點語句115 
7.1從循環中移除代碼116
7.1.1緩存循環結束條件值117 
7.1.2使用更高效的循環語句117 
7.1.3用遞減替代遞增118 
7.1.4從循環中移除不變性代碼118 
7.1.5從循環中移除無謂的函數調用119 
7.1.6從循環中移除隱含的函數調用121 
7.1.7從循環中移除昂貴的、緩慢改變的調用123 
7.1.8將循環放入函數以減少調用開銷123 
7.1.9不要頻繁地進行操作124 
7.1.10其他優化技巧126 
7.2從函數中移除代碼126 
7.2.1函數調用的開銷126 
7.2.2簡短地聲明內聯函數129 
7.2.3在使用之前定義函數129 
7.2.4移除未使用的多態性130 
7.2.5放棄不使用的接口130 
7.2.6用模板在編譯時選擇實現133 
7.2.7避免使用PIMPL慣用法134 
7.2.8移除對DDL的調用135 
7.2.9使用靜態成員函數取代成員函數136 
7.2.10將虛析構函數移基類中136 
7.3優化表達式137 
7.3.1簡化表達式137 
7.3.2將常量組合在一起138 
7.3.3使用更高效的運算符139
7.3.4使用整數計算替代浮點型計算139 
7.3.5雙精度類型可能會比浮點型更快140 
7.3.6用閉形式替代迭代計算141 
7.4優化控制流程慣用法142 
7.4.1用switch替代if-else if-else 142 
7.4.2用虛函數替代switch或if 143 
7.4.3使用無開銷的異常處理144 
7.5小結145 

第8章使用更好的庫146 
8.1優化標準庫的使用146 
8.1.1 C++標準庫的哲學147 
8.1.2使用C++標準庫的註意事項147 
8.2優化現有庫149 
8.2.1改動越少越好149 
8.2.2添加函數，不要改動功能150 
8.3設計優化庫150 
8.3.1草率編碼後悔多150 
8.3.2在庫的設計上，簡約是一種美德151 
8.3.3不要在庫內分配內存152 
8.3.4若有疑問，以速度為準152 
8.3.5函數比框架更容易優化152 
8.3.6扁平繼承層次關係153 
8.3.7扁平調用鏈153 
8.3.8扁平分層設計153 
8.3.9避免動態查找154 
8.3.10留意“上帝函數” 155
8.4小結156 

第9章優化查找和排序157 
9.1使用std::map和std::string的鍵值對錶158 
9.2改善查找性能的工具箱159 
9.2.1進行一次基準測量160 
9.2.2識別出待優化的活動160 
9.2.3分解待優化的活動160 
9.2.4修改或替換算法和數據結構161 
9.2.5在自定義抽像上應用優化過程162 
9.3優化std::map的查找163 
9.3.1以固定長度的字符數組作為std::map的鍵163 
9.3.2以C風格的字符串組作為鍵使用std::map 164 
9.3.3當鍵就是值的時候，使用map的表親std::set 166 
9.4使用頭文件優化算法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優化鍵值對散列表中的查找173 
9.5.1使用std::unordered_map進行散列173 
9.5.2對固定長度字符數組的鍵進行散列174 
9.5.3以空字符結尾的字符串為鍵進行散列175 
9.5.4用自定義的散列表進行散列176 
9.6斯特潘諾夫的抽象懲罰177 
9.7使用C++標準庫優化排序178 
9.8小結179 

第10章優化數據結構181 
10.1理解標準庫容器181 
10.1.1序列容器182 
10.1.2關聯容器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其他數據結構208 
10.10小結209 

第11章優化I/O 210 
11.1讀取文件的秘訣210 
11.1.1創建一個吝嗇的函數簽名211 
11.1.2縮短調用鏈213 
11.1.3減少重新分配213 
11.1.4更大的吞吐量——使用更大的輸入緩衝區215 
11.1.5更大的吞吐量——一次讀取一行216 
11.1.6再次縮短函數調用鏈217 
11.1.7無用的技巧218 
11.2寫文件219 
11.3從std::cin讀取和向std::cout中寫入220 
11.4小結220 

第12章優化並發221
12.1複習並發222 
12.1.1並發概述222 
12.1.2交叉執行226 
12.1.3順序一致性226 
12.1.4競爭227 
12.1.5同步228 
12.1.6原子性228 
12.2複習C++並發方式230 
12.2.1線程230 
12.2.2 promise和future 231 
12.2.3異步任務233 
12.2.4互斥量234 
12.2.5鎖235 
12.2.6條件變量236 
12.2.7共享變量上的原子操作238 
12.2.8展望未來的C++並發特性240 
12.3優化多線程C++程序241 
12.3.1用std::async替代std::thread 242 
12.3.2創建與核心數量一樣多的可執行線程243 
12.3.3實現任務隊列和線程池244 
12.3.4在單獨的線程中執行I/O 245 
12.3.5沒有同步的程序245 
12.3.6移除啟動和停止代碼247 
12.4讓同步更加高效248 
12.4.1減小臨界區的範圍248 
12.4.2限制並發線程的數量249
12.4.3避免驚群250 
12.4.4避免鎖護送250 
12.4.5減少競爭250 
12.4.6不要在單核系統上繁忙等待251 
12.4.7不要永遠等待252 
12.4.8自己設計互斥量可能會低效252 
12.4.9限制生產者輸出隊列的長度252 
12.5並發庫253 
12.6小結254 

第13章優化內存管理255 
13.1複習C++內存管理器API 255 
13.1.1動態變量的生命週期256 
13.1.2內存管理函數分配和釋放內存256 
13.1.3 new表達式構造動態變量259 
13.1.4 delete表達式處置動態變量261 
13.1.5顯式析構函數調用銷毀動態變量262 
13.2高性能內存管理器263 
13.3提供類專用內存管理器264 
13.3.1分配固定大小內存的內存管理器265 
13.3.2內存塊分配區267 
13.3.3添加一個類專用new()運算符269 
13.3.4分配固定大小內存塊的內存管理器的性能270 
13.3.5分配固定大小內存塊的內存管理器的變化形式270 
13.3.6非線程安全的內存管理器是高效的271
13.4自定義標準庫分配器271 
13.4.1 C++11分配器273 
13.4.2 C++98分配器的其他定義274 
13.4.3一個分配固定大小內存塊的分配器278 
13.4.4字符串的分配固定大小內存塊的分配器279 
13.5小結281 
作者介紹282 
封面介紹282