内联汇编的性能：一种基于斐波纳契数列计算的分析-3

look_w

性能预期在上面给出的 5 种实现中，具有对数时间复杂度的矩阵乘方算法在性能上排名第一。动态编程方法、迭代算法和内联汇编实现位居中间，具有线性时间复杂度。递归算法由于其指数时间复杂度而位于最底部。
表 3：运行时复杂度
方法 递归算法  迭代算法  动态编程  内联汇编  矩阵乘方 复杂度 指数  线性  线性  线性  对数 基于运行时分析，预计在采样大小足够大时，实际性能与复杂度呈正比。
测试程序每个实现都可以封装在一个函数中。测试程序使用了以下两个变量：
volatile clock_t start、end；
它们记录每个函数的开始时间和返回时间。使用了 5 个不同的变量来保存每个实现的运行时间。
volatile float elapsedASM、elapsedI、elapsedR、elapsedM、elapsedD；
清单 12 给出了运行时间的计算方法。
清单 12：运行时间的计算

1 2 3 4

start = clock(); while ( myCount-- ) { resASM = fib_asm(limit); } end = clock(); elapsedASM =  ((float) (end - start))*1000 / CLOCKS_PER_SEC ;

除了递归算法之外，所有实现都将对 92 项执行 10,000,000 次计算。大量的循环次数用于延长执行时间，以便正确记录运行时间。另外，由于大于斐波纳契数列中第 100 个数的项超出了整数数据类型长度，所以大于第 90 个数的项实际上是具有 64 位整数的斐波纳契计算的上限。递归函数将使用小得多的参数来进行测试，它只计算斐波纳契数列的第 40 项两次。由于递归算法具有指数时间复杂度，所以应该选择较小的参数来确保程序在其他方法的时间范围内完成。
请参阅完整的  了解更多细节。
实际性能图 6 中给出了在 IBM 多伦多软件实验室的一台运行 Linux 的 z System 机器上执行测试的实际性能结果。
图 6. 相对性能
从图 6 可以明显地看到，在计算最大的斐波纳契数时，内联汇编实现优于其他所有方法。它大约比动态编程和迭代方法快 4 倍。令人惊奇的是，它的性能也优于经过优化的矩阵乘方算法。这一性能优势源于内联汇编实现较小的资源占用。
从理论上讲，如果输入的大小足够大，优化的矩阵乘方算法的性能可能超过内联汇编实现。但实际上，当应用程序的输入受到变量大小限制时，从内联汇编实现生成的紧凑代码的实际速度可能超过某种更快的算法的性能。这是使用内联汇编进一步提高性能，超越最佳算法可以提供的性能的一个示例。
结束语在计算斐波纳契数列的特殊情况下，内联汇编方法的性能优于其他所有算法，即使已证明理论上速度将会更慢。这个示例证明，理论性能可能不切实际。适当地使用内联汇编来调优最注重性能的代码节，这是超越算法所提供的默认速度的一条途径。
一定要注意的是，使用内联汇编所获得的性能只有通过仔细计划和大量测试才能实现。因为 IBM XL 编译器基于多维分析来执行高度复杂的优化，所以在大多数情况下，使用编译器所提供的适当的优化水平可能是最佳选择。必须根据特定系统上的经验测试数据来决定是否使用内联汇编。此外，内联汇编仅应用于最注重性能的代码节。成功实现的前提是：应用程序的固有知识和对系统上可用的汇编程序指令集的全面理解。