Foro - Perl en Español

Desde julio del 2002 se estaba utilizando la biblioteca de código abierto uthash, que se basa en una serie de listas enlazadas, al igual a como lo hace Perl desde la versión 1.

Esta estructura es simple de implementar, pero estamos en una era donde lo que se prima son las prestaciones, y hay que minimizar las faltas de acceso a las cachés de las CPU.

Una solución diferente: el hashing de direccionamiento abierto. Esto es equivalente más o menos a usar un gran array con colisiones encadenadas, y eliminando las listas enlazadas. No se eliminan todas las colisiones, pero las reduce. La estrategia es la de guardar la pareja clave/valor en el array cerca del lugar correcto, y buscar por las posiciones donde la clave podría estar o se agoten todas las posiciones posibles.

Actualmente, uno de los métodos más eficientes es el hashing “Robin Hood”. En actualizaciones, mueve entradas para minimizar la distancia de todas las claves a sus posiciones ideales, no sólo la clave añadida o eliminada. Normalmente, esto aumenta la posibilidad de que se encuentre en la caché de la CPU.

Todo esto ya está disponible en la rama principal del compilador Rakudo. Informes preliminares indican una mejora del 10 % al 15 %.

Artículo completo (en inglés)