測試多線程對多核cpu的分支預測的影響

前言：

現代的cpu都有流水線，分支預測功能，CPU的分支預測準确性可以達到98%以上，但是如果預測失敗，則流水線失效，性能損失很嚴重。

CPU使用的分支預測技術可以參考：

處理器分支預測研究的曆史和現狀.pdf 同時多線程處理器上的動态分支預測器設計方案研究.pdf

正确地利用這些特性，可以寫出高效的程式。

比如在寫if，else語句時，應當把大機率事件放到if語句中，把小機率事件放到else語句中。

但是通常這種考慮都是基于單線程的，在多線程下有可能出現意外情況，比如多個線程同時執行同一處的代碼。

測試：

下面基于Intel Core i5的一些多線程分支預測的測試。

測試思路（真實測試時發現不止以下三種情況，詳細見下面的測試結果）：

兩個線程執行同一處代碼，而if判斷總為true。

兩個線程執行同一處代碼，一個的if判斷總為true，另一個的if判斷時為true，時為false。

兩個線程執行不同的代碼（邏輯功能一樣，隻是位置不同），一個的if判斷總為true，另一個的if判斷時為true，時為false。

代碼如下：

其中test1測試的是同一處代碼，當傳入偶數參數時，則if判斷總為true，當傳入奇數參數時，if判斷時為true時為false。

test2函數測試的是不同一處的代碼，當傳入偶數參數時，則if判斷總為true，當傳入奇數參數時，if判斷時為true時為false。

import java.util.concurrent.CountDownLatch;
public class Test {
	public static int loop = 1000000000;
	public static int sum = 0;
	public static CountDownLatch startGate;
	public static CountDownLatch endGate;
	
	public static void test1(int x1, int x2) throws InterruptedException{
		startGate = new CountDownLatch(1);
		endGate = new CountDownLatch(2);
		new Thread(new T1(x1)).start();
		new Thread(new T1(x2)).start();
		Test.startGate.countDown();
		Test.endGate.await();
	}
	public static void test2(int x1, int x2) throws InterruptedException{
		startGate = new CountDownLatch(1);
		endGate = new CountDownLatch(2);
		new Thread(new T1(x1)).start();
		new Thread(new T2(x2)).start();
		Test.startGate.countDown();
		Test.endGate.await();
	}
}

class T1 implements Runnable{
	int xxx = 0;
	public T1(int xxx){
		this.xxx = xxx;
	}
	@Override
	public void run() {
		try {
			int sum = 0;
			int temp = 0;
			Test.startGate.await();
			long start = System.nanoTime();
			for(int i = 0; i < Test.loop; ++i){
				temp += xxx;
				if(temp % 2 == 0){
					sum += 100;
				}else{
					sum += 200;
				}
			}
			Test.sum += sum;
			long end = System.nanoTime();
			System.out.format("%s, T1(%d): %d\n", Thread.currentThread().getName(), xxx, end - start);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}finally{
			Test.endGate.countDown();
		}
	}
}
class T2 implements Runnable{
	int xxx = 0;
	public T2(int xxx){
		this.xxx = xxx;
	}
	@Override
	public void run() {
		try {
			int sum = 0;
			int temp = 0;
			Test.startGate.await();
			long start = System.nanoTime();
			for(int i = 0; i < Test.loop; ++i){
				temp += xxx;
				if(temp % 2 == 0){
					sum += 100;
				}else{
					sum += 200;
				}
			}
			Test.sum += sum;
			long end = System.nanoTime();
			System.out.format("%s, T2(%d): %d\n", Thread.currentThread().getName(), xxx, end - start);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}finally{
			Test.endGate.countDown();
		}
	}
}           

因為測試的情況多種，簡潔表述如下：

一個test1函數會有兩個結果，如test1(2, 3)得到兩個結果2.1s，2.2s，表示兩個線程執行同一份代碼，一個的if判斷總是true（2是偶數），另一個的總是false（3是奇數），其中第一個線程平均執行一次計算的時間是2.1s，第二個線程平均執行一次計算的時間是2.2s。

測試的main函數中有兩個for循環，每個10次。在表述測試結果時，用簡略表示，如：

一行資料表示執行一次main函數的結果，後面的時間是粗略平均計算得到的

test1(2,3)

2.1s

test1(2,4)

main函數：

public static void main(String[] args) throws InterruptedException {
		for(int i = 0; i < 10; ++i){
			test1(2, 3);
		}
		System.out.println("!!!!!!!!!!!!!!!!!!!!");
		for(int i = 0; i < 10; ++i){
			test1(2, 4);
		}		
	}           

測試結果如下：

1		2.0s			1.8s
2		1.3s
3
4	test2(2,3)		1.7s	test2(2,4)		1.9s
5

先來分析第1行資料，test1(2,3)的結果是最壞的，顯然這是因為兩個線程執行同一份代碼，且兩者的分支預測結果互相幹擾，導緻總是不準。

但是為什麼後面的test1(2,4)的結果也是比較差？盡管兩個線程執行的是同一份代碼，但是兩個線程中if的判斷都總是true，為什麼會出現耗時比較多的情況？

簡單推測1：可能是之前的test1(2,3)影響了test1(2,4)的分支預測的結果，分支預測器中有曆史表，前面執行的分支預測曆史會影響後面的選擇。

再來分析第2行，顯然test1(2,4)是最好的結果，兩個線程執行同一份代碼，且if總是為true。再看第2行的test(2,3)結果，比第1行的要好，為什麼這個和第1行的資料差這麼多？

簡單推測2：應該是不同的核有自己的分支預測器。

再來看test2函數的測試結果，從第4行來看，test2(2,3)的結果符合預期，但是顯然test2(2,4)的結果不理想，為什麼兩個線程執行不同地方的代碼，if判斷總是true，結果會不同？

簡單推測3：受test(2,3)的結果的影響，結合簡單推測1和2，就可以了解為什麼test(2,4)的前一個結果是1.3s，後一個是1.9s了。

再來分析第5行資料，這行資料完全符合預期。

總結：

推測：i5的分支預測器是一個混合的分支預測器。每個核都有曆史表，每一個核都有自己的分支預測器。

多線程下的分支預測并不是很樂觀，如果可以避開多個線程執行同一份代碼，且分支預測條件的結果總是變化，則盡量避開。