Mejorando el rendimiento de un IEnumerable

En el post sobre qué colecciones exponer en APIs públicas, decía que uno de los problemas de exponer un IEnumerable era que el cliente no podía predecir fácilmente si recorrerlo sería una operación cara o barata. Esto es debido a la propia naturaleza de IEnumerable, que permite ir generando los elementos según se van necesitando, por lo que la generación del elemento es costosa, estaremos incurriendo en ese coste cada vez que lo recorramos.

Una opción para evitar esto es utilizar los métodos ToArray o ToList que evaluan el IEnumerable y almacenan los resultados en array o una lista, pero esto tiene varios inconvenientes. Por una parte, es posible que estemos forzando la evaluación de más elementos de los que vamos a necesitas, además, si en IEnumerable contiene infinitos elementos, estos métodos entrarán en un bucle infinito.

Para intentar resolver eso, podemos recurrir a una técnica conocida como memoización (Memoization).

¿Qué es la memoización?

La memoización consiste en almacenar los valores que ya hemos calculado de una función para que, en futuras invocaciones, en lugar de volver a calcularlos, podamos devolver el valor que ya habíamos calculado previamente.

En clojure existe una función, memoize, que permite crear la versión memoizada de una función:

(defn slow-func [x]
  (Thread/sleep 1000)
  x)

(def mslow-func (memoize slow-func))

;; Al ejecutarla la primera vez, se ejecutará la función y tardará 1 segundo
(time (mslow-func 3))
;; "Ellapsed time 999.31121 msec"
;; 3

;; Al ejecutarla nuevamente, usará el resultado calculado previamente
(time (mslow-func 3))
;; "Ellapsed time 0.038881 msec"
;; 3

En el fondo no es más que un sistema de caché primitivo, en el que no existe un control sobre el tamaño de la caché (lo que hace que pueda ser problemático en determinados escenarios).

Memoizando un IEnumerable

La idea es aplicar la misma técnica sobre un IEnumerable usando el patrón decorador. En el caso del IEnumerable realmente no existen parámetros de entrada explícitos, pero podemos considerar que existe un “índice” implícito en la enumeración basado en el número de llamadas realizadas a Enumerator.MoveNext.

A partir de esa idea, lo que haremos será tener una lista que actúe como cache de resultados previos, y cada vez que recorramos el IEnumerable primero devolveremos los elementos de la lista y, cuando se terminen, iremos calculando nuevos elementos del IEnumerable que estamos decorando y cacheándolos en la lista antes de devolverlos.

El código no es muy bonito pero tampoco es excesivamente complicado de seguir:

public class MemoizedEnumerable<T> : IEnumerable<T>
{
  private readonly List<T> cache = new List<T>();

  private readonly IEnumerable<T> innerEnumerable;

  private IEnumerator<Tgt; innerEnumerator;
  private bool innerEnumeratorIsConsumed;
  private bool innerEnumeratorIsDisposed;

  public MemoizedEnumerable(IEnumerable<T> innerEnumerable)
  {
    this.innerEnumerable = innerEnumerable;
  }

  IEnumerator IEnumerable.GetEnumerator()
  {
    return GetEnumerator();
  }

  public IEnumerator<T> GetEnumerator()
  {
    if (innerEnumerator == null)
      innerEnumerator = innerEnumerable.GetEnumerator();
    return new MemoizedEnumerator<T>(this);
  }

  public class MemoizedEnumerator<T> : IEnumerator<T>
  {
    // La idea es devolver primero resultados de la cache.
    // Cuando se termina, se van extrayendo resultados de
    // enumerator y guardandolos en la cache

    private int currentPos;
    private readonly MemoizedEnumerable<T> parent;

    public MemoizedEnumerator(MemoizedEnumerable<T> parent)
    {
      this.parent = parent;
      currentPos = -1;
    }

    object IEnumerator.Current
    {
      get { return Current; }
    }

    public T Current
    {
      get
      {
        return parent.cache[currentPos];
      }
    }

    public bool MoveNext()
    {
      currentPos++;

      // Si tengo algo en la lista, puedo avanzar
      if (currentPos < parent.cache.Count)
        return true;

      // Si se ha acabado la lista y hemos recorrido entero
      // el enumerator, ya no hay nada más
      if (parent.innerEnumeratorIsConsumed)
        return false;

      // Miro a ver si queda algo en el enumerator. Si lo hay,
      // lo cacheo para luego

      parent.innerEnumeratorIsConsumed = !parent.innerEnumerator.MoveNext();

      if (!parent.innerEnumeratorIsConsumed)
        parent.cache.Add(parent.innerEnumerator.Current);

      return !parent.innerEnumeratorIsConsumed;
    }

    public void Reset()
    {
      currentPos = 0;
    }

    public void Dispose()
    {
      // Esto es un poco... peligroso. No puedo hacer el dispose del 
      // enumerator que estoy encapsulando para luego poder seguir
      // donde lo dejé. Esto quiere decir que si está manteniendo 
      // recursos no manejados (por ejemplo, una conexión a una base
      // de datos) tengo un problema potencial.

      // Una vez que haya consumido completamente el enumerator 
      // interno, ya no lo necesito más y puedo disposearlo

      if (parent.innerEnumeratorIsConsumed && 
          !parent.innerEnumeratorIsDisposed)
      {
        parent.innerEnumerator.Dispose();
        parent.innerEnumeratorIsDisposed = true;
      }
    }
  }
}

public static class EnumerableExtensions
{
  public static IEnumerable<T> Memoize(this IEnumerable<T> enumerable)
  {
    return new MemoizedEnumerator<T>(enumerable);
  }
}

Podemos comprobar el funcionamiento con algo así:

public static IEnumerable<int> GetValues()
{
  for (var i = 0; i < 5; i++)
  {
    Console.WriteLine("Generando " + i);
    yield return i;
  }
}

var data = GetValues().Memoize();

foreach (var x in data.Take(2))
  Console.Out.WriteLine(x);

Console.Out.WriteLine("----");

foreach (var x in data)
  Console.Out.WriteLine(x);

Tenemos un método, GetValues, que devuelve un IEnumerable que, cada vez que genera un valor, lo indica en pantalla. Al memoizarlo, cuando ejecutemos el segundo foreach no se volverán a generar los valores consumidos por el primero, obteniendo una salida parecida a esta:

Generando 0
0
Generando 1
1
----
0
1
Generando 2
2
Generando 3
3
Generando 4
4

Como véis, nuestro enumerable memoizado “recuerda” los valores que ya ha generado y evita volver a calcularlos.

El código anterior no está exento de problemas y limitaciones, algunos bastante complicados (¿imposibles?) de resolver. Por una parte, no es en absoluto thread-safe. Si intentamos recorrer en enumerable a la vez desde varias hebras, tendremos problemas. Eso no es un problema demasiado grave ya que ni siquiera sabemos a priori si el enumerable que estamos encapsulando lo era.

Lo peor es que, como indica el comentario en el método Dispose, no podemos hacer un Dispose del enumerador interno hasta que no acabamos de recorrerlo. Dependiendo de cómo se esté generando el enumerable, esto puede ser bastante grave si, por ejemplo, está manteniendo abierta una conexión a una base de datos o un fichero.

Conclusión

La idea de la memoización es interesante y en lenguajes funcionales, donde las funciones tienden a ser puras (sin efectos colaterales) y es habitual trabajar con funciones de orden superior, resulta una manera muy natural de mejorar el rendimiento de algunos algoritmos. También es cierto que hay que tener cuidado porque al no controlar el tamaño de la “caché”, podemos llevarnos sorpresas.

En el caso del IEnumerable, hay escenarios en que puede resultar útil, por ejemplo cuando tenemos varias expresiones LINQ complejas que queremos evitar recalcular:

var result = someList
               .Where(x => x.Name.StartsWith("P"))
               .Select(x => new 
               { 
                 Name = x.Name, 
                 City = x.City,
                 Value = SomeSlowCalculation(x) 
               });

Si recorriésemos dos veces el enumerable, obligaríamos a hacer dos evaluaciones de SomeSlowCalculation para cada elemento de la lista, y eso con el MemoizedEnumerable nos lo ahorraríamos. Sin él, podríamos usar un ToList para materializar el enumerable, pero eso haría que calculásemos cosas que a lo mejor no necesitamos.

De todas formas, la limitación del Dispose hace que no me acabe de convencer esta idea, pero llevaba varios días rondándome la cabeza y he preferido contarla para quitármela de en medio. Puede que a alguien le resulte útil y, si alguno tiene una idea para evitar el problema con el Dispose, estaré encantado de escucharle.


6 comentarios en “Mejorando el rendimiento de un IEnumerable

  1. No conozco demasiado el mundo de .net pero tal vez este articuo te resulte interesante:
    http://bartdesmet.net/blogs/bart/archive/2010/01/07/more-linq-with-system-interactive-functional-fun-and-taming-side-effects.aspx
    via
    http://bugsquash.blogspot.com.es/2011/10/10-reasons-to-use-f-runtime-in-your-c.html
    En este ultimo habla de las ventajas de poder usar versiones persistentes de colecciones (en este caso provenientes de f shap) que no necesitan copias enteras cuando son modificadas sino que crean diferentes versiones de la misma que comparten los datos no modificados.
    La version cacheada no es equivalente a una lista perezosa (o stream), ¿no? como por ejemplo:
    http://blogs.msdn.com/b/wesdyer/archive/2007/02/13/the-virtues-of-laziness.aspx

  2. Juan María Hernández dijo:

    Muchas gracias por los enlaces, son muy interesantes, sobre todo el primero.

    Con respecto a las colecciones persistentes, existe una librería que tiene buena pinta: Immutable Collections . No sé si serán igual de eficientes que las implementaciones de F# (supongo que por el estilo), pero el API es algo más bonita para usarla desde C# y además tiene algunas cosas curiosas (como los builders para optimizar cambios masivos y liberar de presión al GC).

    Sobre lo de la equivalencia entre la versión cacheada y la lazy, no sé muy bien a que te refieres, pero desde luego no se parece al Stream que aparece en ese enlace. En todo caso, se parece más al MemoizeAll del primero (aunque bastante más de andar por casa, por ejemplo no controla el relanzamiento de excepciones).

  3. Un poco confuso….. mira que eres claro, pero aquí no me lo parece :-). En principio estas haciendo una condición implícita sobre IEnumerator que no es cierta y es que los datos subyacentes no siempre son iguales ( menos en una BD ) y por lo tanto un memoize no tiene demasiado sentido, en general podría aplicar esto mismo a casi cualquier colección subyacente… no se, me parece un poco “forzado” el ejemplo,

    Unai

  4. Juan María Hernández dijo:

    Sí, posiblemente no sea el post más claro que he escrito :-)

    Efectivamente, si esperas que los datos sean cambiantes, esta técnica no tiene sentido, pero, sinceramente, en ese caso, creo que sería mejor usar otra abstracción, como IQueryable o las Rx que menciona josejuan para hacer más explícita esa posibilidad.

    El problema que hay con IEnumerable es que, al ser tan flexible, nunca tienes muy claro qué va a pasar con él, y eso hace que “por si acaso”, se acabe llamado a ToList() muchas más veces de las necesarias.

  5. Pingback: Lo mejor de la semana sobre desarrollo web en español vol. 28 | ADWE

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *

*

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>