对于复杂的算法,如何测量其性能?
现在让我们假设我们已经缩小了应用程序中典型瓶颈所在的位置。众所周知,这可能是我们运行的用于重新索引表的批处理过程;可能是在有效日期树上运行的SQL查询;可能是数百个复合对象的XML编组。换句话说,我们可能会遇到以下情况:
public Result takeAnAnnoyingLongTime(Input in) { // impl of above }
不幸的是,即使我们已经确定了瓶颈,我们所能做的就是消除它。没有简单的解决方案可用。
我们如何衡量瓶颈的性能,以使我们知道修补程序的方向正确?
解决方案
- 剖析它
- 在探查器中找到第一行,尝试使其更快。
- 剖析它
- 如果有效,请转至1. 如果无效,请转至2.
我将使用允许我首先找到它们的相同工具/方法来对其进行测量。
即,坚持计时和记录呼叫到处都是。如果数字开始下降,那么我们可能正在做正确的事。
如本msdn专栏中所述,将性能调整与绘画金门大桥的工作进行了比较:完成对整个事物的绘画之后,该回到起点重新开始了。
两点:
- 当心臭名昭著的"优化空闲循环"问题。 (例如,请参见"停车场中的保时捷"标题下的优化故事。)也就是说,仅因为例程要花费大量时间(如分析所示),否则不要以为它是如用户所知导致性能下降。
- 最大的性能提升通常不来自算法的巧妙调整或者优化,而在于认识到完全有更好的算法。一些改进相对明显,而另一些则需要对算法进行更详细的分析,并且可能需要对所涉及的数据结构进行重大更改。这可能包括将处理器时间与I / O时间进行权衡,在这种情况下,我们需要确保我们不仅在优化其中一种措施。
回到问题所在,确保所测量的内容都代表用户实际体验,否则工作可能会完全浪费时间。
这是一个有趣的问题。我认为没有人知道答案。我相信问题的重要部分是对于更复杂的程序,没有人能够预测它们的复杂性。因此,即使我们有探查器结果,也要根据程序的更改来解释它,这非常复杂,因为我们没有最佳解决方案的理论基础。
我认为这是我们拥有如此庞大的软件的原因。我们仅进行优化,以使相当简单的情况在我们的快速机器上也能正常工作。但是,一旦将这些部分组合到一个大型系统中,或者使用了数量级更大的输入,那么所使用的错误算法(在理论上和实践上都是不可见的)就会开始显示出它们的真正复杂性。
示例:我们创建一个处理Unicode的字符串类。我们可以在计算机无关紧要的地方使用它,例如计算机生成的XML处理。但是Unicode处理在其中,占用了一部分资源。就其本身而言,字符串类可以非常快,但是调用它一百万次,则程序将很慢。
我相信当前大多数软件膨胀就是这种性质。有一种减少它的方法,但是它与OOP相矛盾。有一本有趣的书关于各种技术的一本有趣的书,它是面向内存的,但是大多数可以还原以提高速度。
我确定两件事:
1)这是什么复杂性?最简单的方法是绘制时间与输入大小的关系图。
2)如何绑定?是内存,磁盘,IPC还是其他进程或者机器?
现在,第(2)点变得更容易解决和解释:如果我们拥有更多的RAM或者更快的计算机或者更快的磁盘,或者移至千兆以太网等,许多事情就会变得更快。如果我们确定自己的痛苦,则可以在硬件上投入一些资金以使其可以忍受。
这不是一个难题。我们需要了解的第一件事是衡量性能并不是我们发现性能问题的方式。知道某件事有多慢并不能找出原因。我们需要一个诊断工具,一个好的工具。我有很多这样做的经验,这是最好的方法。它不是自动的,但它在大多数探查器周围运行。