जावा में लुकअप टेबल का उपयोग करने से कई कोड या "कथन" के साथ यह कोड थोड़ा तेज़ क्यों है?

Question

मैंने माइक्रो-ऑप्टिमाइज़ेशन प्रश्न को देखते हुए कल (here) देखा, मुझे कुछ अजीब मिला: जावा में कथन थोड़ा बूलियन की एक सरणी में एक बूलियन मान को देखने से तेज़ी से चल रहा है।

मेरे परीक्षणों में, long पर 0 से 1 बिलियन के मानों के नीचे एल्गोरिदम चलाते हुए, alg1 लगभग 2% तेज है। (मैंने ऑर्डर को बदल दिया है जिसमें एल्गोरिदम का परीक्षण किया गया है, और मुझे एक ही परिणाम मिलते हैं)। मेरा सवाल है: alg1 तेज़ क्यों है? मुझे उम्मीद है कि यह एक लुकअप टेबल का उपयोग करने के बाद से alg2 थोड़ा तेज होगा, जबकि alg1 को 4 तुलनाओं और 3 या संचालन के 75% इनपुट के लिए निष्पादित करना होगा।

private final static boolean alg1(long n) 
{ 
    int h = (int)(n & 0xF); 
    if(h == 0 || h == 1 || h == 4 || h == 9) 
    { 
    long tst = (long)Math.sqrt(n); 
    return tst*tst == n; 
    } 
    return false; 

} 

private final static boolean[] lookup = new boolean[16]; 
static 
{ 
    lookup[0] = lookup[1] = lookup[4] = lookup[9] = true; 
} 
private final static boolean alg2(long n) 
{ 
    if(lookup[(int)(n & 0xF)]) 
    { 
    long tst = (long)Math.sqrt(n); 
    return tst*tst == n; 
    } 
    else 
    return false; 
} 

आप उत्सुक हैं, तो इस कोड को अगर एक नंबर एक पूर्ण वर्ग है, और तथ्य यह है कि सही वर्गों में 0, 1, 4, या 9 में हेक्स समाप्त होना चाहिए इस्तेमाल परीक्षण कर रहा है।

Answer 1

डेटा के कुछ यादृच्छिक टुकड़े लोड करना आम तौर पर थोड़ा गैर-ब्रांचिंग कोड से धीमा होता है।

यह सब प्रोसेसर आर्किटेक्चर पर निर्भर करता है। आपका पहला अगर कथन चार निर्देशों के रूप में लागू किया जा सकता है। दूसरे को संभावित रूप से शून्य सूचक जांच की आवश्यकता हो सकती है, सीमाओं की जांच के साथ-साथ लोड और तुलना की आवश्यकता होती है। इसके अलावा अधिक कोड का मतलब अधिक संकलित समय है, और ऑप्टिमाइज़ेशन को किसी तरीके से इंपीड करने का अधिक मौका है।

Answer 2

this article तक पहुँचने सरणी तत्वों के अनुसार, "गैर सरणी तत्वों तक पहुँचने के रूप में महंगा के रूप में 2 या 3 बार" कर रहे हैं। आपका परीक्षण दिखाता है कि अंतर भी बड़ा हो सकता है।

Answer 3

मैं अनुमान अनुमान लगाता हूं कि समस्याएं सरणी के लिए जांच कर रही हैं और यदि सरणी लुकअप विधि कॉल के रूप में लागू किया गया है। यह निश्चित रूप से 4 सीधे int तुलनाओं को ढंक देगा। क्या आपने बाइट कोड देखा है?

Answer 4

यह कोड का एक दिलचस्प टुकड़ा है, लेकिन 2% वास्तव में एक छोटा अंतर है। मुझे नहीं लगता कि आप इससे बहुत कुछ निष्कर्ष निकाल सकते हैं।

Answer 5

वर्तमान उदाहरण में, मैं मानता हूँ कि सीमा की जाँच संभव है कि आप हो रही है (क्यों JVM इस बाहर अनुकूलन नहीं करता मुझे परे है - नमूना कोड निर्धारणात्मक अतिप्रवाह नहीं दिखाया जा सकता है हो सकता है ...

एक और संभावना (विशेष रूप से बड़ी लुकअप टेबल के साथ) कैश विलंबता है ... यह प्रोसेसर के रजिस्टरों के आकार पर निर्भर करता है और कैसे JVM उन्हें उपयोग करने का विकल्प चुनता है - लेकिन यदि बाइट सरणी प्रोसेसर पर पूरी तरह से नहीं रखी जाती है, तो आप 'करूँगा एक प्रदर्शन हिट एक सरल करने के लिए या के रूप में सरणी प्रत्येक चेक के लिए CPU पर खींचा जाता है की तुलना में देखते हैं।