Después del post anterior, estuve mirando el código de Mono para List<T>. Me pareció interesante el comentario del método que sugeria reimplementarlo, creando un grupo de bits, detectar cuáles elementos deben ser copiados y luego crear el array, teniendo el tamaño ya definido.

Desde el principio, las listas genéricas (List<T>) y otras clases de tamaño variable como ArrayList, colas, etc, necesitan incrementar su tamaño cuando un nuevo elemento es agregado. Internamente, todas utilizan un array como base. Cuando se insertan elementos, se debe crear un nuevo array (debidio a que los arrays son de tamaño fijo) y copiar los elementos desde el array antiguo al nuevo. Eso sería muy poco óptimo si se hiciera cada vez que insertamos un elemento. Lo que hace List, particularmente (aunque la mayoría hace lo mismo), es crear un array base de 16 elementos (a menos que se especifique el tamaño inicial con el contructor List<T> (int)). Cuando se inserta un elemento y la capacidad base está copada, se duplica el tamaño actual del array base. Esto permite mejorar el rendimiento geométricamente, respecto a la cantidad de elementos.

Esto está bien si vamos a trabajar con listas y no sabemos qué tamaño máximo tendrá. Pero en el caso de una búsqueda realizada con el método FindAll, podemos obtener ese tamaño antes de crear la lista de destino. Así, el procedimiento sería:

• Calcular tamaño
• Crear lista nueva
• Copiar elementos

Sin embargo, tenemos que realizar la búsqueda en los elementos de la lista. Esta podría hacerse al calcular el tamaño, pero tendríamos que hacerla nuevamente al copiar elementos. La opción ercomendada, entonces, es crear una lista de marcadores. Estos marcadores nos dirán qué elementos fueron encontrados y, por lo tanto, necesitan ser copiados a la lista de destino. El código proponía crear una lista de bits con stackalloc para hacer de marcadores.

¿Qué es stackalloc?. En palabras simples, permiten reservar memoria para tipos nativos directamente en el stack, y no en el heap (¿Confundido? aquí hay una explicación). Normalmente, si declaramos un array, el espacio para los elementos será reservado en el heap, mientras que en el stack sólo tendremos un puntero. La ganancia de reservar esta memoria en el stack es velocidad de acceso; el punto en contra es que perderemos los valores al finalizar la ejecución del método.

Tomando en cuenta todo esto, imeplemté cuatro métodos de búsqueda:

1.- método original: Se crea una lista genérica y se va llenando con los elementos encontrados (sin marcadores)
2.- stackalloc bool: Se reserva un bloque de bool's en el stack, los cuales serán utilizados como marcadores
3.- stackalloc bit: Se reserva un bloque de int's en el stack, cuyos btis serán utilizados como marcadores
4.- bool array: Se crea un array de bool's, los cuales son utilizados como marcadores

Al ejecutarlos con una lista inicial de 100 elementos:



Al ejecutarlos con una lista inicial de 1.000 elementos:



Al ejecutarlos con una lista inicial de 10.000 elementos:



Finalmente, al ejecutarlos con una lista inicial de 100.000 elementos:



El gráfico lo dice todo:


Aunque el segundo algoritmo (bool's en stack) es bastante más eficiente en pequeñas listas, no lo es tanto al incrementar la cantidad de elementos hasta 100.000 (barras azules), donde tienden a equipararse los últimos dos algoritmos, todos con marcadores.