Con la optimización de List<T>::FindAll (Predicate) he aprendido varias lecciones sobre optimización.
La teoría decía que, al marcar los resultados de la búsqueda, utilizar bits es más rápido que utilizar bools, pero mis test daban como ganador a los bools. Para evitar el uso de un array, utilizaba stackalloc, pero, por alguna extraña razón, estaba usando un array para tener los bitmasks! así:
byte [] byteMasks = new byte []
{
0x80,
; 0x40,
0x20,
0x10,
0x08,
0x04,
0x02,
0x01
};
int bitcounter = 0;
foreach (int number in numbers)
{
if (predicate (number))
{
(*ptr) = (byte) ((*ptr) | byteMasks [bitcounter]);
found++;
}
bitcounter++;
if (bitcounter > 7)
{
ptr++;
bitcounter = 0;
}
}
Este código es poco óptimo porque el array byteMasks tiene que ser cargado en el stack cada vez que lo utilizo. La forma óptima es utilizando funciones binarias, por ejemplo:
uint bitmask = 0x80000000;
for (int i = 0; i < this._size; i++)
{
if (match (this._items [i]))
{
(*ptr) = (*ptr) | bitmask;
found++;
}
bitmask = bitmask >> 1;
if (bitmask == 0)
{
ptr++;
bitmask = 0x80000000;
}
}
La mejora es evidente. Comparando este método con el antiguo de llenar una lista desde cero:
100 elementos:
Old method: 00:00:00.0120720
stackalloc bit method: 00:00:00.0004740 (25x)
1.000 elementos:
Old method: 00:00:00.0163290
stackalloc bit method: 00:00:00.0005400 (30x)
10.000 elementos:
Old method: 00:00:00.0133410
stackalloc bit method: 00:00:00.0013280 (10x)
50.000 elementos:
Old method: 00:00:00.0158860
stackalloc bit method: 00:00:00.0047910 (3x)
Un problema que detectó Miguel es que no es posible saber el tamaño del stack en un determinado momento. stackalloc por su parte no retornará un error si no hay espacio suficiente para reservar, por lo tanto era necesario limitar el uso del stack. Como estamos utilizando bits como marcadores (1 bit es a un elemento de la lista), si utilizamos el método nuevo para un máximo de 65536 elementos (0x10000), limitaríamos el uso del stack a 8KB (8 * 1024 * 8).
