A juzgar por las visitas que tuvieron mis problemillas con hebras y lambdas y bucles infinitos que tiran abajo servidores, parece que a la gente le gusta ver cómo se equivocan los demás. Supongo que es parte de la naturaleza humana y el motivo por el cual los videos más vistos en Youtube son, con permiso de los gatos y Justin Bieber, los fail.
Después de comparar la eficiencia de Dapper y NHibernate, no quiero que nadie se quede con la idea errónea de que lo importante es microoptimizar cada aspecto de la aplicación y para ello nada mejor que ilustrarlo con una historia basada en hecho reales.
Cuando se trata de mejorar el rendimiento de una aplicación hay varios aspectos a tener en cuenta, pero los principales son dos:
- Las operaciones de entrada/salida. Estas operaciones se generan cada vez que accedemos a un recurso externo, ya sea una base de datos, un servidor remoto o el sistema de archivos. Todo acceso a un recurso externo es infinitamente más lento que un acceso a memoria, por lo que a mayor número de accesos a un recurso externo, más lenta será una aplicación.
- El tiempo de CPU. Cada operación que realizamos supone un tiempo de proceso de CPU y este tiempo es limitado. Las CPUs son muy rápidas, pero también tienen su límite y podemos llegar a una situación en la que no hay ningún tipo de entrada/salida y, aunque conseguimos que la CPU trabaje al máximo, la operación sigue requiriendo demasiado tiempo.
La mayoría de las veces el problema de las aplicaciones en un acceso excesivo a recursos externos y es lo primero que debemos vigilar, pero cuando el conjunto de datos con el que estamos trabajando crece, el proceso que realizamos localmente puede provocar problemas de rendimiento por las limitaciones de la CPU.
Cuando la CPU es el cuello de botella, es fundamental revisar los algoritmos y estructuras de datos utilizadas para conseguir mejorar la velocidad de nuestra aplicación.
El caso de la sincronización de bases de datos
En mi trabajo del Mundo Real ™ hace tiempo tuvimos que desarrollar una aplicación que sincronizase dos bases de datos heredadas cuya estructura no podíamos modificar. No contábamos con ningún indicador fiable de modificación de registros, por lo que la única forma de hacerlo era leer en memoria los registros de cada base de datos y compararlos para ver si había habido cambios.
Puesto que había que sincronizar muchas tablas y el algoritmo era el mismo para todas, optamos por una solución genérica que cargaba en memoria los registros a modificar usando clases con la misma estructura que las tablas y usaba reflection para comparar propiedad a propiedad los registros cargados de cada base de datos y obtener así los que se habían modificado.
En código era algo así:
public void Merge<T>()
{
var source = GetRowsFromSourceDB<T>();
var target = GetRowsFromTargetDB<T>();
foreach (var s in source)
{
var match = target.First(x => x.Key == s.Key);
// Comparamos por reflection, propiedad a propiedad, ambos registros
if (IsModified(s, match))
ProcessRow(s);
}
}
La idea es muy simple:
- Cargamos en memoria los registros de las dos tablas. Esto nos permite reducir el número de consultas a la base de datos a costa de aumentar el consumo de memoria.
- Para cada registro en la tabla de origen, buscamos el registro equivalente en la tabla de destino.
- Comparamos sus propiedades usando reflection y, si se ha modificado, hacemos el proceso que sea necesario.
Al principio esto funcionaba bien y la eficiencia no era problema, pero con el paso del tiempo y el crecimiento de las tablas, la aplicación empezó a tardar demasiado, superando los 17 minutos de tiempo de ejecución.
Cuando empezamos a pensar sobre ello, lo primero que pensamos fue que nuestro sistema de carga de datos era demasiado lento o que estábamos invirtiendo demasiado tiempo comparando registros usando reflection. En ambos casos la solución pasaba por usar menos reflection, probablemente escribiendo a mano el código para comparar registros o usando LCG para generar dinámicamente métodos que hicieran las comparaciones.
Por suerte soy muy consciente de lo mal que se nos da a los humanos estimar qué es lo que realmente tarda en ejecutarse en una aplicación, así que antes de hacer nada usamos un profiler para ver qué estaba pasando y… sí, era la parte de reflection la que más tardaba, pero más que por la lentitud propia de reflection, porque se ejecutaba demasiadas veces.
Un cambio de algoritmo y todo resuelto
Dicen que el código más rápido es el que no se ejecuta y eso es lo que teníamos que hacer: ejecutar menos código.
Analizando el algoritmo inicial podemos ver que la sincronización de cada tabla tiene coste cuadrático, O(N2), con respecto al número de registros de la tabla. Por cada fila de la tabla de origen, hay que recorrer la tabla de destino para obtener el registro asociado y luego poder comparar.
El problema es que dado un registro, obtener su pareja nos cuesta O(N) porque tenemos que recorrer la lista de registros de destino. Si en lugar de una lista usamos una estructura de datos que nos permita localizar el registro más rápido, ganaremos mucho rendimiento y para eso, nada mejor que una tabla hash que nos permite acceder a un registro a partir de su clave en tiempo constante, O(1).
Ese cambio es sencillo y da lugar a un código como éste:
public void Merge<T>()
{
var source = GetRowsFromSourceDB<T>();
var target = GetRowsFromTargetDB<T>();
var targetDictionary = target.ToDictionary(x => x.Key, x => x);
foreach (var s in source)
{
var match = targetDictionary[s.Key];
// Comparamos por reflection, propiedad a propiedad, ambos registros
if (IsModified(s, match))
ProcessRow(s);
}
}
Es exactamente el mismo número de líneas de código, pero la complejidad a pasado de ser O(N2) a ser O(N+N), que para los que recordéis algo sobre complejidad de algoritmos es equivalente a O(N), es decir, ahora tenemos un algoritmo que se ejecuta en tiempo lineal.
Puede parece que pasar de O(N2) a O(N) no es para tanto, pero hagamos un cálculo rápido. Supongamos que tenemos 10.000 registros (una cifra no demasiado grande) y que la comparación de dos registros usando reflection tarda 0,01ms.
El tiempo del primer algoritmo, con complejidad O(N2), sería algo así:
104 * 104 * 10-2 = 106ms → 1000 segundos
Si medimos el segundo algoritmo, con complejidad O(N), se queda en:
104 * 10-2 = 102ms → 0.1 segundos.
No está nada mal para cambiar sólo una línea de código. Obviamente este cálculo es teórico y en la aplicación real hay otras partes implicadas (como la carga de datos), hay que tener en cuenta el tiempo que se tarda en crear la tabla hash, etc., pero en nuestro caso el tiempo total de ejecución bajó de más de 17 minutos a menos de 5 segundos.
Conclusiones
Por una parte, nunca te fíes de tu intuición con respecto al rendimiento de una aplicación: usa un profiler.
Si nos hubiésemos guiado por nuestra intuición, hubieramos tenido que escribir un mónton de código para comparar registros a mano o un generador de código con Reflection.Emit, cosa que no es trivial y el resultado ni siquiera hubiese sido bueno.
Además, elegir el algoritmo y la estructura de datos correcta puede ser clave para que una aplicación funcione o no.
Estamos tan acostumbrados a tratar con CPUs tan rápidas y conjuntos de datos tan pequeños que muchas veces no prestamos atención a esto, pero en cuanto los datos crecen un poco (y no hace falta que sea tanto), el algoritmo y la estructura de datos importan, y mucho.
Estas son las de las cosas que cuando estudias en segundo de carrera te pueden parecen demasiado teóricas, pero la realidad es que comprender la complejidad de un algoritmo y lo que ello implica te puede sacar de más de un apuro.
Un excelente ejemplo, bastante didáctico.
saludos,
Bravo, bonito ejemplo!
Podrias explicar lo del reflection o mas o menos que hace la funcion isModified(s,match);
Emilio, el código usaba reflection para comparar las propiedades de los objetos. Algo así:
private bool IsModified<T>(T current, T old) { var properties = typeof(T).GetProperties(); foreach (var property in properties) { var currentValue = property.GetValue(current, null); var oldValue = property.GetValue(old, null); if (!Equals(currentValue, oldValue)) return true; } return false; }En realidad era algo más complejo (caché, control de errores, etc).