लिंक्डलिस्ट वीएस ConcurrentLinkedQueue

Question

वर्तमान में एक बहुप्रचारित वातावरण में, हम डेटा रखने के लिए एक लिंक्डलिस्ट का उपयोग कर रहे हैं। कभी-कभी लॉग में हमें NoSuchElementException मिलता है जबकि यह लिंक्डलिस्ट को मतदान कर रहा है। यदि हम लिंक्डलिस्ट से ConcurrentLinkedQueue कार्यान्वयन में जाते हैं तो प्रदर्शन प्रभाव को समझने में सहायता करें।

धन्यवाद, सचिन

Answer 1

जब आप एक NoSuchElementException तो यह हो सकता है क्योंकि ठीक से सिंक्रनाइज़ किया जा रहा नहीं की हो। उदाहरण के लिए: आप it.hasNext() साथ जाँच कर रहे हैं अगर एक तत्व सूची में है और बाद में it.next() के साथ लाने के लिए कोशिश कर रहा। यह तब विफल हो सकता है जब तत्व को बीच में हटा दिया गया है और यह तब भी हो सकता है जब आप संग्रह API के सिंक्रनाइज़ संस्करणों का उपयोग करते हैं।

तो आपकी समस्या को वास्तव में ConcurrentLinkedQueue पर जाने के साथ हल नहीं किया जा सकता है। आप एक अपवाद नहीं मिल सकता है लेकिन आप के लिए तैयार रहना है कि null भी दिया जाता है जब आप से पहले जाँच की है कि यह खाली नहीं है है। (यह अब भी वही त्रुटि है, लेकिन कार्यान्वयन अलग है।) यह रूप में लंबे समय के लिए अपने कोड खालीपन और तत्व वही सिंक्रनाइज़ दायरे में पुन: प्राप्त करने के लिए चेक होने में कोई उचित तुल्यकालन है के रूप में सच है।

एक अच्छा मौका है कि आप NoSuchElementException का व्यापार NullPointerException के बाद व्यापार करने के लिए करते हैं।

यह प्रदर्शन के बारे में आपके प्रश्न को सीधे संबोधित करने वाला उत्तर नहीं हो सकता है, लेकिन ConcurrentLinkedQueue पर जाने के कारण के रूप में लिंक्डलिस्ट में NoSuchElementException होने के कारण थोड़ा अजीब लगता है।

संपादित

टूटा कार्यान्वयन के लिए कुछ छद्म कोड:

//list is a LinkedList 
if(!list.isEmpty()) { 
    ... list.getFirst() 
} 

उचित सिंक के लिए कुछ छद्म कोड:

//list is a LinkedList 
synchronized(list) { 
    if(!list.isEmpty()) { 
     ... list.getFirst() 
    } 
} 

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

//queue is instance of CLQ 
if(!queue.isEmpty()) { // Does not really make sense, because ... 
    ... queue.poll() //May return null! Good chance for NPE here! 
} 

कुछ उचित कोड:

//queue is instance of CLQ 
element = queue.poll(); 

if(element != null) { 
    ... 
} 

या

//queue is instance of CLQ 
synchronized(queue) { 
    if(!queue.isEmpty()) { 
     ... queue.poll() //is not null 
    } 
} 

Answer 2

ConcurrentLinkedQueue एक असीम, धागा सुरक्षित, फीफो आदेश दिया कतार [है]। यह एक लिंक्ड संरचना का उपयोग करता है, जैसा कि हमने खंड 13.2.2 में स्किप सूचियों के आधार के रूप में देखा है, और हैश तालिका ओवरफ़्लो चेनिंग के लिए खंड 13.1.1 में। हमने देखा कि लिंक किए गए ढांचे के मुख्य आकर्षणों में से एक यह है कि सूचक पुनर्गठन द्वारा लागू सम्मिलन और निष्कासन संचालन निरंतर समय में प्रदर्शन करते हैं। इससे उन्हें विशेष रूप से कतार कार्यान्वयन के रूप में उपयोगी बना दिया जाता है, जहां संरचनाओं के सिरों पर कोशिकाओं पर इन परिचालनों की हमेशा आवश्यकता होती है, यानी, कोशिकाएं जिन्हें लिंक किए गए संरचनाओं की धीमी अनुक्रमिक खोज का उपयोग करके स्थित होने की आवश्यकता नहीं होती है।

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

Java Generics and Collections, च। 14.2।

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