Uno de los problemas de rendimiento más comunes que, en general, he encontrado en mis batallas de optimización de rendimiento en .NET ha sido, sin duda, el no elegir correctamente el tipo de colección que debe utilizarse. Es enchufar el profiler, asociar el proceso objeto de análisis… y ¡voilá!, el antipatrón bucle (a veces anidado en 2, 3 o 4 niveles) + colección incorrecta hace acto de presencia. Y es que, aunque en entornos de desarrollo las implementaciones suelen tener un rendimiento “bueno”, la realidad demuestra que cuando la volumetría de datos incrementa, el rendimiento cae en picado. Y, sin embargo, una simple línea de código puede separarnos el éxito o el fracaso.
Veamos un ejemplo práctico.

Caso de negocio

Nuestra empresa necesita crear una nueva consulta para mostrar la información de ventas agrupada por país y provincia. La información de cabeceras de venta y líneas de venta se encuentran almacenadas en dos orígenes de datos distintos. Debemos diseñar un proceso que calcule, mediante código .NET la información agregada. Las clases implicadas en el proceso son:

La forma “tradicional”

La forma “tradicional” para solucionar este ejercicio sería más o menos así:

Así que realizamos una pequeña prueba de carga y vemos cuál es el comportamiento de nuestra función:

Parámetros de las pruebas:

  • Desde 1000 a 9000 cabeceras de venta
  • Desde 20000 a 180000 líneas de venta (20 líneas de venta por cada cabecera)
  • 30 países (elegidos aleatoriamente por factura)
  • 30 províncias por país (elegidos aleatoriamente por factura

Rendimiento con bucles

En el eje vertical tenemos el tiempo que tarda en ejecutarse la función (segundos). En el horizontal, el número de cabeceras de venta procesadas.

¡Ups! El rendimiento cae en picado con “solo” 9.000 cabeceras de venta. ¿Que pasa aquí?

NOTA: En la table de pie de gráfico, el tiempo está expresado en milisegundos.

La forma “LINQ”

Sí, ya, hoy en día hay una forma mucho más rápida y limpia de crear este tipo de funciones. Veamos una implementación alternativa con LINQ to Objects:

¡Mucho mejor! Este código, al menos, es más auto explicativo que el original. (Realmente, me encanta LINQ):

Implementación con LINQ

Houston, tenemos un problema: ¡LINQ to Objects resulta ser un 36% que el método “manual”! Bueno, realmente, el problema no es LINQ, es el tipo de colección elegido. No se adecuado, no funciona bien, cuando hay que realizar búsquedas en memoria. Como agravante, observamos que con volumetrías de datos “normales” para un entorno de desarrollo (1000 registros) el rendimiento de ambos approaches parece “aceptable”.

El problema, realmente, no reside LINQ. Reside en que no se ha seleccionado un tipo de colección adecuado para realizar búsquedas en memoria.

Lookup al rescate

A nivel teórico (que trataremos próximamente en otro post), lo que vemos, es el efecto oculto de la complejidad asintótica de dos listas al cruzarse en memoria. Lo que en SQL Server se conoce como una “Full Table Scan”, pero en código .NET.

Partiendo de la implementación LINQ, vamos a introducir un simple e inocente “Lookup” para las líneas de venta, utilizando como “índice” el Id de cabecera. En la consulta LINQ, atacaremos a este lookup:

Lanzamos… y comparamos:

Comparación de rendimiento

La implementación con LINQ + Lookup (gris en el gráfico anterior), es, simplemente, brutal a nivel de rendimiento. Con 9.000 cabeceras de venta, 20 líneas por pedido, 30 países y 30 provincias, una implementación con bucles necesita 26,4 segundos, LINQ to Objects 71,6 segundos, y LINQ to Objects + Lookup 0,151 segundos.

La utilización de lookups en operaciones de búsqueda en memoria permite incrementar el rendimiento global de las soluciones de una forma, sencillamente, espectacular.

Hasta el infinito y más allá

Estrujemos un poco más solo a la función LINQ to Objects + Lookup, hasta el 1.000.000 de cabeceras de líneas y 20.000.000 de líneas de venta, para observar su comportamiento:

lookup-performance

Su degradación es infinitamente más lenta que aquellos escenarios donde no hay un lookup. Aunque, inevitablemente, a medida que los datos crecen la velocidad de cálculo se van reduciendo. Eso sí, de forma linea, no exponencial como ocurren en otros casos. Como idealmente deberíamos buscar.

El rendimiento de un Lookup manejando 1.000.000 de cabeceras de venta (11,8 segundos) es el abrumadamente superior a un algoritmo con bucles (6.000 cabeceras,  12,3 segundos) o una consulta LINQ sin lookups (4.000 cabeceras, 11,7 segundos)

La importancia de los tipos de colecciones

Es por tanto vital, saber elegir correctamente el tipo de colección a utilizar cuando se está desarrollando una solución. Cada tipo tiene sus características, sus pros y contras, que deben tenerse en cuenta.

Elegir correctamente el tipo de colección a utilizar es vital para garantizar la escalabilidad del software que se está desarrollando, buscando que nuestras funciones tengan un crecimiento lineal en relación al volumen de datos.

En próximos posts trabajaremos la complejidad asintótica desde un punto de vista más teórico, y también daremos un repaso a los principales tipos de colecciones en .NET. Para hacer boca, dejo un par de enlaces:

Cota Superior Asintótica (Wikipedia)

Commonly Used Collection Types (MSDN)