मेरा प्रदर्शन क्रॉल में धीमा क्यों होता है मैं आधार वर्ग में विधियों को स्थानांतरित करता हूं?

Question

मैं सी # में अपरिवर्तनीय बाइनरी पेड़ों के विभिन्न कार्यान्वयन लिख रहा हूं, और मैं चाहता था कि मेरे पेड़ बेस क्लास से कुछ सामान्य तरीकों का वारिस करें।

दुर्भाग्य से, कक्षा वर्ग से प्राप्त कक्षाएं abysmally धीमी हैं। गैर व्युत्पन्न कक्षाएं पर्याप्त प्रदर्शन करती हैं। यहाँ एक AVL पेड़ के दो लगभग समान कार्यान्वयन प्रदर्शित करने के लिए कर रहे हैं:

• AvlTree: http://pastebin.com/V4WWUAyT
• DerivedAvlTree: http://pastebin.com/PussQDmN

दो पेड़ों ठीक उसी कोड है, लेकिन मैं स्थानांतरित कर दिया है बेस क्लास में DerivedAvlTree.Insert विधि।

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 
using Juliet.Collections.Immutable; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
     const int VALUE_COUNT = 5000; 

     static void Main(string[] args) 
     { 
      var avlTreeTimes = TimeIt(TestAvlTree); 
      var derivedAvlTreeTimes = TimeIt(TestDerivedAvlTree); 

      Console.WriteLine("avlTreeTimes: {0}, derivedAvlTreeTimes: {1}", avlTreeTimes, derivedAvlTreeTimes); 
     } 

     static double TimeIt(Func<int, int> f) 
     { 
      var seeds = new int[] { 314159265, 271828183, 231406926, 141421356, 161803399, 266514414, 15485867, 122949829, 198491329, 42 }; 

      var times = new List<double>(); 

      foreach (int seed in seeds) 
      { 
       var sw = Stopwatch.StartNew(); 
       f(seed); 
       sw.Stop(); 
       times.Add(sw.Elapsed.TotalMilliseconds); 
      } 

      // throwing away top and bottom results 
      times.Sort(); 
      times.RemoveAt(0); 
      times.RemoveAt(times.Count - 1); 
      return times.Average(); 
     } 

     static int TestAvlTree(int seed) 
     { 
      var rnd = new System.Random(seed); 

      var avlTree = AvlTree<double>.Create((x, y) => x.CompareTo(y)); 
      for (int i = 0; i < VALUE_COUNT; i++) 
      { 
       avlTree = avlTree.Insert(rnd.NextDouble()); 
      } 

      return avlTree.Count; 
     } 

     static int TestDerivedAvlTree(int seed) 
     { 
      var rnd = new System.Random(seed); 

      var avlTree2 = DerivedAvlTree<double>.Create((x, y) => x.CompareTo(y)); 
      for (int i = 0; i < VALUE_COUNT; i++) 
      { 
       avlTree2 = avlTree2.Insert(rnd.NextDouble()); 
      } 

      return avlTree2.Count; 
     } 
    } 
} 

• AvlTree: 121 एमएस
• DerivedAvlTree में आवेषण 5000 आइटम: यहाँ एक परीक्षण अनुप्रयोग है आवेषण 5000 आइटम 2182 एमएस
में

मेरे प्रोफाइलर इंगित करता है कि कार्यक्रम का एक अत्यधिक राशि खर्च करता है BaseBinaryTree.Insert में समय। कोई भी जिसकी दिलचस्पी EQATEC log file देख सकती है मैंने उपरोक्त कोड के साथ बनाया है (फ़ाइल की भावना बनाने के लिए आपको EQATEC profiler की आवश्यकता होगी)।

मैं वास्तव में अपने सभी बाइनरी पेड़ों के लिए एक सामान्य बेस क्लास का उपयोग करना चाहता हूं, लेकिन यदि प्रदर्शन प्रभावित होगा तो मैं ऐसा नहीं कर सकता।

मेरे DerivedAvlTree को इतनी बुरी तरह से करने का कारण क्या है, और मैं इसे ठीक करने के लिए क्या कर सकता हूं?

Answer 1

नोट - अब यहां एक "साफ" समाधान है, इसलिए अंतिम संपादन पर जाएं यदि आप केवल एक संस्करण चाहते हैं जो तेजी से चलता है और सभी जासूसी कार्यों की परवाह नहीं करता है।

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

public virtual TreeType Insert(T value) 
{ 
    Func<TreeType, T, TreeType, TreeType> nodeFunc = (l, x, r) => 
    { 
     int compare = this.Comparer(value, x); 
     if (compare < 0) { return CreateNode(l.Insert(value), x, r); } 
     else if (compare > 0) { return CreateNode(l, x, r.Insert(value)); } 
     return Self(); 
    }; 
    return Insert<TreeType>(value, nodeFunc); 
} 

private TreeType Insert<U>(T value, 
    Func<TreeType, T, TreeType, TreeType> nodeFunc) 
{ 
    return this.Match<TreeType>(
     () => CreateNode(Self(), value, Self()), 
     nodeFunc); 
} 

यह चाहिए (और जाहिरा तौर पर करता है) यह सुनिश्चित करें कि प्रविष्टि प्रतिनिधि केवल एक बार डालने प्रति बनाया जा रहा है:

इस रिफैक्टरिंग, जिसके बारे में 60% से चल रहा है समय में कटौती पर एक नजर डालें प्रत्येक रिकर्सन पर बनाया जा रहा है। मेरी मशीन पर यह चलने का समय 350 एमएस से 120 एमएस तक घटा देता है (इसके विपरीत, सिंगल-क्लास संस्करण लगभग 30 एमएस में चलता है, इसलिए यह अभी भी कहीं भी नहीं है जहां यह होना चाहिए)।

लेकिन यहां पर जहां यह भी कमजोर हो जाता है - उपरोक्त रिफैक्टरिंग की कोशिश करने के बाद, मुझे लगा, हम्म, शायद यह अभी भी धीमा है क्योंकि मैंने केवल आधा काम किया है। तो मैं भी पहले प्रतिनिधि materializing की कोशिश की:

public virtual TreeType Insert(T value) 
{ 
    Func<TreeType> nilFunc =() => CreateNode(Self(), value, Self()); 
    Func<TreeType, T, TreeType, TreeType> nodeFunc = (l, x, r) => 
    { 
     int compare = this.Comparer(value, x); 
     if (compare < 0) { return CreateNode(l.Insert(value), x, r); } 
     else if (compare > 0) { return CreateNode(l, x, r.Insert(value)); } 
     return Self(); 
    }; 
    return Insert<TreeType>(value, nilFunc, nodeFunc); 
} 

private TreeType Insert<U>(T value, Func<TreeType> nilFunc, 
    Func<TreeType, T, TreeType, TreeType> nodeFunc) 
{ 
    return this.Match<TreeType>(nilFunc, nodeFunc); 
} 

और लगता है क्या ... इस यह फिर से धीमी बनाया! इस संस्करण के साथ, मेरी मशीन पर, इस दौड़ में 250 एमएस से थोड़ा अधिक समय लगा।

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

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

मुझे पता है कि यह एक पूर्ण उत्तर नहीं है, लेकिन उम्मीद है कि यह आपको कम से कम काम करने के लिए कुछ देता है, और हो सकता है कि इस अपघटन के साथ कुछ और प्रयोग मूल संस्करण में प्रदर्शन के करीब हो सकें।

---

संपादित करें: हाँ, मैंने इसे सबमिट करने के ठीक बाद मैं एक और अनुकूलन पर ठोकर खाई। आप आधार वर्ग के लिए इस विधि जोड़ते हैं:

private TreeType CreateNilNode(T value) 
{ 
    return CreateNode(Self(), value, Self()); 
} 

अब प्रसारण समय 38 एमएस करने के लिए यहाँ, अभी मुश्किल से मूल संस्करण से ऊपर चला जाता है। यह मेरे दिमाग को उड़ाता है, क्योंकि वास्तव में कुछ भी इस विधि का संदर्भ नहीं देता है! निजी Insert<U> विधि अभी भी मेरे उत्तर में पहले कोड ब्लॉक के समान है। विधि का संदर्भ देने के लिए पहले तर्क को बदलने के लिए पर जा रहा था, लेकिन मुझे यह नहीं करना था। या तो जिटर देख रहा है कि अज्ञात प्रतिनिधि CreateNilNode विधि के समान है और शरीर को साझा करना (शायद फिर से इनलाइन करना), या ... या, मुझे नहीं पता। यह पहला उदाहरण है जिसे मैंने कभी देखा है जहां एक निजी विधि जोड़ना और इसे कभी भी कॉल नहीं करना 4 के कारक द्वारा प्रोग्राम को तेज कर सकता है।

आपको यह सुनिश्चित करने के लिए यह जांचना होगा कि मैंने गलती से कोई तर्क त्रुटियां नहीं पेश की हैं - मुझे यकीन है कि कोड नहीं है, कोड लगभग समान है - लेकिन यदि यह सब जांचता है, तो यहां आप हैं, यह गैर-व्युत्पन्न AvlTree जितना तेज़ चलता है।

---

आगे अद्यतन

मैं आधार/व्युत्पन्न संयोजन का एक संस्करण है कि वास्तव में थोड़ा तेजी से एकल वर्ग संस्करण की तुलना में चलाता साथ आने के लिए सक्षम था। कुछ coaxing ले लिया, लेकिन यह काम करता है!

हमें क्या करना है एक समर्पित प्रविष्टि बनाना है जो सभी प्रतिनिधियों को केवल एक बार बना सकता है, परिवर्तनीय कैप्चरिंग करने की आवश्यकता के बिना। इसके बजाए, सभी राज्य सदस्य क्षेत्रों में संग्रहीत हैं। BaseBinaryTree वर्ग के अंदर इस रखो:

protected class Inserter 
{ 
    private TreeType tree; 
    private Func<TreeType> nilFunc; 
    private Func<TreeType, T, TreeType, TreeType> nodeFunc; 
    private T value; 

    public Inserter(T value) 
    { 
     this.nilFunc =() => CreateNode(); 
     this.nodeFunc = (l, x, r) => PerformMatch(l, x, r); 
     this.value = value; 
    } 

    public TreeType Insert(TreeType parent) 
    { 
     this.tree = parent; 
     return tree.Match<TreeType>(nilFunc, nodeFunc); 
    } 

    private TreeType CreateNode() 
    { 
     return tree.CreateNode(tree, value, tree); 
    } 

    private TreeType PerformMatch(TreeType l, T x, TreeType r) 
    { 
     int compare = tree.Comparer(value, x); 
     if (compare < 0) { return tree.CreateNode(l.Insert(value, this), x, r); } 
     else if (compare > 0) { return tree.CreateNode(l, x, r.Insert(value, this)); } 
     return tree; 
    } 
} 

हाँ, हाँ, मुझे पता है, इसे का उपयोग कि परिवर्तनशील आंतरिक tree राज्य, लेकिन याद रखें कि इस पेड़ ही नहीं बहुत अन-कार्यात्मक है, यह सिर्फ एक throwaway "runnable है "उदाहरण। किसी ने कभी नहीं कहा कि पेर्फ-ऑप्ट सुंदर था! प्रत्येक रिकर्सिव कॉल के लिए एक नया Inserter बनाने से बचने का यही एकमात्र तरीका है, जो अन्यथा Inserter और उसके आंतरिक प्रतिनिधियों के सभी नए आवंटन के कारण इसे धीमा कर देगा।

अब इस के लिए आधार वर्ग की प्रविष्टि के तरीकों को बदल दें:

public TreeType Insert(T value) 
{ 
    return Insert(value, null); 
} 

protected virtual TreeType Insert(T value, Inserter inserter) 
{ 
    if (inserter == null) 
    { 
     inserter = new Inserter(value); 
    } 
    return inserter.Insert(Self()); 
} 

मैं सार्वजनिक Insert विधि बनाया है गैर आभासी; वास्तविक कार्य को संरक्षित विधि में सौंप दिया जाता है जो Inserter उदाहरण लेता है (या स्वयं बनाता है)। व्युत्पन्न वर्ग फेरबदल, काफी सरल है सिर्फ इस के साथ अधिरोहित Insert विधि की जगह:

protected override DerivedAvlTree<T> Insert(T value, Inserter inserter) 
{ 
    return base.Insert(value, inserter).Balance(); 
} 

यह है कि। अब इसे चलाओ। इसमें AvlTree के रूप में लगभग सटीक समय लगेगा, आमतौर पर रिलीज निर्माण में कुछ मिलीसेकंड कम होते हैं।

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

Answer 2

यह कुछ भी व्युत्पन्न वर्ग भी मूल कार्यान्वयन बुला और उसके बाद शेष राशि बुला से कोई लेना देना नहीं है, यह क्या है?

मुझे लगता है कि आपको अलग-अलग देखने के लिए जेनरेट किए गए मशीन कोड को देखने की आवश्यकता होगी। मैं स्रोत कोड से देख सकता हूं कि आपने बहुत से स्थिर तरीकों को बहुरूप रूप से वर्चुअल विधियों में बदल दिया है ... पहले मामले में जेआईटी जानता है कि वास्तव में किस विधि को बुलाया जाएगा और प्रत्यक्ष कॉल निर्देश भी संभवतः कर सकता है पंक्ति में। लेकिन एक पॉलिमॉर्फिक कॉल के साथ इसमें वी-टेबल लुकअप और अप्रत्यक्ष कॉल करने के अलावा कोई विकल्प नहीं है। वह लुकअप काम के एक महत्वपूर्ण अंश का प्रतिनिधित्व करता है।

यदि आप कॉल ((ट्रीटाइप) को कॉल करते हैं तो जीवन थोड़ा बेहतर हो सकता है)। विधि() इसके बजाय। विधि(), लेकिन संभवतः आप पॉलिमॉर्फिक कॉल को नहीं हटा सकते हैं जब तक आप ओवरराइडिंग विधियों को सील नहीं करते । और फिर भी, आप इस उदाहरण पर रनटाइम चेक के दंड का भुगतान कर सकते हैं।

आधार वर्ग को कुछ हद तक साथ ही मदद कर सकता है में जेनेरिक स्थिर तरीकों में अपने पुन: प्रयोज्य कोड लाना है, लेकिन मुझे लगता है कि आप अभी भी बहुरूपी कॉल के लिए भुगतान करने जा रहे हैं। सी # जेनेरिक बस सी ++ टेम्पलेट्स को अनुकूलित नहीं करते हैं।

Answer 3

आप वीएस आईडीई के तहत चल रहे हैं, है ना? इसमें लगभग 20 गुना अधिक समय लग रहा है, है ना?

इसे चार बार फिर से चलाने के लिए एक लूप लपेटें, इसलिए लंबे संस्करण में 20 सेकंड लगते हैं। फिर जब यह चल रहा है, तो "रोकें" बटन दबाएं, और कॉल स्टैक को देखें। आप देखेंगे कि समस्या 9 5% निश्चितता के साथ क्या है। यदि आप जो देखते हैं उस पर विश्वास नहीं करते हैं, तो इसे और अधिक बार आज़माएं। यह क्यों काम करता है? Here's the long explanation, और here's the short one।