android优化实战（一）-从递归到迭代

1、android是怎样执行你的代码的android平台不只包括java Virtual Machine（VM）来执行代码。而且，应用还被编译成Dalvik 字节码，android 使用它自己的Dalvik VM（android虚拟机）来执行它。java代码仍然被编译成java字节码，然后这些java字节码再被dex编译器编译成Dalvik 字节码，dx（一个SDK工具）。最后，你的应用将只包

ludi7125

1739人浏览 · 2012-05-15 19:00:03

ludi7125 · 2012-05-15 19:00:03 发布

1、android是怎样执行你的代码的

android平台不只包括java Virtual Machine（VM）来执行代码。而且，应用还被编译成Dalvik 字节码，android 使用它自己的Dalvik VM（android虚拟机）来执行它。java代码仍然被编译成java字节码，然后这些java字节码再被dex编译器编译成Dalvik 字节码，dx（一个SDK工具）。最后，你的应用将只包含Dalvik字节码，而不是java字节码。

例如，一个实现用Fibonacci数列计算第n项定义如下：

用一个纯递归实现该数列：

public class Fibonacci {
public static long computeRecursively (int n)
{
if (n > 1) return computeRecursively(n-2) + computeRecursively(n-1);
return n;
}
}

android应用程序，也就是我们常说的被编译成拓展名为.apk的APK包，其实是一个简单的文档（你可以把它变成zip格式看一下）。文档中其中的一个文件是classes.dex，包含着应用的字节码。android toolchain 提供了一个工具（dexdump），能把这样的字节码格式转换成人们可读的一种格式。

computeRecursively运行后的字节码转换成可读格式如下：

002548: |[002548] com.ludi..Fibonacci.computeRecursively:(I)J
002558: 1212 |0000: const/4 v2, #int 1 // #1
00255a: 3724 1100 |0001: if-le v4, v2, 0012 // +0011
00255e: 1220 |0003: const/4 v0, #int 2 // #2
002560: 9100 0400 |0004: sub-int v0, v4, v0

002564: 7110 3d00 0000 |0006: invoke-static {v0},
Lcom/apress/proandroid/Fibonacci;.computeRecursively:(I)J
00256a: 0b00 |0009: move-result-wide v0
00256c: 9102 0402 |000a: sub-int v2, v4, v2
002570: 7110 3d00 0200 |000c: invoke-static {v2},
Lcom/apress/proandroid/Fibonacci;.computeRecursively:(I)J
002576: 0b02 |000f: move-result-wide v2
002578: bb20 |0010: add-long/2addr v0, v2
00257a: 1000 |0011: return-wide v0
00257c: 8140 |0012: int-to-long v0, v4
00257e: 28fe |0013: goto 0011 // -0002

每一行的第一段数字表示代码在文件中的绝对位置（第一行还显示了方法名）。接着显示的是16bit的字节单元。比如，在第三行中，两个字节单元3724 1100的位置是在0x00255a 移动到“if -le v4，v2，0012 // +0011",基本的意思是"如果虚拟寄存器v4中的内容小于或者等于v2中的内容，就会通过跨过17个字节单元跳转到地址 0x0012。（虚拟寄存器表示不存在真正的硬件上的寄存器，而是通过dalvik virtual machine使用的寄存器。

通常，你并不需要了解观察你应用的字节码。特别是Android2.2或者以后的版本。因为2.2以后的版本把Just-In-Time（JIT）编译器引入，这个 Dalvik JIT 编译器编译Dalvik字节码到本地代码，能使程序执行得更快。JIT之所以能如此惊人的提升性能，原因如下：

（1）本地代码能直接被CPU执行而不必被虚拟机解释。

（2）本地代码可为特殊的架构做优化。

google通过Benchmarks（基准测试）表明执行速度中，Android2.2比Android2.1快2到5倍。虽然这个结果还要依据你的代码，不过你可以想象到Android2.2或以后的版本确实执行速度快了很多。

Android2.1或者早期的版本因为缺少JIT编译器而大大影响了你的优化策略。如果你还是想写兼容1.5（Cupcake），1.6（Donut）以及2.1（Eclair），你需要仔细的考虑你的应用需要提供什么。而且，设备运行这些早期的版本确实在性能上比不过新版本。然而，虽然Android2.1或早期版本在android市场上受到冲击，它们仍然占有12%的份额（2011年12月）。我们一般采取策略是：

（1）一点也不优化，你的应用将会在旧版本设备上运行更慢。

（2）需要最低位API level 8运用于你的应用，能使其安装于2.2或以后的版本。

（3）优化你旧的设备，如cpu性能，来提供更好的用户体验。

（友情提示：vmSafeMode 在你的应用配置中可以关闭或打开JIT编译器。它是默认打开的，这项属性自2.2后被加入。）

现在让我们举个例子来看看代码在平台上是如何表现的。如果你熟悉递归和Fibonacci（斐波那契数列），运行效果会运行得很慢。在Samsung Galaxy Tab 10.1，计算第30个斐波那契数需要花费370毫秒。当使JIT编译器失效时，它花费440毫秒。如果你想在应用中使用类似计算的功能，用户体验会很差，因为他不能立即看到运行结果。从用户的角度看，如果计算只花费100毫秒或者更少，这种反应时间才能保证最佳的用户体验，其实这也是我们目标。

优化Fibonacci

第一次优化我们尝试减少方法调用，上面的原始代码我用了两次方法调用，这次我们简化到一次。如下所示：

public class Fibonacci {
public static long computeRecursivelyWithLoop (int n)
{
if (n > 1) {
long result = 1;
do {
result += computeRecursivelyWithLoop(n-2);
n--;
} while (n > 1);
return result;
}
return n;
}
}

运行结果表明，computeRecursively（30）产生了2,692,537方法调用，而computeRecursivelyWithLoop（30）只产生1,346,269。然而，并没有达到我们立即响应最佳用户体验的目的，即100毫秒或更少。computeRecursivelyWithLoop（30）运行耗费了270毫秒来完成。

让我们进一次优化代码，再第二次代码优化中，我把递归方式转换为迭代方式。因为递归算法的执行速度在开发者看来是非常差的，特别是在内存缺乏的嵌入式设备系统（手机、平板）中，运行效果更差。因为递归往往需要消耗大量的内存栈空间，就像我们上面提到，消耗了很多方法调用才能完成。即使能算出结果，但递归算法容易引起栈溢出。所以我们在开发应用中，应尽量使用迭代而不是递归。如下所示就是第二次代码优化：

public class Fibonacci {
public static long computeIteratively (int n)
{
if (n > 1) {
long a = 0, b = 1;
do {
long tmp = b;
b += a;
a = tmp;
} while (--n > 1);
return b;
}
return n;
}
}

因为n次方的斐波那契数列就是两个前一次方程的和，一个简单的循环就可以完成。相对于递归算法，因为线性的原因，迭代算法的复杂度比递归算法大大减少了。结果，运行效果非常好，computeIteratively（30）只耗费了不到1毫秒。由于线性的性质，你可以运用类似的算法来计算超过30次的方程计算。例如，computeIteratively（50000）只耗费了2毫秒就能返回结果。用外推法，你能猜测到computeIteratively（500000）只耗费20到30毫秒之间来完成。

上面的优化结果已经相当令人满意了，但如果你还想进一步优化，使其达到更快的效果，可以在同样的算法基础上做一小小的改变如下所示：

public class Fibonacci {
public static long computeIterativelyFaster (int n)
{
if (n > 1) {
long a, b = 1;
n--;
a = n & 1;
n /= 2;
while (n-- > 0) {
a += b;
b += a;
}
return b;
}
return n;
}
}