Java Fork Join 架構（四）性能4性能

如今，随着編譯器與java虛拟機性能的不斷提升，性能測試結果也僅僅隻能适用一時。但是，本節中所提到的測試結果資料卻能揭示fork/join架構的基本特性。

下面表格中簡單介紹了在下文将會用到的一組fork/join測試程式。這些程式是從util.concurrent包裡的示例代碼改編而來，用來展示fork/join架構在解決不同類型的問題模型時所表現的差異，同時得到該架構在一些常見的并行測試程式上的測試結果。

程式（program）

描述（description）

fib（菲波那契數列）

如第2節所描述的fibonnaci程式，其中參數值為47閥值為13

integrate（求積分）

使用遞歸高斯求積對公式**求-47到48的積分，i為1到5之間的偶數。

micro

對一種棋盤遊戲尋找最好的移動政策，每次計算出後面四次移動。

sort（排序）

使用合并/快速排序算法對1億數字進行排序（基于cilk算法）

mm(矩陣相乘)

2048*2048的double類型的矩陣進行相乘

lu（矩陣分解）

4096*4096的double類型的矩陣進行分解

jacobi（雅克比疊代法）

對一個4096*4096的double矩陣使用疊代方法進行矩陣松弛，疊代次數上限為100。

下文提到的主要的測試，其測試程式都是運作在sun enterprise 10000伺服器上，該伺服器擁有30個cpu，作業系統為solaris7系統，運作solaris商業版1.2 jvm（2.2.2_05釋出版本的一個早期版本）。同時，java虛拟機的關于線程映射的環境參數選擇為“bound threads”(譯者注：xx:+useboundthreads，綁定使用者級别的線程到核心線程，隻與solaris有關)，而關于虛拟機的記憶體參數設定在4.2章節讨論。另外，需要注意的是下文提到的部分測試則是運作在擁有4cpu的sun enterprise450伺服器上。

為了降低定時器粒度以及java虛拟機啟動因素對測試結果的影響，測試程式都使用了數量巨大的輸入參數。而其它一些啟動因素我們通過在啟動定時器之前先運作初始化任務來進行屏蔽。所得到的測試結果資料，大部分都是在三次測試結果的中間值，然而一些測試資料僅僅來自一次運作結果（包括4.2~4.4章節很多測試），是以這些測試結果會有噪音表現。

通過使用不同數目（1~30）的工作線程對同一問題集進行測試，用來得到架構的擴充性測試結果。雖然我們無法保證java虛拟機是否總是能夠将每一個線程映射到不同的空閑cpu上，同時，我們也沒有證據來證明這點。有可能映射一個新的線程到cpu的延遲會随着線程數目的增加而變大，也可能會随不同的系統以及不同的測試程式而變化。但是，所得到的測試結果的确顯示出增加線程的數目确實能夠增加使用的cpu的數目。

加速比通常表示為“time n/time1”.如上圖所示，其中求積分的程式表現出最好的加速比（30個線程的加速比為28.2），表現最差的是矩陣分解程式（30線程是加速比隻有15.35）

另一種衡量擴充性的依據是：任務執行率，及執行一個單獨任務（這裡的任務有可能是遞歸分解節點任務也可能是根節點任務）所開銷的平均時間。下面的資料顯示出一次性執行各個程式所得到的任務執行率資料。很明顯，機關時間内執行的任務數目應該是固定常量。然而事實上，随着線程數目增加，所得到的資料會表現出輕微的降低，這也表現出其一定的擴充性限制。這裡需要說明的是，之是以任務執行率在各個程式上表現的巨大差異，是因其任務粒度的不同造成的。任務執行率最小的程式是fib（菲波那契數列），其閥值設定為13，在30個線程的情況下總共完成了280萬個單元任務。

導緻這些程式的任務完成率沒有表現為水準直線的因素有四個。其中三個對所有的并發架構來說都是普遍原因，是以，我們就從對fjtask架構（相對于cilk等架構）所特有的因素說起，即垃圾回收。

總的來說，現在的垃圾回收機制的性能是能夠與fork/join架構所比對的：fork/join程式在運作時會産生巨大數量的任務單元，然而這些任務在被執行之後又會很快轉變為記憶體垃圾。相比較于順序執行的單線程程式，在任何時候，其對應的fork/join程式需要最多p倍的記憶體空間（其中p為線程數目）。基于分代的半空間拷貝垃圾回收器（也就是本文中測試程式所使用的java虛拟機所應用的垃圾回收器）能夠很好的處理這種情況，因為這種垃圾回收機制在進行記憶體回收的時候僅僅拷貝非垃圾記憶體單元。這樣做，就避免了在手工并發記憶體管理上的一個複雜的問題，即跟蹤那些被一個線程配置設定卻在另一個線程中使用的記憶體單元。這種垃圾回收機制并不需要知道記憶體配置設定的源頭，是以也就無需處理這個棘手的問題。

這種垃圾回收機制優勢的一個典型展現：使用這種垃圾回收機制，四個線程運作的fib程式耗時僅為5.1秒鐘，而如果在java虛拟機設定關閉代拷貝回收（這種情況下使用的就是标記–清除垃圾回收機制了），耗時需要9.1秒鐘。

然而，隻有記憶體使用率隻有達到一個很高的值的情況下，垃圾回收機制才會成為影響擴充性的一個因素，因為這種情況下，虛拟機必須經常停止其他線程來進行垃圾回收。以下的資料顯示出在三種不同的記憶體設定下（java虛拟機支援通過額外的參數來設定記憶體參數），加速比所表現出的差異：預設的4m的半空間，64m的半空間，另外根據線程數目按照公式（2+2p）m設定半空間。使用較小的半空間，在額外線程導緻垃圾回收率攀高的情況下，停止其他線程并進行垃圾回收的開銷開始影響加封。

鑒于上面的結果，我們使用64m的半空間作為其他測試的運作标準。其實設定記憶體大小的一個更好的政策就是根據每次測試的實際線程數目來确定。（正如上面的測試資料，我們發現這種情況下，加速比會表現的更為平滑）。相對的另一方面，程式所設定的任務粒度的閥值也應該随着線程數目成比例的增長。

在上文提到的測試程式中，有四個程式會建立并操作數量巨大的共享數組和矩陣：數字排序，矩陣相乘/分解以及松弛。其中，排序算法應該是對資料移動操作（将記憶體資料移動到cpu緩存）以及系統總記憶體帶寬，最為敏感的。為了确定這些影響因素的性質，我們将排序算法sort改寫為四個版本，分别對byte位元組資料，short型資料，int型資料以及long型資料進行排序。這些程式所操作的資料都在0~255之間，以確定這些對比測試之間的平等性。理論上，操作資料的字寬越大，記憶體操作壓力也相應越大。

測試結果顯示，記憶體操作壓力的增加會導緻加速比的降低，雖然我們無法提供明确的證據來證明這是引起這種表現的唯一原因。但資料的字寬的确是影響程式的性能的。比如，使用一個線程，排序位元組byte資料需要耗時122.5秒，然而排序long資料則需要耗時242.5秒。

正如3.2章節所讨論的，任務竊取模型經常會在處理任務的同步上遇到問題，如果工作線程擷取任務的時候，但相應的隊列已經沒有任務可供擷取，這樣就會産生競争。在fjtask架構中，這種情況有時會導緻線程強制睡眠。

從jacobi程式中我們可以看到這類問題。jacobi程式運作100步，每一步的操作，相應矩陣點周圍的單元都會進行重新整理。程式中有一個全局的屏障分隔。為了明确這種同步操作的影響大小。我們在一個程式中每10步操作進行一次同步。如圖中表現出的擴充性的差異說明了這種并發政策的影響。也暗示着我們在這個架構後續的版本中應該增加額外的方法以供程式員來重寫，以調整架構在不同的場景中達到最大的效率。（注意，這種圖可能對同步因素的影響略有誇大，因為10步同步的版本很可能需要管理更多的任務局部性）

fjtask，或者說其他的fork/join架構在任務配置設定上都是做了優化的，盡可能多的使工作線程處理自己分解産生的任務。因為如果不這樣做，程式的性能會受到影響，原因有二：

從其他隊列竊取任務的開銷要比在自己隊列執行pop操作的開銷大。

在大多數程式中，任務操作操作的是一個共享的資料單元，如果隻運作自己部分的任務可以獲得更好的局部資料通路。

如上圖所示，在大多數程式中，竊取任務的相對資料都最多元持在很低的百分比。然後其中lu和mm程式随着線程數目的增加，會在工作負載上産生更大的不平衡性（相對的産生了更多的任務竊取）。通過調整算法我們可以降低這種影響以獲得更好的加速比。

與其他不同語言的架構相比較，不太可能會得到什麼明确的或者說有意義的比較結果。但是，通過這種方法，最起碼可以知道fjtask在與其他語言（這裡主要指的是c和c++）所編寫的相近架構比較所表現的優勢和限制。下面這個表格展示了幾種相似架構（cilk,hood ,stackthreads,以及filaments）所測試的性能資料。涉及到的測試都是在4cpu的sun enterprise450伺服器運作4個線程進行的。為了避免在不同的架構或者程式上進行重新配置，所有的測試程式運作的問題集都比上面的測試稍小些。得到的資料也是取三次測試中的最優值，以確定編譯器或者說是運作時配置都提供了最好的性能。其中fib程式沒有指定任務粒度的閥值，也就是說預設的1.（這個設定在filaments版的fib程式中設定為1024，這樣程式會表現的和其它版本更為一緻）。

在加速比的測試中，不同架構在不同程式上所得到的測試結果非常接近，線程數目1~4，加速比表現在（3.0~4.0之間）。是以下圖也就隻聚焦在不同架構表現的不同的絕對性能上，然而因為在多線程方面，所有的架構都是非常快的，大多數的差異更多的是有代碼本身的品質，編譯器的不同，優化配置項或者設定參數造成的。實際應用中，根據實際需要選擇不同的架構以彌補不同架構之間表現的巨大差異。

fjtask在處理浮點數組和矩陣的計算上性能表現的比較差。即使java虛拟機性能不斷的提升，但是相比于那些c和c++語言所使用的強大的後端優化器，其競争力還是不夠的。雖然在上面的圖表中沒有顯示，但fjtask版本的所有程式都要比那些沒有進行編譯優化的架構還是運作的快的。以及一些非正式的測試也表明，測試所得的大多數差異都是由于數組邊界檢查，運作時義務造成的。這也是java虛拟機以及編譯器開發者一直以來關注并持續解決的問題。

相比較，計算敏感型程式因為編碼品質所引起的性能差異卻是很少的。