performance हास्केल(जीएचसी) इतनी तेज क्यों है?




haskell ghc (3)

हास्केल ( GHC कंपाइलर के साथ) आप अपेक्षा से बहुत तेज है । सही ढंग से उपयोग किया जाता है, यह निम्न-स्तर की भाषाओं के करीब-करीब हो सकता है। (हास्केलर्स के लिए एक पसंदीदा चीज है कि 5% सी (या यहां तक ​​कि इसे हराएं, लेकिन इसका मतलब है कि आप एक अक्षम सी प्रोग्राम का उपयोग कर रहे हैं, क्योंकि जीएचसी हास्केल को सी में संकलित करता है)।) मेरा सवाल है, क्यों?

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

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

क्षमा करें अगर यह रैंटी लग रहा है, लेकिन यह मेरा प्रश्न है: भौतिक मशीनों से इसकी अमूर्त प्रकृति और मतभेदों पर विचार करते हुए हास्केल (जीएचसी के साथ संकलित) इतनी तेज़ क्यों है?

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


लंबे समय तक यह सोचा गया कि कार्यात्मक भाषाएं तेजी से नहीं हो सकती हैं - और विशेष रूप से आलसी कार्यात्मक भाषाएं। लेकिन ऐसा इसलिए था क्योंकि उनके शुरुआती कार्यान्वयन, संक्षेप में, व्याख्या किए गए थे और वास्तव में संकलित नहीं थे।

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

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

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

तो अंतर्दृष्टि यह है कि "डेटा" और "कोड" का सख्त भेद जो हम मशीनों के काम के लिए "मौलिक" के रूप में सोचते हैं, यह नहीं है कि उन्हें कैसे काम करना चाहिए, लेकिन हमारे कंपाइलर्स द्वारा लगाया गया है। तो हम इसे बाहर फेंक सकते हैं, और कोड (एक कंपाइलर) है जो स्व-संशोधित कोड (निष्पादन योग्य) उत्पन्न करता है और यह सब काफी अच्छी तरह से काम कर सकता है।

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

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

अंत में, यह ध्यान दिया जाना चाहिए कि यह मॉडल अभी भी संकेतों के कारण ओवरहेड पेश करता है। यह उन मामलों में टाला जा सकता है जहां हम जानते हैं कि यह चीजों को कड़ाई से करने के लिए "सुरक्षित" है और इस प्रकार ग्राफ संकेतों को बढ़ाता है। जीएचसी विकी में कुछ विवरणों में सख्तता / मांग का अनुमान लगाने वाले तंत्र को फिर से दस्तावेज किया गया है।


खैर, यहां पर टिप्पणी करने के लिए बहुत कुछ है। मैं जितना कर सकता हूं उतना जवाब देने की कोशिश करूंगा।

सही ढंग से उपयोग किया जाता है, यह निम्न-स्तर की भाषाओं के करीब-करीब हो सकता है।

मेरे अनुभव में, आमतौर पर कई मामलों में जंग के प्रदर्शन के 2x के भीतर होना संभव है। लेकिन कुछ (व्यापक) उपयोग के मामले भी हैं जहां प्रदर्शन निम्न स्तर की भाषाओं की तुलना में खराब है।

या यहां तक ​​कि इसे हराया, लेकिन इसका मतलब है कि आप एक अक्षम सी प्रोग्राम का उपयोग कर रहे हैं, क्योंकि जीएचसी हास्केल को सी में संकलित करता है)

यह पूरी तरह से सही नहीं है। हास्केल सी - (सी का सबसेट) को संकलित करता है, जिसे मूल कोड जनरेटर के माध्यम से असेंबली में संकलित किया जाता है। देशी कोड जनरेटर आमतौर पर सी कंपाइलर की तुलना में तेज़ कोड उत्पन्न करता है, क्योंकि यह कुछ अनुकूलन लागू कर सकता है जो सामान्य सी कंपाइलर नहीं कर सकता है।

मशीन आर्किटेक्चर स्पष्ट रूप से अनिवार्य हैं, जो ट्यूरिंग मशीनों पर आधारित हैं।

यह इसके बारे में सोचने का एक अच्छा तरीका नहीं है, खासकर जब से आधुनिक प्रोसेसर आदेश के बाहर निर्देशों का मूल्यांकन करेंगे और संभवतः एक ही समय में।

वास्तव में, हास्केल में एक विशिष्ट मूल्यांकन आदेश भी नहीं है।

असल में, हास्केल एक मूल्यांकन आदेश को स्पष्ट रूप से परिभाषित करता है

इसके अलावा, मशीन डेटा प्रकारों से निपटने के बजाय, आप हर समय बीजगणितीय डेटा प्रकार बनाते हैं।

वे कई मामलों में मेल खाते हैं, बशर्ते आपके पास पर्याप्त उन्नत कंपाइलर हो।

आपको लगता है कि फ्लाई पर फ़ंक्शंस बनाना और उन्हें चारों ओर फेंकना, प्रोग्राम को धीमा कर देगा।

हास्केल संकलित किया गया है, और इसलिए उच्च-आदेश फ़ंक्शन वास्तव में फ्लाई पर नहीं बनाए जाते हैं।

ऐसा लगता है कि हास्केल कोड को अनुकूलित करने के लिए, आपको अधिक मशीन की बजाय इसे और अधिक सुरुचिपूर्ण और अमूर्त बनाने की आवश्यकता है।

आम तौर पर, हास्केल में बेहतर प्रदर्शन करने के लिए कोड को "मशीन की तरह" बनाना एक अनुत्पादक तरीका है। लेकिन इसे और अधिक अमूर्त बनाना हमेशा एक अच्छा विचार नहीं है। एक अच्छा विचार क्या है जो सामान्य डेटा संरचनाओं और कार्यों का उपयोग कर रहा है जिन्हें अत्यधिक अनुकूलित किया गया है (जैसे लिंक सूचियां)।

उदाहरण के लिए, fx = [x] और f = pure हास्केल में एक ही चीज़ है। एक अच्छा संकलक पूर्व मामले में बेहतर प्रदर्शन नहीं करेगा।

हास्केल (जीएचसी के साथ संकलित) इतनी तेजी से क्यों है, इसकी अमूर्त प्रकृति और भौतिक मशीनों के मतभेदों पर विचार करते हुए?

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

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

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


मुझे लगता है कि यह थोड़ा सा राय आधारित है। लेकिन मैं जवाब देने की कोशिश करूंगा।

मैं डायट्रिच एपीपी से सहमत हूं: यह कई चीजों का संयोजन है जो जीएचसी को तेजी से बनाते हैं।

सबसे पहले और सबसे प्रमुख, हास्केल बहुत उच्च स्तर है। यह संकलक को आपके कोड को तोड़ने के बिना आक्रामक अनुकूलन करने में सक्षम बनाता है।

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

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

इसे देखने का एक और तरीका हो सकता है ... हास्केल क्यों तेज नहीं होना चाहिए ? ऐसा क्या करता है जिससे इसे धीमा कर दिया जाए?

यह पर्ल या जावास्क्रिप्ट जैसी व्याख्या की गई भाषा नहीं है। यह जावा या सी # जैसी वर्चुअल मशीन सिस्टम भी नहीं है। यह देशी मशीन कोड तक सभी तरह से संकलित करता है, इसलिए वहां कोई ओवरहेड नहीं होता है।

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

आप कहते हैं कि "रन-टाइम पर फ्लाई पर फ़ंक्शंस बनाएं" धीमा लगता है, लेकिन यदि आप बहुत सावधानी से देखते हैं, तो आप वास्तव में ऐसा नहीं करते हैं। ऐसा लगता है कि आप ऐसा करते हैं, लेकिन आप नहीं करते हैं। यदि आप कहते हैं (+5) , तो, यह आपके स्रोत कोड में हार्ड-कोड किया गया है। यह रन-टाइम में नहीं बदला जा सकता है। तो यह वास्तव में एक गतिशील समारोह नहीं है। यहां तक ​​कि करीबी फ़ंक्शंस वास्तव में केवल डेटा ब्लॉक में पैरामीटर को सहेज रहे हैं। सभी निष्पादन योग्य कोड वास्तव में संकलन समय पर मौजूद हैं; कोई रन-टाइम व्याख्या नहीं है। (कुछ अन्य भाषाओं के विपरीत जिनके पास "eval function" है।)

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

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

असली हत्यारा आलसी मूल्यांकन है। जब आपको अपने कोड की सख्तता / आलस्य मिलती है, तो आप बेवकूफ तेज़ कोड लिख सकते हैं जो अभी भी सुरुचिपूर्ण और सुंदर है। लेकिन अगर आपको यह सामान गलत लगता है, तो आपका प्रोग्राम हजारों गुना धीमा हो जाता है, और यह वास्तव में स्पष्ट नहीं है कि यह क्यों हो रहा है।

उदाहरण के लिए, मैंने गिनती के लिए एक छोटा सा कार्यक्रम लिखा है कि फाइल में प्रत्येक बाइट कितनी बार दिखाई देता है। 25 केबी इनपुट फ़ाइल के लिए, प्रोग्राम को चलाने के लिए 20 मिनट लग गए और 6 गीगाबाइट रैम निगल लिया! यह बेतुका है !! लेकिन फिर मुझे एहसास हुआ कि समस्या क्या थी, एक बैंग-पैटर्न जोड़ा गया, और रन-टाइम 0.02 सेकेंड तक गिर गया।

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

हास्केल इतनी तेजी से क्या बनाता है? पवित्रता। स्टेटिक प्रकार आलस्य। लेकिन सबसे ऊपर, पर्याप्त उच्च स्तर होने के कारण संकलक मूल रूप से आपके कोड की अपेक्षाओं को तोड़ने के बिना कार्यान्वयन को बदल सकता है।

लेकिन मुझे लगता है कि यह सिर्फ मेरी राय है ...







lambda-calculus