Rendimiento HashSet Add vs Contains para elementos existentes

Question

Por alguna razón, parece que la operación Agregar en un HashSet es más lenta que la operación Contiene cuando el elemento ya existe en el < code> HashSet .

Aquí está la prueba:

    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

¿Por qué Contiene más rápido que Agregar para elementos ya existentes?

Nota: estoy usando esta extensión Stopwatch de otra pregunta 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;
    }

ACTUALIZACIÓN : Las pruebas internas han revelado que la gran diferencia de rendimiento solo ocurre en la versión x64 del marco .NET. Con la versión de 32 bits del framework, Contains parece ejecutarse a la misma velocidad para agregar (de hecho, parece que la versión con el contenido corre un porcentaje más lento en algunas ejecuciones de prueba) En las versiones X64 del marco, la versión con el contenido parece corre aproximadamente un 15% más rápido.

Answer 1

AddIfNotPresent hace una división adicional que no contiene Contains. Eche un vistazo a la IL para Contiene:

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

Esto está calculando la ubicación del depósito para el código hash. El resultado se guarda en la ubicación de memoria local 1.

AddIfNotPresent hace algo similar, pero también guarda el valor calculado en la ubicación 2, para que pueda insertar el elemento en la tabla hash en esa posición si el elemento no existe. Lo guarda porque una de las ubicaciones se modifica más adelante en el ciclo que va a buscar el artículo. De todos modos, aquí está el código relevante para 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

De todos modos, creo que la división extra es lo que está causando que Agregar tome más tiempo que Contiene. A primera vista, parece que podría dividirse esa división adicional, pero no puedo decirlo con certeza sin pasar un poco más de tiempo descifrando el IL.

Answer 2

Interesante, en mi máquina (Dell Latitude D630, dual-core 2.2 Ghz) obtengo resultados casi idénticos para ambas pruebas a menos que ejecute el cronómetro contra una acción null antes de las pruebas. Por ejemplo:

Ejecuto las pruebas con el código exacto que ha proporcionado en la pregunta:

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

Si modifico el código de esta manera:

Después:

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

Añadir:

watch.Time(null, 0);

Mis resultados se convierten en:

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

Esto me parece que algo extraño está sucediendo dentro del Stopwatch que está causando estas fluctuaciones.

Answer 3

Supongo que ejecutó su prueba desde Visual Studio, lo que provocó la supresión de AddIfNotPresent en Add para ser suprimida, por lo que está viendo el resultado de un extra nivel de indirección en las llamadas al método.

Si compilo y ejecuto desde la línea de comandos para eliminar cualquier truco de VS ...

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

... entonces no hay diferencia de rendimiento.

Resultados de muestra (representativos de un mayor número de pruebas):

35036174
35153818

35225763
34862330

35047377
35033323