[科普中国]-运算效率

简介

运算效率是指计算机程序或算法运行时所需的时间或内存的多少。提高运算效率是推动计算机科学发展的重要推动力之一，为了提高运算效率，人们不断对计算机程序或硬件进行优化，即使用更少的时间和内存完成更多的工作。运算效率一般通过计算机性能分析工具得到。

计算机程序优化计算机程序优化一般分为代码优化和算法优化。

代码优化代码优化是指对程序代码进行等价（指不改变程序的运行结果）变换。程序代码可以是中间代码（如四元式代码），也可以是目标代码。等价的含义是使得变换后的代码运行结果与变换前代码运行结果相同。优化的含义是最终生成的目标代码短（运行时间更短、占用空间更小），时空效率优化。原则上，优化可以在编译的各个阶段进行，但最主要的一类是对中间代码进行优化，这类优化不依赖于具体的计算机。在不改变程序运行效果的前提下，对被编译的程序进行等价变换，使之能生成更加高效的目标代码。改进、提高程序途径：1）改进算法；2） 在源程序级上等价变换；3）充分利用系统提供的程序库；4） 编译时优化等1。

算法优化算法优化是指对算法的有关性能进行优化，如时间复杂度、空间复杂度、正确性、健壮性。大数据时代到来，算法要处理数据的数量级也越来越大以及处理问题的场景千变万化。为了增强算法的处理问题的能力，对算法进行优化是必不可少的。算法优化一般是对算法结构和收敛性进行优化。

性能分析概述在软件工程中，性能分析（performance analysis也称为profiling），是以收集程序运行时信息为手段研究程序行为的分析方法，是一种动态程序分析的方法。性能分析量测像是程序的空间或时间复杂度、特定指令的使用情形、函数调用的频率及运行时间等。性能分析的目的在于决定程序的哪个部分应该被优化，从而提高程序的速度或者内存使用效率。性能分析可以由程序的源代码或是可执行文件进行．一般会使用称为性能分析工具（profiler）的工具进行。性能分析工具会使用许多不同的技术，可能是以事件为基础（Event-based）的、统计的、指令导向的，以及仿真的方法。性能分析工具常用在性能工程过程中使用。

分类性能分析器本身也是程序，可以在被分析程序运行时收集相关信息，来分析该程序。根据收集到信息的细微度，以及收集信息的方式，可以分为事件为基础的性能分析器，或是统计式的性能分析器。有些性能分析器为了收集信息，会中断程序的运行，因此在时间量测上有一定的分辨率限制。

事件为基础的性能分析器

以下列出的编程语言有事件为基础的性能分析器：

Java：JVMTI（JVM工具接口）API，以前称为JVMPI（JVM性能分析接口），提供给性能分析器的hook，可以抓到像函数调用、类别加载、卸载、线程的进入及离开等事件。

.NET框架：利用性能分析的API，可以连接到像是COM服务器的性能分析代理器（profiling agent）。像Java一様，在运行会提供许多回调函数给代理器，可以捕捉到像是方法JIT/进入/离开，对象创建及其他。特别的是性能分析代理器可以用任意方式改写目的应用程序的字节码。

Python：Python的性能分析包括profile模块，以调用函数图为基础的hotshot，以及用'sys.setprofile'函数来捕捉像c_{call,return,exception}及python_{call,return,exception}的事件。

Ruby：Ruby也用类似Python的性能分析界面。目前有在profile.rb中的一般性能分析器及相关模块。

统计式的性能分析器

有些性能分析器是用取様的方式运作。取様式的性能分析器利用操作系统的中断，在固定时间取様目的程序的程序计数器。取様式的性能分析器在数值上较不精准，但对目的程序运行时间的影响最小，允许目的程序可以在接近全速的速度下运作。

所得到的数据不是精准值，只是统计上的近似值而已。“实际误差的量一般会大于一个取样时间．若芋某一数值是取様时间的n倍，其误差约为n倍取様时间的平方根”。在实务上统计式的性能分析器会比其他的分析方式更能知道目的程序各部分占的比例，而且相较之下有较少的边际效应（例如内存缓存或是指令解码的管道线等），由于统计式的性能分析器对程序运行速度的影响较小．因此可以侦测到一些其他方式侦测不到的问题。这种方式可以看出用户模式及可中断系统模式（例如系统调用）分别占的时间。不过由于系统程序需处理中断，仍然会花一些CPU的运行周期，分散缓存的读取，而且无法分辨在不可中断核心模式下的行为。

有些特制的硬件可以克服这类的问题：有些最近MIPS微理器中，JTAG接口有一个PCSAMPLE寄存器，可以用一种无法侦测到的方式来取様程序计数器。最常用的统计式的性能分析器包括AMD的CodeAnalyst、苹果公司的 Shark（OSX）、Intel的 VTune及Parallel Amplifier（Intel Parallel Studio的一部分）。