C# List<> Add() method performance

Question

I am working with a List<> collection, adding new objects to the collection inside 2 nested loops. There are some 500000 items added to the collection, after the loops finish to execute.

At first, the addition operation runs well, but soon after there can be noticed a decrease in performance, for the last thousands of elements, the delay time is unbearable.

I have tried various tricks (initializing the collection with a certain size - 500000), replacing the List<> with a LinkedList<> collection, but it didn't help too much.

Can you recommend me a tip to solve the problem? I am interesting in changing the structure with a more optimized one - LinkedList<> for instance performs better than List<> with operations such as addition.

Method which updates the list

   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,                                        });             }         }     } 

---

Small description of the method: - the method reads an object (a concurrent dictionary) and updates a list (in this case a LinkedList) with the forecasts corresponding to a certain article.

The concurrent dictionary object is constantly updated from various threads that access it concurrently.

The list is initialized with null predictions corresponding to all the articles; thus, for instance, if you have 700 articles, in the beginning the list will be populated with 700 blank forecasts.

As the concurrent dictionary is updated by one of the computing threads, it raises an event which calls the method mentioned above, which at its turn, updates the list (prediccionList).

The maximum number of records which could be hold in the prediccionList (in this case) is about 500000 records, but the loss in performance could be noticed after adding some 40000 records in the list.

The code might seem a bit rusty, as I have tried various optimizations tricks (replace the foreach'es with for's, calculate the count's outside the loops, replace the List<> object with a LinkedList<> etc.). Finally I reached the conclusion that the part that slows down the execution time is the line "prediccionList.Add(p);".

The objects that are added to the list are instances of the Prediccion class; this object I consider not to be very heavy, it only contains 7 fields.

Memory usage

I attach the result from a memory profiling. The memory used doesn't surpass 256 MB, thus I don't believe the memory should be a problem here.

Answer 1

The problem has nothing to do with the performance of List or any other .NET data structure. Your problem is purely algorithmic. For example, you have this code fragment:

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

So for every item in the dictionary (prediccion), you're iterating over the entire prediccionList. You've implemented an n^2 algorithm. The amount of time it takes to execute that method is proportional to prediccion.Count * prediccionList.Count.

You need a better algorithm; not a faster collection data structure.