Curiosidad sobre __hash__()

[Francesc Alted]

A Thursday 12 February 2009, Chema Cortes escrigué:
> El 2009/2/11 Francesc Alted <faltet en pytables.org> escribió:
> > A Wednesday 11 February 2009, Jesus Cea escrigué:
> >> Francesc Alted wrote:
> >> > No sé, todo esto me parece, como mínimo, sospechoso (bug?).
> >> > Alguien tiene alguna explicación?
> >>
> >> Puede ser un tema de fragmentación de la "freelist" y de las
> >> cachés de objetos python.
> >
> > Lo he estado pensando, y yo más bien creo que se trata de un tema
> > de slots disponibles.  Es decir, cuando la memoria del sistema está
> > bastante vacía los id() devuelven valores de memoria baja, y las
> > hashes funcionan bastante bien.  Sin embargo, cuando la memoria
> > empieza a 'llenarse', el id() de los nuevos objetos empieza a ser
> > alto, con lo que el algoritmo de la hash ya no funciona tan bien
> > para este caso.  Y parece que, para que esto pase es suficiente con
> > ocupar algo más de 128 MB, lo cual es poquísimo para los estándares
> > de hoy en día.
>
> Yo también creo que hay algo raro cuando se empieza a ocupar
> direcciones de memoria alta, pero por otros motivos. Ya hablé que los
> bits bajos del hash dan el slot base y que los bits altos se usan
> para producir una perturbación. En todos los lados veo que esta
> perturbación es un número sin signo que, mediante una fórmula, da un
> desplazamiento que sumaría un valor positivo a la dirección base para
> localizar el slot donde introducir el item del diccionario. Pero veo
> que la perturbación se inicializa con el hash, que es un número "con
> signo". Hay veces que el desplazamiento calculado sale negativo,
> concretamente para la primera colisión. Al ser negativo, es muy
> posible que se encuentre con un slot ocupado, lo que provocaría un
> "resize" del diccionario para obtener más slots.

Bueno, tú lo has dicho más bonito, pero sí, por ahí supongo que deben ir 
las cosas, pero la verdad es que los detalles internos del intérprete 
se me escapan.

> Como siempre, es una conjetura. Si puedo este fin de semana lo
> comprobaré, a ver si me acuerdo cómo se hacía una depuración en C :-P

Uff, que atrevido ;-)  Pues nada, si descubres algo nos mantienes 
informados...

>
> > Si esto es cierto, me pregunto si, dado que las máquinas empiezan a
> > tener cantidades de memoria bastante grandes, los de Python
> > deberían plantearse subir el esquema 16bit/16bit (el que nos
> > comentaba Chema) a 24bit/24bit (por decir algo), sobretodo para
> > máquinas de 64-bits.
>
> En el mismo código que define el objeto diccionario, se dice que los
> enteros largos de 32bits podrían no ser suficientes en el futuro
> (64bits) para resolver las colisiones, y añade:
>
> "Getting a hash code as fat as Py_ssize_t is the only real cure.  But
> in practice, this probably won't make a lick of difference for many
> years (at which point everyone will have terabytes of RAM on 64-bit
> boxes)."
>
> 'Py_ssize_t' serían los enteros largos con signo con el mismo tamaño
> que los punteros.

Lo mismo estaría bien hacerlo pronto, aún sin necesidad de llegar a 
tener terabytes de memoria :-P

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