Curiosidad sobre __hash__()
Francesc Alted
faltet en pytables.org
Mar Feb 10 10:29:10 CET 2009
A Tuesday 10 February 2009, Chema Cortes escrigué:
> Yo también he hecho mis experimentos. Se supone que el hash es para
> mejorar la velocidad de accesos arbitrarios, así que mi experimento
> intenta incorporar algo de aleatoriedad. Para recorrer
> secuencialmente todo el diccionario, como haces en tu código, tal vez
> no se aprecie ninguna mejora.
>
>
> In [7]: from random import choice
>
> In [8]: class A(object):
> ...: def __hash__(self): #__hash__ compacto
> ...: return id(self) >> 3
> ...:
>
> In [9]: class B(object):
> ....: def __hash__(self): #__hash__ como entero largo sin
> signo ....: return id(self)
> ....:
> ....:
>
> In [10]: class C(object): #__hash__ por defecto (entero 32bit con
> signo) ...: pass
> ...:
>
> In [11]: N = 1000000
>
> In [12]: dA = dict((A(),i) for i in xrange(N))
>
> In [13]: dB = dict((B(),i) for i in xrange(N))
>
> In [14]: dC = dict((C(),i) for i in xrange(N))
>
> In [15]: %time l = [dA[choice(dA.keys())] for i in xrange(1000)]
> CPU times: user 122.01 s, sys: 6.07 s, total: 128.08 s
> Wall time: 134.27 s
>
> In [16]: %time l = [dB[choice(dB.keys())] for i in xrange(1000)]
> CPU times: user 151.80 s, sys: 5.85 s, total: 157.65 s
> Wall time: 171.92 s
>
> In [17]: %time l = [dC[choice(dC.keys())] for i in xrange(1000)]
> CPU times: user 150.35 s, sys: 5.20 s, total: 155.55 s
> Wall time: 160.03 s
>
>
> En el bugs.python.org se hablaba de ganancias del 10%. Yo estoy
> consiguiendo del orden del 18% (y sin optimizar en C).
>
> > O sea, que de manera consistente, la hash sin dividir parece que
> > saca más rendimiento (un 15%) que la dividida por 8. No sé, lo
> > mismo el rendimiento depende de la plataforma (o no he hecho bien
> > los cálculos).
>
> Estoy convencido que la plataforma tiene bastante influencia. He
> probado con tu mismo código (corrigiendo el primer caso con >>3 , y
> añadiendo el caso del __hash__ por defecto) y los tiempos que me
> salen son, respectivamente, 2.081, 2.302 y 1.20. Me sale a la inversa
> que a tí.
>
> PD: Pruebas hechas en un AMD Sempron 3000+, 64/32bits
Mmm, pues puede que haya diferencias por plataforma, pero yo más bien
diría que es problema de cómo medimos los tiempos. Hay que tener en
cuenta que el tiempo de búsqueda en la tabla hash es normalmente
despreciable comparado con la infraestructura que montamos para
medirlo. Así que muchas veces medimos más cosas como fallos de caché
(de ahí pueden salir las diferencias por plataforma) o simplemente
aleatoriedades (derivadas del uso de choice(), como en tu caso) que
tiempos reales.
Así que he intentado diseñar un benchmark que elimine ese tipo de
aleatoriedades (y aunque el tema de las fluctuaciones for diferencias
en las cachés es más peludo, también he elegido diccionarios
suficientemente grandes para que no quepan dentro de las caches de los
procesadores actuales). Aquí van los resultados para un Core2 @ 3 GHz
con 8 MB de cache secundaria, openSUSE 11.1, gcc 4.3 y Python 2.6:
In [1]: import random
In [2]: class A(object):
...: def __hash__(self):
...: return id(self) >> 3
...:
In [3]: class B(object):
...: def __hash__(self):
...: return id(self) >> 0
...:
In [4]: class C(object):
...: pass
...:
In [5]: N = 1000000
In [6]: dA = dict((A(),i) for i in xrange(N))
In [7]: dB = dict((B(),i) for i in xrange(N))
In [8]: dC = dict((C(),i) for i in xrange(N))
In [9]: random.seed(1000) ; dAkeys = dA.keys() ; random.shuffle(dAkeys)
In [10]: random.seed(1000) ; dBkeys = dB.keys() ; random.shuffle(dBkeys)
In [11]: random.seed(1000) ; dCkeys = dC.keys() ; random.shuffle(dCkeys)
In [12]: %timeit [dA[k] for k in dAkeys]
10 loops, best of 3: 774 ms per loop
In [13]: %timeit [dB[k] for k in dBkeys]
10 loops, best of 3: 789 ms per loop
In [14]: %timeit [dC[k] for k in dCkeys]
10 loops, best of 3: 484 ms per loop
In [15]: %timeit [k for k in dAkeys]
10 loops, best of 3: 164 ms per loop
Como se ve, para minimizar el efecto de extraer todas la claves para
elegir sólo una (demasiado costoso en tiempo), lo que he hecho ha sido
extraes las claves en una lista aparte para después barajarlas
(shuffle). He usado una semilla antes de barajar para generar siempre
la misma secuencia de mezcla. Con eso he intentado minimizar los
efectos aleatorios del generador de números pseudo-aleatorios.
Para ver los tiempos reales de búsqueda en el diccionario, he calculado
el tiempo que se usa en la 'infraestructura' (comando [15]) del
benchmark, que habría que restarlo de los anteriores. Con esto, los
tiempos medios de búsqueda me salen:
Con hash compacto (id(self) >> 8) --> 610 ns
Con hash normal (id(self) >> 0) --> 625 ns
Con hash implementada en C (defecto) --> 320 ns
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).
> 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 ;-)
Saludos,
--
Francesc Alted
------------ próxima parte ------------
_______________________________________________
Lista de correo Python-es
http://listas.aditel.org/listinfo/python-es
FAQ: http://listas.aditel.org/faqpyes
Más información sobre la lista de distribución Python-es