تجاوز يساوي و GetHashCode. لكن هل هو ضروري؟

إذا كنت معتادًا على C # ، فأنت على الأرجح تعرف أنه يجب عليك دائمًا تجاوز Equals ، وكذلك GetHashCode ، لتجنب GetHashCode الأداء. ولكن ماذا سيحدث إذا لم يتم ذلك؟ اليوم ، نقارن الأداء مع خيارين للضبط ونأخذ في الاعتبار الأدوات التي تساعد على تجنب الأخطاء.

ما مدى خطورة هذه المشكلة؟

لا تؤثر كل مشكلة أداء محتملة على وقت تشغيل التطبيق. طريقة Enum.HasFlag ليست فعالة للغاية (*) ، ولكن إذا لم تستخدمها على جزء من التعليمات البرمجية التي تستهلك موارد كثيرة ، فلن تكون هناك مشاكل خطيرة في المشروع. هذا هو الحال أيضًا مع النسخ المحمية التي تم إنشاؤها بواسطة أنواع هيكلية غير للقراءة فقط في سياق للقراءة فقط. المشكلة موجودة ، ولكن من غير المحتمل أن تكون ملحوظة في التطبيقات العادية.

(*) تم إصلاحه في .NET Core 2.1 ، وكما ذكرت في منشور سابق ، يمكن الآن تخفيف العواقب باستخدام HasFlag ذاتي التكوين للإصدارات الأقدم.

لكن المشكلة التي سنتحدث عنها اليوم هي مشكلة خاصة. إذا لم يتم إنشاء طريقتين Equals و GetHashCode في البنية ، فسيتم استخدام إصداراتهما القياسية من System.ValueType . ويمكن أن تقلل بشكل كبير من أداء التطبيق النهائي.

لماذا الإصدارات القياسية بطيئة؟

بذل مؤلفو CLR قصارى جهدهم لجعل الإصدارات القياسية من Equals و GetHashCode فعالة قدر الإمكان لأنواع القيم. ولكن هناك عدة أسباب لفقدان هذه الأساليب في فعالية إصدار المستخدم ، المكتوب لنوع معين يدويًا (أو تم إنشاؤه بواسطة المترجم).

1. توزيع تحويل العبوة. تم تصميم CLR بطريقة تجعل كل استدعاء لعنصر محدد في System.ValueType أو System.Enum يؤدي إلى تحويل التفاف (**).

(**) إذا كانت الطريقة لا تدعم تجميع JIT. على سبيل المثال ، في Core CLR 2.1 ، يتعرف برنامج التحويل البرمجي JIT على طريقة Enum.HasFlag ويقوم بإنشاء رمز مناسب لا يبدأ الالتفاف.

2. التعارضات المحتملة في الإصدار القياسي من طريقة GetHashCode . عند تنفيذ دالة التجزئة ، نواجه معضلة: لجعل توزيع دالة التجزئة جيدًا أو سريعًا. في بعض الحالات ، يمكنك القيام بالأمرين معًا ، ولكن في نوع ValueType.GetHashCode ، يكون هذا صعبًا عادةً.

دالة التجزئة التقليدية لبنية النوع "تجمع" رموز التجزئة في جميع المجالات. ولكن الطريقة الوحيدة للحصول على رمز تجزئة الحقل في أسلوب ValueType هي استخدام الانعكاس. هذا هو السبب في أن مؤلفي CLR قرروا التضحية بالسرعة من أجل التوزيع ، والإصدار القياسي من GetHashCode يُرجع فقط رمز التجزئة للحقل غير الصفري الأول و "يفسد" عليه بمعرف النوع (***) (لمزيد من التفاصيل ، انظر RegularGetValueTypeHashCode في coreclr repo على github).

(***) استنادًا إلى التعليقات الموجودة في مستودع 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). يصبح عدد العمليات لملء المجموعة O (N ^ 2) (حيث N هو عدد الإدخالات ذات التعقيد O (N) لكل إدراج). وهذا يعني أن الإدراج في مجموعة من 1000 عنصر سيؤدي إلى إجراء 500000 مكالمة تقريبًا مع ValueType.Equals . هنا عواقب طريقة باستخدام التفكير!

كما يظهر الاختبار ، سيكون الأداء مقبولًا إذا كنت محظوظًا وكان العنصر الأول للهيكل فريدًا (في حالة Position_Path_DefaultEquality ). ولكن إذا لم يكن الأمر كذلك ، فستكون الإنتاجية منخفضة للغاية.

مشكلة حقيقية

أعتقد الآن أنه يمكنك تخمين المشكلة التي واجهتها مؤخرًا. منذ أسبوعين تلقيت رسالة خطأ: زاد وقت تشغيل التطبيق الذي أعمل عليه من 10 إلى 60 ثانية. لحسن الحظ ، كان التقرير مفصلاً للغاية واحتوى على أثر لأحداث Windows ، لذلك تم اكتشاف نقطة المشكلة بسرعة - ValueType.Equals .

بعد إلقاء نظرة سريعة على الشفرة ، أصبح من الواضح ما هي المشكلة:

 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; } } 

لقد استخدمت مجموعة تحتوي على نوع هيكل مخصص مع الإصدار القياسي من Equals . ولسوء الحظ ، كان يحتوي على حقل أول اختياري ، يساوي دائمًا String.equals . ظلت الإنتاجية عالية حتى زاد عدد العناصر في المجموعة بشكل ملحوظ. في غضون دقائق ، تمت تهيئة مجموعة تحتوي على عشرات الآلاف من العناصر.

هل تطبيق ValueType.Equals/GetHashCode الافتراضي يعمل دائمًا ببطء؟

لكل من ValueType.Equals و ValueType.GetHashCode طرق تحسين خاصة. إذا كان النوع لا يحتوي على "مؤشرات" وتم تعبئته بشكل صحيح (سأعرض مثالاً في دقيقة) ، فسيتم استخدام الإصدارات المحسنة: يتم تنفيذ عمليات تكرار GetHashCode على كتل المثيلات ، ويتم استخدام XOR من 4 بايت ، ويقارن أسلوب Equals مثيلين باستخدام 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 ، ويسمى من تكرار ValueType.Equals ومن تكرار ValueType.GetHashCode .

لكن التحسين شيء خبيث للغاية.

أولاً ، من الصعب فهمه عند تشغيله ؛ حتى التغييرات الطفيفة على الرمز يمكن تشغيلها وإيقافها:

 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 صحيح و MyDouble.Equals خطأ. في معظم الحالات ، لا يكون الفرق كبيرًا ، ولكن تخيل عدد الساعات التي ستقضيها في إصلاح المشكلة الناتجة عن هذا الاختلاف.

كيف تتجنب مشكلة مماثلة؟

هل يمكنك أن تسألني كيف يمكن أن يحدث ما سبق في موقف حقيقي؟ إحدى الطرق الواضحة لتشغيل أساليب Equals و GetHashCode في أنواع البنية هي استخدام قاعدة FxCop CA1815 . لكن هناك مشكلة واحدة: هذا نهج صارم للغاية.

يمكن أن يكون للتطبيق الذي يعتبر الأداء حاسمًا فيه مئات الأنواع الهيكلية التي لا تستخدم بالضرورة في مجموعات التجزئة أو القواميس. لذلك ، يمكن لمطوري التطبيقات تعطيل القاعدة ، مما سيؤدي إلى عواقب غير سارة إذا كان نوع البنية يستخدم وظائف معدلة.

الطريقة الأكثر صحة هي تحذير المطور إذا تم تخزين بنية نوع "غير مناسب" مع قيم افتراضية متساوية للعناصر (المحددة في التطبيق أو مكتبة خارجية) في مجموعة تجزئة. بالطبع أتحدث عن ErrorProne.NET والقاعدة التي أضفتها بمجرد أن واجهت هذه المشكلة:



إصدار ErrorProne.NET ليس مثالياً و "يلوم" الكود الصحيح إذا تم استخدام محلل مساواة مخصص في المنشئ:



ولكن ما زلت أعتقد أن الأمر يستحق التحذير إذا لم يتم استخدام بنية ذات عناصر متساوية افتراضيًا عند إنتاجها. على سبيل المثال ، عندما راجعت System.Collections.Generic.KeyValuePair <TKey, TValue> بنية System.Collections.Generic.KeyValuePair <TKey, TValue> المحددة في mscorlib لا تستبدل Equals و GetHashCode . من غير المحتمل أن يقوم أي شخص بتعريف متغير مثل HashSet <KeyValuePair<string, int>> اليوم ، ولكن أعتقد أنه حتى BCL يمكنه كسر القاعدة. لذلك ، من المفيد اكتشاف ذلك قبل فوات الأوان.

الخلاصة

• يمكن أن يكون لتطبيق المساواة الافتراضية للأنواع الهيكلية عواقب وخيمة على تطبيقك. هذه مشكلة حقيقية وليست نظرية.
• تستند عناصر المساواة الافتراضية لأنواع القيم إلى التفكير.
• سيكون التوزيع الذي يقوم به الإصدار القياسي من GetHashCode سيئًا جدًا إذا كان الحقل الأول من العديد من الحالات له نفس القيمة.
• هناك إصدارات محسنة لطرق Equals و GetHashCode القياسية ، ولكن لا يجب الاعتماد عليها ، لأنه حتى تغيير الرمز الصغير يمكن أن يوقف تشغيلها.
• استخدم قاعدة FxCop للتأكد من أن كل نوع هيكل يتجاوز عناصر المساواة. ومع ذلك ، فمن الأفضل منع المشكلة مع المحلل إذا تم تخزين البنية "غير المناسبة" في مجموعة تجزئة أو في جدول تجزئة.

موارد إضافية

• ErrorProne.NET على جيثب
• ErrorProne.NET بنيات في المخزن