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