Compatible numeric hashes

[GvR, 2010-03-21 17:04:48]

(This is not a complete review, just some things that popped into my mind.
Hopefully you can get someone of Tim Peters's kaliber to review.)

http://codereview.appspot.com/660042/diff/19001/11011
File Objects/longobject.c (right):

http://codereview.appspot.com/660042/diff/19001/11011#newcode2577
Objects/longobject.c:2577: this multiplies by 2**PyLong_SHIFT modulo 2**31 - 1.
*/
Can't say I understand all this. I guess my number theory is lacking; I don't
get how you can compute modulo a prime by using a shift. ;-(

http://codereview.appspot.com/660042/diff/19001/11011#newcode2582
Objects/longobject.c:2582: incrementing.  This preserves the value modulo
incrementing? This comment seems outdated now.

http://codereview.appspot.com/660042/diff/19001/11007
File Python/sysmodule.c (right):

http://codereview.appspot.com/660042/diff/19001/11007#newcode578
Python/sysmodule.c:578: A private struct sequence providing parameters used for
computing\n\
Why private? I'm sure 3rd party number implementations will want to consult this
too. It should be a public API.

[dickinsm, 2010-03-23 11:56:56]

http://codereview.appspot.com/660042/diff/19001/11011
File Objects/longobject.c (right):

http://codereview.appspot.com/660042/diff/19001/11011#newcode2577
Objects/longobject.c:2577: this multiplies by 2**PyLong_SHIFT modulo 2**31 - 1.
*/
On 2010/03/21 17:04:48, GvR wrote:
> Can't say I understand all this. I guess my number theory is lacking; I don't
> get how you can compute modulo a prime by using a shift. ;-(

I'll add some explanatory comments. (That 2**31 - 1 needs to be changed to
_PyHASH_MASK, too.)  The idea's something like the following:  suppose 0 <= x <
2**31;  you want to multiply x by 2**15 and then reduce the result modulo
2**31-1.  Let y be the portion of x that's shifted out of the top of the
original 31 bits, so that x * 2**15 = y * 2**31 + z for some z.  Then since
2**31 reduces to 1 modulo 2**31-1, y*2**31 reduces to y.  So x*2**15 reduces to
y + z.  IOW, you just take the 15 bits that were shifted out of the top
(y*2**31) and add them back in at the bottom (as y), so you end up with a
rotation.

http://codereview.appspot.com/660042/diff/19001/11011#newcode2582
Objects/longobject.c:2582: incrementing.  This preserves the value modulo
On 2010/03/21 17:04:48, GvR wrote:
> incrementing? This comment seems outdated now.

Agreed.  I'll remove it.

http://codereview.appspot.com/660042/diff/19001/11009
File Objects/object.c (right):

http://codereview.appspot.com/660042/diff/19001/11009#newcode667
Objects/object.c:667: 1 + reduce(x-1) if x > 0
On reflection, I think this could be simplified to just reduce(x).  (So it
reduces to 0, ... P-1 rather than 1, ... P).  The +-1 aren't necessary, and just
make it that little bit harder and more error-prone for 3rd party hashes.

FWIW, the (minor) advantages of the extra +-1 were:

  - it means that hash(x) == 0 iff x == 0, hash(x) > 0 for
    all x > 0 and hash(x) < 0 for x < 0.  Which is cute,
    but not really especially useful.

  - it retains the property that hash(x) == x for all
    (Python 2.x, short) ints x, with two exceptions
    (-1 and -2**31).  Without the +-1 above, there are 4
    exceptions (-1, -2**31+1, -2**31 and 2**31-1), so makes
    the implementation for short ints slightly cleaner.
    Since this isn't likely to go into 2.x anyway, that's
    not much of an advantage.  Also, this doesn't help on
    64-bit platforms, where we're using 61 bits rather than
    63.

http://codereview.appspot.com/660042/diff/19001/11010
File Objects/typeobject.c (right):

http://codereview.appspot.com/660042/diff/19001/11010#newcode4936
Objects/typeobject.c:4936: h = PyLong_AsLongAndOverflow(res, &overflow);
There's a missing exception check on the result of PyLong_AsLongAndOverflow
here.

http://codereview.appspot.com/660042/diff/19001/11010#newcode4938
Objects/typeobject.c:4938: if (PyLong_Check(res))
Need to check what the correct behaviour is when the __index__ method returns
something that's not a Python integer;  add tests for this if they don't already
exist.

http://codereview.appspot.com/660042/diff/19001/11007
File Python/sysmodule.c (right):

http://codereview.appspot.com/660042/diff/19001/11007#newcode578
Python/sysmodule.c:578: A private struct sequence providing parameters used for
computing\n\
On 2010/03/21 17:04:48, GvR wrote:
> Why private? I'm sure 3rd party number implementations will want to consult
this
> too. It should be a public API.

Okay, will make it public.  That gives me greater motivation to make sure that I
get it absolutely right first time.  :)

[dickinsm, 2010-03-23 12:12:09]

http://codereview.appspot.com/660042/diff/19001/11010
File Objects/typeobject.c (right):

http://codereview.appspot.com/660042/diff/19001/11010#newcode4938
Objects/typeobject.c:4938: if (PyLong_Check(res))
On 2010/03/23 11:56:56, dickinsm wrote:
> Need to check what the correct behaviour is when the __index__ method returns
something that's not a Python integer.

Bah.  I meant __hash__ method, of course.

[Christophe Simonis, 2010-04-04 17:15:20]

http://codereview.appspot.com/660042/diff/42010/51008
File Doc/library/stdtypes.rst (right):

http://codereview.appspot.com/660042/diff/42010/51008#newcode674
Doc/library/stdtypes.rst:674: hash = -2
Error: must be
   hash_ = -2

[dickinsm, 2010-05-22 10:05:57]

http://codereview.appspot.com/660042/diff/42010/51008
File Doc/library/stdtypes.rst (right):

http://codereview.appspot.com/660042/diff/42010/51008#newcode674
Doc/library/stdtypes.rst:674: hash = -2
On 2010/04/04 17:15:20, Christophe Simonis wrote:
> Error: must be
>    hash_ = -2

Thanks!  Fixed in the next iteration.

[dickinsm, 2010-05-23 10:46:32]

http://codereview.appspot.com/660042/diff/63001/64009
File Doc/library/stdtypes.rst (right):

http://codereview.appspot.com/660042/diff/63001/64009#newcode631
Doc/library/stdtypes.rst:631: - If ``x = m / n`` is a negative rational number
and ``n`` is not divisible by
Remove the "and ``n`` is not divisible by ``P``" here.

http://codereview.appspot.com/660042/diff/63001/64009#newcode637
Doc/library/stdtypes.rst:637: - The particular values ``sys.hash_info.inf``,
``sys.hash_info.ninf`` and
"sys.hash_info.ninf" should be "-sys.hash_info.inf".