f# - एफ#बनाम ओकैमल: ढेर ओवरफ्लो




ocaml stack-overflow (2)

मुझे हाल ही में पाइथन प्रोग्रामर के लिए एफ # के बारे में एक प्रस्तुति मिली, और इसे देखने के बाद, मैंने "चींटी पहेली" के समाधान को लागू करने का निर्णय लिया।

एक चींटी है जो एक प्लानर ग्रिड पर घूम सकती है। चींटी एक स्थान बाईं ओर, दाएं, ऊपर या नीचे एक स्थानांतरित कर सकती है। यही है, सेल (एक्स, वाई) से चींटी कोशिकाओं (x + 1, y), (x-1, y), (x, y + 1), और (x, y-1) पर जा सकती है। अंक जहां एक्स और वाई निर्देशांक के अंकों की संख्या 25 से अधिक है, चींटी के लिए पहुंच योग्य नहीं हैं। उदाहरण के लिए, बिंदु (5 9, 7 9) पहुंच योग्य नहीं है क्योंकि 5 + 9 + 7 + 9 = 30, जो 25 से अधिक है। सवाल यह है कि अगर यह शुरू होता है तो एंटी एक्सेस कितने अंक (1000, 1000) हो सकता है, सहित (1000, 1000) खुद?

मैंने ओकैमल की 30 लाइनों में अपना समाधान लागू किया, और इसे आजमाया:

$ ocamlopt -unsafe -rectypes -inline 1000 -o puzzle ant.ml
$ time ./puzzle
Points: 148848

real    0m0.143s
user    0m0.127s
sys     0m0.013s

नीट, मेरा परिणाम डीओ और सी ++ में लियोनार्डो के कार्यान्वयन के समान है। लियोनार्डो के सी ++ कार्यान्वयन की तुलना में, ओकैमल संस्करण सी ++ की तुलना में लगभग 2 गुना धीमा चलता है। जो ठीक है, दिया गया है कि लियोनार्डो ने रिकर्सन को हटाने के लिए कतार का उपयोग किया था।

मैंने फिर कोड को एफ # में अनुवादित किया ... और यहां मुझे जो मिला है:

[email protected] /g/Tmp/ant.fsharp
$ /g/Program\ Files/FSharp-2.0.0.0/bin/fsc.exe ant.fs
Microsoft (R) F# 2.0 Compiler build 2.0.0.0
Copyright (c) Microsoft Corporation. All Rights Reserved.

[email protected] /g/Tmp/ant.fsharp
$ ./ant.exe

Process is terminated due to StackOverflowException.
Quit

[email protected] /g/Tmp/ant.fsharp
$ /g/Program\ Files/Microsoft\ F#/v4.0/Fsc.exe ant.fs
Microsoft (R) F# 2.0 Compiler build 4.0.30319.1
Copyright (c) Microsoft Corporation. All Rights Reserved.

[email protected] /g/Tmp/ant.fsharp
$ ./ant.exe

Process is terminated due to StackOverflowException

स्टैक ओवरफ़्लो ... F # I के दोनों संस्करणों के साथ मेरी मशीन में है ... जिज्ञासा से, मैंने तब उत्पन्न बाइनरी (ant.exe) लिया और इसे आर्क लिनक्स / मोनो के तहत चलाया:

$ mono -V | head -1
Mono JIT compiler version 2.10.5 (tarball Fri Sep  9 06:34:36 UTC 2011)

$ time mono ./ant.exe
Points: 148848

real    1m24.298s
user    0m0.567s
sys     0m0.027s

हैरानी की बात यह है कि यह मोनो 2.10.5 (यानी कोई ढेर ओवरफ्लो) के तहत चलता है - लेकिन इसमें 84 सेकंड लगते हैं, यानि ओकैमल - ओओएस से 587 गुना धीमा होता है।

तो यह कार्यक्रम ...

  • OCaml के तहत ठीक चलाता है
  • .NET / F # के तहत बिल्कुल काम नहीं करता है
  • काम करता है, लेकिन मोनो / एफ # के तहत, बहुत धीमी है।

क्यूं कर?

संपादित करें: अजीबता जारी है - "--optimize + --checked-" का उपयोग करना समस्या गायब हो जाती है, लेकिन केवल ArchLinux / Mono के अंतर्गत ; विंडोज एक्सपी और विंडोज 7/64 बिट के तहत, बाइनरी स्टैक ओवरफ्लो का अनुकूलित संस्करण भी।

अंतिम संपादन : मैंने जवाब स्वयं पाया - नीचे देखें।


कार्यकारी सारांश:

  • मैंने एक एल्गोरिदम का एक सरल कार्यान्वयन लिखा ... वह पूंछ-पुनरावर्ती नहीं था।
  • मैंने इसे लिनक्स के तहत ओकैमल के साथ संकलित किया।
  • यह ठीक काम किया, और 0.14 सेकंड में समाप्त हो गया।

यह समय एफ # के लिए बंदरगाह के लिए समय था।

  • मैंने कोड (प्रत्यक्ष अनुवाद) का अनुवाद एफ # में किया।
  • मैंने विंडोज के तहत संकलित किया, और इसे चलाया - मुझे एक ढेर ओवरफ्लो मिला।
  • मैंने लिनक्स के तहत बाइनरी ली और इसे मोनो के तहत चलाया।
  • यह काम किया, लेकिन बहुत धीमी गति से चला (84 सेकंड)।

तब मैंने स्टैक ओवरफ्लो पर पोस्ट किया - लेकिन कुछ लोगों ने सवाल (श्वास) बंद करने का फैसला किया।

  • मैंने संकलित करने की कोशिश की - ऑप्टिमाइज़ + - चेक-
  • बाइनरी अभी भी विंडोज के तहत बहती है ...
  • ... लेकिन लिनक्स / मोनो के तहत ठीक (और 0.5 सेकंड में समाप्त) चलाएं।

यह स्टैक आकार की जांच करने का समय था: विंडोज के तहत, एक और एसओ पोस्ट ने इंगित किया कि यह डिफ़ॉल्ट रूप से 1 एमबी तक सेट है । लिनक्स के तहत, "uname -s" और एक परीक्षण कार्यक्रम के संकलन ने स्पष्ट रूप से दिखाया कि यह 8 एमबी है।

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

लिनक्स / ओकैमल और लिनक्स / मोनो / एफ # निष्पादन समय (0.14 बनाम 0.5) के बीच का अंतर यह है कि मैंने इसे मापने के सरल तरीके के कारण: "समय ./binary ..." स्टार्टअप समय को भी मापता है, जो मोनो के लिए महत्वपूर्ण है /.NET (अच्छी तरह से, इस साधारण छोटी समस्या के लिए महत्वपूर्ण)।

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

नया संस्करण विंडोज के तहत भी ठीक है, और 0.5 सेकंड में समाप्त हुआ।

तो, कहानी का नैतिक:

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

पीएस डॉ। जॉन हैरोप से कुछ अतिरिक्त इनपुट:

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


मुझे जवाब संक्षेप में करने की कोशिश करें।

3 अंक बनाए जाने हैं:

  • समस्या: एक रिकर्सिव फ़ंक्शन पर स्टैक ओवरफ़्लो होता है
  • यह केवल खिड़कियों के नीचे होता है: लिनक्स पर, समस्या के आकार की जांच के लिए, यह काम करता है
  • OCaml कार्यों में एक ही (या समान) कोड
  • समस्या का परीक्षण करने के लिए + कंपाइलर ध्वज अनुकूलित करें, काम करता है

यह बहुत आम है कि एक स्टैक ओवरफ़्लो अपवाद एक रिकर्सिव वाल का परिणाम है। यदि कॉल पूंछ की स्थिति में है, तो संकलक इसे पहचान सकता है और tailcall अनुकूलन लागू कर सकता है, इसलिए रिकर्सिव कॉल स्टैक स्पेस नहीं लेगा। Tailcall अनुकूलन F # में हो सकता है, सीआरएल में, या दोनों में:

सीएलआर पूंछ अनुकूलन 1

एफ # रिकर्सन (अधिक सामान्य) 2

एफ # पूंछ 3 कॉल करता है

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

संपादित करें: यह पता चला है कि यह किया जा सकता है (इस ब्लॉग पोस्ट को http://www.bluebytesoftware.com/blog/2006/07/04/ModifyingStackReserveAndCommitSizesOnExistingBinaries.aspx ) मैं इसे पुनः प्राप्त नहीं करता, लेकिन कम से कम परिस्थितियों में यह कम से कम है मुमकिन।

ओकैम संस्करण काम कर सकता है क्योंकि यह लिनक्स के तहत चलाया गया था। हालांकि, विंडोज के तहत ओकैम संस्करण भी परीक्षण करना दिलचस्प होगा। मुझे पता है कि ओकैमल कंपाइलर एफ # की तुलना में पूंछ-कॉल अनुकूलन पर अधिक आक्रामक है .. क्या यह आपके मूल कोड से पूंछ-पुन: प्रयोज्य फ़ंक्शन भी निकाल सकता है?

"--Optimize +" के बारे में मेरा अनुमान यह है कि यह अभी भी कोड को दोबारा शुरू कर देगा, इसलिए यह अभी भी विंडोज के तहत असफल हो जाएगा, लेकिन निष्पादन योग्य तेज़ी से चलकर समस्या को कम करेगा।

अंत में, निश्चित समाधान पूंछ रिकर्सन का उपयोग करना है (कोड को फिर से लिखना या आक्रामक संकलक अनुकूलन पर वास्तविकता से); रिकर्सिव फ़ंक्शंस के साथ स्टैक ओवरफ़्लो समस्या से बचने का यह एक अच्छा तरीका है।





tail-recursion