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

यह पता चला कि यह ऑपरेशन "सरल" के रूप में नहीं है जैसा कि लगता है, खासकर अगर हम इसे आधुनिक भाषाओं में एक आभासी मशीन के साथ मानते हैं। नीचे मैं दिखाऊंगा कि कैसे आप एक-लाइन के समाधान को दर्जनों लाइनों के एक जोड़े के समाधान के साथ बदल सकते हैं, एल्गोरिदम के प्रदर्शन को ~ 10 गुना बढ़ा सकते हैं। मैं अभी यह कहना चाहूंगा कि उदाहरण जावा पर लागू होंगे, लेकिन अधिकांश अन्य भाषाओं और आभासी मशीनों के लिए समान विचार सत्य होंगे - मुख्य रूप से .NET- आधारित के लिए।

वास्तव में, एल्गोरिथ्म की संपूर्ण गतिविधि निम्न से घट गई:

बाहर से प्राप्त करें (नेटवर्क या डिस्क) एन फ़ील्ड का एक सेट: ( _{1 में} , _{2 में} , ..., _{एन में} )
एक दर्जन सरल ऑपरेशन जैसे कि सरल परिस्थितियों के लिए चेक के साथ बाहर नकल करना
नियंत्रण वर्णों से सभी पंक्तियाँ ( ₁ , आउट ₂ , ..., आउट _m ) साफ़ करें
उन्हें और स्थानांतरित करें (डिस्क पर जलाएं या नेटवर्क पर भेजें)

मेरे दृष्टिकोण से, ऐसे कार्य के लिए एक डिस्क या नेटवर्क पर आराम करना तर्कसंगत होगा - प्रोसेसर लोड यहां कम से कम होना चाहिए। हालांकि, सरलतम रूपरेखा ने एक पूरी तरह से अलग चीज दिखाई। मूल संस्करण में एक पंक्ति शामिल थी, जो एल्गोरिथम के कामकाजी समय का 80-90% खर्च करती थी - यह बिल्कुल एक पंक्ति थी, जिसने ऑपरेशन 3 किया, यहां यह है:

विकल्प 1

s = s.replaceAll("\\p{Cntrl}", "");

मुझे यह भी पता है कि यह लाइन कहां से आई थी - वाक्यांश "जावा स्ट्रिप नॉन-प्रिंटेबल कैरेक्टर" के लिए एक त्वरित Google खोज इस विशेष विकल्प की पैदावार देती है। इसलिए, कार्य स्पष्ट है, लक्ष्य स्पष्ट हैं, प्रोग्रामर का गौरव आहत है ("ऐसा कैसे हो सकता है कि मैं वास्तव में इस दुर्भाग्यपूर्ण रेखा को फैल नहीं सकता"), चलें!

हम एक साधारण स्ट्रैपिंग को कोड़ा मारते हैं जो एल्गोरिथम के चलने के समय को मापता है, इसे बाकी कोड से अलग करता है, एक परीक्षण इनपुट लाइन उत्पन्न करता है जिसे हम एल्गोरिथ्म के माध्यम से लाखों बार चलाएंगे और प्रदर्शन को मापेंगे। यह पता चला है कि पहला विकल्प प्रति सेकंड 517009 लाइनों को संसाधित करता है । हम कई माप लेते हैं, हम समझते हैं कि हमारे माप और प्रयोगों की सटीकता लगभग 2-3% है - अर्थात्। मोटे तौर पर, आप अंतिम 4 अंकों को बिल्कुल नहीं देख सकते हैं, और अंत से पांचवें अंक को देख सकते हैं, लेकिन नहीं देख सकते हैं। यानी कहीं 500..540 हजार के बीच परिणाम।

हम याद करते हैं कि वास्तव में हमारे पास लाइनों के लिए क्या है और हमें फ़िल्टर करने के लिए क्या चाहिए और \p{Cntrl} । हम समझते हैं कि यह तत्व अनिवार्य रूप से 0 से 31 समावेशी, प्लस 127 वाले कोड के साथ वर्णों की पसंद के बराबर है। बस मामले में, हम जल्दी से जाँचते हैं कि क्या कुछ काम करेगा यदि हम इस \p{Cntrl} को सभी वर्णों के अधिक सामान्य संलयन में बदल दें हमारे मामले में [az] जैसे ऑपरेटर के माध्यम से एक नियमित अभिव्यक्ति में:

विकल्प 2

 s = s.replaceAll("[\\x00-\\x1F]", "");

नहीं, ऐसा नहीं है। सभी समान 520000% 3% ।

हम याद करते हैं कि अद्भुत जावा भाषा में, संकलक, आभासी मशीन और stdlibs अक्सर एक अलग जीवन जीते हैं और सबसे अधिक संभावना है कि वे इस तरह के एक सरल ऑपरेशन का अनुकूलन नहीं करेंगे - इस तथ्य के बावजूद कि एक ही नियमित अभिव्यक्ति को लाखों बार दोहराया जाता है, यह हर बार संकलित होता है। स्ट्रिंग # रिप्लेसमेंट के लिए प्रलेखन में झाँकने से इस अनुमान की पुष्टि होती है। हम इस बहुत संकलन को कोष्ठक से बाहर रखने की कोशिश कर रहे हैं:

विकल्प 3

 public static final Pattern KILL_CC_PATTERN = Pattern.compile("[\\x00-\\x1F]"); ... Matcher m = KILL_CC_PATTERN.matcher(s); s = m.replaceAll("");

अचानक, एक पंक्ति के बजाय - तीन, और उत्पादकता बढ़कर 640,000 of 3% हो गई - कई बार नहीं, लेकिन अचानक हमने + 23% वापस जीत लिया।

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

विकल्प 4

 StringBuilder sb = new StringBuilder(s.length()); for (int j = 0; j < s.length(); j++) { int ch = s.codePointAt(j); if (ch >= ' ') sb.appendCodePoint(ch); } s = sb.toString();

1 के बजाय 7 लाइनें, लेकिन पहले से ही 710000 of 3% प्रति सेकंड लाइनें। यह पहले से ही + 37% है - एक तिहाई से अधिक।

हम आगे भी सोचते रहते हैं। एक साधारण विचार पॉप अप होता है - क्या होता है यदि आप यूनिकोड कोडपॉइंट्स के साथ काम को हटा देते हैं और नियमित जावा चार्ट का उपयोग करने के लिए स्विच करते हैं? हम सभी प्रकार के सरोगेट, कंपोजिट आदि को देखने का अवसर खो देते हैं। एक पूरे के रूप में - लेकिन अलग करने के दृष्टिकोण से - कुछ भी बुरा नहीं होगा। हम कोशिश करते हैं:

विकल्प 5

 StringBuilder sb = new StringBuilder(s.length()); for (int j = 0; j < s.length(); j++) { char ch = s.charAt(j); if (ch >= ' ') sb.append(ch); } s = sb.toString();

वही 7 लाइनें, पहली नज़र में यह परिवर्तन नगण्य है, लेकिन प्रदर्शन अचानक 1,052,000 ! 3% तक बढ़ जाता है ! यह पहले से ही शांत है - यह मूल (+ 103%) के सापेक्ष 2 गुना अधिक है।

क्या इसे और भी तेज किया जा सकता है? आप कर सकते हैं! आइए StringBuilder के अंदर देखें, अचानक हम देखेंगे कि यह किसी भी तरह का जंगली जादू नहीं है जो कि जेवीएम सी-कोड में गहराई तक जाता है, लेकिन शुद्ध जावा में खुद के लिए काफी समाधान है। StringBuilder के अंदर, डेटा संरचनाएँ तुच्छ रूप से संग्रहीत की जाती हैं जो वर्णों के लिंक को चार सरणियों के माध्यम से जोड़ती हैं। हमारे मामले में, ये सभी संरचनाएं अनावश्यक रूप से हैं - हम वहां लाइन के बीच में कुछ डालने नहीं जा रहे हैं, अलग से धक्का दें, आदि। आप वास्तव में मूर्खतापूर्ण तरीके से सरणियों पर सब कुछ कर सकते हैं, लगभग एक सी-वे:

विकल्प 6

 char[] res = new char[s.length()]; int newLen = 0; for (int j = 0; j < s.length(); j++) { char ch = s.charAt(j); if (ch >= ' ') { res[newLen] = ch; newLen++; } } s = new String(res, 0, newLen);

10 लाइनें थीं , लेकिन उत्पादकता दोगुनी हो गई: 2022000 ! 3% ! यह रेगेक्सपी के साथ मूल संस्करण की तुलना में 4 गुना तेज है।

यहां और क्या अनुकूलित किया जा सकता है? वास्तव में, हमने append कॉल को अनुकूलित किया, लेकिन क्या String#charAt() का उपयोग करके लाइन के माध्यम से मार्ग का अनुकूलन करना संभव है? यह पता चला है कि यह भी संभव है। एक और कप कॉफी पीने के बाद, आइए स्ट्रिंग क्लास और उसी स्ट्रिंगबर्ल के स्रोतों के अंदर झांकने की कोशिश करें। वहां हम देखेंगे कि स्ट्रिंग के अंदर सारा काम उसी char[] साथ चला जाता है, अर्थात आप विधि कॉलों की संख्या को कम कर सकते हैं ( invokevirtual संदर्भ में invokevirtual प्रकार के invokevirtual ), जो कि aload , iload , castore आदि जैसे कार्यों को कम कर सकते हैं। - जो बहुत "सस्ते" हैं और जेवीएम द्वारा अच्छी तरह से अनुकूलित हैं।

इस प्रकार, सब कुछ सामान्य है: आप एक स्ट्रिंग # getChars के साथ उन्हें बदलकर कई charAt () कॉल से दूर हो सकते हैं। हम जाँच करते हैं:

विकल्प 7

 char[] oldChars = new char[s.length()]; s.getChars(0, s.length(), oldChars, 0); char[] newChars = new char[s.length()]; int newLen = 0; for (int j = 0; j < s.length(); j++) { char ch = oldChars[j]; if (ch >= ' ') { newChars[newLen] = ch; newLen++; } } s = new String(newChars, 0, newLen);

एक और छोटा चमत्कार होता है: 12 लाइनें, लेकिन 2500000 , 3% , अर्थात्। मूल से 5 गुना तेज।

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

यदि स्ट्रिंग # getChars () के बजाय स्ट्रिंग # getBytes () का उपयोग किया जाता है, तो क्या होता है? कुछ भी अच्छा नहीं होगा, जावा के अंदर, यह 16-बिट प्रकार के चार्ट के सरणियों के रूप में तार संग्रहीत करता है; getBytes () जैसे ऑपरेशन बहुत महंगे हैं, क्योंकि किसी भी एन्कोडिंग में परिवर्तित होना (इसे utf-8, कोई भी दो-बाइट एन्कोडिंग या सिंगल-बाइट एन्कोडिंग) एक गैर-तुच्छ ऑपरेशन है। सबसे धीमा, विचित्र रूप से पर्याप्त, विंडोज़ -1251 में बदलने का विकल्प था।
जहां भी संभव हो, अंतिम रूप से जोड़ना, पारंपरिक रूप से आयोजित राय के विपरीत, कोई लाभ नहीं देता है
सरणी के साथ ऑपरेशन के अंदर वेतन वृद्धि का उपयोग करना - newChars[newLen++] - कुछ भी नहीं, लेकिन कोड के साथ कोड को छोटा करना
इस विशेष स्थान में समानांतरीकरण कुछ भी नहीं देता है - 2-3-4 थ्रेड स्पॉनिंग और भागों में एक पंक्ति पर काम करने की लागत इस तरह के समानांतर से लाभ के साथ असंगत हैं; साथ ही, मूल समस्या में, समरूपता पहले से ही क्लस्टर ढांचे द्वारा प्रदान की गई थी

खेल रुचि को जारी रखने के लिए, मैंने इस कार्य को स्टैकओवरफ़्लो पर फेंक दिया और वहाँ उन्होंने मुझे कुछ बल्कि प्राचीन, लेकिन आश्चर्य की बात, प्रभावी तरीकों से, अनिवार्य रूप से शुद्ध सी-शैली में प्रेरित किया:

विकल्प 8

 int length = s.length(); char[] oldChars = new char[length]; s.getChars(0, length, oldChars, 0); int newLen = 0; for (int j = 0; j < length; j++) { char ch = oldChars[j]; if (ch >= ' ') { oldChars[newLen] = ch; newLen++; } } s = new String(oldChars, 0, newLen);

अजीब तरह से पर्याप्त है, यह 3,100,000 of 3% लाइनों को प्रति सेकंड देता है, अर्थात। मूल से लगभग 6 गुना तेज, और पिछले सबसे अच्छे विकल्प की तुलना में 24% तेज।

मुख्य लाभ सी से दो तुच्छ, अच्छी तरह से ज्ञात निर्माणों के माध्यम से प्राप्त किया जाता है, जो अभी भी काम कर रहे हैं: चर लंबाई में स्ट्रिंग की लंबाई की गणना करना (स्ट्रिंग # लंबाई पर कॉल को सहेजना) () - किसी कारण से मैंने उम्मीद की थी कि जेवीएम मेरे लिए यह करेगा) और एक ही समय में एक ही ओल्डचेयर एरे का उपयोग करते हुए पुरानी और नई लाइन दोनों को स्टोर करने के लिए (इस तथ्य का लाभ उठाते हुए कि हमें हमेशा पुरानी लाइन से जे-थ कैरेक्टर की आवश्यकता होती है, और जे-थ कैरेक्टर हमेशा जे </ न्यूलेन पढ़ने के समय)।

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

विकल्प 9

 public static char[] buf = new char[1024]; ... int length = s.length(); char[] oldChars = (length < 1024) ? buf : new char[length]; s.getChars(0, length, oldChars, 0); int newLen = 0; for (int j = 0; j < length; j++) { char ch = oldChars[j]; if (ch >= ' ') { oldChars[newLen] = ch; newLen++; } } s = new String(oldChars, 0, newLen);

एक तिपहिया , ऐसा लगता है, लेकिन प्रति सेकंड 3490000 of 3% लाइनों के रूप में ज्यादा देता है, अर्थात। 6.7 × वृद्धि (या पिछले विकल्प के सापेक्ष + 12.5%)।

अंतिम संस्करण, जिस पर मैंने अभी तक रोक दिया है, दसवां है। वास्तव में, आप जिस अंतिम चीज़ को बचा सकते हैं, वह एक नई स्ट्रिंग ऑब्जेक्ट बना रही है - यह विशेष रूप से ऐसा करने के लिए एक दया है, यदि व्यवहार में, एल्गोरिथ्म से गुजरने वाली 99.9% लाइनों को स्ट्रिपिंग की आवश्यकता नहीं है और आउटपुट इनपुट के बराबर है।

विकल्प 10

 public static char[] buf = new char[1024]; ... int length = s.length(); char[] oldChars = (length < 1024) ? buf : new char[length]; s.getChars(0, length, oldChars, 0); int newLen = 0; for (int j = 0; j < length; j++) { char ch = oldChars[j]; if (ch >= ' ') { oldChars[newLen] = ch; newLen++; } } if (newLen != length) s = new String(oldChars, 0, newLen);

यह थोड़ा धोखा है, क्योंकि इनपुट स्ट्रीम के बारे में एक प्राथमिक ज्ञान का उपयोग किया जाता है, लेकिन यह इसके लायक है। अंतिम सर्वोत्तम परिणाम प्रति सेकंड प्रसंस्करण के दौरान 5350000 लाइनें प्रति सेकंड होता है जिसमें केवल 0.1% लाइनों को संसाधित करने की आवश्यकता होती है। वृद्धि पहले से ही मूल संस्करण से 10 × या पिछले संस्करण से + 53% है।

निष्कर्ष और नैतिकता

1 लाइन पर 5-6 घंटे का काम इसे 15 लाइनों में बदल सकता है और इसे 10 गुना तेज कर सकता है; उच्च कीमत, लेकिन पर्याप्त है अगर यह वास्तव में अड़चन है
जावा stdlibs और JVM कोड पढ़ना काफी उपयोगी हो सकता है
यह हमेशा के लिए आवश्यक है कि धर्म में लापरवाही बरतें "सब कुछ धीमा है, जेएनआई को सब कुछ फिर से लिखें" - अक्सर समस्या को जेएनआई के बिना हल किया जा सकता है
जावा में कोडपॉइंट्स के साथ काम करना लगभग हमेशा चार के साथ काम करने की तुलना में धीमा होगा; यदि आप वास्तव में इनका उपयोग करना चाहते हैं, तो कोडपॉइंट की आवश्यकता क्यों है, इसे प्रेरित करने के लिए इसे एक नियम के रूप में लेने के लायक है
बिल्ट-इन जावा रेगेक्स, सबसे पहले, एक कमबख्त एपीआई है (जिससे अनावश्यक रूप से अक्सर एक ही भाव संकलित किया जाता है), दूसरे, वे ऐसे सरल ऑपरेशन पर काफी धीमी गति से होते हैं; हालाँकि, यह अंतर्निहित जावा regexps धीमा है - और इसलिए सभी जानते हैं
जावा में कोई भी जटिल डेटा संरचनाएं (StringBuffer, StringBuilder, String) प्रायः आदिम प्रकारों की बुनियादी सरणियों के साथ अंदर काम करती हैं, और अक्सर हम जितना चाहते हैं उससे कम इसे बेहतर रूप से करते हैं
बहुत सारी पुरानी चालें (अंतिम, व्यापक पात्रों के बजाय बाइट्स के साथ काम करना) काम नहीं करती हैं
बहुत सारी पुरानी तरकीबें (आमतौर पर इस्तेमाल की जाने वाली पद्धति का एक चर में परिणाम, स्मृति आवंटन पर बचत करना, पुन: उपयोग करना) बहुत अच्छी तरह से काम करती हैं

हम्म। शायद किसी को पता है कि यह कैसे भी तेजी से करने के लिए?

PS लेख की शुरुआत में अद्भुत तस्वीर के लेखक JcOlivera.com हैं , यह फोटो CC-BY-NC-ND के तहत वितरित किया गया है।

एक स्ट्रिंग से सभी नियंत्रण वर्ण कैसे निकालें - एक तूफानी अनुकूलन का इतिहास

निष्कर्ष और नैतिकता

More articles: