一起談.NET技術，Silverlight 的多線程能力（下）

　　在正式程式設計前，筆者還要重申上期非常重要的觀點：Silverlight多線程主要作用不是在于提高性能，而是在于使用者體驗。這裡要給多線程潑一盆冷水了，多線程與性能提升不是正比關系，如果你使用一個單核CPU的用戶端裝置，那麼即便你建立100個多線程也與單線程的計算性能是一樣的，因為一個CPU時間片下隻能處理一個線程，多線程也必須串行處理，甚至還可能因為過多的CPU排程開銷而導緻性能不及單線程的情況。當然在多核的情況下多線程可以負載到多個CPU上并行執行而提升性能，經過筆者在項目實施前的技術研究中發現如果用戶端有N核的情況下，Silverlight多線程可以被N個CPU時間片平分，而CLR将同時讓N+1個線程處于Ready狀态，經過反複測試多線程性能是單線程的近N倍。其實用戶端已經呈現多核趨勢，就在不久前釋出了PSP的下一代産品NGP采用ARM 4核處理器，而iPad2采用A5雙核處理器，而我們現在用的筆記本與桌上型電腦基本都是超過2核的處理器，是以多線程的計算能力還是很有前景的。

　　下面我們就一起來看看執行個體，這個執行個體筆者選擇了比較容易懂的素數計數函數（Prime-counting function）作為執行個體，用數學專業術語來說就是π(x)，有沒有搞錯怎麼和圓周率有關？這裡不是圓周率而是π函數，是一個用來表示小于或等于某個實數x的素數的個數的函數。比如π(10)=4，因為不大于10的素數有2,3,5,7共計4個。對于π(x)的确定性算法筆者準備了兩種：

試除法

具體方法是從3開始對所有不大于x的奇數進行素數判斷。當判斷i是否為素數時，通過從3開始到i的平方根（i=m*n中必然有一個因子小于i的平方根）的所有奇數進行試除，如果i能被整除則i不是素數，否則i是素數。該算法最易了解，而且可以并行試除，并行試除法的思路是按照2k*m+n的同餘類進行分組，如果有k個并行組，那麼對于從3開始對所有不大于x的奇數可以用{2k*m+1,2k*m+3,…,2k*m+2k-1}共k個同餘組來分别進行試除，最後π(x)等于所有分組素數求和。

埃拉托斯特尼篩法

埃拉托斯特尼篩法，簡稱埃氏篩或愛氏篩，是一種由古希臘數學家埃拉托斯特尼所提出的一種簡單檢定素數的算法，該算法的思路從第一個素數開始，按照素數的倍數都是合數的思路，全部篩去，然後再篩去第二個素數的倍數，一直到目前素數大于x的平方根時結束，所得到沒有篩去的數都是素數。該算法是已知确定性算法中時間複雜度最低的算法，但缺點是不能并行（至少筆者目前還沒有找到并行篩法，如果你找到了請與筆者聯系）。

　　在本案例中筆者使用試除法進行多線程計算，并通過篩法來校驗計算的正确性。下面我們首先實作Silverlight的兩個算法類：

試除類PrimeFinder

該類主要負責對并行算法的支援，其中MaxPrime屬性用來記錄最大素數，PrimeCount屬性記錄素數個數，Stat屬性的類型為枚舉類WorkerStat { Init, Working, Worked }，用以監視線程的工作狀态。OnFindComplete事件用于通知UI線程查找完成。其中主要函數實作如下：

publicvoid FindPrime()

{

　　_primeCount = 0;

　　_stat = WorkerStat.Working;

for (uint i = _startNum; i <= _maxNam; i += _step)

　　if (IsPrime(i))

　　{

　　　　_primeCount++;

　　　　_maxPrime = i;

　　}

}

　　_stat = WorkerStat.Worked;

　　//通知完成查找

　　InvokeFindComplete(EventArgs.Empty);

privatebool IsPrime(uint x)

　　if (x == 1u) returnfalse;

　　uint sqrtx = (uint)(Math.Sqrt(x));

　　for (uint i = 3u; i <= sqrtx; i += 2u)

　　　　if (x % i == 0) returnfalse;

　　return true;

其中FindPrime方法用于查找記錄素數，查找起始點從_startNum開始，步進為_step。而IsPrime方法用于判斷是否是素數，周遊從3開始到x的平方根的所有奇數能否整除x。

埃拉托斯特尼篩法類EratosthenesFinder

該類用于驗證多線程下試除法查找的結果是否正确，其中主要函數FindPrime實作如下：

publicvoid FindPrime(uint MaxNumber)

_primeCount = 1;

bool[] Numbers = newbool[MaxNumber];

uint SqrtMaxNumber = (uint)(Math.Sqrt(MaxNumber -= 1u));

for (uint i = 1u; i < SqrtMaxNumber; )

　　　　while (Numbers[i += 2u]) ;

　　　　for (uint k = ((uint)(MaxNumber / i) + 1u) | 1u; k > i; )

　　　　{

　　　　　　while (Numbers[k -= 2u]) ;

　　　　　　Numbers[k * i] = true;

　　　　}

　　for (uint i = 3u; i < MaxNumber; i += 2u)

　　if (!Numbers[i])

　　在首頁面上，筆者建立了6個按鈕執行不同的調用方式：

背景單線程執行Eratosthenes篩法進行驗證

在UI線程直接查找

在背景單線程查找

基于ThreadPool的背景多線程查找

基于BackgroundWorker的背景多線程查找

基于Thread的背景多線程查找

　　而對于DispatchTimer類，筆者将其作為定時器用于對背景線程狀态的監控。具體方法如下：

　　在首頁面中加入定時器屬性dt，并在頁面加載事件中定義定時器時歇與Tick事件：

DispatcherTimer dt = newDispatcherTimer();

void MainPage_Loaded(object sender, RoutedEventArgs e)

　　……

　　dt.Interval = newTimeSpan(0, 0, 0, 0, 10);

　　dt.Tick += newEventHandler(dt_Tick);

void dt_Tick(object sender, EventArgs e)

　　tbTimer.Text = (Environment.TickCount - StartTickCount).ToString();

　　switch (CurrFinder)

　　　　caseUseFinder.EratosthenesFinder:

　　　　tbPrimeCount.Text = (efinder.PrimeCount).ToString();

　　　　break;

　　　　caseUseFinder.SinglePrimeFinder:

　　　　tbPrimeCount.Text = (singlefinder.PrimeCount + 1).ToString();

　　　　caseUseFinder.MultiPrimeFinder:

　　　　tbPrimeCount.Text = (multifinder.Sum(t => t.PrimeCount) + 1).ToString();

　　　　tbIdleThread.Text = multifinder.Count(t => t.Stat == WorkerStat.Init).ToString();//閑置線程數

　　　　tbWorkingThread.Text = multifinder.Count(t => t.Stat == WorkerStat.Working).ToString();//工作線程數

　　　　tbWorkedThread.Text = multifinder.Count(t => t.Stat == WorkerStat.Worked).ToString();//完成線程數

　　　　break

　　　　……

　　t_Tick事件定義了單線程與多線程下對查找過程和多線程工作狀态的顯示。而在所有查找方法調用前觸發dt.Start()事件開始監控；在完成查找時，調用dt.Stop()事件停止監控。

　　下面鑒于篇幅所限，我主要介紹基于ThreadPool的背景多線程查找的實作方式：

privatevoid btnMultiWorker_Click(object sender, System.Windows.RoutedEventArgs e)

　　//設定目前查找器

　　CurrFinder = UseFinder.MultiPrimeFinder;

　　gdMultiThreadInfo.Visibility = Visibility.Visible;

　　multifinder.Clear();

　　CallBackThreadCount = 0;

　　StartTickCount = Environment.TickCount;

　　dt.Start();

　　//構造多線程查找器

　　for (uint i = 0; i < ThreadCount; i++)

　　　　//對餘2i+1的同餘類進行查找，步進為兩倍線程數

　　　　PrimeFinder afinder = newPrimeFinder(2 * i + 1, MaxNum, 2 * ThreadCount);

　　　　afinder.OnFindComplete += (s1, e1) => Dispatcher.BeginInvoke(multifinder_OnFindComplete);

　　　　multifinder.Add(afinder);

　　　　ThreadPool.QueueUserWorkItem(state => afinder.FindPrime(), i);

void multifinder_OnFindComplete()

　　CallBackThreadCount++;

　　//當全部完成時顯示結果

　　if (CallBackThreadCount == ThreadCount)

　　　　dt.Stop();

　　　　tbLog.Text += string.Format("背景多線程試除法找到{0}内的素數共{1}個，最大素數為{2}，耗時{3}毫秒(基于ThreadPool)\n", MaxNum, multifinder.Sum(t => t.PrimeCount) + 1, multifinder.Max(t => t.MaxPrime), Environment.TickCount - StartTickCount);

　　以上代碼中gdMultiThreadInfo是顯示多線程資訊的Grid。而multifinder為查找器背景運作執行個體的集合，通過該集合可以彙總資料，比如通過multifinder.Max(t => t.MaxPrime)就可以找到最大素數。在建構多線程查找器時，我們按照使用者輸入的線程數ThreadCount 來建構同等個數的同餘類，由于偶數不用查找，是以我們的步進可以是兩倍于ThreadCount，這樣同餘類的餘數剛好是2i+1（其中i從0到ThreadCount-1），讓每個查找線程司職不同的同餘類。這裡我們通過ThreadPool線程池來加載每個背景線程，并将每個背景線程執行個體的OnFindComplete事件通過該UI執行個體的Dispatcher分發器屬性的BeginInvoke方法委托給UI線程中的multifinder_OnFindComplete事件來完成。在完成的回調事件中如果全部數量的背景線程都完成就進行結果顯示，其中multifinder.Sum(t => t.PrimeCount) + 1的原因是在試除法中沒有考慮2這個素數。

　　其他5種方式的實作不再贅述。現在我們開始實測，筆者在一台8核的PC機上進行了400萬以内素數查找，結果如下：

　　這裡筆者設定了8線程同時測算，其多線程效率為單線程的7.5倍（接近8倍）。當設定線程數為16時，結果幾乎保持不變，也就是說當多線程數量大于CPU核數時多線程也存在等待CPU時間片去排程的問題，而不能全部并行。經過測試工作線程數等于核數+1，在8核的PC上運作情況如下圖所示：

　　最後的結論是多線程最多能提升CPU核數倍，是以背景線程數剛好等于CPU核數時效率最優。到這裡筆者還不想結束本期話題，因為大家對Silverlight的性能還沒有一個橫向對比。是以，筆者分别在JavaScript（IE9）和Flash CS5中完成了同樣試除法的開發。

　　JavaScript代碼如下：

<scripttype="text/javascript">

function IsPrime(x) {

if (x == 1) returnfalse;

var sqrtx = Math.sqrt(x);

for (var i = 3; i <= sqrtx; i += 2) {

if (x % i == 0) returnfalse;

return true;

function FindPrime() {

var _maxNumber = this.tbMaxNum.value;

if (/^\d+$/.test(_maxNumber)) // 驗證輸入是否是整數

　　var startwatch = new Date(); // 計時器初始化

　　var _maxPrime;

　　var _primeCount = 0;

　　for (var i = 1; i <= _maxNumber; i += 2)

　　　　if (IsPrime(i)) {

　　　　　　_primeCount++;

　　　　　　_maxPrime = i;

　　var t = new Date() - startwatch;

　　　　tbLog.value += "JavaScript試除法找到" + _maxNumber + "内的素數共" + _primeCount + "個，最大素數為" + _maxPrime + "，耗時" + t + "毫秒\n"

　　}else{

　　　　alert("輸入的不是整數！");

</script>

　　FlashCS5 ActionScript代碼如下：

stop();

btnFind.useHandCursor = true;

btnFind.addEventListener(MouseEvent.CLICK, clickHandler);

function clickHandler(event:MouseEvent):void {FindPrime();}

function FindPrime():void

　　var _maxNumber = nsMaxNum.value;

　　var startwatch = new Date();// 計時器, 初始化.

　　　　if (IsPrime(i))

　　var t:Number = Number(int(new Date()) - int(startwatch));

　　taLog.text += "ActionScript試除法找到" + _maxNumber + "内的素數共" + _primeCount + "個，最大素數為" + _maxPrime + "，耗時" + t + "毫秒\n";

function IsPrime(x)

　　if (x == 1)return false;

　　var sqrtx = Math.sqrt(x);

　　for (var i = 3; i <= sqrtx; i+=2)

　　　　if (x % i == 0)

　　　　　　return false;

　　兩種語言在同一台PC上的運作結果如下圖：

　　其中JavaScript在IE9中查找400萬以内素數耗時3800毫秒，Flash CS5耗時35715毫秒，在同樣算法、同一浏覽器下三者性能對比如下表：

Silverlight多線程（8核8線程）

Silverlight單線程

JavaScript

Flash CS5

耗時（毫秒）

266

2016

3800

35715

性能比（倍）

134.8

17.7

9.4

1

　　（注：以上性能對比僅供參考）

　　通過本期對Silverlight的多線程能力分析，想必大家對Silverlight的多線程程式設計有了大概了解。筆者認為對于RIA應用而言為使用者提供無等待的響應速度比更多的功能顯得更為重要！