内联汇编的性能：一种基于斐波纳契数列计算的分析-1
|
- UID
- 1066743
|
内联汇编的性能：一种基于斐波纳契数列计算的分析-1
简介从 2015 年的 V1.1 开始，IBM XL C/C++ for Linux on z Systems 编译器支持内联汇编特性。该特性为软件工程师提供了直接访问一组芯片级汇编程序指令的能力。使用内联汇编，软件工程师可以轻松地指定最佳的指令来加速特定代码节，超越了算法或编译器锁所能提供的速度。这对高性能应用程序不可或缺，尤其在改进的代码节位于关键执行路径上时。
本文将讨论和对比计算斐波纳契数列的内联汇编方法与以下 4 种未使用内联汇编的算法的性能。
- 具有指数时间 (exponential time) 复杂度的递归算法
- 具有线性时间复杂度的动态编程算法
- 具有线性时间复杂度的迭代实现
- 具有对数时间复杂度的优化的矩阵乘方算法
本文假设读者熟悉针对 Linux on z Systems 的内联汇编。软件工程师可能发现本系列以前的文章能够增进知识。
IBM XL 编译器基于用户代码的多维分析来执行高度复杂的优化。为了抵消计算机自动执行的各种优化对相对环境的意外影响，本文的所有编译没有指定任何级别的编译器优化。
斐波纳契数列的定义斐波纳契数列以意大利数学家雷纳尔多·波纳契（也称为斐波纳契）的名字命名，可在多个学科中找到它的应用，比如数学、建筑学、几何学、计算机科学和自然中。它是从 0, 1 对（或 1, 1）开始的整数数列。数列中的后一个数是前两个数的和。用数学中的项来表示就是，斐波纳契数列 (Fn) 定义由与前两项（F0、F1 或 F1、F2）的递归关系来定义，如下所示：
1
2
3
4
5
6
7
| F0 = 0
F1 = 1
Fn = F(n-2) + F(n-1) if n >1
or
F1 = 1
F2 = 1
Fn = F(n-2) + F(n-1) if n >2
|
斐波纳契数的另一种增强形式是，负斐波纳契数列，其中的索引扩展到负数。在斐波纳契数的三种定义中，本文的分析基于该数列的更加现代的形式 F0, F1, …, Fn。表 1 中给出了前几个斐波纳契数。
表 1：前几个斐波纳契数的列表
F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 0 1 1 2 3 5 8 13 21 34 55 89
递归算法基于斐波纳契数列的递归定义，计算第 n 个斐波纳契数的递归算法是一种直观的实现。
清单 1：递归算法的伪代码
1
2
3
4
5
6
| Fib(n):
if n in range [0,1]
return n
else
return Fib(n-2) + Fib(n-1)
end if
|
递归算法与该数列的递归定义具有自然的对应关系。递归步骤的运行时复杂度可用以下等式来表达：
1
2
3
| T(n) = T(n-1) + T(n-2)+ Theta(1)
>= 2 T(n-2)
= Theta(2<sup>n/2</sup>)
|
因此，此实现的复杂度是指数时间级的。
清单 2：计算第 n 个斐波纳契数的递归算法
1
| long long fib_r(int n)<br>{<br> return n <= 1 ? n : fib_r(n-1) + fib_r(n-2) ; <br>}
|
图 1. 斐波纳契递归算法的递归树 从图 1 中显示的算法的递归树，可以看到一些表达式在过程中计算了多次。例如，在 Fib(n) 和 Fib(n-1) 执行的调用中，都计算了表达式 Fib(n-2)。反复计算是递归算法具有指数时间的主要原因。如果可以避免所有多余的计算，时间复杂度将获得改善。对于斐波纳契数列，这个问题可以使用动态编程解决。通过利用记忆 保留计算的值供以后使用，动态编程技术消除了在递归算法中发生的反复计算，加快了执行速度。
动态编程算法为了消除多余的计算，动态编程利用了默记法 (Memoization) 来保留计算的值供以后使用。由于每一项只计算一次，所以动态编程方法的时间复杂度是线性的。本文将讨论计算斐波纳契数列的两种著名的动态编程算法：默记法版本和自底向上版本。
动态编程方法的默记法版本从该技术的名称可以看出，该方法通过将计算的值存储在某种形式的数据结构中来记住它们。只有在新计算的结果不在算法的记忆中时，才需要计算它。尽管默记法方法仍依赖于递归步骤，但默记法查找可以确保每个表达式在该过程中只计算一次。记忆查找操作被认为具有不变的时间复杂度。
清单 3：默记法动态编程的伪代码
1
2
3
4
5
6
7
8
9
10
11
12
| Mem = { } //Data structure storing computed values
Fib(n):
if n in Mem //Return existing value from Memory
return Mem[n] //Early exit when handling known values
end if
if n if n in range [0,1] //Base step of the recursion
fib ? n
else //Recursive steps
fib ? Fib(n-2) + Fib(n-1)
end if
Mem[n] ? fib //Memorize new value
return fib //Return the new computed value
|
因为斐波纳契数的每个值只计算一次，所以此方法的运行时复杂度为线性时间。如图 2 所示，动态编程方法的默记法版本的递归树不会反复计算已知值。
图 2. 动态编程算法的递归树 尽管默记法版本可以降低运行时复杂度，但它仍依赖于递归函数调用。设置和管理函数调用的成本已在复杂度计算中忽略，但它们实际上并不是微不足道的。下面即将讨论的技术称为自底向上遍历，可以帮助避免支持函数调用的额外成本。
动态编程的反向遍历（自底向上）版本反向遍历方法不从递归树顶部的根开始遍历，而是自底向上遍历递归树。在计算斐波纳契数的特殊情况下，该算法将从索引 0 开始，然后向上遍历到索引 n。它仍使用一种数据结构来记住计算的值，但它将递归函数调用替换为查找操作。根据定义，第 n 个斐波纳契数计算为 Fn = F(n-2) + F(n-1)。因为前面的两项 F(n-2) 和 F(n-1) 可从算法的记忆中进行检索，所以不需要递归函数调用。
清单 4：反向遍历动态编程的伪代码
1
2
3
4
5
6
7
8
9
10
| Fib(n):
Mem = {} //the memory
for k in range [0,1,…,n] //traverse bottom-up
if k in range [0,1] //compute each term
Mem[k] ? k //starting with indices 0 and 1
else:
Mem[k] ? Mem[k-1] + Mem[k-2] //Retrieve known values
end if
end for
return Mem[n]
|
由于记忆查找可预防反复计算已知的项，所以斐波纳契数列的每一项都只计算了一次。因此该算法具有线性时间复杂度。此外，因为递归函数调用被替换成了记忆查找操作，所以消除了设置和管理递归函数调用的额外成本。
清单 5：计算第 n 个斐波纳契数的动态编程方法
1
2
3
4
5
6
7
8
9
10
11
12
| long long fib_d(int n)
{
int k;
long long memory[n];
for ( k = 0 ; k <= n ; ++k ) {
if ( k <= 1 )
memory[k] = k;
else
memory[k] = memory[k-1] + memory[k-2];
}
return memory[n];
}
|
迭代算法类似于反向遍历方法，迭代算法迭代从索引 0 一直到索引 n 的整个数列。在此过程中，它使用了前两个数的和更新了斐波纳契数列的每一项。但是，迭代算法没有记住计算的值。图 3 提供了用于计算斐波纳契数的迭代算法的可视化表示。
图 3. 迭代算法的可视化 点击查看大图
因为为该程序设定的需求是计算第 n 个斐波纳契数，所以在实际实现中，可以跳过使用计算的值 res 更新斐波纳契数列的实际值的步骤。在需要时，很容易实现该算法。
清单 6：计算第 n 个斐波纳契数的迭代方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| long long fib_i(int n)
{
int k;
long long e0 = 0, e1 = 1, res = 0;
for ( k = 0 ; k <= n ; ++k ) { //iterate from 0 to n
if ( k <= 1 )
res = k; //base case for F0 and F1
else {
res = e0 + e1; //res is the sum of 2 previous terms
e0 = e1; //update the 2 previous terms
e1 = res; // -------- ditto --------
}
}
return res; //return Fn
}
|
因为迭代算法仅迭代整个斐波纳契数列一次，所以它的复杂度为线性时间级。类似于反向遍历算法，它不会调用递归函数。 |
|
|
|
|
|
