जेवीएम के लुकअपस्विच और टेबलस्विच के बीच अंतर?

Question

मुझे जावा बाइटकोड में लुकअपविच और टेबलस्विच को समझने में कुछ कठिनाई है।

यदि मैं अच्छी तरह से समझता हूं, तो LookUpSwitch और TableSwitch दोनों जावा स्रोत के switch कथन से मेल खाते हैं? क्यों एक जावा स्टेटमेंट 2 अलग बाइटकोड उत्पन्न करता है?

जैस्मिन प्रत्येक के प्रलेखन:

• LookupSwitch
• tableswitch

Answer 1

अंतर यह है कि एक lookupswitch एक तालिका का उपयोग करता कुंजी के साथ और लेबल, अभी तक एक tableswitch का उपयोग करता है लेबल केवल के साथ एक मेज है।

टेबलविच निष्पादित करते समय, स्टैक के शीर्ष पर int मान सीधे कूदने के गंतव्य को पकड़ने के लिए तालिका में एक सूचकांक के रूप में उपयोग किया जाता है और तुरंत कूदता है। संपूर्ण लुकअप + कूद प्रक्रिया ओ (1) ऑपरेशन है, जिसका अर्थ है कि यह तेजी से चमक रहा है।

जब एक lookupswitch प्रदर्शन, ढेर के शीर्ष पर पूर्णांक मूल्य तक कोई मिलान पाया जाता तालिका में कुंजी के खिलाफ तुलना की जाती है और उसके बाद इस कुंजी के बगल में कूद गंतव्य कूद प्रदर्शन करने के लिए प्रयोग किया जाता है। चूंकि लुकअपविच टेबल हमेशा को सॉर्ट किया जाना चाहिए ताकि प्रत्येक एक्स < वाई के लिए कीएक्सएक्स < कुंजी वाई, संपूर्ण लुकअप + कूद प्रक्रिया ओ (लॉग एन) ऑपरेशन है क्योंकि कुंजी को बाइनरी खोज एल्गोरिदम का उपयोग करके खोजा जाएगा (यह है एक मैच खोजने के लिए या यह निर्धारित करने के लिए कि कोई भी कुंजी मिलान नहीं करता है) के लिए सभी संभावित कुंजी के विरुद्ध int मान की तुलना करना आवश्यक नहीं है। ओ (लॉग एन) ओ (1) से कुछ हद तक धीमा है, फिर भी यह अभी भी ठीक है क्योंकि कई प्रसिद्ध एल्गोरिदम ओ (लॉग एन) हैं और इन्हें आमतौर पर तेज़ माना जाता है; यहां तक ​​कि ओ (एन) या ओ (एन * लॉग एन) अभी भी एक बहुत अच्छा एल्गोरिदम माना जाता है (धीमी/खराब एल्गोरिदम में ओ (एन^2), ओ (एन^3), या इससे भी बदतर) है।

निर्णय का उपयोग करने का निर्णय संकलक द्वारा किया गया है कि कॉम्पैक्ट स्विच स्टेटमेंट है, उदाहरण के लिए

switch (inputValue) { 
    case 1: // ... 
    case 2: // ... 
    case 3: // ... 
    default: // ... 
} 

ऊपर स्विच पूरी तरह कॉम्पैक्ट है, इसमें कोई संख्यात्मक "छेद" नहीं है।संकलक इस तरह एक tableswitch पैदा करेगा:

tableswitch 1 3 
    OneLabel 
    TwoLabel 
    ThreeLabel 
    default: DefaultLabel 

जैस्मिन पेज से छद्म कोड बहुत अच्छी तरह से इस बताते हैं:

int val = pop();    // pop an int from the stack 
if (val < low || val > high) { // if its less than <low> or greater than <high>, 
    pc += default;    // branch to default 
} else {      // otherwise 
    pc += table[val - low];  // branch to entry in table 
} 

इस कोड को कैसे इस तरह के एक tableswitch काम करता है पर बहुत स्पष्ट है। valinputValue है, low 1 (स्विच में सबसे कम केस मूल्य) होगा और high 3 होगा (स्विच में उच्चतम केस मान)।

कुछ छेद के साथ भी एक स्विच कॉम्पैक्ट हो सकता है, उदा।

switch (inputValue) { 
    case 1: // ... 
    case 3: // ... 
    case 4: // ... 
    case 5: // ... 
    default: // ... 
} 

उपरोक्त स्विच "लगभग कॉम्पैक्ट" है, इसमें केवल एक छेद है।

tableswitch 1 6 
    OneLabel 
    FakeTwoLabel 
    ThreeLabel 
    FourLabel 
    FiveLabel 
    default: DefaultLabel 

    ; <...code left out...> 

    FakeTwoLabel: 
    DefaultLabel: 
    ; default code 

आप देख सकते हैं, संकलक 2, FakeTwoLabel के लिए एक नकली मामले को जोड़ने के लिए है: एक संकलक निम्नलिखित अनुदेश उत्पन्न कर सकता है। चूंकि 2 स्विच का कोई वास्तविक मूल्य नहीं है, इसलिए FakeTwoLabel वास्तव में एक लेबल है जो डिफ़ॉल्ट रूप से कोड प्रवाह को बदलता है जहां डिफ़ॉल्ट मामला स्थित है, क्योंकि 2 के मान को वास्तव में डिफ़ॉल्ट केस निष्पादित करना चाहिए।

तो एक स्विच को एक टेबलविच बनाने के लिए कंपाइलर के लिए पूरी तरह कॉम्पैक्ट नहीं होना चाहिए, फिर भी इसे कम से कम कॉम्पैक्टनेस के करीब होना चाहिए। अब निम्नलिखित स्विच पर विचार करें:

switch (inputValue) { 
    case 1: // ... 
    case 10: // ... 
    case 100: // ... 
    case 1000: // ... 
    default: // ... 
} 

यह स्विच कहीं नहीं सघनता के पास है, यह एक से अधिक सौ गुना अधिक मूल्यों से छेद है। कोई इसे एक अतिरिक्त स्विच कहता है। इस स्विच को टेबलविच के रूप में व्यक्त करने के लिए कंपाइलर को लगभग हजार नकली मामले उत्पन्न करना होगा। परिणाम नाटकीय रूप से कक्षा फ़ाइल के आकार को उड़ाने, एक विशाल मेज होगी। यह व्यावहारिक नहीं है। इसके बजाय यह एक लुकअपविच उत्पन्न करेगा:

lookupswitch 
    1  : Label1 
    10  : Label10 
    100  : Label100 
    1000 : Label1000 
    default : DefaultLabel 

इस तालिका में हजारों से अधिक की बजाय केवल 5 प्रविष्टियां हैं। तालिका में 4 वास्तविक मान हैं, ओ (लॉग 4) 2 है (लॉग यहां 2 बीटीडब्लू के आधार पर लॉग है, न कि 10 के आधार पर, क्योंकि कंप्यूटर द्विआधारी संख्याओं पर काम करता है)। इसका मतलब यह है कि इनपुट Value के लिए लेबल खोजने के लिए या निष्कर्ष पर आने के लिए यह दो तुलनाओं में वीएम लेता है, मान तालिका में नहीं है और इस प्रकार डिफ़ॉल्ट मान निष्पादित किया जाना चाहिए। यहां तक ​​कि यदि तालिका में 100 प्रविष्टियां थीं, तो यह सही लेबल खोजने के लिए अधिकतम 7 तुलनाओं में वीएम ले जाएगा या डिफ़ॉल्ट लेबल पर कूदने का फैसला करेगा (और 7 तुलना 100 तुलनाओं से बहुत कम है, आपको नहीं लगता?)।

तो यह बकवास है कि ये दो निर्देश एक दूसरे के लिए परिवर्तनीय हैं या दो निर्देशों के कारण ऐतिहासिक कारण हैं। दो अलग-अलग प्रकार की स्थितियों के लिए दो निर्देश हैं, एक कॉम्पैक्ट मूल्यों (अधिकतम गति के लिए) के साथ स्विच के लिए और एक अतिरिक्त मूल्यों के साथ स्विच के लिए (अधिकतम गति, अभी भी अच्छी गति और बहुत ही कॉम्पैक्ट टेबल प्रतिनिधित्व सभी संख्यात्मक छेदों के बावजूद)।

Answer 2

मुझे लगता है यह जावा बाईटकोड के कुछ विशिष्ट बंधन मशीन कोड को रेखांकित करने के ज्यादातर ऐतिहासिक है, के कारण (जैसे सूर्य की अपनी सीपीयू)।

टेबलविच अनिवार्य रूप से एक गणना की गई कूद है, जहां एक लुकअप टेबल से गंतव्य लिया जाता है। इसके विपरीत लुकअपविच के लिए प्रत्येक मान की तुलना की आवश्यकता होती है, मूल रूप से एक पुनरावृत्ति कठिन तालिका तत्व जब तक मिलान मान नहीं मिलता है।

जाहिर है कि उन ऑपोड्स अदला-बदले हैं, लेकिन मानों के आधार पर, एक या दूसरा तेज या अधिक कॉम्पैक्ट हो सकता है (उदाहरण के बीच बड़े अंतर के साथ चाबियों के सेट की तुलना करें और चाबियों के अनुक्रमिक सेट)।

Answer 3

Java Virtual Machine Specification अंतर का वर्णन करें। "टेबलविच निर्देश का उपयोग तब किया जाता है जब स्विच के मामलों को लक्षित ऑफसेट्स की एक तालिका में सूचकांक के रूप में कुशलता से दर्शाया जा सकता है।" विनिर्देश अधिक जानकारी का वर्णन करता है।

Answer 4

जब वास्तव में javac 1.8.0_45 किसी भी को संकलित स्विच करता है?

यह तय करने के लिए कि किस समय उपयोग करना है, आप javac विकल्प एल्गोरिदम का आधार के रूप में उपयोग कर सकते हैं।

हम जानते हैं कि javac का स्रोत langtools रेपो में है।

फिर हम grep:

hg grep -i tableswitch 

और पहला परिणाम langtools/src/share/classes/com/sun/tools/javac/jvm/Gen.java है:

// Determine whether to issue a tableswitch or a lookupswitch 
// instruction. 
long table_space_cost = 4 + ((long) hi - lo + 1); // words 
long table_time_cost = 3; // comparisons 
long lookup_space_cost = 3 + 2 * (long) nlabels; 
long lookup_time_cost = nlabels; 
int opcode = 
    nlabels > 0 && 
    table_space_cost + 3 * table_time_cost <= 
    lookup_space_cost + 3 * lookup_time_cost 
    ? 
    tableswitch : lookupswitch; 

कहाँ:

• hi: अधिकतम मामले मूल्य
• lo: न्यूनतम मामले मूल्य

तो हम निष्कर्ष है कि यह समय जटिलता के लिए की एक वजन के साथ, दोनों समय और स्थान जटिलता को ध्यान में लेता है।

TODO मुझे समझ में नहीं आता कि lookup_time_cost = nlabels और log(nlabels) नहीं, क्योंकि tableswitch बाइनरी खोज के साथ ओ (लॉग (एन)) में किया जा सकता है।

बोनस: सी ++ कार्यान्वयन भी कर एक ओ के बीच एक अनुरूप विकल्प (1) कूद मेज और हे (लंबी (एन)) द्विआधारी खोज: Advantage of switch over if-else statement