[翻译] Java Hidden Costs | 技不如人，甘拜下风

翻译

随着 Java 8 被引入 Andorid, 我们更要时刻牢记标准库的 API 和语言特性都伴随着额外的性能消耗。虽然我们的设备不断升级，有了更大的内存，更高的运行速度，但是代码对性能的影响仍是至关重要的。360AnDev 的这次分享将会探讨一些 Java 特性的隐式消耗。我们主要关注与第三方库开发者和应用开发者相关的性能优化方法，并介绍相关的测试工具。

Introduction

文章前面并不会介绍优化相关内容，解决办法会在最后部分。以及本文会有大量命令行工具的使用方法，相关资源连接也会文章末尾附上。

Dex file

我们从一个多选题开始，这段代码里有几个方法？0, 1 or 2?

1 2	class Example { }

翻译好累不翻了…

0 -> 源文件里确实是 0 个
1 -> 编译成字节码，查看 class 文件，有自动生成的无参构造函数
2 -> 在 Andorid 中，字节码还会被转换成 dex 文件，使用 SDK 里的工具可以查看详细信息

javac

$ echo "class Example {
}" > Example.java

$ javac Example.java

$ javap Example.class
class Example {
Example();
}

dex

$ dx --dex --output=example.dex Example.class

$ dexdump -f example.dex

$ dexdump -f example.dex

Processing 'example.dex'...
Opened 'example.dex', DEX version '035'
DEX file header:
magic               : 'dex\n035\0'
checksum            : 53c72da5
...
field_ids_off       : 0 (0x000000)
method_ids_size     : 2	<--------------------------注意这里
method_ids_off      : 156 (0x00009c)
...

也就是下面这两个方法

1 2	Example <init>() java.lang.Object <init>()

Java 内部类


// ItemsView.java
public class ItemsView {
    private class ItemsAdapter {
    }
}

$ javac ItemsView.java

$ ls
ItemsView.class
ItemsView.java
ItemsView$ItemsAdapter.class

ItemsView 编译后生成两个单独的类文件，由此可见其在 Java 中并没有真正的嵌套。

使用 javap 指令查看，ItemsView.class 中没有任何关于其内部类的信息。另一个值得注意的是虽然内部类 ItemsAdapter 在源文件中被声明为 private ，但在其类文件中却不是私有的，而是默认的 package 访问权限。

//  Compiled from "ItemsView.java"
public class ItemsView {
  public ItemsView();
}

// Compiled from "ItemsView.java"
class ItemsView$ItemsAdapter {
    ItemsView$ItemsAdapter();
}

看起来内部类只是以一种更高效的方式生成了两个处于同一包名下彼此相邻的类文件。

Ps: 我编出来和他说的不一样啊…

java version "1.8.0_121"
Java(TM) SE Runtime Environment (build 1.8.0_121-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.121-b13, mixed mode)

$ javac ItemsView.java -source 1.7 -target 1.7

//  Compiled from "ItemsView.java"
public class ItemsView {
  public ItemsView();
}

// Compiled from "ItemsView.java"
class ItemsView$ItemsAdapter {
  final ItemsView this$0;
}

继续上面的，在我们的假设中嵌套类只是生成两个类，但下面两段代码又引出新的问题。

Compile Ok


public class ItemsView {
    private static String displayText(String item) {
        return ""; // TODO
    }
    private class ItemsAdapter {
        void bindItem(TextView tv, String item) {
            tv.setText(ItemsView.displayText(item));
        }
    }
}

Compile Error

// ItemsView.java
public class ItemsView {
    private static String displayText(String item) {
        return ""; // TODO
    }
}
// ItemsView$ItemsAdapter.java
class ItemsView$ItemsAdapter {
    void bindItem(TextView tv, String item) {
        tv.setText(ItemsView.displayText(item));
    }
}

反编译看下编译成功的结果，又出来一个我们没写的方法。也就是说只要在刚才编译失败的那个分离版本中也写上这么一个方法，编译就没问题了。表面上看起来没什么，但这个方法是实实在在的加到你的方法数上的。

$ javap -p ItemsView

class ItemsView {
    ItemsView();
    private static java.lang.String displayText(…);
    static java.lang.String access$000(…);
}

More Dex

这东西不光在 javac 里有影响，你把它转成 dex 也是这样的。

$ dx --dex --output=example.dex *.class

$ dex-method-list example.dex

ItemsView <init>()
ItemsView access$000(String) → String
ItemsView displayText(String) → String
ItemsView$ItemsAdapter <init>(ItemsView)
ItemsView$ItemsAdapter bindItem(TextView, String)
android.widget.TextView setText(CharSequence)
java.lang.Object <init>()

那么 Jack compiler 呢？还是一样，只不过不叫 access 改叫 -wrap0 了

$ java -jar android-sdk/build-tools/24.0.1/jack.jar \
        -cp android-sdk/platforms/android-24/android.jar \
        --output-dex . \
        ItemsView.java

$ dex-method-list classes.dex

ItemsView -wrap0(String) → String
ItemsView <init>()
ItemsView displayText(String) → String
ItemsView$ItemsAdapter <init>(ItemsView)
ItemsView$ItemsAdapter bindItem(TextView, String)
android.widget.TextView setText(CharSequence)
java.lang.Object <init>()

我们还有 ProGuard 不是，能不能搞定这个方法呢？


$ echo "-dontobfuscate
-keep class ItemsView$ItemsAdapter { void bindItem(...); }
" > rules.txt

$ java -jar proguard-base-5.2.1.jar \
    -include rules.txt \
    -injars . \
    -outjars example-proguard.jar \
    -libraryjars android-sdk/platforms/android-24/android.jar

$ dex-method-list example-proguard.jar

ItemsView access$000(String) → String
ItemsView$ItemsAdapter bindItem(TextView, String)
android.widget.TextView setText(CharSequence)

构造函数因为没使用被移除了，但是实际使用时还是会用到他们，所以我们这里手动保留一下。

$ dex-method-list example-proguard.jar

ItemsView <init>()
ItemsView access$000(String) → String
ItemsView$ItemsAdapter <init>(ItemsView)
ItemsView$ItemsAdapter bindItem(TextView, String)
android.widget.TextView setText(CharSequence)
java.lang.Object <init>()

最终结果，access方法仍然存在，但是 displayText 消失了。发生了什么？解压 Proguard 生成的 jar 文件，使用 javap 查看 class 文件：

$ unzip example-proguard.jar

$ javap -c ItemsView

public final class ItemsView {
    static java.lang.String access$000(java.lang.String);
        Code:
            0: ldc #1 // String ""
            2: areturn
}

是因为没有其他位置使用这个方法， Proguard 对 displayText 进行了优化。可以见得 Proguard 在这里确实有那么一点用处，不过对一个简单的 demo 起效并不足以证明。你可能不以为然，觉得内部类的影响没什么大不了的，那我们下面接着说匿名内部类。

匿名内部类

class MyActivity extends Activity {
    @Override protected void onCreate(Bundle state) {
        super.onCreate(state);

        setContentView(R.layout.whatever);
        findViewById(R.id.button).setOnClickListener(
            new OnClickListener() {
                @Override public void onClick(View view) {
                    // Hello!
                }
            });
    }
}

这东西我们常用，匿名内部类其实就是嵌套类，只不过他没有名字。如果你访问了一个外部类的 private 方法，他就会对应生成 access 方法，访问字段也是这样。

class MyActivity extends Activity {
    private int count;

    @Override protected void onCreate(Bundle state) {
        super.onCreate(state);

        setContentView(R.layout.whatever);
        findViewById(R.id.button).setOnClickListener(
            new OnClickListener() {
                @Override public void onClick(View view) {
                    count = 0;
                    ++count;
                    --count;
                    count++;
                    count--;
                    Log.d("Count", "= " + count);
                }
            });
    }
}

你猜上面这段代码会生成多少个 access 方法呢？

$ javac -bootclasspath android-sdk/platforms/android-24/android.jar \
MyActivity.java

$ javap MyActivity
class MyActivity extends android.app.Activity {
    MyActivity();
    protected void onCreate(android.os.Bundle);
    static int access$002(MyActivity, int); // count = 0    write
    static int access$004(MyActivity);        // ++count         preinc
    static int access$006(MyActivity);        // --count         predec
    static int access$008(MyActivity);        // count++         postinc
    static int access$010(MyActivity);        // count--         postdec
    static int access$000(MyActivity);        // count         read
}

可想而知，如果一个 Activity 或是 Fragment 里有几个这样的 listener，那方法数还不得爆炸。

现实世界

我们来看看你手机里的应用吧，先把你安装的 APK 都拷贝出来

$ adb shell mkdir /mnt/sdcard/apks

$ adb shell cmd package list packages -3 -f \
| cut -c 9- \
| sed 's|=| /mnt/sdcard/apks/|' \
| xargs -t -L1 adb shell cp

$ adb pull /mnt/sdkcard/apks

然后用 dex-method-list 和 grep 统计下方法数

#!/bin/bash                                                 accessors.sh
set -e

METHODS=$(dex-method-list $1 | \grep 'access\$')
ACCESSORS=$(echo "$METHODS" | wc -l | xargs)
METHOD_AND_READ=$(echo "$METHODS" | egrep 'access\$\d+00\(' | wc -l | xargs)
WRITE=$(echo "$METHODS" | egrep 'access\$\d+02\(' | wc -l | xargs)
PREINC=$(echo "$METHODS" | egrep 'access\$\d+04\(' | wc -l | xargs)
PREDEC=$(echo "$METHODS" | egrep 'access\$\d+06\(' | wc -l | xargs)
POSTINC=$(echo "$METHODS" | egrep 'access\$\d+08\(' | wc -l | xargs)
POSTDEC=$(echo "$METHODS" | egrep 'access\$\d+10\(' | wc -l | xargs)
OTHER=$(($ACCESSORS - $METHOD_AND_READ - $WRITE - $PREINC - $PREDEC - $POSTINC - $POSTDEC))

NAME=$(basename $1)

echo -e "$NAME\t$ACCESSORS\t$READ\t$WRITE\t$PREINC\t$PREDEC\t$POSTINC\t$POSTDEC\t$OTHER"

最后使用这个脚本遍历 pull 出来的 APK


$ column -t -s $'\t' \
<(echo -e "NAME\tTOTAL\tMETHOD/READ\tWRITE\tPREINC\tPREDEC\tPOSTINC\tPOSTDEC\tOTHER" \
&& find apks -type f | \
xargs -L1 ./accessors.sh | \
sort -k2,2nr)

相信结果一定令人印象深刻。

解决办法也相当简单，不使用 private 或者使用 package 访问权限。使用 IntelliGate 可以对代码进行检测，并将问题代码高亮，有效的提示你注意这个问题。

Synthetic 方法

Synthetic 方法是自动生成的。而且上面 accessor 并不是唯一的例子，泛型也是其中之一。

// Callbacks.java

interface Callback<T> {
    void call(T value);
}

class StringCallback implements Callback<String> {
    @Override public void call(String value) {
        System.out.println(value);
    }
}

假设我们有一个方法接收一个泛型值，编译后可以发现，这个方法被转换成了两个。一个是我们使用的，另一个的参数却是 Object，这就是类型擦除。我们不得不为它生成方法。

$ javap -c StringCallback
class StringCallback implements Callback<java.lang.String> {
    StringCallback();
        Code: <removed>

    public void call(java.lang.String);
        Code: <removed>

    public void call(java.lang.Object);
        Code:
        0: aload_0
        1: aload_1
        2: checkcast #4 // class java/lang/String
        5: invokevirtual #5 // Method call:(Ljava/lang/String;)V
        8: return
}

查看生成的方法，只是做了类型转换，然后调用实际方法。对于返回值的泛型也是这样

$ javac -bootclasspath android-sdk/platforms/android-24/android.jar \
    Example.java

$ javap -c ViewProvider
class ViewProvider implements Provider<android.view.View> {
    ViewProvider();
        Code: <removed>

    public android.view.View get(android.content.Context);
        Code: <removed>

    public java.lang.Object get(android.content.Context);
        Code:
            0: aload_0
            1: aload_1
            2: invokevirtual #4 // Method get:(…)Landroid/view/View;
            5: areturn
}

许多人还没注意到 Java 的一个特性

class ViewProvider implements Provider<View> {
    @Override public View get(Context context) {
        return new View(context);
    }
}

class TextViewProvider extends ViewProvider {
    @Override public TextView get(Context context) {
        return new TextView(context);
    }
}

你可以将这个返回值限定为一个更具体的类型。这被称为 covariant(协变)返回类型。返回值并不是强制的要像例子里那样实现一个 interface。这个 base class 可以是 interface 也可以是其他任何东西。你可以将 base class 中任何一个方法的返回值类型变成一个更为特定的类。

常用于你在其他类中使用这个方法时，想调用 get 方法获取某个具体的实现类型，而不是更宽广的基类，比如这个例子中的 View。将返回值类型限定为 TextView 是被允许的。

Covariant return type

代价是什么？

$ javap TextViewProvider

class TextViewProvider extends ViewProvider {
    TextViewProvider();
    public android.widget.TextView get(android.content.Context);
    public android.view.View get(android.content.Context);
    public java.lang.Object get(android.content.Context);
}

又出现一个方法。在当前的例子中，它既是一个泛型也是个 covariant 返回值类型。我们把原有的一个方法变成了仨，然而并没有做啥有意义的事。下面的 python 脚本可以用来检测：

#!/usr/bin/python

import os
import subprocess
import sys

list = subprocess.check_output(["dex-method-list", sys.argv[1]])

class_info_by_name = {}

for item in list.split('\n'):
    first_space = item.find(' ')
    open_paren = item.find('(')
    close_paren = item.find(')')
    last_space = item.rfind(' ')

    class_name = item[0:first_space]
    method_name = item[first_space + 1:open_paren]
    params = [param for param in item[open_paren + 1:close_paren].split(', ') if len(param) > 0]
    return_type = item[last_space + 1:]
    if last_space < close_paren:
        return_type = 'void'

    # print class_name, method_name, params, return_type

    if class_name not in class_info_by_name:
        class_info_by_name[class_name] = {}
    class_info = class_info_by_name[class_name]

    if method_name not in class_info:
        class_info[method_name] = []
    method_info_by_name = class_info[method_name]

    method_info_by_name.append({
        'params': params,
        'return': return_type
    })

count = 0
for class_name, class_info in class_info_by_name.items():
    for method_name, method_info_by_name in class_info.items():
        for method_info in method_info_by_name:
            for other_method_info in method_info_by_name:
                if method_info == other_method_info:
                    continue # Do not compare against self.
                params = method_info['params']
                other_params = other_method_info['params']
                if len(params) != len(other_params):
                    continue # Do not compare different numbered parameter lists.

                match = True
                erased = False
                for idx, param in enumerate(params):
                    other_param = other_params[idx]
                    if param != 'Object' and not param[0].islower() and other_param == 'Object':
                        erased = True
                    elif param != other_param:
                        match = False

                return_type = method_info['return']
                other_return_type = other_method_info['return']
                if return_type != 'Object' and other_return_type == 'Object':
                    erased = True
                elif return_type != other_return_type:
                    match = False

                if match and erased:
                    count += 1
                    # print "FOUND! %s %s %s %s" % (class_name, method_name, params, return_type)
                    # print " %s %s %s %s" % (class_name, method_name, other_params, other_return_type)

print os.path.basename(sys.argv[1]) + '\t' + str(count)

想知道这个 case 在应用中有多么普遍，我们会像上面一样遍历所有 apk，耗时会有点长。

$ column -t -s $'\t' \
    <(echo -e "NAME\tERASED" \
        && find apks -type f | \
            xargs -L1 ./erased.py | \
            sort -k2,2nr)

大约有小几千。这种情况我们能做的不多，使用 ProGuard 可以剔除那些没被使用的方法，但是如果你在泛型场景中调用过的方法，将不会被移除。

最后的一个关于方法的例子里，我想讲点未来会出现在 Android 开发中的 Java 8 feature。

class Greeter {
    void sayHi() {
        System.out.println("Hi!");
    }
}
class Example {
    public static void main(String... args) {
        Executor executor = Executors.newSingleThreadExecutor();
        final Greeter greeter = new Greeter();
        executor.execute(new Runnable() {
            @Override public void run() {
                greeter.sayHi();
            }
        });
    }
}

我们已经使用 retro-lamina 有段日子了。Jack compiler 也实现了类似的功能，为了向后兼容。那么这里的性能消耗和新的语言特性之间有什么关联吗？

接下来就看段代码来说。

class Greeter {
    void sayHi() {
        System.out.println("Hi!");
    }
}

class Example {
    public static void main(String... args) {
        Executor executor = Executors.newSingleThreadExecutor();
        Greeter greeter = new Greeter();
        executor.execute(() -> greeter.sayHi());
    }
}

在 lambda 世界里，只是减少了冗余的代码。实际上还是会创建一个 Runnable ，并且隐含了很多内容。你不必再指定其类型，实现的方法名和参数名。
最后，方法引用。因为可以推断出此处不需要接收参数，也不用返回值，我们只要执行这个方法就好，所以可以自动将其转换成 Runnable。

class Greeter {
    void sayHi() {
        System.out.println("Hi!");
    }
}

class Example {
    public static void main(String... args) {
        Executor executor = Executors.newSingleThreadExecutor();
        Greeter greeter = new Greeter();
        executor.execute(greeter::sayHi);
    }
}

How much do these cost?

那么他们各自的性能消耗优势怎样？

Retrolambda toolchain

$ javac *.java

$ java -Dretrolambda.inputDir=. -Dretrolambda.classpath=. \
    -jar retrolambda.jar

$ dx --dex --output=example.dex *.class

$ dex-method-list example.dex


Jack toolchain 

$ java -jar android-sdk/build-tools/24.0.1/jack.jar \
        -cp android-sdk/platforms/android-24/android.jar \
        --output-dex . *.java

$ dex-method-list classes.dex

Jack’s ，这里没有使用 ProGuard ，也不开启 Jack’s 的 minification ，因为对结果没什么影响。当前这个匿名内部类的例子方法数是 2。

Example$1 <init>(Greeter)
Example$1 run()

$ javap -c 'Example$1'
final class Example$1 implements java.lang.Runnable {
    Example$1(Greeter);
        Code: <removed>

    public void run();
        Code:
        0: aload_0
        1: getfield #1 // Field val$greeter:LGreeter;
        4: invokevirtual #3 // Method Greeter.sayHi:()V
        7: return
}

Retrolambda 的旧版本开销比较大，一小段代码就会多生成六七个方法，不过新版本中下降到 4 个。
相比之下，多出来两个方法

Example lambda$main$0(Greeter)
Example$$Lambda$1 <init>(Greeter)
Example$$Lambda$1 lambdaFactory$(Greeter) → Runnable
Example$$Lambda$1 run()

$ javap -c 'Example$$Lambda$1'

final class Example$$Lambda$1 implements java.lang.Runnable {
    public void run();
        Code:
            0: aload_0
            1: getfield #15 // Field arg$1:LGreeter;
            4: invokestatic #21 // Method Example.lambda$main$0:
            7: return
}

最上面的那个方法就是和 jack 不同的地方。当你用 lambda 定义一段代码时，要有个位置存放这段代码。它没有被编码在定义 lambda 的那段代码的方法内，那会很奇怪，因为他不属于那个方法。必须有一个位置保存这段代码，以便在你请求这段代码时调用。
它实际上将和 runnable 实现的那个很像。run 方法和构造函数仍在，只不过 run 函数没有直接调用 Greeter，而是返回原始类调用那段 lambda 方法。

Example lambda$main$0(Greeter)
Example$$Lambda$1 <init>(Greeter)
Example$$Lambda$1 lambdaFactory$(Greeter) → Runnable
Example$$Lambda$1 run()

retrolambda 也没有直接使用生成类的构造函数来实例化，而是用一个静态工厂方法创建它。Jack 基本和他一样，只不过没有这个静态方法。

Example -Example_lambda$1(Greeter)
Example <init>()
Example main(String[])
Example run(Runnable)
Example$-void_main_java_lang_String__args_LambdaImpl0 <init>(Greeter)
Example$-void_main_java_lang_String__args_LambdaImpl0 run()
Greeter <init>()
Greeter sayHi()
java.io.PrintStream println(String)
java.lang.Object <init>()
java.lang.Runnable run()

最上面就是需要额外生成的那个方法。
访问了一个私有方法的话 retrolambda 和 jack 就不得不生成额外方法，实际上这个方法是由 java 产生的，也就是第四个方法。

Jack 现存一个 bug，会为每一个单独的方法引用生成一个 accessor 方法，希望能够尽快修复。

Lambdas in the wild

统计 apk 中的情况


#!/bin/bash             lambdas.sh
set -e

ALL=$(dex-method-list $1)

RL=$(echo "$ALL" | \grep ' lambda\$' | wc -l | xargs)
JACK=$(echo "$ALL" | \grep '_lambda\$' | wc -l | xargs)

NAME=$(basename $1)

echo -e "$NAME\t$RL\t$JACK"

$ column -t -s $'\t' \
    <(echo -e "NAME\tRETROLAMBDA\tJACK" \
        && find apks -type f | \
            xargs -L1 ./lambdas.sh | \
            sort -k2,2nr)

NAME                         RETROLAMBDA     JACK
com.squareup.cash             826             0
com.robinhood.android         680             0
com.imdb.mobile             306             0
com.stackexchange.marvin     174             0
com.eventbrite.attendee     53                 0
com.untappdllc.app             53                 0

显然，使用 lambda 的人还比较少，使用 jack 编译 lambda 的人为 0，再或者他们使用了 ProGuard，lambda 的类名何方法被消除了。

我是因为 65K 方法数的限制才研究的这里，不过实际上这些方法对运行时也会造成影响。

Collections

接下来介绍的内容更偏向于运行时， collections 。

HashMap<K, V>                ArrayMap<K, V>
HashSet<K, V>                ArraySet<V>
HashMap<Integer, V>            SparseArray<V>
HashMap<Integer, Boolean>    SparseBooleanArray
HashMap<Integer, Integer>    SparseIntArray
HashMap<Integer, Long>        SparseLongArray
HashMap<Long, V>            LongSparseArray<V>

这是一组对应的集合，相对于 HashMap ， Android 提供的实现有着显著优势。
以前常听人说自动装箱，将原始类型转换成对象。Java 对于常用的数字有缓存，但是剩下的就需要每次使用时都重新创建一个对象，这会带来很大的性能消耗。
除了上面这点，还有数据寻址和数据的内存布局。
如果你看 HashMap 的源码，他用一个 array 来保存 Node。当你进行存取操作时，都要进入这个 array 执行一个 hash 操作。并且这个 Node array，Node 包含了 key，value，hash，next Node 的引用。想要获取 value 还要进入 Node，再之后获取 value 的引用，跳转到 value，他们都在内存的不同区域。跳来跳去是不是很烦。
还有 hash 碰撞，要做的事更多了。Sparse array 就是用来替代 HashMap 的。在讲之前再说一个优势，内存布局。
下面是两个类

$ java -jar jol-cli-0.5-full.jar internals java.util.HashMap
# Running 64-bit HotSpot VM.
# Objects are 8 bytes aligned.
java.util.HashMap object internals:
OFFSET     SIZE     TYPE DESCRIPTION                 VALUE
0         4         (object header)                 01 00 00 00
4         4         (object header)                 00 00 00 00
8         4         (object header)                 9f 37 00 f8
12         4         Set AbstractMap.keySet             null
16         4         Collection AbstractMap.values     null
20         4         int HashMap.size                 0
24         4         int HashMap.modCount             0
28         4         int HashMap.threshold             0
32         4         float HashMap.loadFactor         0.75
36         4         Node[] HashMap.table             null
40         4         Set HashMap.entrySet             null
44         4         (loss due to the next object alignment)

Instance size: 48 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

一个 HashMap 对象自己要用 48 byte，还不赖。


$ java -jar jol-cli-0.5-full.jar internals 'java.util.HashMap$Node'
# Running 64-bit HotSpot VM.
# Objects are 8 bytes aligned.

java.util.HashMap$Node object internals:
OFFSET     SIZE     TYPE DESCRIPTION     VALUE
0         12         (object header)     N/A
12         4         int Node.hash         N/A
16         4         Object Node.key     N/A
20         4         Object Node.value     N/A
24         4         Node Node.next         N/A
28         4         (loss due to the next object alignment)

Instance size: 32 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

32 bytes. 数组里的每个元素都这么大，你想想乘上数组 size 要有多大。再然后，HashMap 这东西里边还有个叫负载因子的货，它确保 HashMap 不会被填爆，控制 array 增长，这就导致后边永远是空的。默认负载因子控制 array 只使用 75% 。

现在可以看下 Sparse array 的寻址和内存使用情况了。 Sparse array 同时保存两个数组，一个存 key，一个存 value。与 HashMap 不同，查找 key 时，进行的是二分搜索，直接返回 value 对应的 index，就可以拿到 value 了。数组是连续的，跳转少了很多，没有链表，不必要的东西都没了。但是二分搜索带来的是不稳定的时间复杂度，所以保持这个 map 在一个很小的 size 很重要，几百个差不多，上千的话还是 HashMap 更好。

$ javac SparseArray.java

$ java -cp .:jol-cli-0.5-full.jar org.openjdk.jol.Main \
internals android.util.SparseArray

# Running 64-bit HotSpot VM.
# Objects are 8 bytes aligned.

android.util.SparseArray object internals:
OFFSET     SIZE     TYPE DESCRIPTION                 VALUE
0         4         (object header)                 01 00 00 00
4         4         (object header)                 00 00 00 00
8         4         (object header)                 1a 69 01 f8
12         4         int SparseArray.mSize             0
16         1         boolean SparseArray.mGarbage     false
17         3         (alignment/padding gap)         N/A
20         4         int[] SparseArray.mKeys         [0, 0, 0, 0, 0, 0, …]
24         4         Object[] SparseArray.mValues     [null, null, null, …]
28         4         (loss due to the next object alignment)

Instance size: 32 bytes
Space losses: 3 bytes internal + 4 bytes external = 7 bytes total

JVM 64 bit 和 Android 64 bit 应该差不多，简单看下就好，领会精神。
对象大小其实无关紧要，重要的是内部元素。 key 和 value。SparseArray 虽然没有负载因子，但是这些数组是隐式的树，所以实际上也有空置的空间。这里只能将它模糊的描述为和负载因子差不多内存消耗。实际情况取决于你存储的数据形式。列出一个假想的内存消耗计算公式：

SparseArray<V>
32 + (4 * entries + 4 * entries) / 0.75

HashMap<Integer, V>
48 + 32 * entries + 4 * (entries / loadFactor) + 8

一个实例，50 个元素，二分搜索超快

SparseArray<V>
32 + (4 * 50 + 4 * 50) / 0.75 = 656

HashMap<Integer, V>
48 + 32 * 50 + 4 * (50 / 0.75) + 8 = 1922

Conclusion

打开 private member inspection 选项
RetroLambda 要用最新版本
试试 Jack (Ps. Jack已经挂了)
开启 ProGuard
不要使用 ProGuard 中的 * * 规则，100% 错误的用法

Res

Ref

https://news.realm.io/news/360andev-jake-wharton-java-hidden-costs-android/