Производительность HashSet Добавление и содержание для существующих элементов

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 расширение из другого вопроса SO.

    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 выполняет дополнительное деление, которое Contains не выполняет. Взгляните на IL для Contains:

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

В любом случае, я думаю, что дополнительный разрыв - это то, что заставляет Add занимать больше времени, чем Contains. На первый взгляд кажется, что это дополнительное разделение может быть учтено, но я не могу сказать наверняка, не потратив немного больше времени на расшифровку IL.

Answer 2

Интересно, что на моей машине (Dell Latitude D630, двухъядерный процессор с частотой 2,2 ГГц) я получаю почти одинаковые результаты для обоих тестов, если только не запускаю секундомер против 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 , поэтому вы видите результат дополнительного уровень косвенности в вызовах методов.

Если я скомпилирую и запущу из командной строки, чтобы удалить любую хитрость VS ...

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

... тогда разница в производительности отсутствует.

Пример выходных данных (представитель большего числа тестов):

35036174
35153818

35225763
34862330

35047377
35033323