Silverlight 的多線程能力（下）

來源: infoq 發布時間: 2011-03-25 10:08 閱讀: 3123 次推薦: 0 原文鏈接 [收藏]

　　上一期筆者介紹了Silverlight實現多線程的諸多解決方案，本期筆者將通過一個實例來實現所有多線程編程方法，并且還將于JavaScript和Flash兩種Web客戶端技術性能進行比較，請勿拍磚。

　　在正式編程前，筆者還要重申上期非常重要的觀點：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的兩個算法類：

該類主要負責對并行算法的支持，其中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。

該類用于驗證多線程下試除法查找的結果是否正確，其中主要函數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])
　　{
　　　　_primeCount++;
　　　　_maxPrime = i;
　　}

　　//通知完成查找
　　InvokeFindComplete(EventArgs.Empty);
}

試除類PrimeFinder
埃拉托斯特尼篩法類EratosthenesFinder

　　在主頁面上，筆者創建了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();
　　　　break;
　　　　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();// 計時器, 初始化.
　　var _maxPrime;
　　var _primeCount = 0;
　　for (var i = 1; i <= _maxNumber; i += 2)
　　{
　　　　if (IsPrime(i))
　　　　{
　　　　　　_primeCount++;
　　　　　　_maxPrime = 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;
　　　　}
　　}
　　return true;
}

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