java - packed switch 和 sparse switch dalvik操作码的区别

Question

我想知道 dalvik 中 packed switch 和 sparse switch 操作码的区别。如果你能提供例子，请。谷歌提供的解释我不清楚。

packed-switch sparse switch

谢谢。

Answer 1

听起来好像packed-switch相当于Java的tableswitch，sparse-switch相当于lookupswitch .

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

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

编译器将选择使用哪个。如果键倾向于聚集在一起或紧密地打包，则可以使用packed-switch(或者，在 Java 术语中，tableswitch)高效排放。但是如果键稀疏，并且值的范围(high - low + 1)很大，那么使用跳转表将需要一大块字节码，因为无论是否有相应的 case 标签，该范围内的所有值都必须存在于跳转表中。在这些情况下，编译器将发出一个 sparse-switch (lookupswitch)。

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

让我们看一些例子。考虑以下 Java 代码，它将生成一个 tableswitch(并且在转换为 Dalvik 时生成一个 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，对于这个特定示例，它具有更紧凑的字节码足迹:

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