¿Por qué las operaciones LINQ pueden ser más rápidas que un bucle normal?

Question

Un amigo y yo estábamos un poco perplejos durante una discusión de programación de hoy. Como ejemplo, creamos un problema ficticio de tener un List<int> de n enteros aleatorios (típicamente 1.000.000) y queríamos crear una función que devolviera el conjunto de todos los enteros que había más de uno. Bastante sencillo. Creamos una instrucción LINQ para resolver este problema y un algoritmo simple de ordenación por inserción.

Ahora, cuando probamos la velocidad con la que se ejecutó el código (usando System.Diagnostics.StopWatch), los resultados fueron confusos. El código LINQ no solo superó al tipo simple, sino que ejecutó más rápido que un soloforeach/for que solo hizo un solo bucle de la lista, y que no tenía operaciones dentro (que, en una pista lateral, pensé que el compilador debía descubrir y eliminar todo junto).

Si generamos un nuevo List<int> de números aleatorios en la misma ejecución del programa y ejecutamos nuevamente el código LINQ, el rendimiento aumentaría en órdenes de magnitud (típicamente mil veces). El rendimiento de los bucles vacíos fue, por supuesto, el mismo.

Entonces, ¿qué está pasando aquí? ¿LINQ utiliza el paralelismo para superar los bucles normales? ¿Cómo son estos resultados aún posibles? LINQ usa quicksort que se ejecuta en n * log (n), que por definición ya es más lento que n.

¿Y qué ocurre en el salto de rendimiento en la segunda pasada?

Estábamos desconcertados e intrigados con estos resultados y esperábamos que la comunidad aclarara algunas ideas, solo para satisfacer nuestra propia curiosidad.

Answer 1

Sin duda alguna no ha realizado la consulta, simplemente la ha definido. LINQ construye un árbol de expresiones que en realidad no se evalúa hasta que realice una operación que requiera que la enumeración sea iterada. Intente agregar una operación ToList() o Count() a la consulta LINQ para forzar la evaluación de la consulta.

Según su comentario, espero que esto sea similar a lo que ha hecho. Nota: No he dedicado tiempo a averiguar si la consulta es lo más eficiente posible; Solo quiero alguna consulta para ilustrar cómo se puede estructurar el código.

var dataset = ... 

var watch = Stopwatch.StartNew(); 

var query = dataset.Where(d => dataset.Count(i => i == d) > 1); 

watch.Stop(); // timer stops here 

foreach (var item in query) // query is actually evaluated here 
{ 
    ... print out the item... 
} 

Answer 2

Sugeriría que LINQ es solo más rápido que un 'bucle normal' cuando su algoritmo es menos que perfecto (o tiene algún problema en su código). Por lo tanto, LINQ será más rápido de clasificar que usted si no escribe un algoritmo de clasificación eficiente, etc.

LINQ suele ser 'tan rápido como' o 'lo suficientemente cerca de' la velocidad de un ciclo normal, y puede ser más rápido (y más simple) para codificar/depurar/leer. Ese es su beneficio, no la velocidad de ejecución.

Si está funcionando más rápido que un bucle vacío, está haciendo algo mal. Probablemente, como se sugiere en los comentarios, no está considerando la ejecución diferida y la instrucción LINQ no se está ejecutando en realidad.

Answer 3

Si no compiló con "Optimizar código" habilitado, probablemente vea este comportamiento. (Sin duda explicaría por qué no se eliminó el bucle vacío).

El código subyacente a LINQ, sin embargo, es parte de un código ya compilado, que sin duda se habrá optimizado (por el JIT, NGen o similar).