<br><div class="gmail_quote">On Wed, Jan 18, 2012 at 9:55 AM, "Martin v. Löwis" <span dir="ltr"><<a href="mailto:martin@v.loewis.de" target="_blank">martin@v.loewis.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Am 18.01.2012 17:01, schrieb PJ Eby:<br>
<div>> On Tue, Jan 17, 2012 at 7:58 PM, "Martin v. Löwis" <<a href="mailto:martin@v.loewis.de" target="_blank">martin@v.loewis.de</a><br>
</div><div><div>> <mailto:<a href="mailto:martin@v.loewis.de" target="_blank">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>
> Wouldn't that break the ABI in 2.x?<br>
<br>
</div></div>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?<br></blockquote><div><br></div><div>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?).</div>
<div><br></div><div>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?</div>
<div><br></div><div>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?</div>
<div><br></div><div>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.</div><div><br></div><div>
-gps</div></div>