8

我想知道 dalvik 中打包开关和稀疏开关操作码之间的区别。请您提供示例。谷歌提供的解释对我来说不清楚。

打包开关 稀疏开关

谢谢。

4

1 回答 1

20

听起来好像packed-switch等同于 Java 的tableswitch,sparse-switch和lookupswitch.

Apacked-switch使用一个简单的跳转表，以 形式索引low + n，其中low是case标签中最低的测试值，n是 的输入switch。每个索引处的值表示每个case. 找到正确的跳转地址是一个常数时间的操作。

Asparse-switch使用键值对的排序列表，其中每个键是case标签中的测试值，值是跳转偏移量。为 a 找到正确的跳转目标lookupswitch需要对键进行二分搜索，因此它是对数时间操作。

编译器将选择使用哪个。如果键倾向于聚集或紧密地打包在一起，则可以有效地发出a packed-switch（或者，在 Java 术语中， a ）。tableswitch但是如果键是稀疏的，而值的high - low + 1范围case（ . 在这些情况下，编译器将发出sparse-switch( lookupswitch)。

有趣的是，Dalvik 工程师选择以描述应该使用它们的密钥分布的方式命名这些操作码，而 Java 工程师选择描述字节码操作数类似的概念数据结构的名称。

让我们看一些例子。考虑以下 Java 代码，它将产生 a tableswitch（并且，当转换为 Dalvik 时， a packed-switch）：

static String packedSwitch(final int n) {
    switch (n) {
        case 5:
            return "Five";
        case 3:
            return "Three";
        case 1:
            return "One";
        default:
            return "Other";
    }
}

从概念上讲，packed-switch操作码的有效负载看起来像这样：

实际打包开关

如您所见，它相当紧凑。五个插槽中的三个指向实际case目标，其余两个跳转到default目标。但是，如果我们的测试值更加分散怎么办？

static String sparseSwitch(final int n) {
    switch (n) {
        case 500:
            return "Five Hundred";
        case 300:
            return "Three Hundred";
        case 100:
            return "One Hundred";
        default:
            return "Other";
    }
}

如果编译器尝试将其作为 发出packed-switch，则有效负载将如下所示：

理论打包开关

注意几百个槽中只有三个实际上指向case原始代码中的标签。其余的只是为了填满跳跃表。不是很节省空间，是吗？这就是为什么编译器会发出一个sparse-switch，对于这个特定的例子来说，它的字节码占用要紧凑得多：

稀疏开关

现在，这更合理，你不觉得吗？然而，缺点是我们不能根据输入准确地知道要跳转到哪个索引，而是必须对表执行二进制搜索，直到找到匹配的测试值。开关越大，对性能的影响越显着，尽管该影响具有对数曲线。

于 2013-11-08T12:15:06.750 回答