C# List <> Add() método rendimiento

Question

Estoy trabajando con una lista <> colección, agregando nuevos objetos a la colección dentro de 2 bucles anidados. Hay unos 500000 elementos agregados a la colección, una vez que los bucles terminan de ejecutarse.

Al principio, la operación de adición funciona bien, pero poco después puede notarse una disminución en el rendimiento, para los últimos miles de elementos, el tiempo de retardo es insoportable.

He intentado varios trucos (inicializando la colección con un cierto tamaño - 500000), reemplazando la lista <> con una colección LinkedList <>, pero no ayudó demasiado.

¿Me puede recomendar un consejo para solucionar el problema? Me resulta interesante cambiar la estructura por una más optimizada: LinkedList <> por ejemplo funciona mejor que List <> con operaciones como add.

método que actualiza la lista

private void UpdateForecastList(ConcurrentDictionary<Int32, RegistroSalidaProductoPrevision> prediccion, bool soloMejoresMetodos = true) 
    { 
     foreach (KeyValuePair<int, RegistroSalidaProductoPrevision> kvp in prediccion) 
     { 
      KeyValuePair<int, RegistroSalidaProductoPrevision> localKvp = kvp; 

      IList<Prediccion> pExistente = prediccionList.Where(p => p.Id == localKvp.Key).ToList(); 

      Articulo articulo = (articuloList.Where(a => a.Id == localKvp.Key)).First(); 

      if (pExistente.Count > 0) 
      { 
       foreach (var p in pExistente) 
       { 
        prediccionList.Remove(p); 
       } 
      } 

      if (kvp.Value.Previsiones.Count > 0) 
      { 
       var previsiones = kvp.Value.Previsiones.Where(prevision => prevision.Value.LPrevision[1] != null).ToList(); 
       int previsionesCount = previsiones.Count; 

       for (int a = 0; a < previsionesCount; a++) 
       { 
        var registros = previsiones[a].Value.LPrevision[1].Serie; 
        int c = registros.Count; 

        if (soloMejoresMetodos) 
        { 
         if (localKvp.Value.MejorMetodo != previsiones[a].Key) continue; 
         for (int i = 0; i < c; i++) 
         { 
          var p = new Prediccion() 
             { 
              Id = articulo.Id, 
              Nombre = articulo.Codigo, 
              Descripcion = articulo.Descripcion, 
              NombreMetodo = 
               Utils.SplitStringByCapitals(previsiones[a].Value.NombreMetodo), 
              Fecha = registros[i].Fecha, 
              PrediccionArticulo = Math.Round(registros[i].Cantidad, 2), 
              EsMejorMetodo = 
               (previsiones[a].Value.NombreMetodo == localKvp.Value.MejorMetodo) 
                ? true 
                : false 
             }; 

          // This line experiences performance loss 
          prediccionList.Add(p); 
         } 
        } 
        else 
        { 
         for (int i = 0; i < c; i++) 
         { 
          prediccionList.Add(new Prediccion() 
                { 
                 Id = articulo.Id, 
                 Nombre = articulo.Codigo, 
                 Descripcion = articulo.Descripcion, 
                 NombreMetodo = previsiones[a].Value.NombreMetodo, 
                 Fecha = registros[i].Fecha, 
                 PrediccionArticulo = 
                  Math.Round(registros[i].Cantidad, 2), 
                 EsMejorMetodo = 
                  (previsiones[a].Value.NombreMetodo == 
                  localKvp.Value.MejorMetodo) 
                   ? true 
                   : false 
                }); 
         } 
        } 
       } 
      } 
      else 
      { 
       prediccionList.Add(new Prediccion() 
             { 
              Id = articulo.Id, 
              Nombre = articulo.Codigo, 
              Descripcion = articulo.Descripcion, 
              NombreMetodo = kvp.Value.ErroresDatos[0].Texto, 
             }); 
      } 
     } 
    } 

---

pequeña descripción del método: - el método lee un objeto (un diccionario concurrente) y actualiza una lista (en este caso un LinkedList) con el pronósticos correspondientes a un determinado artículo.

El objeto de diccionario simultáneo se actualiza constantemente desde varios subprocesos que acceden a él simultáneamente.

La lista se inicializa con predicciones nulas correspondientes a todos los artículos; así, por ejemplo, si tiene 700 artículos, al principio la lista se completará con 700 pronósticos en blanco.

Como el diccionario concurent se actualiza mediante uno de los hilos informáticos, se genera un evento que llama al método mencionado anteriormente, que a su vez actualiza la lista (prediccionList).

El número máximo de registros que podrían mantenerse en la prediccionList (en este caso) es de aproximadamente 500000 registros, pero la pérdida en el rendimiento podría notarse después de agregar unos 40000 registros en la lista.

El código puede parecer un poco oxidado, como he intentado varios trucos optimizaciones (sustituyen a los foreach'es por de, calculan el recuento de fuera de los bucles, sustituir la lista <> objeto con una LinkedList <> etc.). Finalmente llegué a la conclusión de que la parte que ralentiza el tiempo de ejecución es la línea "prediccionList.Add (p);".

Los objetos que se agregan a la lista son instancias de la clase Prediccion; este objeto no lo considero muy pesado, solo contiene 7 campos.

Uso de memoria

adjunto el resultado de una perfiles de memoria. La memoria utilizada no supera los 256 MB, por lo que no creo que la memoria sea un problema aquí.

Answer 1

Puede usar una matriz que será más rápida (pero no consultable). No conozco los detalles de su código, pero es posible que desee refractar y usar un databse. 500000 elementos nunca serán rápidos

Answer 2

¿Qué le parece usar una matriz en lugar de List?Puede inicializarlo para que tenga un tamaño inicial (digamos 500000 elementos) y si eso no es suficiente, use Array.Resize para agregar otro 100000. Solo tiene que hacer un seguimiento de la cantidad real de elementos, ya que la propiedad Length solo le dará el cantidad de elementos

Tenga en cuenta, sin embargo, que la llamada Array.Resize también puede llevar mucho tiempo, ya que básicamente se generará una nueva matriz del nuevo tamaño y todos los elementos de la matriz original se copiarán en la nueva matriz. No deberías llamar esto con demasiada frecuencia.

Answer 3

Si los objetos que está agregando a la lista son de un tamaño significativo, podría sufrir limitaciones de memoria.

Si su proceso es de 32 bits, tendrá que limitarse a 2 GB en total antes de quedarse sin espacio de direcciones, pero si es de 64 bits, podría exceder fácilmente la memoria física en la máquina y comenzar a buscar en el disco.

¿Qué tan grandes son sus objetos?

Answer 4

En mi experiencia, el rendimiento de List<T> depende de la memoria. Siempre sigue el mismo patrón, la inserción es rápida hasta cierto punto, y luego el rendimiento cae bruscamente. En mi máquina, esto suele ocurrir cuando alcanzo la marca de la memoria 1.2G. He tenido el mismo problema con casi todas las colecciones que he probado, así que creo que es más un problema subyacente .net que un problema List<T>.

Recomendaría intentar reducir el tamaño del objeto de las cosas que está utilizando 500,000 de (reemplace long s con int s, etc. ...) y pruebe a continuación.
Pero tenga cuidado, incluso si logra que funcione rápido en su máquina, podría estar sobre el umbral de la máquina donde se implementa la aplicación.

Answer 5

medida que su lista se hace más grande, cada vez que es expandir la recogida de la basura, el marco es copiar su contenido a una nueva lista lugar, debido a la forma cómo funciona recolector de basura. Es por eso que se vuelve más y más lento a medida que se hace más grande. (GC on MSDN)

Las soluciones posibles (que se me ocurren) son utilizar una lista o matriz con un tamaño predefinido que está seguro de que no se llenará, o si no es una opción, luego usar System.Collections.Generic. LinkedList, pero como ya lo ha intentado, es posible que deba implementar una lista personalizada, un enlace único si corresponde (LinkedList tiene doble enlace).

Para aumentar las posibilidades de obtener una buena respuesta, debe publicar el código del objeto que conserva en la colección, y la parte donde agrega elementos, para que podamos comprender mejor de qué se trata.

Además, consulte http://www.simple-talk.com/dotnet/performance/the-top-5-.net-memory-management-misconceptions/, creo que será de ayuda para usted.

ACTUALIZACIÓN: de indexación debe ser el funcionamiento barato, pero sin embargo, es posible que trate de leer previsiones [a] (y registros [i] en bucle anidado) en la variable local en el principio del bucle, se ahorrará par de indexaciones (x 100000 iteraciones, podría hacer alguna diferencia, si clr no está optimizando esto?).

Answer 6

Ha intentado dar una capacidad en la inicialización. Por lo tanto, no será necesario volver a asignar la memoria y llevar los contenidos antiguos al nuevo espacio de memoria.

List<long> thelist = new List<long>(500000); 

Answer 7

Usar un Struct en lugar de una Clase puede mejorar su rendimiento significativamente.

También puede obtener rendimiento perdiendo sus Propiedades de cadena de Prediccion Class/Struct.

que estaba interesado en el impacto real durante mucho tiempo, por lo que aquí es mi punto de referencia:

Tomé diferentes estructuras de datos y poner 20 millones de objetos/estructuras en ellos. Aquí está el resultado:

 
List: 
Adding 20000000 TestClass to a List`1 took 3563,2068 ms 
Accessing 20000000 TestClass from a List took 103,0203 ms 
Adding 20000000 TestStruct to a List`1 took 2239,9639 ms 
Accessing 20000000 TestStruct from a List took 254,3245 ms 

Initialized List: 
Adding 20000000 TestClass to a List`1 took 3774,772 ms 
Accessing 20000000 TestClass from a List took 99,0548 ms 
Adding 20000000 TestStruct to a List`1 took 1520,7765 ms 
Accessing 20000000 TestStruct from a List took 257,5064 ms 

LinkedList: 
Adding 20000000 TestClass to a LinkedList`1 took 6085,6478 ms 
Adding 20000000 TestStruct to a LinkedList`1 took 7771,2243 ms 

HashSet: 
Adding 20000000 TestClass to a HashSet`1 took 10816,8488 ms 
Adding 20000000 TestStruct to a HashSet`1 took 3694,5187 ms 

Now I added a string to the class/struct: 
List: 
Adding 20000000 TestClassWithString to a List`1 took 4925,1215 ms 
Accessing 20000000 TestClassWithString from a List took 120,0348 ms 
Adding 20000000 TestStructWithString to a List`1 took 3554,7463 ms 
Accessing 20000000 TestStructWithString from a List took 456,3299 ms

Este es mi programa de pruebas:

static void Main(string[] args) 
    { 
     const int noObjects = 20*1000*1000; 

     Console.WriteLine("List:"); 
     RunTest(new List<TestClass>(), noObjects); 
     RunTest(new List<TestStruct>(), noObjects); 
     Console.WriteLine(); 

     Console.WriteLine("Initialized List:"); 
     RunTest(new List<TestClass>(noObjects), noObjects); 
     RunTest(new List<TestStruct>(noObjects), noObjects); 
     Console.WriteLine(); 

     Console.WriteLine("LinkedList:"); 
     RunTest(new LinkedList<TestClass>(), noObjects); 
     RunTest(new LinkedList<TestStruct>(), noObjects); 
     Console.WriteLine(); 

     Console.WriteLine("HashSet:"); 
     RunTest(new HashSet<TestClass>(), noObjects); 
     RunTest(new HashSet<TestStruct>(), noObjects); 
     Console.WriteLine(); 

     Console.WriteLine("Now I added a string to the class/struct:"); 
     Console.WriteLine("List:"); 
     RunTest(new List<TestClassWithString>(), noObjects); 
     RunTest(new List<TestStructWithString>(), noObjects); 
     Console.WriteLine(); 

     Console.ReadLine(); 
    } 




    private static void RunTest<T>(ICollection<T> collection, int noObjects) where T : ITestThing 
    { 
     Stopwatch sw = new Stopwatch(); 
     sw.Restart(); 
     for (int i = 0; i < noObjects; i++) 
     { 
      var obj = Activator.CreateInstance<T>(); 
      obj.Initialize(); 
      collection.Add(obj); 
     } 
     sw.Stop(); 
     Console.WriteLine("Adding " + noObjects + " " + typeof(T).Name + " to a " + collection.GetType().Name + " took " + sw.Elapsed.TotalMilliseconds + " ms"); 

     if (collection is IList) 
     { 
      IList list = (IList) collection; 
      // access all list objects 
      sw.Restart(); 
      for (int i = 0; i < noObjects; i++) 
      { 
       var obj = list[i]; 
      } 
      sw.Stop(); 
      Console.WriteLine("Accessing " + noObjects + " " + typeof (T).Name + " from a List took " + sw.Elapsed.TotalMilliseconds + " ms"); 
     } 
    } 

TestClass y TestStruct tanto tener este aspecto (uno con 'clase', uno con 'struct'):

public class TestClass : ITestThing 
{ 
    public int I1; 
    public int I2; 
    public double D1; 
    public double D2; 
    public long L1; 
    public long L2; 

    public void Initialize() 
    { 
     D1 = 1; 
     D2 = 2; 
     I1 = 3; 
     I2 = 4; 
     L1 = 5; 
     L2 = 6; 
    } 
} 

Solo TestStruct es public struct en lugar de public class y TestClassWithString y TestStructWithString public string S1 que se inicializa con "abc".

ITestThing está ahí porque las estructuras no pueden tener un Constructor, así que necesitaba alguna forma de llamar al método Initialize() de una manera genérica, pero resulta que no importa mucho si llamo Initialize () o no.

Tenga en cuenta que las diferencias en las duraciones serían aún más extremas si hubiera escrito el código sin formato para cada caso de prueba sin Interface o Activator.CreateInstance, pero ese código creció demasiado tan pronto como agregué la 2da prueba caso ...

RESUMEN

Usted puede mejorar en gran medida su rendimiento mediante el uso de una lista con el tamaño inicial y poner Structs en ella, y no instancias de las clases (objetos). También trate de evitar cadenas en sus Structs, ya que cada instancia de String es nuevamente un objeto que trató de evitar utilizando un Struct en lugar de un Object.

Answer 8

El problema no tiene nada que ver con el rendimiento de List o cualquier otra estructura de datos .NET. Tu problema es puramente algorítmico. Por ejemplo, usted tiene este fragmento de código:

foreach (KeyValuePair<int, RegistroSalidaProductoPrevision> kvp in prediccion) 
    { 
     KeyValuePair<int, RegistroSalidaProductoPrevision> localKvp = kvp; 

     IList<Prediccion> pExistente = prediccionList.Where(p => p.Id == localKvp.Key).ToList(); 

     Articulo articulo = (articuloList.Where(a => a.Id == localKvp.Key)).First(); 

Así, por cada elemento en el diccionario (prediccion), que estés interactuando sobre todo el prediccionList. Has implementado un algoritmo n^2. La cantidad de tiempo que lleva ejecutar ese método es proporcional a prediccion.Count * prediccionList.Count.

Necesita un mejor algoritmo; no una estructura de datos de recopilación más rápida.