प्रदर्शन अचानक का एक पहलू ~ 10

Question

पृष्ठभूमि की जानकारी

मैं हाल ही में एल्गोरिदम और datastructures पर मेरी कक्षा के लिए असाइनमेंट में सौंप दिया द्वारा बढ़ जाती है। असाइनमेंट बेतरतीब ढंग से जेनरेट किए गए सरणी के maximum-subarray को खोजने के लिए समाधान लागू करना था। हमें एक ब्रूट फोर्स एल्गोरिदम, और एक रिकर्सिव डिवाइड-एंड-विजय एल्गोरिदम लागू करने के लिए कहा गया था।

हमें तब चलने वाले समय का विश्लेषण करने के लिए कहा गया था, यह देखने के लिए कि किस समस्या का आकार ब्रूट फोर्स एल्गोरिदम रिकर्सिव समाधान से तेज़ होगा। यह समस्या के आकार को बढ़ाने के लिए चलने वाले समय (सिस्टम.नानोटाइम() मापों का उपयोग करके) एल्गोरिदम दोनों को मापकर किया गया था।

हालांकि, यह निर्धारित करने से मुझे थोड़ा सा ट्रिकियर लगता है।

जिज्ञासा

अगर मैं, पुनरावर्ती एल्गोरिदम के लिए समय से चल रहा है चला जाता है, एक रन से अगले करने के लिए 10 से अधिक बार 5000 की समस्याओं आकारों के साथ एल्गोरिदम के दोनों चल रहा है, एक से, द्वारा शुरू लगभग 10 के कारक (~ 1800μS से निष्पादित करने के लिए, ~ 200μS निष्पादित करने के लिए) और यह शेष पुनरावृत्तियों के लिए बहुत तेज़ रहता है। एक उदाहरण के लिए नीचे चित्र देखें

2 और 3 स्तंभ सिर्फ सत्यापित करने के लिए किया जाता है कि दोनों एल्गोरिदम सही अधिकतम subarray

यह जावा 1.6.0_29 साथ ओएस एक्स 10.7.3 पर परीक्षण किया गया था वापसी - विंडोज 7 और जावा 1.6 (सटीक संस्करण संख्या अज्ञात) चलाने वाले पीसी पर निष्पादित होने पर परिणाम समान थे।

कार्यक्रम के लिए स्रोत कोड यहां पाया जा सकता: क्या एल्गोरिथ्म अचानक कि ज्यादा बेहतर प्रदर्शन करने के लिए जा रहा है "गरम" के बाद का कारण बनता है: https://gist.github.com/2274983

मेरा प्रश्न है?

Answer 1

टिप्पणीकारों ने पहले ही बताया है कि जेआईटी इस व्यवहार के कारण होने की संभावना है, लेकिन ऐसा लगता है कि ओपी को यह नहीं पता कि वह क्या है। जावा बाईटकोड व्याख्या

1. : तो बस संक्षिप्त व्याख्या करने के लिए:

   आपका जावा वर्चुअल मशीन 2 तरीकों से एक कार्यक्रम चला सकते हैं। असल में, दुभाषिया बाइटकोड पर एक-एक करके "चलता है", यह जांचता है कि प्रत्येक क्या है, और इसी क्रिया को निष्पादित करता है।

2. बाइटकोड को मशीन कोड में कनवर्ट करना, जो अंतर्निहित सीपीयू सीधे चला सकता है। इसे "जस्ट-इन-टाइम संकलन" या जेआईटी कहा जाता है।

कार्यक्रम जो मशीन कोड को JIT'd दिया है अब तक तेजी से चलाते हैं, लेकिन संकलन समय है, जो कार्यक्रम शुरू हुआ धीमी कर सकता है लेता है। तो आपका JVM एक समझौता करता है: शुरुआत में यह केवल बाइटकोड का अर्थ देता है, लेकिन यदि एक निश्चित विधि को कई बार निष्पादित किया जाता है, तो यह JIT संकलित करता है कि व्यक्तिगत विधि केवल है। आम तौर पर प्रोग्राम कोड का केवल एक छोटा हिस्सा कई बार निष्पादित किया जाएगा (आंतरिक लूप, इत्यादि) इसलिए यह रणनीति प्रभावी है।

इसका अपवाद यह है कि जब आप प्रदर्शन-परीक्षण जावा कोड होते हैं, तो आपको पहले एक लूप में अपना कोड चलाकर JVM को "गर्म" करना होगा कि प्रदर्शन-महत्वपूर्ण विधियां सभी जेआईटी संकलित हैं।

इस मामले में, आपके रिकर्सिव समाधान को ब्रूट फोर्स समाधान की तुलना में जेआईटी संकलन से बहुत अधिक लाभ होता है। यह इंगित कर सकता है कि जेआईटी कंपाइलर कुछ ऑप्टिमाइज़ेशन ढूंढ रहा है जो रिकर्सिव समाधान को बहुत लाभ देता है - शायद उन रिकर्सिव कॉल को पुनरावर्तक कोड में परिवर्तित कर रहा है?

Answer 2

एक सुझाव, आपके कोड की किसी भी पंक्ति को पढ़ने के बिना, जब आप अपने आवेदन को "गर्म" करते हैं, तो आप अपने वीएम को अपने उपकरण के लिए तय की गई कुछ मात्रा में स्मृति प्राप्त करते हैं।

उदाहरण के लिए, अपने 5000 सरणी इकाइयों को एक ऐरेलिस्ट में कहें- एक-एक करके। ऐरे सूची एक निश्चित आकार से शुरू होती है और जब यह पहुंच जाती है तो इसकी सीमा सीमित होती है और इसे पुराने आकार में कॉपी किया जाता है। यदि आप इस ArrayList का पुन: उपयोग करते हैं- दूसरे भाग में यह सूची सही आकार में होगी और तेजी से काम करेगी।

यह स्थिति कुछ अन्य स्थानों में हो सकती है।

Answer 3

मेरा सुझाव है कि आप -XX:+PrintCompliation के साथ दौड़ें और आपको लगभग 10,000 कॉल या पुनरावृत्तियों के बाद देखना चाहिए, महत्वपूर्ण विधियों को संकलित किया गया है। यह आपको दिखाएगा कि किन तरीकों से अंतर आया है यदि आप देखना चाहते हैं कि क्या कोड देखना है यदि आप जानना चाहते हैं कि क्या देखना है। संकलन का पूरा बिंदु आपके कोड के प्रदर्शन में सुधार करना है।

---

आपको अप्रत्याशित कोड के लिए सबसे तेज़ गति मिलेगी। असल में मैं कहूंगा कि जावा कोड चलाने के लिए सबसे कुशल भाषाओं में से एक है जो कुछ भी नहीं करता है।

एक निष्पक्ष उदाहरण के लिए, आप कोड का अनुकूलन करने की जरूरत है, तो मैं

• Math.floor गिरा() यह कुछ भी नहीं है, (hi + lo) /2 हमेशा एक पूर्णांक है। ऐसा करने का सबसे तेज़ और सुरक्षित तरीका (hi + lo) >>> 1
• अधिकतम प्राप्त करने के लिए Math.max का उपयोग किया जाता है।
• अधिकतम 0 पर पहुंचने पर योग लूप को रोकने के लिए break; जोड़ा गया।

मेरे लिए यह 70% तक कटौती करता है, मुझे प्राप्त अनुपात 110 गुना है।