Rendimiento HashSet Add vs Contains para elementos existentes
-
06-07-2019 - |
Pregunta
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.
Solución
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.
Otros consejos
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.
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