Perché Any è più lento di Contiene?

Question

I destinati il ​​seguente test:

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"); 

I risultati quando null non è presente:

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

Quando null è presente elemento 4000:

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

Quando null è presente alla elemento 10:

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

Così, quando l'oggetto è vicino alla parte anteriore, Any è leggermente più veloce; quando è dietro, è molto più lento. Perché?

Answer 1

Any dovrà chiamare un delegato per ogni elemento che controlla (un'istruzione aggiuntiva callvirt che è improbabile che venga inserita dal JIT). Contains esegue solo tale controllo. Ecco perché Any è più lento. Sospetto che il fatto che Any sembri più veloce di quanto contenuto quando l'elemento è visto molto presto è che il benchmark non può rispecchiarlo facilmente poiché sono molto vicini. Il tempo di impostazione per la chiamata al metodo è la maggior parte del lavoro svolto in quel caso (piuttosto che l'effettiva operazione di ricerca).

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

Qualsiasi è più lento a causa Contiene è su misura per il contenitore specifico che si sta utilizzando (Array/List/etc), in modo da non avere il sovraccarico di cottura fino un IEnumerable, chiamando MoveNext() tutte le ora, ecc.

Tuttavia, l'utilizzo di Any renderà più facile il refactoring, poiché se si modifica quella raccolta, è possibile utilizzarla, quindi in realtà la cambierei in Contains solo se si conosce tramite un profiler che questo è importante pezzo di codice. E se lo è, probabilmente dovresti finire ad usare una struttura dati più intelligente, ad ogni modo come un HashSet, dal momento che sia Any che Contains sono O (n).

Answer 3

Immagino che abbia a che fare con il fatto che Any è un metodo di estensione, parte della libreria LINQ e comporta l'uso di delegati (tramite la sintassi Func <>). Ogni volta che devi chiamare un metodo separato (specialmente come delegato) rallenta.

Answer 4

Come altre persone hanno già notato, sia i metodi Contains che Any sono metodi di estensione di Enumerable. La grande differenza nelle prestazioni ha un paio di motivi:

Prima di tutto, si fornisce un delegato a Qualsiasi, che deve essere chiamato per ogni oggetto, mentre il metodo Con non deve.Le chiamate delegate sono veloci quanto una chiamata a un metodo di interfaccia. Per questo motivo, Any è più lento.

Successivamente, qualcosa che altre persone sembrano aver mancato, il metodo di estensione Contiene ha un ottimizzazione delle prestazioni per le raccolte che implementano ICollection. Poiché oggetto [] implementa ICollection, la chiamata del metodo di estensione risulta in una chiamata di metodo sull'array stesso. Internamente, questo metodo array.Contains utilizza un semplice ciclo per iterare sull'array per confrontare il valore. Ciò significa che il controllo dei limiti dell'array viene effettuato solo una volta iterando l'array.

Poiché il metodo Any deve chiamare il delegato, non è possibile eseguire un'ottimizzazione delle prestazioni come con il metodo Contains. Ciò significa che il metodo Any esegue iterazioni sulla raccolta utilizzando l'interfaccia IEnumerable, che porta a una chiamata all'interfaccia + a un limite di array controlla + una chiamata delegata su ogni singolo elemento. Confrontalo con l'array.Contains, dove non ci sono chiamate di interfaccia, nessuna chiamata di delegato e un singolo controllo di limiti.

[Aggiornamento]: Un'ultima nota. La ragione per cui Any è più veloce con piccole collezioni (e nel tuo caso con un valore nullo all'inizio della raccolta) ha a che fare con il cast su ICollection che fa Enumerable.Contains Quando fai il cast su ICollection tu stesso, tu " Vedrai che la chiamata a Contains è più veloce di Any:

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