सूची <T> .ddRange कार्यान्वयन suboptimal

Question

मेरे सी # अनुप्रयोग प्रोफाइलिंग से संकेत मिलता है कि List<T>.AddRange में महत्वपूर्ण समय बिताया गया है। परावर्तक का उपयोग कोड को देखने के लिए इस विधि का संकेत दिया है कि यह List<T>.InsertRange जो इस तरह के रूप में कार्यान्वित किया जाता है कहता है:

public void InsertRange(int index, IEnumerable<T> collection) 
{ 
    if (collection == null) 
    { 
     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); 
    } 
    if (index > this._size) 
    { 
     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); 
    } 
    ICollection<T> is2 = collection as ICollection<T>; 
    if (is2 != null) 
    { 
     int count = is2.Count; 
     if (count > 0) 
     { 
      this.EnsureCapacity(this._size + count); 
      if (index < this._size) 
      { 
       Array.Copy(this._items, index, this._items, index + count, this._size - index); 
      } 
      if (this == is2) 
      { 
       Array.Copy(this._items, 0, this._items, index, index); 
       Array.Copy(this._items, (int) (index + count), this._items, (int) (index * 2), (int) (this._size - index)); 
      } 
      else 
      { 
       T[] array = new T[count];   // (*) 
       is2.CopyTo(array, 0);    // (*) 
       array.CopyTo(this._items, index); // (*) 
      } 
      this._size += count; 
     } 
    } 
    else 
    { 
     using (IEnumerator<T> enumerator = collection.GetEnumerator()) 
     { 
      while (enumerator.MoveNext()) 
      { 
       this.Insert(index++, enumerator.Current); 
      } 
     } 
    } 
    this._version++; 
} 

private T[] _items; 

यह तर्क कर सकते हैं कि इंटरफेस (केवल InsertRange में से एक अधिभार वाले) की सादगी के प्रदर्शन भूमि के ऊपर सही ठहराते रनटाइम प्रकार cheching और कास्टिंग। लेकिन (*) के साथ मैंने 3 लाइनों के पीछे क्या कारण हो सकता है? मुझे लगता है कि यह तेजी से विकल्प को फिर से लिखा जा सकता है:

is2.CopyTo(this._items, index); 

आप इस सरल और जाहिरा तौर पर तेजी से विकल्प का उपयोग नहीं करने के लिए किसी भी कारण से देखते हैं?

संपादित करें:

जवाब के लिए धन्यवाद। तो आम सहमति यह है कि यह एक दोषपूर्ण/दुर्भावनापूर्ण तरीके से CopyTo को लागू करने वाले इनपुट संग्रह के खिलाफ एक सुरक्षा उपाय है। मेरे लिए यह लगातार 1) रनटाइम प्रकार की जांच का भुगतान करने के लिए एक ओवरकिल की तरह लगता है 2) अस्थायी सरणी के गतिशील आवंटन 3) प्रतिलिपि ऑपरेशन को दोगुना करें, जब यह सब InsertRange के 2 या कुछ और ओवरलोड को परिभाषित करके सहेजा जा सकता था , अब IEnumerable हो रहा है, दूसरा List<T> प्राप्त कर रहा है, तीसरा T[] प्राप्त हो रहा है। बाद के दो को वर्तमान मामले में जितनी तेजी से दोगुनी दौड़ने के लिए लागू किया जा सकता था।

संपादित करें 2:

मैं एक वर्ग फ़ास्टलिस्ट, समान सूची में लागू है, सिवाय यह भी AddRange की एक अधिभार जो एक टी [] तर्क लेता प्रावधान है कि किया था। इस अधिभार को गतिशील प्रकार सत्यापन, और तत्वों की दोहरी प्रतिलिपि की आवश्यकता नहीं है। मैंने इस फास्टलिस्ट को प्रोफाइल किया था। सूची के खिलाफ एड्रेंज करें। 4-बाइट सरणी को एक सूची में 1000 बार जोड़कर जोड़ें, जो प्रारंभ में अचंभित था। मेरा कार्यान्वयन मानक सूची की गति को धड़कता है। 9 (नौ!) के कारक के साथ जोड़ें। List.AddRange हमारे आवेदन के महत्वपूर्ण उपयोग परिदृश्यों में से एक में रनटाइम का लगभग 5% लेता है, एक श्रेणी के साथ सूची को एक तेज़ AddRange प्रदान करने से एप्लिकेशन रनटाइम 4% तक सुधार सकता है।

Answer 1

वे सम्मिलन की सीमाओं के बाहर गंतव्य सूची के सूचकांक तक पहुंचने से ICollection<T> के कार्यान्वयन को रोक रहे हैं। उपरोक्त कार्यान्वयन में CopyTo के दोषपूर्ण (या "मैनिपुलेटिव") कार्यान्वयन के परिणामस्वरूप होता है।

ध्यान रखें कि T[].CopyTo को सचमुच आंतरिक रूप से memcpy के रूप में कार्यान्वित किया गया है, इसलिए उस पंक्ति को जोड़ने का प्रदर्शन ओवरहेड मिनट है। जब आपके पास जबरदस्त कॉल की सुरक्षा जोड़ने की इतनी कम लागत होती है, तो आप ऐसा भी कर सकते हैं।

संपादित करें: हिस्सा मैं अजीब लगता है तथ्य यह है कि (अस्थायी सरणी के लिए नकल) ICollection<T>.CopyTo को कॉल तुरंत EnsureCapacity के आह्वान के बाद नहीं होती है। यदि इसे उस स्थान पर ले जाया गया था, तो किसी भी synchronous exception का पालन करके सूची अपरिवर्तित रहेगी। जैसा कि है, वह स्थिति केवल तभी रखती है जब प्रविष्टि सूची के अंत में होती है। यहां तर्क है:

• सभी आवश्यक आवंटन सूची तत्वों को बदलने से पहले होता है।
• Array.Copy के लिए कॉल असफल नहीं हो सकता क्योंकि
  • स्मृति पहले से ही आवंटित किया जाता है
  • सीमा पहले से ही जाँच कर रहे हैं
  • स्रोत और गंतव्य सरणियों के तत्व प्रकार से मेल
  • कोई "कॉपी निर्माता नहीं है "सी ++ में इस्तेमाल किया जाता है - यह सिर्फ एक memcpy
• एकमात्र आइटम जो अपवाद फेंक सकता है बाहरी कॉलपर हैऔर सूची का आकार बदलने और अस्थायी सरणी आवंटित करने के लिए आवश्यक आवंटन। यदि इनमें से तीन सम्मिलन के लिए तत्वों को स्थानांतरित करने से पहले होते हैं, तो सूची बदलने के लिए लेनदेन एक तुल्यकालिक अपवाद नहीं फेंक सकता है।
• अंतिम नोट: यह पता सख्ती से असाधारण व्यवहार - उपर्युक्त तर्क थ्रेड-सुरक्षा जोड़ें।

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

• मैं कि reinvent the square wheel चाहते मेरी डेवलपर टीम लोग बर्दाश्त नहीं कर सकता नहीं करना चाहती।
• I निश्चित रूप से मेरी टीम पर लोगों को चाहते हैं जो संभावित प्रदर्शन समस्याओं की परवाह करते हैं, और उनके कोड के दुष्प्रभावों के बारे में प्रश्न पूछें। यह बिंदु मौजूद होने पर जीतता है - लेकिन जब तक लोग प्रश्न पूछ रहे हैं, मैं उन्हें अपने प्रश्नों को ठोस उत्तरों में बदलने के लिए प्रेरित करूंगा। यदि आप मुझे दिखा सकते हैं कि एक प्रारंभिक रूप से एक बुरा विचार प्रतीत होता है, तो यह एक महत्वपूर्ण लाभ प्राप्त करता है, तो यह वही तरीका है जो चीजें कभी-कभी जाती है।

Answer 2

यह एक अच्छा सवाल है, मैं एक कारण के साथ आने के लिए संघर्ष कर रहा हूं। संदर्भ स्रोत में कोई संकेत नहीं है। एक संभावना यह है कि वे एक समस्या से बचने की कोशिश करते हैं जब कक्षा आईसीओलेक्शन <> .CopyTo() विधि ऑब्जेक्ट्स को 0 के अलावा किसी प्रारंभिक इंडेक्स में कॉपी करने के विरुद्ध लागू करती है या सुरक्षा उपाय के रूप में, संग्रह को सरणी तत्वों के साथ गड़बड़ करने से रोकती है इसका उपयोग नहीं होना चाहिए।

एक और यह है कि यह एक काउंटर-मापन है जब संग्रह थ्रेड-असुरक्षित तरीके से उपयोग किया जाता है। यदि किसी आइटम को किसी अन्य थ्रेड द्वारा संग्रह में जोड़ा गया है तो यह संग्रह वर्ग 'CopyTo() विधि होगी जो विफल रहता है, माइक्रोसॉफ्ट कोड नहीं। सही व्यक्ति को सेवा कॉल मिलेगी।

ये महान स्पष्टीकरण नहीं हैं।

Answer 3

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

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

संक्षेप में आप सूची वर्ग के कार्यान्वयन को सीमेंट कर देंगे, भले ही ऑब्जेक्ट उन्मुख प्रोग्रामिंग हमें बताती है कि डेटास्ट्रक्चर का आंतरिक कार्यान्वयन कुछ ऐसा होना चाहिए जिसे अन्य कोड तोड़ने के बिना बदला जा सके।