Cameron Laird 提供了一些有用的示例,这些示例对于很有可能在您自己的应用程序开发中发生的各种性能问题而言,是很合适的模型。
性能突破似乎有两种不同的实现方式:简单的和困难的。这并非陈词滥调;这两者之间的界限极其清楚。
当您听说了某些简单的方式时,您拍手叹道:“噢”、“对极了”或“太棒了”。虽然在许多情况下实现这些方式的第一个应用需要相当聪明的头脑,但是它们易于理解。
另一种方式涉及了仔细的测量、专门的知识和大量的调优工作。这些过程通常是令人痛苦的,也是值得的,要视“本地条件”(比如硬件的具体情况)而定。
优秀的程序员可以用“困难”或“简单”方式进行工作。由于性能对 linux 程序员而言是非常重要的主题,因此我提供了四个来源于实际(编程)生活中的故事,它们按“困难”和“简单”方式配成两对。
始终从需求入手
死亡和交税都是不可避免的。对于开发人员而言,与此差不多同等重要的是仔细考虑需求;这是每种编程都会提到的一个主题。
尽管性能的确很重要,但是处理这种需求的最佳方法往往并不是显而易见的。我经常会碰到一个软件难题,它大致符合这样的模式:程序正处于使用之中。它的功能是正确的。但是某个用户使用了一下,然后报告说它“太慢了”,需要加速。某团队成员很快添加了“监视器”,这降低一点性能,但是使用户能一直知晓长期运行的计算还需多少时间。于是满足度就增加了。
我在 20 世纪 60 年代末首次注重到这种现象,此后每十年就可以看到一回。我觉得从某种意义上讲自从计算开始它就一直在发生。要害并不在于最终用户轻易受骗或者可以被光鲜的“装饰”转移注重力。相对我们狭隘、专业的“性能”概念而言,他们只是有更广泛的目的。在许多情况下,当他们指出计算需要更快一点时,他们真正的意思是他们需要更快更可靠地知道该计算将要进行多久。得知精确的时间信息后,最终用户可以在计算机延迟期间快乐地安排其它任务。
建议参与处理性能的每个人都进行“热身练习”。首先,阅读或重读您最喜欢的有关需求治理方面的参考资料;下面的参考资料一节提供了几个有用的起点。
其次,在您的工具箱中放置一些“进度监视器”、“进度栏”或“秒表”,当您发现让用户等得太久时可以迅速地将其插入应用程序中。这些根本不用付出太多,如下面这两个示例所示。
两个倒计时示例
执行一个长时间的计算,同时又要让用户知晓其进度,这构成了应用程序设计中一个非常有趣的问题。它是个并发性或“多任务”的实例。许多开发人员都相信:作为正确的解决方案,并发性需要有精巧的机制,非凡需要有复杂的线程代码。
其实不然。下面的参考资料一节列出了一篇较早的 developerWorks 专栏文章,我在其中概述了并发性涉及的许多技术。此外,至少自 1988 年以来,基本上已经在所有 UNIX 主机上实现了简单的并发编程,在 1988 年这一年 ksh 对其“协同进程(co-PRocess)”进行了标准化。假如您将下面清单 1 中的 ksh 源代码保存为 ex1.ksh,然后运行它,您会看到“倒计时”显示:“十、九、八,等等”,然后看到 ksh 子进程的结果:“All done”。实际运用中,您可能会对长期运行的化学计算或数据库检索使用类似这样的操作:启动操作作为子进程,但是让用户始终知道操作的进展或完成之前还剩多少时间。更新显示只用了几行源代码。
清单 1. 示例倒计时显示的 ksh 源代码
(echo "This models a long-lasting process"; sleep 10;
echo "All done") &
for ((i = 10; i 0; i--))
do
printf "%2d seconds before completion ...\r" $i
sleep 1
done
read -p line;# Discard the title line.
read -p line
echo ""
echo "Output from the sub-process is '$line'."
为用户提供“实时”信息只需要进行适量的编码;即使基于字符的应用程序也可以做到这一点。假如图形用户界面(GUI)更适合您的情况,那也很简单。许多工具箱都内置了“忙碌”、“等待”或“进度”显示。假如您还没有这样一个工具箱,那么几行 Tk 或另一个新式的 GUI 工具箱就足以制作有点“类似的”倒计时钟面或进度栏。下面是一个在几个页面试用过的“从头开始做的”示例:
清单 2. 示例倒计时显示的 Tk 源代码
proc countdown {seconds} {
init
countdown_kernel $seconds
}
proc countdown_kernel seconds {
hands $seconds
if !$seconds return
after 1000 [list countdown_kernel [incr seconds -1]]
}
proc draw_hand {angle decorations} {
eval .c create line $::size $::size [get_xy $angle] $decorations
}
proc end_coordinate difference {
set hand_length [eXPr $::size * .9]
return [expr $::size + $hand_length * $difference]
}
proc get_xy angle {
return [list [end_coordinate [expr sin($angle)]][end_coordinate [expr -cos($angle)]]]
}
proc hands seconds {
catch {.c delete withtag hands}
set twopi 6.283185
set seconds_angle [expr $seconds * $twopi / 60.]
draw_hand $seconds_angle "-width 1 -tags hands"
set minutes_angle [expr $seconds_angle / 60.]
draw_hand $minutes_angle"-width 3 -capstyle projecting -tags hands"
}
proc init {} {
catch {destroy .c}
set ::size 30
set full_diameter [expr 2 * $::size]
pack [canvas .c -width $full_diameter -height $full_diameter]
set border 2
set diameter [expr 2 * $::size - $border]
.c create oval $border $border$diameter $diameter-fill white -outline black
}
countdown 10
这个倒计时显示了分针和秒针,如图 1 所示,其信息内容与前面的程序相同。
图 1. 用 Tk 编码的模拟倒计时时钟的外观
请记住:信息可以代替功能。您的最终用户对应用程序的内部状态越了解,他们对您的要求就越少。只要让您的程序显示它们是如何工作的,就可以解决许多明显的性能问题。
排序很难
前面介绍的是“简单的”课程;没有专门的编程背景知识的“平民百姓”也可以理解前面的段落。但是排序却属于“困难”这一类。而且这肯定是困难的:Donald Knuth 的一整卷有关计算的经典系列都致力于研究排序和搜索(请参阅参考资料以获取对 Knuth 撰写的 The Art of Computer Programming 的评论的链接)。
结果证实,由于深层次的原因,排序是许多性能难题的核心所在。性能只是大规模计算的问题。人类一次只能理解几个方面,因此对于那些大得要花掉很长时间才能把握的问题,我们采用的方式是用某种方式把它们组织起来或使其结构化。排序是这些方式中最常见的一种;可以对已排序列表进行二元搜索而不进行线性搜索。例如,这使得在纽约市电话号簿中进行的手工查找得到了简化,将一个百万级大小的问题简化成一个一百万的对数(也就是,大约为 14)级的问题。
那是典型的排序工作;高级算法通常比低级算法快一千倍或更多。值得进行巧妙的排序。
但是最聪明的做法就是避免进行整体排序,或者至少将排序仅限于在不受注重的场合进行。这在数据库治理系统中很常见;其它好处之一就是,它们答应构造“插入时”索引。需要排序结果时,可以直接从索引中读取。这一操作的代价就是:创建或插入元素的时间稍微有点长,但是假如应用程序具有典型的工作流的话,用户觉察不到这一点。
Knuth 的参考资料描述了其它许多策略,比如用来在特定的条件下加快排序操作的“Boyer-Moore”或“Rabin-Karp”。统一这些策略的一个公共原则是:解决通用问题比解决比较特定的问题更轻易。数学家对此很熟悉;假如将代数中的常见问题考虑成复数而不是实数时,那么这些问题就更轻易处理,尽管复数算法较难。
这就是我对“装饰-排序-去除装饰(decorate-sort-undecorate,DSU)”的看法。假定您拥有这样的数据集:
"Jane Jones" - 15,000
"Dan Smith"-6,000
"Kim Black"- 40,000