¿Por qué es más lento que contiene?

Question

I diseñado el siguiente ensayo:

var arrayLength=5000; 
object[] objArray=new object[arrayLength]; 

for(var x=0;x<arrayLength;x++) 
{ 
    objArray[x]=new object(); 
} 
objArray[4000]=null; 
const int TestSize=int.MaxValue; 

System.Diagnostics.Stopwatch v= new Stopwatch(); 
v.Start(); 
for(var x=0;x<10000;x++) 
{ 
    objArray.Contains(null); 
} 
v.Stop(); 
objArray.Contains(null).Dump(); 
v.Elapsed.ToString().Dump("Contains"); 

//Any == 
v.Reset(); 
v.Start(); 
for(var x=0;x<10000;x++) 
{ 
    objArray.Any(o=>o==null); 
} 
v.Stop(); 
objArray.Any(x=>x==null).Dump(); 
v.Elapsed.ToString().Dump("Any"); 

//Any Equals 
v.Reset(); 
v.Start(); 
for(var x=0;x<10000;x++) 
{ 
    objArray.Any(obj=>object.Equals(obj,null)); 
} 
v.Stop(); 
objArray.Any(obj=>object.Equals(obj,null)).Dump(); 
v.Elapsed.ToString().Dump("Any"); 

los resultados cuando nulo no está presente:

• Contains False 00:00:00.0606484
• Any == False 00:00:00.7532898
• Any object.Equals False 00:00:00.8431783

Cuando nulo está presente en el elemento 4000:

• Contains True 00:00:00.0494515
• Any == True 00:00:00.5929247
• Any object.Equals True 00:00:00.6700742

Cuando nulo está presente en el elemento 10:

• Contains True 00:00:00.0038035
• Any == True 00:00:00.0025687
• Any True 00:00:00.0033769

Así que cuando el objeto está cerca del frente, Any es ligeramente más rápido; cuando está atrás, es mucho más lento. ¿Por qué?

Answer 1

Any tendrá que llamar a un delegado para cada elemento que comprueba (una instrucción adicional callvirt que es poco probable que se inserte en el JIT). Contains solo realiza ese control. Es por eso que Any es más lento. Sospecho que el hecho de que Any parezca más rápido que el que contiene cuando el elemento se ve muy temprano es que el punto de referencia no puede reflejarlo fácilmente ya que están muy cerca. El tiempo de configuración para la llamada al método es la mayor parte del trabajo realizado en ese caso (en lugar de la operación de búsqueda real).

The anonymous method: 
--- C:\Users\Mehrdad\AppData\Local\Temporary Projects\ConsoleApplication1\Program.cs 
      Console.WriteLine(s.Any(a => a == 1)); 
00000000 xor   eax,eax 
00000002 cmp   ecx,1 
00000005 sete  al 
00000008 ret 

Relevant part of Enumerable.Any code: 
... 
00000051 mov   edx,eax 
00000053 mov   rcx,qword ptr [rbx+8] 
00000057 call  qword ptr [rbx+18h] // calls the anonymous method above 
0000005a movzx  ecx,al 
0000005d test  ecx,ecx 
... 

Answer 2

Cualquier es más lento porque Contiene se adapta al contenedor específico que está usando (Array/Lista/etc), por lo que no tiene la sobrecarga de disparar hasta un IEnumerable, llamar a MoveNext() todo el tiempo, etc.

Sin embargo, el uso de Cualquiera facilitará la refactorización, ya que si cambia esa colección, puede seguir utilizándola, así que realmente solo la cambiaría a Contiene si sabe a través de un generador de perfiles que se trata de una importante pieza de código. Y si lo es, probablemente debería terminar usando una estructura de datos más inteligente de todos modos como un HashSet, ya que tanto Cualquiera como Contiene son O (n).

Answer 3

Supongo que tiene que ver con el hecho de que Any es un método de extensión, parte de la biblioteca LINQ e implica el uso de delegados (a través de la sintaxis Func <>). Cada vez que tenga que llamar a un método separado (especialmente como delegado) se ralentizará.

Answer 4

Como ya han señalado otras personas, los métodos Contiene y Cualquiera son métodos de extensión de Enumerable. La gran diferencia en el rendimiento tiene un par de razones:

En primer lugar, debe proporcionar un delegado al Any, que debe invocarse para cada objeto, mientras que el método Contiene no tiene por qué hacerlo.Las llamadas de delegado son tan rápidas como una llamada a un método de interfaz. Por esta razón, Any es más lento.

A continuación, algo que otras personas parecen haber perdido, el método de extensión Contiene tiene una optimización del rendimiento para las colecciones que implementan ICollection. Debido a que object [] implementa ICollection, la llamada al método de extensión da como resultado una llamada a un método en la matriz misma. Internamente, este método array.Contains usa un simple for loop para iterar sobre la matriz para comparar el valor. Esto significa que la comprobación de los límites de la matriz se realiza una sola vez iterando la matriz.

Como el método Any debe llamar a su delegado, no es posible una optimización del rendimiento como con el método Contiene. Esto significa que el método Cualquiera itera sobre la colección utilizando la interfaz IEnumerable, que conduce a una llamada de interfaz + una comprobación de límites de matriz + una llamada de delegado en cada elemento. Compare eso con la matriz. Contiene, donde no hay llamadas de interfaz, no hay llamadas de delegado y una verificación de límites individuales.

[Actualización]: Una última nota. La razón por la cual Any es más rápido con colecciones pequeñas (y en su caso con un valor nulo al comienzo de la colección) tiene que ver con el elenco de ICollection que hace el Enumerable.Contains. Cuando usted hace el elenco a ICollection usted mismo, usted Veremos que la llamada a Contiene es más rápida que Cualquiera:

for(var x=0;x<10000;x++) 
{ 
    ICollection<object> col = objArray; 
    col.Contains(null); 
}