الفرق بين التبديل المعبأ والمفتاح المتفرق Dalvik Opcode

Question

أريد أن أعرف الفرق بين التبديل المعبأ والرموز المتفرقة في Dalvik. من فضلك إذا كنت تستطيع تقديم أمثلة. التفسير الذي قدمته Google غير واضح بالنسبة لي.

تبديل معبأة مفتاح متفرق

شكرًا.

Answer 1

يبدو كما لو packed-switch يعادل جافا tableswitch, ، و sparse-switch إلى lookupswitch.

أ packed-switch يستخدم جدول قفزة بسيط ، مفهرس بواسطة النموذج low + n, ، أين low هي أدنى قيمة اختبار بين case تسميات ، و n هو المدخلات إلى switch. تمثل القيم الموجودة في كل فهرس إزاحة Bytecode لكل منها case. العثور على عنوان القفز الصحيح هو عملية وقت ثابت.

أ sparse-switch يستخدم قائمة مصنفة من أزواج القيمة الرئيسية ، حيث يكون كل مفتاح قيمة اختبار من أ case التسمية ، والقيم هي القفز على تعويضات. العثور على هدف القفز الصحيح ل lookupswitch يتطلب بحثًا ثنائيًا على المفتاح ، لذلك فهو عملية لوجاريتمية.

سيختار التحويل البرمجي الذي يجب استخدامه. إذا كانت المفاتيح تميل إلى التجميع أو معباه عن كثب معا ، ثم أ packed-switch (أو ، من حيث Java ، أ tableswitch) يمكن أن تنبعث بكفاءة. ولكن إذا كانت المفاتيح متناثر, ونطاق القيم (high - low + 1) كبير ، فإن استخدام جدول القفز يتطلب كتلة كبيرة من رمز bytecode ، حيث يجب أن توجد جميع القيم في هذا النطاق في جدول القفز بغض النظر عما إذا كان هناك مقابل case ضع الكلمة المناسبة. في هذه السيناريوهات ، سوف ينبعث المترجم sparse-switch (lookupswitch).

ومن المثير للاهتمام ، أن مهندسي Dalvik اختاروا تسمية هذه الرموز opcons بطريقة تصف التوزيعات الرئيسية التي يجب استخدامها ، في حين اختار مهندسو Java الأسماء التي تصف هياكل البيانات المفاهيمية التي تشبه معاملات Bytecode.

دعونا نلقي نظرة على بعض الأمثلة. النظر في رمز Java التالي ، والذي سينتج tableswitch (وعند تحويله إلى دالفيك ، أ 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 سيبدو رمز Opcode مثل هذا:

كما ترون ، إنه مضغوط إلى حد ما. ثلاثة من الفتحات الخمس تشير إلى الفعلية 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, ، التي لديها بصمة باخرة أكثر إحكاما لهذا المثال بالذات:

الآن ، هذا أكثر منطقية ، ألا تعتقد ذلك؟ ومع ذلك ، فإن الجانب السلبي هو أنه بدلاً من معرفة أي فهرس بالضبط الذي يجب القفز إليه بناءً على الإدخال ، يتعين علينا إجراء بحث ثنائي على الجدول حتى نجد قيمة اختبار مطابقة. كلما زاد التبديل ، زاد التأثير على الأداء ، على الرغم من أن التأثير له منحنى لوغاريتمي.