बराबरी और GetHashCode ओवरराइडिंग। लेकिन क्या यह जरूरी है?

यदि आप C # से परिचित हैं, तो आप सबसे अधिक संभावना जानते हैं कि प्रदर्शन में GetHashCode से बचने के लिए, आपको हमेशा Equals , साथ ही GetHashCode को ओवरराइड करना होगा। लेकिन अगर ऐसा नहीं किया गया तो क्या होगा? आज, हम दो ट्यूनिंग विकल्पों के साथ प्रदर्शन की तुलना करते हैं और त्रुटियों से बचने में मदद करने के लिए उपकरणों पर विचार करते हैं।

यह समस्या कितनी गंभीर है?

प्रत्येक संभावित प्रदर्शन समस्या अनुप्रयोग क्रम को प्रभावित नहीं करती है। Enum.HasFlag विधि बहुत कुशल नहीं है (*), लेकिन यदि आप इसका उपयोग संसाधन-गहन कोड के कोड पर नहीं करते हैं, तो परियोजना में कोई गंभीर समस्या नहीं होगी। यह गैर-पठनीय संरचना प्रकारों द्वारा तैयार की गई संरक्षित प्रतियों के मामले में भी है। समस्या मौजूद है, लेकिन सामान्य अनुप्रयोगों में ध्यान देने योग्य होने की संभावना नहीं है।

(*) .NET कोर 2.1 में फिक्स्ड, और, जैसा कि मैंने पिछले प्रकाशन में बताया था , अब पुराने संस्करणों के लिए स्व-कॉन्फ़िगर किए गए HasFlag का उपयोग करके परिणामों को कम किया जा सकता है।

लेकिन आज हम जिस समस्या के बारे में बात करेंगे वह विशेष है। यदि संरचना में Equals और GetHashCode विधियाँ नहीं बनाई गई हैं, तो System.ValueType से उनके मानक संस्करण System.ValueType । और वे अंतिम आवेदन के प्रदर्शन को काफी कम कर सकते हैं।

मानक संस्करण धीमा क्यों हैं?

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

1. पैकेजिंग रूपांतरण का वितरण। CLR को इस तरह से डिज़ाइन किया गया है कि System.ValueType या System.Enum प्रकार में परिभाषित तत्व के लिए हर कॉल एक रैपिंग ट्रांसफ़ॉर्म (**) को ट्रिगर करता है।

(**) यदि विधि JIT संकलन का समर्थन नहीं करती है। उदाहरण के लिए, कोर सीएलआर 2.1 में, जेआईटी संकलक Enum.HasFlag विधि को Enum.HasFlag है और उपयुक्त कोड उत्पन्न करता है जो लपेटना शुरू नहीं करता है।

2. GetHashCode विधि के मानक संस्करण में संभावित विरोध। हैश फ़ंक्शन को लागू करते समय, हम एक दुविधा का सामना करते हैं: हैश फ़ंक्शन के वितरण को अच्छा या तेज करने के लिए। कुछ मामलों में, आप दोनों कर सकते हैं, लेकिन ValueType.GetHashCode प्रकार में, यह आमतौर पर मुश्किल होता है।

एक पारंपरिक हैश प्रकार की संरचना सभी क्षेत्रों के हैश कोड को जोड़ती है। लेकिन ValueType विधि में फ़ील्ड हैश कोड प्राप्त करने का एकमात्र तरीका प्रतिबिंब का उपयोग करना है। इसीलिए CLR के लेखकों ने वितरण के लिए गति का त्याग करने का निर्णय लिया, और GetHashCode का मानक संस्करण केवल पहले गैर-शून्य फ़ील्ड के हैश कोड को लौटाता है और इसे एक प्रकार के पहचानकर्ता (***) के साथ " RegularGetValueTypeHashCode " करता है (अधिक जानकारी के लिए RegularGetValueTypeHashCode पर coreclr repo में RegularGetValueTypeHashCode देखें)।

(***) CoreCLR रिपॉजिटरी में टिप्पणियों को देखते हुए, भविष्य में स्थिति बदल सकती है।

 public readonly struct Location { public string Path { get; } public int Position { get; } public Location(string path, int position) => (Path, Position) = (path, position); } var hash1 = new Location(path: "", position: 42).GetHashCode(); var hash2 = new Location(path: "", position: 1).GetHashCode(); var hash3 = new Location(path: "1", position: 42).GetHashCode(); // hash1 and hash2 are the same and hash1 is different from hash3 

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

3. प्रतिबिंब पर आधारित कार्यान्वयन की गति कम है। बहुत कम। अगर सही तरीके से इस्तेमाल किया जाए तो प्रतिबिंब एक शक्तिशाली उपकरण है। यदि आप इसे कोड के संसाधन-गहन टुकड़े पर चलाते हैं तो परिणाम भयानक होंगे।

आइए देखें कि एक विफल हैश फ़ंक्शन, जिसके परिणामस्वरूप (2) और प्रतिबिंब-आधारित कार्यान्वयन हो सकता है, प्रदर्शन को प्रभावित करता है:

 public readonly struct Location1 { public string Path { get; } public int Position { get; } public Location1(string path, int position) => (Path, Position) = (path, position); } public readonly struct Location2 { // The order matters! // The default GetHashCode version will get a hashcode of the first field public int Position { get; } public string Path { get; } public Location2(string path, int position) => (Path, Position) = (path, position); } public readonly struct Location3 : IEquatable<Location3> { public string Path { get; } public int Position { get; } public Location3(string path, int position) => (Path, Position) = (path, position); public override int GetHashCode() => (Path, Position).GetHashCode(); public override bool Equals(object other) => other is Location3 l && Equals(l); public bool Equals(Location3 other) => Path == other.Path && Position == other.Position; } private HashSet<Location1> _locations1; private HashSet<Location2> _locations2; private HashSet<Location3> _locations3; [Params(1, 10, 1000)] public int NumberOfElements { get; set; } [GlobalSetup] public void Init() { _locations1 = new HashSet<Location1>(Enumerable.Range(1, NumberOfElements).Select(n => new Location1("", n))); _locations2 = new HashSet<Location2>(Enumerable.Range(1, NumberOfElements).Select(n => new Location2("", n))); _locations3 = new HashSet<Location3>(Enumerable.Range(1, NumberOfElements).Select(n => new Location3("", n))); _locations4 = new HashSet<Location4>(Enumerable.Range(1, NumberOfElements).Select(n => new Location4("", n))); } [Benchmark] public bool Path_Position_DefaultEquality() { var first = new Location1("", 0); return _locations1.Contains(first); } [Benchmark] public bool Position_Path_DefaultEquality() { var first = new Location2("", 0); return _locations2.Contains(first); } [Benchmark] public bool Path_Position_OverridenEquality() { var first = new Location3("", 0); return _locations3.Contains(first); } 

  Method | NumOfElements | Mean | Gen 0 | Allocated | -------------------------------- |------ |--------------:|--------:|----------:| Path_Position_DefaultEquality | 1 | 885.63 ns | 0.0286 | 92 B | Position_Path_DefaultEquality | 1 | 127.80 ns | 0.0050 | 16 B | Path_Position_OverridenEquality | 1 | 47.99 ns | - | 0 B | Path_Position_DefaultEquality | 10 | 6,214.02 ns | 0.2441 | 776 B | Position_Path_DefaultEquality | 10 | 130.04 ns | 0.0050 | 16 B | Path_Position_OverridenEquality | 10 | 47.67 ns | - | 0 B | Path_Position_DefaultEquality | 1000 | 589,014.52 ns | 23.4375 | 76025 B | Position_Path_DefaultEquality | 1000 | 133.74 ns | 0.0050 | 16 B | Path_Position_OverridenEquality | 1000 | 48.51 ns | - | 0 B | 

यदि पहले फ़ील्ड का मान हमेशा समान होता है, तो डिफ़ॉल्ट रूप से हैश फ़ंक्शन सभी तत्वों के लिए एक समान मूल्य देता है और हैश सेट प्रभावी रूप से O (N) सम्मिलित और खोज कार्यों के साथ एक लिंक की गई सूची में परिवर्तित हो जाता है। संग्रह को भरने के लिए संचालन की संख्या ओ (एन ^ 2) बन जाती है (जहां एन प्रत्येक प्रविष्टि के लिए जटिलता ओ (एन) के साथ आवेषण की संख्या है)। इसका मतलब है कि 1000 तत्वों के सेट में डालने से ValueType.Equals लगभग 500,000 कॉल ValueType.Equals । यहाँ परावर्तन का उपयोग करते हुए एक विधि के परिणाम हैं!

जैसा कि परीक्षण से पता चलता है, यदि आप भाग्यशाली हैं और संरचना का पहला तत्व अद्वितीय है ( Position_Path_DefaultEquality के मामले में) प्रदर्शन स्वीकार्य होगा। लेकिन अगर ऐसा नहीं है, तो उत्पादकता बेहद कम होगी।

वास्तविक समस्या

मुझे लगता है कि अब आप अनुमान लगा सकते हैं कि मैंने हाल ही में किस समस्या का सामना किया है। कुछ हफ़्ते पहले मुझे एक त्रुटि संदेश मिला: मैं जिस एप्लिकेशन पर काम कर रहा हूं उसका रनटाइम 10 से 60 सेकंड तक बढ़ गया है। सौभाग्य से, रिपोर्ट बहुत विस्तृत थी और इसमें विंडोज घटनाओं का एक ट्रेस था, इसलिए समस्या की जगह को जल्दी से खोजा गया था - ValueType.Equals ने 50 सेकंड लोड किए।

कोड पर त्वरित नज़र डालने के बाद, यह स्पष्ट हो गया कि समस्या क्या थी:

 private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount; readonly struct ErrorLocation { // Empty almost all the time public string OptionalDescription { get; } public string Path { get; } public int Position { get; } } 

मैंने एक tuple का उपयोग किया जिसमें Equals मानक संस्करण के साथ एक कस्टम संरचना टाइप की गई थी। और दुर्भाग्य से, इसमें एक वैकल्पिक पहला क्षेत्र था, जो लगभग हमेशा String.equals बराबरी String.equals । जब तक सेट में तत्वों की संख्या में काफी वृद्धि नहीं हुई तब तक उत्पादकता अधिक रही। कुछ ही मिनटों में, हजारों तत्वों के साथ एक संग्रह शुरू किया गया।

क्या डिफ़ॉल्ट ValueType.Equals/GetHashCode कार्यान्वयन हमेशा धीमी गति से चल रहा है?

ValueType.Equals और ValueType.GetHashCode दोनों में विशेष अनुकूलन विधियाँ हैं। यदि प्रकार में "पॉइंटर्स" नहीं है और इसे सही तरीके से पैक किया गया है (मैं एक मिनट में एक उदाहरण दिखाऊंगा), तो अनुकूलित संस्करणों का उपयोग किया जाता है: GetHashCode पुनरावृत्तियों को उदाहरण के ब्लॉक पर किया जाता है, 4 बाइट्स के XOR का उपयोग किया जाता है, Equals विधि memcmp का उपयोग करके दो उदाहरणों की तुलना memcmp ।

 // Optimized ValueType.GetHashCode implementation static INT32 FastGetValueTypeHashCodeHelper(MethodTable *mt, void *pObjRef) { INT32 hashCode = 0; INT32 *pObj = (INT32*)pObjRef; // this is a struct with no refs and no "strange" offsets, just go through the obj and xor the bits INT32 size = mt->GetNumInstanceFieldBytes(); for (INT32 i = 0; i < (INT32)(size / sizeof(INT32)); i++) hashCode ^= *pObj++; return hashCode; } // Optimized ValueType.Equals implementation FCIMPL2(FC_BOOL_RET, ValueTypeHelper::FastEqualsCheck, Object* obj1, Object* obj2) { TypeHandle pTh = obj1->GetTypeHandle(); FC_RETURN_BOOL(memcmp(obj1->GetData(), obj2->GetData(), pTh.GetSize()) == 0); } 

चेक खुद ValueTypeHelper::CanCompareBits में किया जाता है ValueTypeHelper::CanCompareBits , इसे ValueType.Equals के ValueType.Equals और ValueType.Equals की पुनरावृत्ति से दोनों कहा जाता है।

लेकिन अनुकूलन एक बहुत ही कपटी बात है।

सबसे पहले, यह समझना मुश्किल है कि इसे कब चालू किया जाए; कोड में मामूली बदलाव भी इसे चालू और बंद कर सकते हैं:

 public struct Case1 { // Optimization is "on", because the struct is properly "packed" public int X { get; } public byte Y { get; } } public struct Case2 { // Optimization is "off", because struct has a padding between byte and int public byte Y { get; } public int X { get; } } 

स्मृति संरचना के बारे में अधिक जानकारी के लिए, मेरा ब्लॉग, "एक प्रबंधित वस्तु का आंतरिक तत्व, भाग 4. फ़ील्ड संरचना" देखें ।

दूसरे, स्मृति की तुलना जरूरी नहीं कि आपको सही परिणाम दे। यहाँ एक सरल उदाहरण है:

 public struct MyDouble { public double Value { get; } public MyDouble(double value) => Value = value; } double d1 = -0.0; double d2 = +0.0; // True bool b1 = d1.Equals(d2); // False! bool b2 = new MyDouble(d1).Equals(new MyDouble(d2)); 

+0,0 और +0,0 समान हैं, लेकिन अलग-अलग बाइनरी अभ्यावेदन हैं। इसका मतलब है कि Double.Equals सत्य है और Double.Equals गलत है। ज्यादातर मामलों में, अंतर महत्वपूर्ण नहीं है, लेकिन कल्पना करें कि आप इस अंतर के कारण होने वाली समस्या को ठीक करने में कितने घंटे बिताएंगे।

इसी तरह की समस्या से कैसे बचें?

क्या आप मुझसे पूछ सकते हैं कि उपरोक्त वास्तविक स्थिति में कैसे हो सकता है? Equals प्रकार और Equals प्रकार के GetHashCode तरीकों को चलाने का एक स्पष्ट तरीका है FxCop CA1815 नियम का उपयोग करना। लेकिन एक समस्या है: यह बहुत सख्त दृष्टिकोण है।

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

एक अधिक सही दृष्टिकोण डेवलपर को चेतावनी देने के लिए है यदि "अनुपयुक्त" प्रकार के तत्वों के समान डिफ़ॉल्ट मानों के साथ संरचना (एप्लिकेशन या तीसरे पक्ष के पुस्तकालय में परिभाषित) एक हैश सेट में संग्रहीत है। बेशक मैं ErrorProne.NET और नियम के बारे में बात कर रहा हूँ जैसे ही मैं इस समस्या में भाग गया



ErrorProne.NET संस्करण सही नहीं है और सही कोड को "दोष" देगा यदि कस्टम समानता रिज़ॉल्वर का उपयोग निर्माता में किया जाता है:



लेकिन मुझे अभी भी लगता है कि अगर यह उत्पादन किया जा रहा है, तो डिफ़ॉल्ट रूप से समान तत्वों वाले किसी संरचना का उपयोग नहीं किया जाता है, तो यह चेतावनी के लायक है। उदाहरण के लिए, जब मैंने अपने नियम की जाँच की, तो मैंने महसूस किया कि System.Collections.Generic.KeyValuePair <TKey, TValue> mscorlib में परिभाषित संरचना Equals और GetHashCode अधिलेखित नहीं करती है। यह संभावना नहीं है कि कोई भी HashSet <KeyValuePair<string, int>> जैसे वैरिएबल को परिभाषित करेगा, लेकिन मेरा मानना ​​है कि BCL नियम को तोड़ भी सकता है। इसलिए, बहुत देर हो जाने से पहले इस की खोज करना उपयोगी है।

निष्कर्ष

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

अतिरिक्त संसाधन

• ErrorProne.NET जीथब पर
• ErrorProne.NET स्टोर में संरचना