أداء Hashset ADD VS يحتوي على العناصر الموجودة

Question

لسبب ما ، يبدو Add العملية على HashSet أبطأ من Contains العملية عندما يكون العنصر موجود بالفعل في HashSet.

هنا دليل:

    Stopwatch watch = new Stopwatch();
    int size = 10000;
    int iterations = 10000;


    var s = new HashSet<int>();
    for (int i = 0; i < size; i++) {
        s.Add(i);
    }

    Console.WriteLine(watch.Time(() =>
    {
        for (int i = 0; i < size; i++) {
            s.Add(i);
        }
    }, iterations));

    s = new HashSet<int>();
    for (int i = 0; i < size; i++) {
        s.Add(i);
    }

    // outputs: 47,074,764

    Console.WriteLine(watch.Time(() =>
    {
        for (int i = 0; i < size; i++) {
            if (!s.Contains(i))
                s.Add(i);
        }
    }, iterations));

    // outputs: 41,125,219

لماذا Contains اسرع من Add للعناصر الموجودة بالفعل؟

ملاحظة: أنا أستخدم هذا Stopwatch تمديد من سؤال آخر.

    public static long Time(this Stopwatch sw, Action action, int iterations) {
        sw.Reset();
        sw.Start();
        for (int i = 0; i < iterations; i++) {
            action();
        }
        sw.Stop();

        return sw.ElapsedTicks;
    }

تحديث: كشف الاختبار الداخلي أن فرق الأداء الكبير يحدث فقط في إصدار X64 من إطار .NET. مع وجود إصدار 32 بت من الإطار يحتوي على سرعة متطابقة لإضافة (في الواقع يبدو أن الإصدار الذي يحتوي على يحتوي على مئوية أبطأ في بعض عمليات الاختبار) على إصدارات X64 من الإطار ، يبدو أن الإصدار مع يحتوي على أنه يحتوي تشغيل حوالي 15 ٪ أسرع.

Answer 1

يقوم Addifnotpresent بعمل فجوة إضافية لا تحتوي على. ألقِ نظرة على IL لـ:

IL_000a:  call       instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0)
  IL_000f:  stloc.0
  IL_0010:  ldarg.0
  IL_0011:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_0016:  ldloc.0
  IL_0017:  ldarg.0
  IL_0018:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_001d:  ldlen
  IL_001e:  conv.i4
  IL_001f:  rem
  IL_0020:  ldelem.i4
  IL_0021:  ldc.i4.1
  IL_0022:  sub
  IL_0023:  stloc.1

هذا هو حساب موقع الجرافة لرمز التجزئة. يتم حفظ النتيجة في موقع الذاكرة المحلية 1.

يقوم AddIfNotPresent بشيء مشابه ، لكنه يوفر أيضًا القيمة المحسوبة في الموقع 2 ، بحيث يمكنه إدراج العنصر في جدول التجزئة في هذا الموضع إذا لم يكن العنصر موجودًا. يقوم بذلك لأن أحد المواقع يتم تعديله لاحقًا في الحلقة التي تبحث عن العنصر. على أي حال ، إليك الكود ذي الصلة لـ Addifnotpresent:

IL_0011:  call       instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0)
  IL_0016:  stloc.0
  IL_0017:  ldloc.0
  IL_0018:  ldarg.0
  IL_0019:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_001e:  ldlen
  IL_001f:  conv.i4
  IL_0020:  rem
  IL_0021:  stloc.1
  IL_0022:  ldarg.0
  IL_0023:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_0028:  ldloc.0
  IL_0029:  ldarg.0
  IL_002a:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_002f:  ldlen
  IL_0030:  conv.i4
  IL_0031:  rem
  IL_0032:  ldelem.i4
  IL_0033:  ldc.i4.1
  IL_0034:  sub
  IL_0035:  stloc.2

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

Answer 2

مثيرة للاهتمام ، على الجهاز الخاص بي (Dell Latitude D630 ، Dual-Core 2.2 GHz) أحصل على نتائج متطابقة تقريبًا لكلا الاختبارين ما لم أدير ساعة توقيت مقابل أ null العمل قبل الاختبارات. فمثلا:

أقوم بتشغيل الاختبارات باستخدام الكود الدقيق الذي قدمته في السؤال:

Without Contains(): 8205794
With Contains():    8207596

إذا قمت بتعديل الكود بهذه الطريقة:

بعد، بعدما:

Stopwatch watch = new Stopwatch();
int size = 10000;
int iterations = 10000;

يضيف:

watch.Time(null, 0);

أصبحت نتائجي:

Without Contains(): 8019129
With Contains():    8275771

يبدو لي أن شيئًا غريبًا يجري داخل Stopwatch وهذا يسبب هذه التقلبات.

Answer 3

أظن أنك أجريت اختبارك من Visual Studio الذي تسبب في تحديث AddIfNotPresent داخل Add لكي يتم قمعها ، لذلك ترى نتيجة لمستوى إضافي من عدم التوجيه في مكالمات الطريقة.

إذا قمت بتجميع وركضت من سطر الأوامر لإزالة أي خداع مقابل ...

> csc /o+ /t:exe Program.cs
> Program.exe

... ثم لا يوجد فرق في الأداء.

مخرجات عينة (ممثل عدد أكبر من الاختبارات):

35036174
35153818

35225763
34862330

35047377
35033323