Curiosidad sobre __hash__()

[Francesc Alted]

A Tuesday 10 February 2009, Chema Cortes escrigué:
> 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.

Pues suerte que te ha dado la "locura", porque yo desde luego no me 
imaginaba que el algoritmo hash fuera ese (leyendo los comentarios del 
código queda claro que eso de las tablas hash es todo un mundo).

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

En efecto.  Aunque para entradas de un millón de elementos, yo diría que 
la distribución debe ser más parecida a una plana (con unos 15 
elementos en cada slot, o lo que es lo mismo, unas 15 colisiones por 
slot en la hash de 16 bits).

> 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.

Así parece, sí.

> 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.

Bueno, no creo que en lectura el tema de la platforma tenga mucho que 
ver.  Acabo de rehacer el experimento en mi antiguo (y entrañable :-) 
portátil que tiene un Pentium 4 @ 2 GHz con 256 KB de cache secudaria, 
y las conclusiones son parecidas que con mi máquina de 64-bits, a 
saber:

Con hash compacto (id(self) >> 8) --> 2375 ns
Con hash normal (id(self) >> 0) --> 2325 ns
Con hash implementada en C (defecto) --> 935 ns

O sea, que no se observan diferencias substanciales entre hashes con 
corrimiento o no.  Esto es lógico ya que, como hemos visto, para 
diccionarios tan grandes la tabla hash tiene una media de 15 colisiones 
por slot, corras o no los bits 3 posiciones.  Lo que no sé es, si para 
plataformas de 64-bits, las particiones de 16/16 pasan a ser de 32/32, 
aunque parece lógico suponer que sea así, así que diría que en ese caso 
habrían muchas menos colisiones, pero vaya, estoy elucubrando (o sea 
que tengo bastantes probablidades de equivocarme).

Dicho esto, y mirando con más cuidado el ticket 5186, parece que la 
gente habla de optimización en la *creación* de diccionarios, y no en 
su consulta.  En tal caso, y para tamaños de diccionarios pequeños 
(digamos, hasta 2**(16+3) = 524288 entradas, y de hecho, ellos hacen 
las pruebas con 10000 elementos), sí que tiene sentido suponer que un 
corrimiento de 3 bits puede dar lugar a que la hash tenga menos 
colisiones (ya que los 3 primeros bits son siempre 0 para posiciones de 
objectos en memoria, y por tanto ellos nunca van a decidir el slot).

De hecho, esta mejora *sí* que la observo, tanto en platformas de 
32-bit:

In [22]: %time dA = dict((A(),i) for i in xrange(N))
CPU times: user 40.25 s, sys: 0.32 s, total: 40.57 s
Wall time: 41.97 s

In [24]: %time dB = dict((B(),i) for i in xrange(N))
CPU times: user 45.20 s, sys: 0.33 s, total: 45.53 s
Wall time: 48.38 s

In [26]: %time dC = dict((C(),i) for i in xrange(N))
CPU times: user 59.60 s, sys: 0.52 s, total: 60.12 s
Wall time: 64.94 s

como en 64-bit:

In [63]: %time dA = dict((A(),i) for i in xrange(N))
CPU times: user 13.23 s, sys: 0.06 s, total: 13.29 s
Wall time: 13.31 s

In [65]: %time dB = dict((B(),i) for i in xrange(N))
CPU times: user 15.68 s, sys: 0.06 s, total: 15.74 s
Wall time: 16.34 s

In [67]: %time dC = dict((C(),i) for i in xrange(N))
CPU times: user 21.29 s, sys: 0.05 s, total: 21.33 s
Wall time: 21.37 s

Así pues, se ve una diferencia de velocidad entre el modelo con 
corrimiento (el que llamábamos 'compacto') y el no corrido de entre un 
15% (32-bit) y un 22% (64-bit), cosa que no es despreciable en 
absoluto, en efecto.

> 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.

Pues sí, y hablando de conjeturas y elucubraciones, llama la atención 
que en los tiempos de arriba, para los objectos C() que no sobrecargan 
el método hash (por tanto, éste es equivalente a B()), los tiempos sean 
un 30% superiores que para objectos B().  He intentado entender lo que 
pasa pero no he podido :-/

Llegados a este punto, me pregunto si las medidas que hago son buenas, o 
algún efecto que no entiendo las hacen inservibles (supongo que la 
misma pregunta puede aplicarse a la gente que hace los benchmarks para 
el ticket 5186).  En fin, si alguien tiene alguna explicación para el 
problema de los objetos C() se lo agradecería (no es que realmente me 
importe demasiado, pero una vez llegados a este punto me gustaría saber 
qué narices pasa).

> 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.

Bueno, afortunadament la gente de Python ya ha trabajado mucho el tema 
de 64-bits en plataformas Linux/AMD (aunque eso no quiere decir que 
esté todo solucionado, y menos para plataformas Wintel ;-)

> ...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.

:-)

Saludos,

-- 
Francesc Alted
_______________________________________________
Lista de correo Python-es 
http://listas.aditel.org/listinfo/python-es
FAQ: http://listas.aditel.org/faqpyes