[Python-Dev] Hashing proposal: change only string-only dicts

[Gregory P. Smith]

On Wed, Jan 18, 2012 at 9:55 AM, "Martin v. Löwis" <martin at v.loewis.de>wrote:

> Am 18.01.2012 17:01, schrieb PJ Eby:
> > On Tue, Jan 17, 2012 at 7:58 PM, "Martin v. Löwis" <martin at v.loewis.de
> > <mailto:martin at v.loewis.de>> wrote:
> >
> >     Am 17.01.2012 22:26, schrieb Antoine Pitrou:
> >     > Only 2 bits are used in ob_sstate, meaning 30 are left. These 30
> bits
> >     > could cache a "hash perturbation" computed from the string and the
> >     > random bits:
> >     >
> >     > - hash() would use ob_shash
> >     > - dict_lookup() would use ((ob_shash * 1000003) ^ (ob_sstate & ~3))
> >     >
> >     > This way, you cache almost all computations, adding only a
> computation
> >     > and a couple logical ops when looking up a string in a dict.
> >
> >     That's a good idea. For Unicode, it might be best to add another slot
> >     into the object, even though this increases the object size.
> >
> > Wouldn't that break the ABI in 2.x?
>
> I was thinking about adding the field at the end, so I thought it
> shouldn't. However, if somebody inherits from PyUnicodeObject, it still
> might - so my new proposal is to add the extra hash into the str block,
> either at str[-1], or after the terminating 0. This would cause an
> average increase of four bytes of the storage (0 bytes in 50% of the
> cases, 8 bytes because of padding in the other 50%).
>
> What do you think?
>

str[-1] is not likely to work if you want to maintain ABI compatibility.
 Appending it to the data after the terminating \0 is more likely to be
possible, but if there is any possibility that existing compiled extension
modules have somehow inlined code to do allocation of the str field even
that is questionable (i don't think there are?).

I'd also be concerned about C API code that uses PyUnicode_Resize(). How do
you keep track of if you have filled in these extra bytes at the end in or
not?  allocation and resize fill it with a magic value indicating "not
filled in" similar to a tp_hash of -1?

Regardless of all of this, I don't think this fully addresses the overall
issue as strings within other hashable data structures like tuples would
not be treated this way, only strings directly stored in a dict.  Sure you
can continue on and "fix" tuples and such in a similar manner but then what
about user defined classes that implement __hash__ based on the return
value of hash() on some strings they contain?

I don't see anything I'd consider a real complete fix unless we also
backport the randomized hash code so that people who need a guaranteed fix
can enable it and use it.

-gps
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20120119/7a1d0896/attachment.html>