c# - foreach+break vs linq Diferencia de rendimiento FirstOrDefault

performance .net-4.0

Question

Tengo dos clases que realizan la obtención de datos del rango de fechas de fechas para días determinados.

public class IterationLookup<TItem>
{
    private IList<Item> items = null;

    public IterationLookup(IEnumerable<TItem> items, Func<TItem, TKey> keySelector)
    {
        this.items = items.OrderByDescending(keySelector).ToList();
    }

    public TItem GetItem(DateTime day)
    {
        foreach(TItem i in this.items)
        {
           if (i.IsWithinRange(day))
           {
               return i;
           }
        }
        return null;
    }
}


public class LinqLookup<TItem>
{
    private IList<Item> items = null;

    public IterationLookup(IEnumerable<TItem> items, Func<TItem, TKey> keySelector)
    {
        this.items = items.OrderByDescending(keySelector).ToList();
    }

    public TItem GetItem(DateTime day)
    {
        return this.items.FirstOrDefault(i => i.IsWithinRange(day));
    }
}

Luego hago pruebas de velocidad que muestran que la versión de Linq es aproximadamente 5 veces más lenta . Esto tendría sentido cuando almacenara elementos localmente sin enumerarlos usando ToList . Esto lo haría mucho más lento, porque con cada llamada a FirstOrDefault , linq también realizaría OrderByDescending . Pero ese no es el caso, así que realmente no sé lo que está pasando. Linq debe realizar un funcionamiento muy similar a la iteración.

Este es el extracto del código que mide mis tiempos

IList<RangeItem> ranges = GenerateRanges(); // returns List<T>

var iterLookup = new IterationLookup<RangeItems>(ranges, r => r.Id);
var linqLookup = new LinqLookup<RangeItems>(ranges, r => r.Id);

Stopwatch timer = new Stopwatch();

timer.Start();
for(int i = 0; i < 1000000; i++)
{
    iterLookup.GetItem(GetRandomDay());
}
timer.Stop();
// display elapsed time

timer.Restart();
for(int i = 0; i < 1000000; i++)
{
    linqLookup.GetItem(GetRandomDay());
}
timer.Stop();
// display elapsed time

¿Por qué sé que debería funcionar mejor? Porque cuando escribo un código muy similar sin usar estas clases de búsqueda, Linq se comporta de forma muy similar a las iteraciones de foreach ...

// continue from previous code block

// items used by both order as they do in classes as well
IList<RangeItem> items = ranges.OrderByDescending(r => r.Id).ToList();

timer.Restart();
for(int i = 0; i < 1000000; i++)
{
    DateTime day = GetRandomDay();
    foreach(RangeItem r in items)
    {
        if (r.IsWithinRange(day))
        {
            // RangeItem result = r;
            break;
        }
    }
}    
timer.Stop();
// display elapsed time

timer.Restart();
for(int i = 0; i < 1000000; i++)
{
   DateTime day = GetRandomDay();
   items.FirstOrDefault(i => i.IsWithinRange(day));
}
timer.Stop();
// display elapsed time

Este es, en mi opinión, un código muy similar. FirstOrDefault tanto como yo sé, también iterar por el tiempo que sea necesario hasta que llegue a un artículo válido o hasta que llegue al final. Y esto de alguna manera es lo mismo que foreach con break .

Pero incluso la clase de iteración tiene un rendimiento peor que mi ciclo simple de iteración foreach cual también es un misterio porque todos los gastos generales que tiene son la llamada a un método dentro de una clase en comparación con el acceso directo.

Pregunta

¿Qué estoy haciendo mal en mi clase LINQ que funciona muy lento?
¿Qué estoy haciendo mal en mi clase de iteración por lo que se realiza el doble de lento que el bucle foreach directo?

¿Qué tiempos se están midiendo?

Yo hago estos pasos:

1. Generar rangos (como se ve a continuación en los resultados)
2. Cree instancias de objetos para IterationLookup, LinqLookup (y mi clase optimizada de intervalo de fechas BitCountLookup, que no forma parte de la discusión aquí)
3. Inicie el temporizador y ejecute 1 millón de búsquedas en días aleatorios dentro del rango de fechas máximo (como se ve en los resultados) utilizando la clase IterationLookup instanciada previamente.
4. Inicie el temporizador y ejecute 1 millón de búsquedas en días aleatorios dentro del rango de fechas máximo (como se ve en los resultados) utilizando la clase LinqLookup instanciada previamente.
5. Inicie el temporizador y ejecute 1 millón de búsquedas (6 veces) utilizando foreach manual + ciclos de interrupción y llamadas de Linq.

Como puede ver, la ejemplificación de objetos no se mide .

Apéndice I: Resultados sobre búsquedas de millones

Los rangos mostrados en estos resultados no se superponen, lo que debería hacer que ambos enfoques sean aún más similares en caso de que la versión LINQ no rompa el bucle en la coincidencia exitosa (lo cual es muy probable).

Generated Ranges: ID Range 000000000111111111122222222223300000000011111111112222222222 123456789012345678901234567890112345678901234567890123456789 09 22.01.-30.01. |-------| 08 14.01.-16.01. |-| 07 16.02.-19.02. |--| 06 15.01.-17.01. |-| 05 19.02.-23.02. |---| 04 01.01.-07.01.|-----| 03 02.01.-10.01. |-------| 02 11.01.-13.01. |-| 01 16.01.-20.01. |---| 00 29.01.-06.02. |-------| Lookup classes... - Iteration: 1028ms - Linq: 4517ms !!! THIS IS THE PROBLEM !!! - BitCounter: 401ms Manual loops... - Iter: 786ms - Linq: 981ms - Iter: 787ms - Linq: 996ms - Iter: 787ms - Linq: 977ms - Iter: 783ms - Linq: 979ms

Apéndice II: GitHub: código Gist para probar por ti mismo

He puesto un Gist para que puedas obtener el código completo tú mismo y ver qué está pasando. Cree una aplicación de consola y copie Program.cs en ella y agregue otros archivos que son parte de esta esencia.

Cógelo here .

Apéndice III: Pensamientos finales y pruebas de medición

Lo más problemático fue, por supuesto, la implementación LINQ que fue terriblemente lenta. Resulta que esto tiene todo que ver con la optimización del compilador delegado. LukeH brindó la mejor y más útil solución que realmente me hizo probar diferentes enfoques para esto. GetItem varios enfoques diferentes en el método GetItem (o GetPointData como se llama en Gist):

1. la forma habitual en que lo harían la mayoría de los desarrolladores (y también se implementa en Gist y no se actualizó después de que los resultados revelaran que esta no es la mejor forma de hacerlo):

   return this.items.FirstOrDefault(item => item.IsWithinRange(day));

2. al definir una variable de predicado local:

   Func<TItem, bool> predicate = item => item.IsWithinRange(day);
   return this.items.FirstOrDefault(predicate);

3. constructor de predicados local:

   Func<DateTime, Func<TItem, bool>> builder = d => item => item.IsWithinRange(d);
   return this.items.FirstOrDefault(builder(day));

4. generador de predicados local y variable de predicado local:

   Func<DateTime, Func<TItem, bool>> builder = d => item => item.IsWithinRange(d);
   Func<TItem, bool> predicate = builder(day);
   return this.items.FirstOrDefault(predicate);

5. constructor de predicado a nivel de clase (estático o de instancia):

   return this.items.FirstOrDefault(classLevelBuilder(day));

6. predicado definido externamente y proporcionado como parámetro de método

   public TItem GetItem(Func<TItem, bool> predicate)
   {
       return this.items.FirstOrDefault(predicate);
   }

   al ejecutar este método también tomé dos enfoques:

   1. predicado provisto directamente en la llamada al método dentro de for loop:

      for (int i = 0; i < 1000000; i++)
      {
          linqLookup.GetItem(item => item.IsWithinRange(GetRandomDay()));
      }

   2. generador de predicados definido fuera for bucle:

      Func<DateTime, Func<Ranger, bool>> builder = d => r => r.IsWithinRange(d);
      for (int i = 0; i < 1000000; i++)
      {
          linqLookup.GetItem(builder(GetRandomDay()));
      }

Resultados: lo que funciona mejor

Para comparar cuando se usa la clase de iteración, se tarda aprox. 770ms para ejecutar 1 millón de búsquedas en rangos generados aleatoriamente.

1. 3 local predicate builder resulta ser el mejor optimizador del compilador por lo que funciona casi tan rápido como las iteraciones habituales. 800 ms .

2. Generador de predicados 6.2 definido fuera for ciclo: 885 ms

3. Predicado 6.1 definido dentro for ciclo for : 1525 ms

4. todos los demás tomaron entre 4200 ms - 4360 ms y se consideran inutilizables.

Por lo tanto, cada vez que utilice un predicado en un método que se pueda invocar externamente con frecuencia, defina un constructor y ejecútelo. Esto dará mejores resultados.

La mayor sorpresa para mí sobre esto es que los delegados (o predicados) pueden consumir mucho tiempo.

Answer 1

A veces, LINQ aparece más lento porque la generación de delegados en un bucle (especialmente un bucle no obvio sobre llamadas a métodos) puede agregar tiempo. En su lugar, es posible que desee considerar mover su buscador fuera de la clase para hacerlo más genérico (como que su selector de claves está en construcción):

public class LinqLookup<TItem, TKey>
{
    private IList<Item> items = null;

    public IterationLookup(IEnumerable<TItem> items, Func<TItem, TKey> keySelector)
    {
        this.items = items.OrderByDescending(keySelector).ToList();
    }

    public TItem GetItem(Func<TItem, TKey> selector)
    {
        return this.items.FirstOrDefault(selector);
    }
}

Dado que no utiliza un lambda en su código iterativo, esto puede ser un poco diferente ya que tiene que crear el delegado en cada pasada a través del ciclo. Por lo general, este tiempo es insignificante para la codificación diaria, y el tiempo para invocar al delegado no es más caro que otras llamadas a métodos, es solo la creación de delegados en un ciclo cerrado que puede agregar ese poco de tiempo extra.

En este caso, dado que el delegado nunca cambia para la clase, puede crearla fuera del código que está recorriendo y sería más eficiente.

Actualización :

De hecho, incluso sin ninguna optimización, compilando en modo de lanzamiento en mi máquina no veo la diferencia de 5x. Acabo de realizar 1,000,000 búsquedas en un Item que solo tiene un campo DateTime , con 5,000 elementos en la lista. Por supuesto, mis datos, etc. son diferentes, pero se puede ver que los tiempos realmente son muy cercanos cuando abstrae el delegado:

iterativo: 14279 ms, 0.014279 ms / llamada

linq w opt: 17400 ms, 0.0174 ms / llamada

Estas diferencias de tiempo son muy pequeñas y vale la pena la legibilidad y las mejoras de mantenimiento del uso de LINQ. Sin embargo, no veo la diferencia de 5x, lo que me lleva a pensar que hay algo que no estamos viendo en su arnés de prueba.

Answer 2

Además de la respuesta de Gabe , puedo confirmar que la diferencia parece deberse al costo de reconstruir el delegado para cada llamada a GetPointData .

Si agrego una sola línea al método GetPointData en su clase GetPointData , desacelera hasta el mismo ritmo de rastreo que LinqRangeLookupSingle . Intentalo:

// in IterationRangeLookupSingle<TItem, TKey>
public TItem GetPointData(DateTime point)
{
    // just a single line, this delegate is never used
    Func<TItem, bool> dummy = i => i.IsWithinRange(point);

    // the rest of the method remains exactly the same as before
    // ...
}

(No estoy seguro de por qué el compilador y / o jitter no pueden simplemente ignorar el delegado superfluo que agregué arriba. Obviamente, el delegado es necesario en su clase LinqRangeLookupSingle ).

Una posible solución consiste en componer el predicado en LinqRangeLookupSingle para que se le pase un point como argumento. Esto significa que el delegado solo necesita ser construido una vez , no cada vez que se GetPointData método GetPointData . Por ejemplo, el siguiente cambio acelerará la versión LINQ para que sea bastante comparable con la versión foreach :

// in LinqRangeLookupSingle<TItem, TKey>
public TItem GetPointData(DateTime point)
{
    Func<DateTime, Func<TItem, bool>> builder = x => y => y.IsWithinRange(x);
    Func<TItem, bool> predicate = builder(point);

    return this.items.FirstOrDefault(predicate);
}

Answer 3

Supongamos que tiene un ciclo como este:

for (int counter = 0; counter < 1000000; counter++)
{
    // execute this 1M times and time it 
    DateTime day = GetRandomDay(); 
    items.FirstOrDefault(i => i.IsWithinRange(day)); 
}

Este ciclo creará 1,000,000 de objetos lambda para que la llamada i.IsWithinRange acceso al day . Después de cada creación de lambda, el delegado que llama a i.IsWithinRange se invoca en promedio 1,000,000 * items.Length . items.Length / 2 veces. Ambos factores no existen en su ciclo foreach , por lo que el ciclo explícito es más rápido.