स्कैला: उत्परिवर्तनीय बनाम अपरिवर्तनीय ऑब्जेक्ट प्रदर्शन - आउटऑफमेमरी एरर

Question

मैं अपरिवर्तनीय प्रदर्शन की विशेषताओं की तुलना करना चाहता था। मैप और mutable.एक समान ऑपरेशन के लिए स्कैला में मैप (अर्थात्, कई मानचित्रों को एक ही में विलय करना। this question देखें)। मेरे पास उत्परिवर्तनीय और अपरिवर्तनीय मानचित्र दोनों के लिए समान कार्यान्वयन प्रतीत होता है (नीचे देखें)।

एक परीक्षण के रूप में, मैंने 1,000,000 सिंगल-आइटम मैप [इंट, इंट] युक्त एक सूची बनाई और इस सूची को उन कार्यों में पारित किया जिन्हें मैं परीक्षण कर रहा था। पर्याप्त स्मृति के साथ, परिणाम असुरक्षित थे: ~ 1200ms mutable.Map, ~ 1800ms immutable.Map, और ~ 750ms mutable.Map का उपयोग करके एक अनिवार्य कार्यान्वयन के लिए - सुनिश्चित नहीं है कि वहां बड़े अंतर के लिए क्या खाते हैं, लेकिन स्वतंत्र महसूस करें उस पर टिप्पणी भी।

मुझे थोड़ा आश्चर्य हुआ, शायद क्योंकि मैं थोड़ा मोटा हो रहा हूं, यह है कि इंटेलिजे 8.1 में डिफ़ॉल्ट रन कॉन्फ़िगरेशन के साथ, दोनों उत्परिवर्तनीय कार्यान्वयनों ने आउटऑफमेमरी एरर को मारा, लेकिन अपरिवर्तनीय संग्रह नहीं हुआ। अपरिवर्तनीय परीक्षण पूरा होने के लिए चला गया, लेकिन यह बहुत धीरे-धीरे हुआ - इसमें लगभग 28 सेकंड लगते हैं। जब मैंने अधिकतम जेवीएम मेमोरी बढ़ा दी (लगभग 200 एमबी तक, सुनिश्चित नहीं है कि थ्रेसहोल्ड कहां है), मुझे ऊपर के परिणाम मिल गए।

क्यों परिवर्तनशील कार्यान्वयन स्मृति समाप्त हो जाती है, लेकिन अपरिवर्तनीय कार्यान्वयन नहीं करता है:

वैसे भी, यहाँ है कि मैं क्या सच में जानना चाहते है? मुझे संदेह है कि अपरिवर्तनीय संस्करण कचरा कलेक्टर को चलाने के लिए अनुमति देता है और म्यूटेबल कार्यान्वयन से पहले स्मृति को मुक्त करता है - और उन सभी कचरे के संग्रह अपरिवर्तनीय कम-स्मृति चलाने की धीमी गति को समझते हैं - लेकिन मुझे और अधिक विस्तृत जानकारी चाहिए उस से स्पष्टीकरण।

नीचे कार्यान्वयन। (नोट: मैं दावा नहीं करते कि इन सबसे अच्छा कार्यान्वयन संभव हो रहे हैं सुधार का सुझाव के लिए स्वतंत्र महसूस।।)

def mergeMaps[A,B](func: (B,B) => B)(listOfMaps: List[Map[A,B]]): Map[A,B] = 
    (Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) { (acc, kv) => 
     acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv) 
    } 

    def mergeMutableMaps[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] = 
    (mutable.Map[A,B]() /: (for (m <- listOfMaps; kv <- m) yield kv)) { (acc, kv) => 
     acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv) 
    } 

    def mergeMutableImperative[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] = { 
    val toReturn = mutable.Map[A,B]() 
    for (m <- listOfMaps; kv <- m) { 
     if (toReturn contains kv._1) { 
     toReturn(kv._1) = func(toReturn(kv._1), kv._2) 
     } else { 
     toReturn(kv._1) = kv._2 
     } 
    } 
    toReturn 
    } 

Answer 1

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

protected def addEntry(e: Entry) { 
    val h = index(elemHashCode(e.key)) 
    e.next = table(h).asInstanceOf[Entry] 
    table(h) = e 
    tableSize = tableSize + 1 
    if (tableSize > threshold) 
    resize(2 * table.length) 
} 

resize लाइन में 2 * देखते हैं? म्यूटेबल HashMap हर बार अंतरिक्ष से बाहर होने पर दोगुना हो जाता है, जबकि अपरिवर्तनीय स्मृति उपयोग में बहुत रूढ़िवादी होता है (हालांकि मौजूदा कुंजी आमतौर पर अपडेट होने पर दो बार स्थान पर कब्जा कर लेती है)।

अब, अन्य प्रदर्शन समस्याओं के लिए, आप पहले दो संस्करणों में कुंजी और मानों की एक सूची बना रहे हैं। इसका मतलब है कि, किसी भी मानचित्र में शामिल होने से पहले, आपके पास पहले से ही प्रत्येक Tuple2 (कुंजी/मान जोड़े) स्मृति में दो बार है! इसके अलावा List का ओवरहेड, जो छोटा है, लेकिन हम ओवरहेड के दस लाख से अधिक तत्वों के बारे में बात कर रहे हैं।

आप एक प्रक्षेपण का उपयोग करना चाह सकते हैं, जो इससे बचाता है। दुर्भाग्यवश, प्रक्षेपण Stream पर आधारित है, जो स्कैला 2.7.x पर हमारे उद्देश्यों के लिए बहुत विश्वसनीय नहीं है। एक मूल्य की गणना नहीं करता है जब तक यह आवश्यक है

for (m <- listOfMaps.projection; kv <- m) yield kv 

एक Stream: फिर भी ऐसा करें। कचरा कलेक्टर को अप्रयुक्त तत्वों को भी एकत्र करना चाहिए, जब तक आप Stream के सिर का संदर्भ न रखें, जो आपके एल्गोरिदम में ऐसा लगता है।

संपादित

पूरक के रूप में एक के लिए/उपज समझ एक या अधिक संग्रह लेता है और एक नया संग्रह लौट आते हैं। जितनी बार यह समझ में आता है, लौटने वाला संग्रह मूल संग्रह के समान प्रकार का होता है। इसलिए, उदाहरण के लिए, निम्नलिखित कोड में, समझदारी एक नई सूची बनाती है, जिसे l2 के अंदर संग्रहीत किया जाता है। यह val l2 = नहीं है जो नई सूची बनाता है, लेकिन समझ के लिए।

val l = List(1,2,3) 
val l2 = for (e <- l) yield e*2 

अब, चलो कोड को देखो पहले दो एल्गोरिदम में इस्तेमाल किया जा रहा (ऋण mutable कीवर्ड):

(Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) 

foldLeft ऑपरेटर, यहाँ के साथ अपने /: पर्याय लिखा है, पर सक्रिय किया जाएगा वस्तु समझ के लिए लौट आया। याद रखें कि ऑपरेटर के अंत में : ऑब्जेक्ट और पैरामीटर के क्रम को बदल देता है।

अब, मान लीजिए कि यह कौन सा ऑब्जेक्ट है, जिस पर foldLeft कहा जा रहा है। इस समझ में पहला जनरेटर m <- listOfMaps है। हम जानते हैं कि listOfMaps टाइप सूची [एक्स] का एक संग्रह है, जहां एक्स वास्तव में यहां प्रासंगिक नहीं है। List पर एक समझ के परिणाम हमेशा एक और List है। अन्य जेनरेटर प्रासंगिक नहीं हैं।

तो आप इस List लेते हैं, प्रत्येक Map जो इस List का एक घटक है अंदर सभी कुंजी/मान मिलता है, और एक नया List कि सभी के साथ हैं। यही कारण है कि आप अपनी सारी चीजों को डुप्लिकेट कर रहे हैं।

(वास्तव में, यह उससे भी बदतर है, क्योंकि प्रत्येक जनरेटर एक नया संग्रह बनाता है, दूसरा जनरेटर द्वारा बनाए गए संकलन सिर्फ listOfMaps के प्रत्येक तत्व का आकार है, हालांकि, और तुरंत उपयोग के बाद उन्हें छोड़ दिया जाता)

अगला प्रश्न - वास्तव में, पहला, लेकिन उत्तर को उलटा करना आसान था - यह है कि projection का उपयोग कैसे मदद करता है।

जब आप projection पर List पर कॉल करते हैं, तो यह Stream (स्कैला 2.7.x पर) के प्रकार का नया ऑब्जेक्ट देता है। सबसे पहले आप सोच सकते हैं कि यह केवल चीजों को और खराब कर देगा, क्योंकि अब आपके पास List की तीन प्रतियां होंगी, बजाय एक की बजाय। लेकिन Stream पूर्व-गणना नहीं है। यह आलसी गणना की गई है।

क्या है कि इसका मतलब है कि जिसके परिणामस्वरूप वस्तु, Stream, नहीं List की एक प्रति, बल्कि, एक समारोह है कि Stream गणना करने के लिए जरूरत पड़ने पर इस्तेमाल किया जा सकता है, लेकिन है। एक बार गणना की गई, परिणाम रखा जाएगा ताकि इसे फिर से गणना करने की आवश्यकता न हो।

इसके अलावा, map, flatMap और एक Stream सभी की filter जिसका मतलब है कि आप उन सब को एक साथ श्रृंखला कर सकते हैं List जो उन्हें बनाया की एक प्रतिलिपि बनाने के बिना एक नया Stream लौटने के लिए,। चूंकि yield के साथ समझ के लिए इन कार्यों का उपयोग करें, डेटा की अनावश्यक प्रतियों को रोकने के अंदर Stream का उपयोग करें।

अब, मान लीजिए आप कुछ इस तरह लिखा है:

val kvs = for (m <- listOfMaps.projection; kv <-m) yield kv 
(Map[A,B]() /: kvs) { ... } 

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

अब मूल रूप ::

(Map[A,B]() /: (for (m <- listOfMaps.projection; kv <-m) yield kv)) 

इस मामले में, Stream एक ही समय में यह गणना की जाती है पर प्रयोग किया जाता है पर विचार करें। के कुछ समय के लिए Stream के लिए foldLeft कैसे परिभाषित किया गया है पर नजर डालते हैं:

override final def foldLeft[B](z: B)(f: (B, A) => B): B = { 
    if (isEmpty) z 
    else tail.foldLeft(f(z, head))(f) 
} 

तो Stream खाली है, बस संचायक वापसी। अन्यथा, एक नए संचयक (f(z, head)) की गणना करें और फिर इसे Stream के tail पर फ़ंक्शन पास करें।

एक बार f(z, head) निष्पादित हो गया है, हालांकि, head का कोई शेष संदर्भ नहीं होगा। या, दूसरे शब्दों में, कार्यक्रम में कहीं भी Stream के लिए इंगित नहीं करेगा, और इसका मतलब है कि कचरा कलेक्टर इसे इकट्ठा कर सकता है, इस प्रकार स्मृति को मुक्त कर सकता है।

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

अंत में, सवाल यह है कि तीसरे एल्गोरिदम से इसका लाभ क्यों नहीं मिलता है। खैर, तीसरा एल्गोरिदम yield का उपयोग नहीं करता है, इसलिए किसी भी डेटा की कोई भी प्रतिलिपि नहीं बनाई जा रही है। इस मामले में, projection का उपयोग केवल एक संकेतक परत जोड़ता है।