提高C++性能的编程技术笔记：设计优化/可扩展性/系统体系结构相关+测试代码
1. 設計優化
我們可以粗略地將性能優化分為兩種類型：編碼優化和設計優化。編碼優化定義為不需要完整理解要解決的問題或者應用程序的執行流程就能實施的優化。通過定義看出，編碼優化用于局部代碼，同時該過程不牽涉周圍的代碼。除了這些容易實現的優化之外，剩下的所有優化都可以歸結為設計優化。這些優化是系統性的----它們依賴于其它組件甚至一些關聯度很低的模塊的代碼。設計優化貫穿于所有代碼。
設計靈活性：軟件庫是通用的，但應用程序卻不是。將關注的焦點集中于代碼的細節將會產生更高效的代碼。可以通過降低靈活性來增加效率。
緩存：緩存先前的結果有多種不同的方式。其中的一種方式是將其作為對象的成員數據。如果你發現自己的程序不斷重復地使用一個對象來獲得一個相關的結果，那么更好的做法是將這個結果作為此對象的數據成員保存起來，并在將來的計算中使用。
高效的數據結構：軟件性能通常等同于算法和所使用的數據結構的效率，有時算法和數據結構的效率被認為是影響軟件性能的最重要因素。不論事實如何，使用高效率的算法是實現軟件高效率的一個必要條件，這是毋庸置疑的。
延遲計算：許多性能優化通過更高效的計算方法來獲取速度。一些重大的性能優化不僅可以通過提高計算速度實現，還通過消除計算來獲得。
無用計算：
無效代碼：造成的損害包括增加了可執行程序的規模、增大了內存占用，以及產生了源代碼冗余。充斥著失效代碼和僵死代碼的源代碼難于理解、維護和擴展。
在軟件性能和靈活性之間存在一種基本的平衡。對于在80%時間內執行的20%的軟件，性能通常損失在靈活性上。
在代碼細節中可以利用緩存優化代碼，在這個程序設計中也能采用這種方法。通常可以通過將先前的計算結果保存起來避免大量的計算。
對于軟件的高效性而言，使用高效的算法和數據結構是必要條件，但并非充分條件。
有些計算只有在特定執行條件下才需要。這些計算應該被推遲到確實需要它們的路徑上來完成。如果過早地執行計算，那么其結果可能并沒有被調用。
大型軟件往往會變得錯綜復雜，雜亂不堪。混亂軟件的一大特點就是執行失效代碼：那些曾經用來實現某個目標，但現在已經不需要的代碼。定期清理失效和僵死代碼可以增強軟件性能，同時對于軟件也是一種維護。
2. 可擴展性
可擴展性面對的挑戰是使應用程序的運行速度跟得上處理器能力的提升。
主流的單處理器架構由一個CPU和一個主存模塊組成，其中程序數據和指令存儲在主存中。因為CPU的速度至少比主存快一個數量級，所以我們在處理器(CPU)和主存之間插入了一塊快速內存作為緩沖。這塊內存也被稱為緩存。緩存可以提供更快的速度來訪問程序數據和指令。緩存分為兩個物理模塊，其中一個存儲數據，另一個存儲指令。為了獲取指令本身，對于每條指令處理器至少需要訪問一次內存。而絕大多數的指令都需要額外內存參照物來獲取數據。每當處理器需要訪問內存時，首先會在緩存里尋找，因為緩存的訪問命中率高達90%，所以訪問主存的次數很少。
應用程序是由一個進程或多個協作進程組成。而每個進程由一個或多個線程組成。在現代操作系統中，調度的實體就是線程。操作系統執行的是線程，而不是進程。線程都放在系統的運行隊列(Run Queue)里等待調度。在隊列前端的線程就是下一個即將被執行的線程。
現代單處理器計算機由搶占式多任務處理操作系統控制，而該操作系統造成了程序是并發執行的錯覺。從用戶的角度來看，多個程序在并發執行。但正如所說的，這是一個錯覺。在硬件的層面上，任意時刻內都僅有一個線程在單CPU上運行，多任務是通過線程輪流使用CPU來完成的。
對稱多處理器(Symmetric MultiProcessor, SMP)架構：特點：首先是多處理器(MP)，這種系統包含多個同樣的CPU；其次是對稱的，所有的處理器對于系統來說都是一樣的，都有相同的處理能力。例如，它們都有一樣的訪問內存中的任何位置和任意I/O設備的能力。最后，剩余的組成部分是唯一的。這種架構只有一個內存系統、一個操作系統拷貝和一個運行隊列。SMP架構具有擴展性的潛力。
Amdahl定律：針對應用程序的順序執行部分會限制其可擴展性的情況，Amdahl定律做了量化分析。順序(單線程)計算是可擴展性的主要絆腳石。
多線程和同步：以下面的簡單代碼為例：x = x + 1; 假設兩個線程執行上面的語句，我們期望x的值變為x+2，當然其它的結果都是不正確的。但問題是這個語句并不是原子執行，實際上它會被分解為以下匯編語句：
load x, r5 // 將x的值讀入r5寄存器
add r5, 1 // r5寄存器加1
store r5, x //將r5寄存器的值存回x如果兩個線程幾乎同時執行這段代碼，它們的指令可能以某種方式交替執行，而這種方式會導致x+1成為x的新值，而不是x+2。這種不合適的交叉執行線程被稱為競爭條件，為了解決競爭條件，就需要保證這些匯編代碼塊是原子執行的，我們稱這些代碼塊為臨界區。一旦有線程進入臨界區，只有當進入的線程離開后其它的線程才能進入。在這種情況下，我們稱這兩個線程是同步的(或者說串行化的)，同時稱該臨界區是互斥的。因為變量x可以被多個線程訪問，所以我們稱它為共享數據，臨界區就是為解決對共享數據的訪問而設置的。為了保證共享數據的訪問安全(以及正確執行)，我們使用一個鎖----一個標記(比特位或者整型)與共享數據相關聯。線程進入臨界區之前首先要檢查鎖的狀態，如果鎖的狀態是關閉的，則說明當前沒有其它線程在臨界區內執行，因此允許該線程進入臨界區，同時將鎖的狀態變為打開，以此來表示已有線程進入到臨界區內(檢查和設定鎖狀態的操作由硬件來保證是原子的)。如果鎖是打開的，該線程必須要等待當前在臨界區中執行的線程改變鎖的狀態后才能進入臨界區。當臨界區由鎖來保護時，我們稱它的執行是順序進行的，因為想進入臨界區的線程必須得在隊列里等候，并且每次僅進入一個。
將任務分解為多個子任務：為了發揮可擴展性的潛力，應用程序必須將計算任務分為多個可以并行執行的子任務。
緩存共享數據：一旦能越過臨界區訪問，就會看到可擴展性為應用程序所帶來的好處。這個想法的最簡答的應用就是緩存共享數據，這些數據在將來的訪問中不需要鎖來控制就能重用。
無共享：減少共享是件好事，但并沒有完全消除競爭。有時，可以為每個線程提供僅供其使用的私有資源而非共享資源，來完全消除共享。
部分共享：當每個線程都需要資源的單個實例時，可以使實例成為線程私有對象來輕松地消除競爭。如果不能事先確定所需實例的數量，你就需要使用資源池，讓所有線程共享。這樣共享資源經常成為線程競爭的焦點，會嚴重地降低性能和可擴展性，導致線程大量時間都處于空轉狀態。部分共享資源池提供了一種解決這種激烈競爭的方法。
鎖粒度：使用單個鎖來保護多個不相關的共享資源，一般來說都不是一個好主意。這樣做會擴大臨界區的范圍，并造成其它不相關的線程間沖突。此規則的唯一例外是在滿足以下兩個條件時：所有共享資源總是一起操作；任何共享資源的操作都不會消耗大量的CPU周期。
偽共享：緩存的原子單元以行為單位。一般來說一個緩存行可以存儲大量字節,典型的緩存行有128字節。當從主內存加載4字節的整數時，并不是僅加載這4字節，而是把包含它的整個行立即加載到緩存。同樣，當另外的緩存(在不同的處理器上運行)使這個整數無效時，整個緩存行都是無效的。因此，變量在物理內存中的布局對于SMP的可擴展性十分重要。緩存一致性風暴將會嚴重地降低性能和可擴展性。
驚群現象：當線程無法獲取繁忙的鎖時，將會使用下面兩種方式之一處理：(1). 進入自旋，每次循環都嘗試獲取鎖。這對于短時的鎖有效，但在空自旋等待資源可用的同時，長時間的自旋鎖會導致線程耗盡CPU資源。(2). 線程進入休眠并等待喚醒，當鎖釋放后，所有等待的線程將醒來。我們把這種類型的鎖稱為簡單鎖，用來區分自旋鎖。
當很多的線程并發地競爭簡單鎖，那么除了獲得鎖的線程，其余線程都進入休眠狀態。當鎖最后變得可用時，將會出現兩種情況：(1). 只有一個線程被喚醒，它一般是等待隊列上優先級最高的線程。(2). 所有的線程都被喚醒，這會導致”驚群線程”。喚醒所有等待線程的問題在于只有一個線程是真正被喚醒的，其余線程仍舊要回去等待。鑒于線程上下文切換的耗費巨大，我們會遭到性能和可擴展性上的巨大損失。
讀/寫鎖：另一種消除同步問題的方式是放寬只能有一個線程獨占訪問共享數據的要求。共享數據有時候需要順序來訪問，是因為共享數據也許只被訪問它的其中一個線程修改過。所以我們可以只允許一個修改數據的線程(寫者)訪問共享數據。相反，只讀取共享數據的線程(讀者)可以同時訪問共享數據。讀/寫鎖允許多個讀者線程訪問共享數據而不用等待獨占訪問。線程對共享數據進行讀訪問必須滿足以下條件之一：(1). 沒有其它線程訪問數據；(2). 所有訪問數據的線程都是讀者線程。如果寫者線程已獲取訪問權，所有的讀者線程都必須等待寫者線程離開臨街區。當且僅當沒有其它線程獲取對共享資源的訪問權，才可以授予寫者線程訪問權限。如果所有線程都要修改一個共享資源，讀/寫鎖將不會有任何的幫助。實際上，這種類型的鎖會降低性能，因為它們的實現更為復雜，所以性能就低于普通鎖。但如果你的共享數據在絕大多數時間里在執行讀操作，而讀/寫鎖將消除讀者線程間的競爭，所以能提高擴展性。
SMP是多處理器架構。它通過一條總線連接多個對稱的處理器和一個內存系統。總線是SMP架構可擴展性的薄弱環節。讓每個處理器都有自己的大緩存可以有效地控制總線的競爭。
Amdahl定律給出了一個應用的可擴展性的上限，順序化計算限制了擴展性。
實現可擴展性的技巧是減少或者消除順序化的代碼。以下是可以達到這個目標的一些步驟：
任務分解：將大的任務分為小任務，使線程并發地執行這些小任務。
代碼移出：臨界區應該只包含關鍵代碼，不直接操作共享資源的代碼不要放在臨界區內。
利用緩存：有時，通過緩存之前訪問過的數據，可以消除對臨界區的訪問。
無共享：如果需要少量、數目固定的資源實例，可以不使用公共資源池。你可以把這些資源實例設為線程私有，并最后回收。
部分共享：有兩個一樣的資源池可以減少一半的競爭。
鎖粒度：不要用同樣的鎖來保護所有資源，除非這些資源是同時更新的。
偽共享：不要在類定義里把兩個使用頻度都很高的鎖放太靠近。你肯定不希望它們共享同一個緩存并觸發緩存一致性風暴。
驚群現象：仔細分析你的鎖調用的特征。當鎖被釋放時，是所有的等待線程都被喚醒還是只喚醒一個線程？喚醒所有線程會威脅到應用的可擴展性。
系統和類庫調用：考察這些調用的實現特征。它們有可能是隱藏了順序化的代碼。
讀/寫鎖：以讀為主的共享數據會從這種鎖中獲益，使用這種鎖，可以消除讀者線程之間的競爭。
3. 系統體系結構相關話題
存儲器層級：所有對性能的討論最終都會集中到存儲器使用和存儲器使用模式上。通常來說，算法復雜度最核心的方面是算法需要的存儲器訪問量和訪問類型。通常來說,一般的計算機都至少有5個存儲器層級，而一些主要的存儲器層級有時還包含子層級。存儲器層級從最快(訪問時間最短)到最慢(訪問時間最長)其排序為：寄存器、L1(第一級)芯片內緩存、L2(第二級)芯片外緩存、主存(半導體動態隨機訪問內存：DRAM、SDRAM、RAMBUS、SyncLink等等)、磁盤存儲器。
很多人僅根據訪問時間和處理器速度來研究內存訪問。然而，這種觀點忽視了延時和帶寬的交互作用。訪問時間是一個延時問題。總線寬度和脈沖時間是帶寬問題。延遲并不會和帶寬以同樣的比例改善，或者說，我們可以用較快的速度移動數據塊，但是，訪問內存中的單個字節的速度提升很慢。
寄存器：存儲器之王。在存儲器層級上的所有實體中，寄存器延遲最短，帶寬最高，開銷最小。寄存器可由機器代碼直接尋址。存儲器層次結構的所有其它級別都基于虛擬或物理地址劃分，或基于操作系統管理的存儲系統(文件系統)索引來劃分。保留字register告訴編譯器，不要把變量放在內存，或者更精確地說，不要給變量分配內存地址。這只是一種建議，如inline保留字一樣，編譯器可能不理會。一些編譯器會完全忽略寄存器指令。是否將一個變量放到寄存器，一個重要依據是變量被加載和存儲的次數。正確地使用寄存器存放變量可以使某些編譯器產生的個別方法在性能上大幅提升。
磁盤和內存結構：一般來說,程序代碼會顯示出很好的局域性，而對代碼的存儲進行管理似乎并沒有必要。在一些例子里，程序代碼的活動集尺寸過于龐大時，就應該根據執行情況來重新安排代碼的存儲位置，將相關的代碼放到同一個或者多個文件中去。因為性能原因而進行代碼重組是另外一個方面的考慮，這種重組可以反饋給編譯器，使編譯器提供更好的自動優化。
緩存效應：緩存不僅可以提供對訪問過的數據更快的訪問速度，同時可以為以前訪問過的數據提供一小塊預取內存區域。緩存每次提取幾行數據，并對其進行管理。典型的緩存行包含32字節數據，這些數據按32位邊界對齊。通常緩存只能管理完整的緩存行。
緩存抖動：在多處理系統中，最有趣的緩存效應是緩存一致性協議給緩存性能帶來的影響。緩存一致性協議是由內存/緩存控制器所使用的一種機制，該控制器維護多個內存的一致性，否則它們會成為不相關的緩存。緩存一致性協議是基于內存所有者的概念，以及同位緩存作讀操作的顯示驗證。這些基本相當于一種協議，該協議允許多個緩存共享一個數據的拷貝，但在一個時間點只有一個緩存有寫操作的權限。緩存一致性協議要求緩存之間直接通信。這種大量通信會降低系統的性能。主要的原因是緩存之間的通信通路是系統的共享資源，這樣的通信必須是順序進行的。如果內存總線忙于處理其它緩存事務，緩存就必須等待其它忙完后才能通信。這種等待緩存更新訪問被稱為緩存抖動(cache thrash)。緩存抖動是典型的多處理器不能維持其它處理器關系而導致的問題。
避免跳轉：最快的代碼是直線型的代碼：沒有條件判斷，沒有循環，沒有調用，沒有返回。一般來說，程序的關鍵路徑越像一條直線，執行速度就越快。請記住：短小而帶有很多分支的代碼要比長而沒有分支的代碼所用的執行時間長。
使用簡單計算代替小分支：分支是性能的敵人。而很多時候，分支是不可避免的，但有時分支可以用計算來代替。這可能是一個重要的性能提升策略。
線程化的影響：多進程和多線程是兩個關系密切但又相區別的并發編程類型。多進程允許多個獨立的大進程相互通信。線程是子進程，它們是大進程的片段，但是它們都可以獨立的調度。凡是從應用的角度討論多任務都應該包含阻塞這個主題。這里有兩種常見的I/O請求：阻塞和非阻塞，或者稱為同步和異步。同步I/O要等待I/O請求完成后才能切換上下文，然后繼續處理，也就是說同步I/O請求首先要求阻塞，直到I/O請求完成才做下一步的處理。異步I/O是在滿足請求之前可以盡可能多地處理I/O事務，并要把所取得的進展返回到進程上下文，無論處理完多少事務，都不進行阻塞處理。通常還有一種中間I/O請求，這種類型的請求在某些時間里進行同步操作，而其余時間是異步操作。雖然在同步和異步操作之間的中間層可以給任務提供更有趣的操作能力，但是從性能的角度來看，它本質上仍是一種同步操作。
線程只有在同步請求資源或數據不可用時，才會阻塞。請求線程必須等待系統滿足請求，而要滿足這個請求就要完成I/O操作。當一個線程在等待相應的I/O操作完成時，要把它從處理器中切換出去，讓其它沒有被阻塞的線程運行。在I/O操作完成之后，線程再次變成可調度狀態，并最終切換到處理器里運行。被阻塞的高優先級的線程將在I/O請求處理完成后立即恢復執行。
常見的程序是同步的單線程，它在某一時刻只能做一件事。一旦請求無法立即得到滿足，整個程序就會被阻塞并等待操作系統完成它的請求。相反的是，一些復雜的程序會使用多個邏輯并發的物理和邏輯處理流來編寫。這使得程序可執行多個相對獨立的片段，而不用管它們在某個時間點是否完成了I/O請求。
多線程是一種相當有用的機制，而且在合適的系統中能帶來巨大的性能優勢，但錯誤地使用線程概念會導致嚴重的性能問題。多線程要求要進行上下文切換，而這種切換會耗費上千個處理周期。多線程還要頻繁地使用鎖來保護共享內存區域。鎖也會浪費大量的處理周期，卻對程序的完成沒有任何作用。
上下文切換：是指將一個進程(線程)從處理器移出并把另外一個進程移入處理器。這個過程中要保存進程和處理器的狀態。保存進程的狀態是為了維護進程執行點的精確記錄。保存處理器的狀態是為了在相關進程繼續執行時，處理器能返回原狀態。處理器狀態是進程狀態的一部分，但不是全部。
進程上下文是操作系統所定義的一種結構，因此與操作系統關系密切。操作系統對該結構進行管理，這個結構包含進程的相關信息，如分配的內存范圍、頁映射表、打開的文件指針、子進程、處理器狀態變量(寄存器、程序計數器、可能還有旁路轉換緩沖，即Translation-Lookaside Buffer, TLB)，還有進程狀態變量如優先級、所有者、運行時間和當前狀態(可調度、已阻塞、運行中)。大多數進程狀態保存在內存里，只會偶爾訪問，但進程上下文的處理器狀態部分一直是由處理器使用的，并且必須放在處理器里用于進程執行。每次進程換出時，與進程相關的處理器狀態要從處理器移到內存里，每次進程換入時，處理器要把這部分數據加載進來。
上下文切換有三個主要的開銷：處理器上下文遷移、緩存和TLB丟失，以及調度開銷。上下文切換和緩存之間的交互對程序的性能影響是最有害的。緩存的結構類型對系統性能的特性有顯著的影響。根據訪問緩存時所用的地址類型可以將緩存分為兩類。虛擬地址緩存從進程的虛擬地址空間訪問。虛擬地址與進程無關。另一種緩存類型是物理地址緩存，本質上與有ID標記的虛擬緩存相同。不同點在于，它不依賴于標記里的ID地址對，而是在提交緩存之前強制系統將虛擬地址轉換為物理地址。
內核交叉：異步輪詢相對于同步線程而言是一個很好的替代方案。雖然異步不是一種簡單的軟件技術，但在一些系統里，它可以帶來很多性能的優勢。這個問題與內核交叉的代價聯系密切，同時又與上下文切換相關。在程序顯式地調用服務例程，而該例程需要以內核權限執行時，就會發生內核交叉。在發生內核交叉時下面兩件事中的一件也會發生：胖系統調用和瘦系統調用；而具體發生哪一個則取決于系統所使用的機制和服務請求的類型。
線程化選擇：有3種主要的劃分線程的方法：單個、小型和大型。單線程簡單的形式就是一個程序，只由一個線程控制。然而，在更為復雜形式中，單線程程序可以使用異步I/O來實現邏輯并發和獨立操作。單線程異步模型依賴于程序內部結構來監視程序各個部分的狀態，同時依賴輪詢來測試這些部分的I/O有效性。使用異步I/O可以保證：第一，沒有子任務會因為一些I/O請求不能立即滿足而阻塞整個任務；第二，程序的控制元素可以決定什么時候交出處理器的控制權，還可以決定什么時候繼續處理。這樣的系統往往圍繞一個中央控制循環來構造，并順序執行每個子任務。雖然這是一個很復雜的方法，但是在一些環境里，這種方法可以提供比多線程環境更好的性能。但如果使用不當，會出現無止境的空輪詢，導致任務沒有進展。大型線程是一種把請求當做獨立處理實體的機制。可以理解為這種線程劃分方法把每個重要的對象方法都看作一個線程。當重要對象被創建時，為其分配自己的線程，該線程將伴隨對象的整個生命周期，從創建到銷毀。這種機制可能非常高效，但也會在上下文切換時出現問題。小型多線程是將單線程和大型多線程方法相結合的機制。小型線程傾向于把子任務的完成作為中心，而不是把完成整改獨立請求作為中心。決定采用何種線程時，最重要的方面可能是將要支持程序運行的硬件。
要使用的存儲器離處理器越遠，訪問所需的時間就越長。離處理器最近的是寄存器，雖然容量很少，但是速度很快。對寄存器的優化對程序的性能提升而言是極其有意的。
虛擬存儲器并不是無償的，不加選擇地依賴系統管理的虛擬結構可能會影響性能，而且一般都是降低性能。
上下文切換的開銷巨大，需避免上下文切換。
以下是測試代碼(design_optimizations.cpp)：
#include "design_optimizations.hpp"
#include <string.h>
#include <iostream>
#include <chrono>
#include <string>
#include <numeric>
#include <vector>namespace design_optimizations_ {// reference: 《提高C++性能的編程技術》：第十四章：設計優化
namespace {void stringSum1(const std::vector<std::string>& vs, std::string& result)
{int vectorSize = vs.size();int* stringSizes = new int[vectorSize];int totalInputLength = 0;for (int i = 0; i < vectorSize; ++i) {stringSizes[i] = vs[i].length();totalInputLength += stringSizes[i];}char* s = new char[totalInputLength+1];memset(s, 0, totalInputLength+1);int sp = 0;for (int i = 0; i < vectorSize; ++i) {memcpy(&s[sp], vs[i].c_str(), stringSizes[i]);sp += stringSizes[i];}delete[] stringSizes;result = s;delete[] s;
}} // namespaceint test_design_optimizations_1()
{std::chrono::high_resolution_clock::time_point time_start, time_end;const int count{1000000}, count2{100000};std::vector<std::string> vectorx;for (int i = 0; i < 100; ++i) {vectorx.emplace_back("abcd");}{ // test string add: std::accumulate: 此函數的性能弱點測試time_start = std::chrono::high_resolution_clock::now();for (int i = 0; i < count; ++i) {std::string empty;std::string result = std::accumulate(vectorx.cbegin(), vectorx.cend(), empty);//fprintf(stdout, "result: %s\n", result.c_str());}time_end = std::chrono::high_resolution_clock::now(); fprintf(stdout, "string add operation std::accumulate time spend: %f seconds\n",(std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // test string add: custom function: 為了提高性能而犧牲了通用性time_start = std::chrono::high_resolution_clock::now();for (int i = 0; i < count; ++i) {std::string result;stringSum1(vectorx, result);//fprintf(stdout, "result: %s\n", result.c_str());}time_end = std::chrono::high_resolution_clock::now(); fprintf(stdout, "string add operation custom function time spend: %f seconds\n",(std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}return 0;
}} // namespace design_optimizations_執行結果如下：
GitHub： https://github.com/fengbingchun/Messy_Test?
總結
以上是生活随笔為你收集整理的提高C++性能的编程技术笔记：设计优化/可扩展性/系统体系结构相关+测试代码的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 以安装PyTorch为例说明Anacon
- 下一篇： 提高C++性能的编程技术笔记：总结