C++怎么為多線程性能設計數據結構

本篇內容主要講解“C++怎么為多線程性能設計數據結構”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“C++怎么為多線程性能設計數據結構”吧!

8.3.1 為復雜操作劃分數組元素

假設你正在做一些復雜的數學計算,你需要將兩個大矩陣想乘。為了實現矩陣相乘,你將第一個矩陣的第一行每個元素與第二個矩陣的第一列相對應的每個元素相乘,并將結果相加得到結果矩陣左上角第一個元素。然后你繼續將第二行與第一列相乘得到結果矩陣第一列的第二個元素,以此類推。正如圖8.3所示,突出顯示的部分表明了第一個矩陣的第二行與第二個矩陣的第三列配對,得到結果矩陣的第三列第二行的值。

圖8.3 矩陣相乘

為了值得使用多線程來優化該乘法運算,現在我們假設這些都有幾千行和幾千列的大矩陣。通常,非稀疏矩陣在內存中是用一個大數組表示的,第一行的所有元素后面是第二行的所有元素,以此類推。為了實現矩陣相乘,現在就有三個大數組了。為了獲得更優的性能,你就需要注意數據存取部分,特別是第三個數組。

有很多在線程間劃分工作的方法。假設你有比處理器更多的行例,那么你就可以讓每個線程計算結果矩陣中某些列的值,或者讓每個線程計算結果矩陣中某些行的值,或者甚至讓每個線程計算結果矩陣中規則矩形子集的值。

回顧8.2.3節和8.2.4節,你就會發現讀取數組中的相鄰元素比到處讀取數組中的值要好,因為這樣減少了緩存使用以及假共享。如果你使每個線程處理一些列,那么就需要讀取第一個矩陣中的所有元素以及第二個矩陣中相對應的列中元素,但是你只會得到列元素的值。假設矩陣是用行順序存儲的,這就意味著你從第一行中讀取N個元素,從第二行中讀取N個元素,以此類推(N的值是你處理的列的數目)。別的線程會讀取每一行中別的元素,這就很清楚你應該讀取相鄰的的列,因此每行的N個元素就是相鄰的,并且最小化了假共享。當然,如果這N個元素使用的空間與緩存線的數量相等的話,就不會有假共享,因為每個線程都會工作在獨立的緩存線上。

另一方面,如果每個線程處理一些行元素,那么就需要讀取第二個矩陣中的所有元素,以及第一個矩陣中相關的行元素,但是它只會得到行元素。因為矩陣是用行順序存儲的,因此你現在讀取從N行開始的所有元素。如果你選擇相鄰的行,那么就意味著此線程是現在唯一對這N行寫入的線程;它擁有內存中連續的塊并且不會被別的線程訪問。這就比讓每個線程處理一些列元素更好,因為唯一可能產生假共享的地方就是一塊的最后一些元素與下一個塊的開始一些元素。但是值得花時間確認目標結構。

第三種選擇一劃分為矩形塊如何呢?這可以被看做是先劃分為列,然后劃分為行。它與根據列元素劃分一樣存在假共享問題。如果你可以選擇塊的列數目來避免這種問題,那么從讀這方面來說,劃分為矩形塊有這樣的優點:你不需要讀取任何一個完整的源矩陣。你只需要讀取相關的目標矩陣的行與列的值。從具體方面來看,考慮兩個1000行和1000列的矩陣相乘。就有一百萬個元素。如果你有100個處理器,那么每個線程可以處理10行元素。盡管如此,為了計算這10000個元素,需要讀取第二個矩陣的所有元素(一百萬個元素)加上第一個矩陣相關行的10000個元素,總計1010000個元素;另一方面,如果每個線程處理100行100列的矩陣塊(總計10000個元素) ,那么它們需要讀取第一個矩陣的100行元素( 100 x 1000=100000元素)和第二個矩陣的100列元素(另一個100000個元素)。這就只有200000元素,將讀取的元素數量降低到五分之一。如果你讀取更少的元素,那么發生緩存未命中和更好性能的潛力的機會就更少了。

因此將結果矩陣劃分為小的方塊或者類似方塊的矩陣比每個線程完全處理好幾行更好。當然,你可以調整運行時每個塊的大小,取決于矩陣的大小以及處理器的數量。如果性能很重要,基于目標結構分析各種選擇是很重要的。

你也有可能不進行矩陣乘法,那么它是否適用呢?當你在線程間劃分大塊數據的時候,同樣的原則也適用于這種情況。仔細觀察數據讀取方式,并且識別影響性能的潛在原因。在你遇到的問題也可能有相似的環境,就是只要改變工作劃分方式可以提高性能而不需要改變基本算法。

好了,我們已經看到數組讀取方式是如何影響性能的。其他數據結構類型呢?

8.3.2其他數據結構中的數據訪問方式

從根本上說,當試圖優化別的數據結構的數據訪問模式時也是適用的。

1、在線程間改變數據分配,使得相鄰的數據被同一個線程適用。

2、最小化任何給定線程需要的數據。

3、確保獨立的線程訪問的數據相隔足夠遠來避免假共享。

當然,運用到別的數據結構上是不容易的。例如,二叉樹本來就很難用任何方式來再分,有用還是沒用,取決于樹是如何平衡的以及你需要將它劃分為多少個部分。同樣,樹的本質意味著結點是動態分配的,并且最后在堆上不同地方。

現在,使數據最后在堆上不同地方本身不是一個特別的問題,但是這意味著處理器需要在緩存中保持更多東西。實際上這可以很有利。如果多個線程需要遍歷樹,那么它們都需要讀取樹的結點,但是如果樹的結點至包含指向該結點持有數據的指針,那么當需要的時候,處理器就必須從內存中載入數據。如果線程正在修改需要的數據,這就可以避免結點數據與提供樹結構的數據間的假共享帶來的性能損失。

使用互斥元保護數據的時候也有同樣的問題。假設你有一個簡單的類,它包含一些數據項和一個互斥元來保護多線程讀取。如果互斥元和數據項在內存中離得很近,對于使用此互斥元的線程來說就很好;它需要的數據已經在處理器緩存中了,因為為了修改互斥元已經將它載入了。但是它也有一個缺點:當第一個線程持有豆斥元的時候,如果別的線程試圖鎖住互斥元,它們就需要讀取內存。互斥元的鎖通常作為一個在互斥元內的存儲單元上試圖獲取互斥元的讀一修改一寫原子操作來實現的,如果互斥元已經被鎖的話,就接著調用操作系統內核。這個讀一修改一寫操作可能導致擁有互斥元的線程持有的緩存中的數據變得無效。只要使用互斥元,這就不是問題。盡管如此,如果互斥元和線程使用的數據共享同一個緩沖線,那么擁有此互斥元的線程的性能就會因為另一個線程試圖鎖住該互斥元而受到影響。

測試這種假共享是否是一個問題的方法就是在數據元素間增加可以被不同的線程并發讀取的大塊填充數據例如,你可以使用:

來測試互斥元競爭問題或者使用：

來測試數組數據是否假共享。如果這樣做提高了性能,就可以得知假共享確實是一個問題,并且你可以保留填充數據或者通過重新安排數據讀取的方式來消除假共享。

當然,當設計并發性的時候,不僅需要考慮數據讀取模式,因此讓我們來看看別的需要考慮的方面。

8.4 為并發設計時的額外考慮

本章我們看了一些在線程間劃分工作的方法,影響性能的因素,以及這些因素是如何影響你選擇哪種數據讀取模式和數據結構的。但是,設計并發代碼需要考慮更多。你需要考慮的事情例如異常安全以及可擴展性。如果當系統中處理核心增加時性能(無論是從減少執行時間還是從增加吞吐量方面來說)也增加的話,那么代碼就是可擴展的。從理論上說,性能增加是線性的。因此一個有100個處理器的系統的性能比只有一個處理器的系統好100倍。

即使代碼不是可擴展的,它也可以工作。例如,單線程應用不是可擴展的,異常安全是與正確性有關的。如果你的代碼不是異常安全的,就可能會以破碎的不變量或者競爭條件結束,或者你的應用可能因為一個操作拋出異常而突然終止。考慮到這些,我們將首先考慮異常安全。

8.4.1 并行算法中的異常安全

異常安全是好的C++代碼的一個基本方面,使用并發性的代碼也不例外。實際上,并行算法通常比普通線性算法需要你考慮更多關于異常方面的問題。如果線性算法中的操作拋出異常,該算法只要考慮確保它能夠處理好以避免資源泄漏和破碎的不變量。它可以允許擴大異常給調用者來處理。相比之下,在并行算法中,很多操作在不同的線程上運行。在這種情況下,就不允許擴大異常了,因為它在錯誤的調用棧中。如果一個函數大量產生以異常結束的新線程,那么該應用就會被終止。

作為一個具體的例子,我們來回顧清單2.8中的 parallel_accumulate函數,清單8.2中會做一些修改

清單8.2 sta::accumulate的并行版本(來自清單2.8)

現在我們檢查并且確定拋出異常的位置:總的說來,任何調用函數的地方或者在用戶定義的類型上執行操作的地方都可能拋出異常。

首先,你調用distance 2,它在用戶定義的迭代器類型上執行操作。因為你還沒有進行任何工作,并且這是在調用線程上,所以這是沒問題的。下一步,你分配了results選代器3和threads迭代器4。同樣,這是在調用線程上,并且你沒有做任何工作或者生產任何線程,因此這是沒問題的。當然,如果threads構造函數拋出異常,那么就必須清楚為results分配的內存,析構函數將為你完成它。

跳過block_start 的初始化5因為這是安全的,就到了產生線程的循環中的操作6、7、8。一旦在7中創造了第一個線程,如果拋出異常的話就會很麻煩,你的新sta::thread 對象的析構函數會調用

std::terminate 然后中程序,

調用accumulate_block 9也可能會拋出異常,你的線程對象將被銷毀并且調用std:terminate ;另一方面,最后調用std::accumulate 10的時候也可能拋出異常并且不導致任何困難,因為所有線程將在此處匯合。

這不是對于主線程來說的,但是也可能拋出異常,在新線程上調用 accumulate_block 可能拋出異常1。這里沒有任何catch塊,因此該異常將被稍后處理并且導致庫調用sta::terminate()來中止程序。

即使不是顯而易見的,這段代碼也不是異常安全的。

1·增加異常安全性

好了,我們識別出了所有可能拋出異常的地方以及異常所造成的不好影響。那么如何處理它呢?我們先來解決在新線程上拋出異常的問題。

在第4章中介紹了完成此工作的工具。如果你仔細考慮在新線程中想獲得什么,那么很明顯當允許代碼拋出異常的時候,你試圖計算結果來返回。std: :packaged_task 和std:future 的組合設計是恰好的。如果你重新設計代碼來使用 std::packaged_task ,就以清單8.3中的代碼結束。

清單8.3使用std::packaged_task的std::accumulate的并行版本

第一個改變就是,函數調用accumulate_block操作直接返回結果,而不是返回存儲地址的引用1。你使用std::packaged_task 和std::future來保證異常安全,因此你也可以使用它來轉移結果。這就需要你調用std::accumulate 2明確使用默認構造函數T而不是重新使用提供的result值,不過這只是一個小小的改變。

下一個改變就是你用futures 向量3,而不是用結果為每個生成的線程存儲一個 std:future 。在生成戈程的循環中,你首先為 accumulate_block 創造一個任務4。std:packaged_task

既然你已經使用了future ,就不再有結果數組了,因此必須將最后一塊的結果存儲在一個變量中7而不是存儲在數組的一個位置中。同樣,因為你將從future中得到值,使用基本的for 循環比使用std:accumulate要簡單,以提供的初始值開始8,并且將每個future的結果累加起來9。如果相應的任務拋出異常,就會在future中捕捉到并且調用get() 時會再次拋出異常。最后,在返回總的結果給調用者之前要加上最后一個塊的結果10。

因此,這就去除了一個可能的問題,工作線程中拋出的異常會在主線程中再次被拋出。如果多于一個工作線程拋出異常,只有一個異常會被傳播,但是這也不是一個大問題。如果確實有關的話,可以使用類似

std::nested_exception來捕捉所有的異常然后拋出它。

如果在你產生第一個線程和你加入它們之間拋出異常的話,那么剩下的問題就是線程泄漏。最簡單的方法就是捕獲所有異常,并且將它們融合到調用joinable()的線程中,然后再次拋出異常。

現在它起作用了。所有線程將被聯合起來,無論代碼是如何離開塊的。盡管如此, try-catch塊是令人討厭的,并且你有復制代碼。你將加入正常的控制流以及捕獲塊的線程中。復制代碼不是一個好事情,因為這意味著需要改變更多的地方。我們在一個對象的析構函數中檢查它,畢竟,這是C++中慣用的清除資源的方法。下面是你的類。

這與清單2.3中的thread_guard類是相似的，除了它擴展為適合所有線程。你可以如清單8.4所示簡化代碼。

清單8.4 std：：accumulate的異常安全并行版本

一旦你創建了你的線程容器,也就創建了一個新類的實例1來加入所有在退出的線程。你可以去除你的聯合循環,只要你知道無論函數是否退出,這些線程都將被聯合起來。注意調用 futures[i].get() 2將被阻塞直到結果出來,因此在這一點并不需要明確地與線程融合起來。這與清單8.2中的原型不一樣,在清單8.2中你必須與線程聯合起來確保正確復制了結果向量。你不僅得到了異常安全代碼,而且你的函數也更短了,因為將聯合代碼提取到你的新(可再用的)類中了。

2. STD::ASYNC()的異常安全

你已經知道了當處理線程時需要什么來實現異常安全,我們來看看使用std::async() 時需要做的同樣的事情。你已經看到了,在這種情況下庫為你處理這些線程,并且當future是就緒的時候,產生的任何線程都完成了。需要注意到關鍵事情就是異常安全,如果銷毀future的時候沒有等待它,析構函數將等待線程完成。這就避免了仍然在執行以及持有數據引用的泄漏線程的問題。清單8.5所示就是使用std::async ()的異常安全實現。

清單8.5 使用std::async的std::accumulate的異常安全并行版本

這個版本使用遞歸將數據劃分為塊而不是重新計算將數據劃分為塊,但是它比之前的版本要簡單一些,并且是異常安全的。如以前一樣,你以計算序列長度開始1,如果它比最大的塊尺寸小的話,就直接調用

std::accumuate 2。如果它的元素比塊尺寸大的話,就找到中點3然后產生一個異步任務來處理前半部分![序號4。范圍內的第二部分就用一個直接的遞歸調用來處理5。,然后將這兩個塊的結果累加6。庫確保了std::async調用使用了可獲得的硬件線程,并且沒有創造很多線程。一些"異步”調用將在調用get()的時候被異步執行6。

這種做法的好處在于它不僅可以利用硬件并發,而且它也是異常安全的。如果遞歸調用拋出異常5,當異常傳播時,調用std::async 4創造的future就會被銷毀。它會輪流等待異步線程結束,因此避免了懸掛線程。另一方面,如果異步調用拋出異常,就會被future捕捉,并且調用get() 6將再次拋出異常。

當設計并發代碼的時候還需要考慮哪些方面呢?讓我們來看看可擴展性。如果將你的代碼遷移到更多處理器系統中會提高多少性能呢?

8.4.2可擴展性和阿姆達爾定律

可擴展性是關于確保你的應用可以利用系統中增加的處理器。一種極端情況就是你有一個完全不能擴展的單線程應用,即使你在系統中增加100個處理器也不會改變性能。另一種極端情況是你有類似SETI@Home[3]的項目,被設計用來利用成千上萬的附加的處理器(以用戶將個人計算機增加到網絡中的形式)。

對于任何給定的多線程程序,當程序運行時,執行有用工作的線程的數量會發生變化。即使每個線程都在做有用的操作,初始化應用的時候可能只有一個線程,然后就有一個任務生成其他的線程。但是即使那樣也是一個不太可能發生的方案。線程經常花時間等待彼此或者等待I/O操作完成

除非每次線程等待事情(無論是什么事情)的時候都有另一個線程在處理器上代替它,否則就有一個可以進行有用工作的處理器處于閑置狀態

一種簡單的方法就是將程序劃分為只有一個線程在做有用的工作"串行的"部分和所有可以獲得的處理器都在做有用工作的"并行的"部分。如果你在有更多處理器的系統上運行你的應用,理論上就可以更快地完成"并行"部分,因為可以在更多的處理器間劃分工作,但是"串行的"部分仍然是串行的。在這樣一種簡單假設下,你可以通過增加處理器數量來估計可以獲得的性能。如果“連續的"部分組成程序的一個部分fs,那么使用N個處理器獲得的性能P就可以估計為

這就是阿姆達爾定律(Amdahl'slaw ) ,當談論并發代碼性能的時候經常被引用。如果所有事情都能被并行,那么串行部分就為0,加速就是N,或者,如果串行部分是三分之一,即使有無限多的處理器,你也不會得到超過3的加速

盡管如此,這是一種很理想的情況。因為任務很少可以像方程式所需要的那樣被無窮劃分,并且所有事情都達到它所假設的CPU界限是很少出現的。正如你看到的,線程執行的時候會等待很多事情。

阿姆達爾定律中有一點是明確的,那就是當你為性能使用并發的時候,值得考慮總體應用的設計來最大化并發的可能性,并且確保處理器始終有有用的工作來完成。如果你可以減少“串行”部分或者減少線程等待的可能性,你就可以提高在有更多處理器的系統上的性能。或者,如果你可以為系統提供更多的數據,并且保持并行部分準備工作,就可以減少串行部分,增加性能P的值。

從根本上說,可擴展性就是當增加更多的處理器的時候,可以減少它執行操作的時間或者增加在一段時間內處理的數據數量。有時這兩點是相同的(如果每個元素可以處理得更快,那么你就可以處理更多數據) ,但是并不總是一樣的。在選擇在線程間劃分工作的方法之前,識別出可擴展性的哪些方面對你很重要是很必要的。

在這部分的開始我就提到過線程并不是總有有用的工作來做。有時它們必須等待別的線程,或者等待I/O操作完成,或者別的事情。如果在等待中你給系統一些有用的事情,你就可以有效的"隱藏等待。

8.4.3用多線程隱藏遲

在很多關于多線程代碼性能的討論中,我們都假設當它們真正在處理器上運行時,線程在"全力以赴的運行并且總是有有用的工作來做。這當然不是正確的,在應用代碼中,線程在等待的時候總是頻繁地被阻塞。例如,它們可能在等待一些I/O操作的完成,等待獲得互斥元,等待另一個線程完成一些操作并且通知一個條件變量,或者只是休眠一段時間。

無論等待的原因是什么,如果你只有和系統中物理處理單元一樣多的線程,那么有阻塞的線程就意味著你在浪費CPU時間。運行一個被阻塞的線程的處理器不做任何事情。因此,如果你知道一個線程將會有相當一部分時間在等待,那么你就可以通過運行一個或多個附加線程來使用那個空閑的CPU時間。

考慮一個病毒掃描應用,它使用管道在線程間劃分工作。第一個線程搜索文件系統來檢查文件并且將它們放到隊列中。同時,另一個線程獲得隊列中的文件名,載入文件,并且掃描它們的病毒。你知道搜索文件系統的文件來掃描的線程肯定會達到I/O界限,因此你就可以通過運行一個附加的掃描線程來使用“空閑的"CPU時間。那么你就有一個搜索文件線程,以及與系統中的物理核或者處理器相同數量的掃描線程。因為掃描線程可能也不得不從磁盤讀取文件的重要部分來掃描它們,擁有更多掃描線程也是很有意義的。但是在某個時刻會有太多線程,系統會再次慢下來因為它花了更多時間切換程序,正如8.2.5節所描述的。

仍然,這是一個最優化問題,因此測量線程數量改變前后的性能時很重要的;最有的線程數量將很大程度上取決于工作的性質和線程等待的時間所占的比例。

取決于應用,它也可能用完空閑的CPU時間而沒有運行附加的線程。例如,如果一個線程因為等待I/O操作的完成而被阻塞,那么使用可獲得的異步I/O操作就很有意義了。那么當在背后執行I/O操作的時候,線程就可以執行別的有用的工作了。在別的情況下,如果一個線程在等待另一個線程執行一個操作,那么等待的線程就可以自己執行那個操作而不是被阻塞,正如第7章中的無鎖隊列。在一個極端的情況下,如果線程等待完成一個任務并且該任務沒有被其他線程執行,等待的線程可以在它內部或者另一個未完成的任務中執行這個任務。清單8.1中你看到了這個例子,在排序程序中只要它需要的塊沒有排好序就不停地排序它。

有時它增加線程來確保外部事件及時被處理來增加系統響應性,而不是增加線程來確保所有可得到的處理器都被應用了。

8.4.4 用并發提高響應性

很多現代圖形用戶接口框架是事件驅動的,使用者通過鍵盤輸入或者移動鼠標在用戶接口上執行操作,這會產生一系列的事件或者消息,稍后應用就會處理它。系統自己也會產生消息或者事件。為了確保所有事件和消息都能被正確處理,通常應用都有下面所示的一個事件循環。

顯然, API的細節是不同的,但是結構通常是一樣的,等待一個事件,做需要的操作來處理它,然后等待下一個事件。如果你有單線程應用,就會導致長時間運行的任務很難被寫入,如8.1.3節描述的。為了確保用戶輸入能被及時處理, get_event()和process()必須以合理的頻率被調用,無論應用在做什么操作。這就意味著要么任務必須定期暫停并且將控制交給事件循環,要么方便的時候在代碼中調用get_event()/

process()代碼。每一種選擇都將任務的實現變得復雜了。

通過用并發分離關注點,你就可以將長任務在一個新線程上執行,并且用一個專用的GUI線程來處理事件。線程可以通過簡單的方法互相訪問,而不是必須以某種方式將事件處理代碼放到任務代碼中。清單8.6列出了這種分離的簡單概括。

清單8.6從任務線程中分離GUI線程

通過這種方式分離障礙,用戶線程能夠及時地響應事件,即使任務要執行很長時間。這種響應性通常是使用應用時用戶體驗的關鍵。無論何時執行一個特定操作(無論該操作是什么) ,應用都會被完全鎖住,這樣使用起來就不方便了。通過提供一個專用的事件處理線程, GUI可以處理GUI特有的消息(例如調整窗口大小或者重畫窗口)而不會中斷耗時處理的執行,并且當它們確實影響長任務時會傳遞相關的消息。

到此，相信大家對“C++怎么為多線程性能設計數據結構”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！