Curiosidad sobre __hash__()

[Chema Cortes]

El 2009/2/10 Francesc Alted <faltet en pytables.org> escribió:

> Como se ve, la diferencia en tiempo entre usar un hash 'compacto' y
> el 'normal' es menor del 3%, cosa que no es significativa en absoluto.
> Obviamente, la hash por defecto (implementada en C) es casi 2x más
> rápida que las otras.  Pero diría que una hash 'compacta' implementada
> en C no sería significativamente más rápida que el defecto (si lo
> fuera, entonces no entiendo cómo funcionan las hashes en absoluto).

Me ha dado la "locura" de mirar cómo se implementan las búsquedas en
diccionarios. No se usa el hash tal cual para "organizar" los items.
Del hash sólo se usan los 16 bits más bajos para ir llenando los slots
donde colocar los items. Los 16 bits superiores se emplean para
introducir una "perturbación" cuando se producen las primeras
colisiones (hacen más densos los diccionarios). Al parecer, de esta
manera se consigue que los items similares se coloquen próximos para
ser leídos de golpe a una caché en donde hacer búsquedas más rápidas.

Podemos olvidarnos de distribuciones de hashes "compactas" y
"homogéneas"; más se parece a una especie de distribución gaussiana.

Según esta nueva visión, muchas colisiones son resueltas en el momento
de añadir el item, y no sólo cuando se hacen las búsquedas como
pensábamos. En cuento a velocidad, depende mucho del éxito en la
lecturas a caché. Intuyo que las arquitecturas de 64bits, capaces de
leer a caché el doble de bytes en un golpe, no están siendo
aprovechadas del todo. Así mismo, cuando se usa id(a)>>3 como hash se
estaría evitando operar con los 16bits altos para "densificar" el
diccionario. Estas operaciones en 16bits están penalizadas en
procesadores de 64bits, por lo que sería una explicación para la
mejora de rapidez que hemos visto.

Por supuesto, son todo conjeturas. El própio código en C de python
tiene muchas referencias sobre los cambios a hacer para adaptarse a
64bits. De momento habrá que esperar.

>> PD2 [OT]: Por coincidencias de la vida, estaba leyendo estos días un
>> artículo del "Communications of ACM" de enero del 2009 titulado "The
>> Long Road To 64 Bits", donde se repasa la lenta y compleja transición
>> que ha sufrido el tamaño del direccionamiento de los procesadores.
>> ¡Cuánta historia olvidada...!
>> <http://mags.acm.org/communications/200901/?pg=46>
>
> ¿Olvidada?  No! ahora es precisamente cuando nos toca a los usuarios
> el 'sufrirla' (y si no, que le pregunten a la compañía de Ballmer sus
> penurias para sacar una versión de 64-bits de su SO en condiciones.
> Por suerte, Linux y AMD nos han permitido asomarnos a ese mundo con
> unos cuantos años de ventaja sobre plataformas Wintel ;-)

No me refería sólo a los 64bits, sino a los "errores" de diseño con
los direccionamientos. Mucho se habla de cuando Bill Gates dijo que
con 640Kbytes de memoria era más que suficiente. Este tipo de
opiniones hicieron tomar una serie de decisiones erróneas que todavía
estamos sufriendo. Ahora parece que con los 64bits se quiere no caer
en los mismo errores, pero el tránsito parece muy lento, y va a
requerir revisar mucho código como nuestro querido python.

...y en cuanto a historia, más bien me refería la mía personal, con
los procesadores M68000 y lso TRAPs que aprovechaban los bits
superiores no usados del direccionamiento de memoria. Parecía muy
inteligente hasta que hubo que cambiarse a mejores procesadores.
_______________________________________________
Lista de correo Python-es 
http://listas.aditel.org/listinfo/python-es
FAQ: http://listas.aditel.org/faqpyes