打包开关和稀疏开关dalvik操作码之间的区别

Question

我想知道dalvik中打包交换机和稀疏交换机操作码之间的区别.如果你能提供例子,请.我不清楚谷歌提供的解释.

打包开关 稀疏开关

谢谢.

Answer 1

这听起来好像packed-switch是等同于Java的tableswitch,并sparse-switch给lookupswitch.

A packed-switch使用一个简单的跳转表,由表单索引low + n,其中low是case标签中最低的测试值,并且n是输入switch.每个索引处的值表示每个索引的字节码偏移量case.找到正确的跳转地址是一个恒定时间操作.

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

编译器将选择使用哪个.如果密钥往往聚集在一起或紧密堆积在一起,则可以有效地发出packed-switch(或者,在Java术语中,a tableswitch).但是如果键是稀疏的,并且values(high - low + 1)的范围很大,则使用跳转表将需要大块字节码,因为该范围内的所有值必须存在于跳转表中,无论是否存在相应的case标签.在这些场景中,编译器将发出一个sparse-switch(lookupswitch).

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

我们来看一些例子.考虑以下Java代码,它将产生一个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";
    }
}

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

请注意,几百个插槽中只有三个实际上指向case原始代码中的标签.其余的只是填补跳转表.空间效率不是很高,是吗？这就是编译器发出的原因sparse-switch,这个特定的例子具有更紧凑的字节码占用空间:

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