上一期笔者介绍了 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 的两个算法类:
- 试除类 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]) { _primeCount++; _maxPrime = i; } // 通知完成查找 InvokeFindComplete(EventArgs.Empty); }
在主页面上,笔者创建了 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 …… } }
dt_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 上的运行结果如下图:
其中 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
(注:以上性能对比仅供参考)
本期示例地址: http://space.silverlightchina.net/xpeter/Demo/xPrime.html
源代码地址: http://space.silverlightchina.net/xpeter/Demo/Code/xPrime.rar
通过本期对 Silverlight 的多线程能力分析,想必大家对 Silverlight 的多线程编程有了大概了解。笔者认为对于 RIA 应用而言为用户提供无等待的响应速度比更多的功能显得更为重要!
评论