Author: Philip Jenvey <[email protected]>
Branch: py3k-newhash
Changeset: r63951:34a0157937d1
Date: 2013-05-09 15:32 -0700
http://bitbucket.org/pypy/pypy/changeset/34a0157937d1/
Log: modernize int's hash: it's now x modulo the new HASH_MODULUS. an
exact port of CPython's impl is tricky for 64bit because it assumes
HASH_BITS (61) >= rbigint's SHIFT (63), which isn't true on PyPy. so
our algorithm differs and we calculate the hash via the 'wide' type
like many rbigint methods
diff --git a/pypy/module/sys/system.py b/pypy/module/sys/system.py
--- a/pypy/module/sys/system.py
+++ b/pypy/module/sys/system.py
@@ -3,6 +3,7 @@
from rpython.rlib import rfloat, rbigint
from rpython.rtyper.lltypesystem import rffi, lltype
from pypy.objspace.std.floatobject import HASH_INF, HASH_MODULUS, HASH_NAN
+from pypy.objspace.std.longobject import HASH_MODULUS
from pypy.objspace.std.complexobject import HASH_IMAG
diff --git a/pypy/objspace/std/floatobject.py b/pypy/objspace/std/floatobject.py
--- a/pypy/objspace/std/floatobject.py
+++ b/pypy/objspace/std/floatobject.py
@@ -1,5 +1,4 @@
import operator
-import sys
from pypy.interpreter.error import OperationError
from pypy.objspace.std import model, newformat
from pypy.objspace.std.floattype import float_typedef, W_AbstractFloatObject
@@ -7,7 +6,8 @@
from pypy.objspace.std.model import registerimplementation, W_Object
from pypy.objspace.std.register_all import register_all
from pypy.objspace.std.noneobject import W_NoneObject
-from pypy.objspace.std.longobject import W_LongObject, newlong_from_float
+from pypy.objspace.std.longobject import (
+ HASH_BITS, HASH_MODULUS, W_LongObject, newlong_from_float)
from rpython.rlib.rarithmetic import (
LONG_BIT, intmask, ovfcheck_float_to_int, r_uint)
from rpython.rlib.rfloat import (
@@ -23,8 +23,6 @@
HASH_INF = 314159
HASH_NAN = 0
-HASH_BITS = 61 if sys.maxsize > 2 ** 31 - 1 else 31
-HASH_MODULUS = (1 << HASH_BITS) - 1
class W_FloatObject(W_AbstractFloatObject):
"""This is a implementation of the app-level 'float' type.
diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py
--- a/pypy/objspace/std/longobject.py
+++ b/pypy/objspace/std/longobject.py
@@ -6,9 +6,12 @@
from pypy.objspace.std.multimethod import FailedToImplementArgs
from pypy.objspace.std.intobject import W_IntObject
from pypy.objspace.std.noneobject import W_NoneObject
-from rpython.rlib.rbigint import rbigint
+from rpython.rlib.rarithmetic import intmask
+from rpython.rlib.rbigint import SHIFT, _widen_digit, rbigint
from pypy.objspace.std.longtype import long_typedef, W_AbstractLongObject
+HASH_BITS = 61 if sys.maxsize > 2 ** 31 - 1 else 31
+HASH_MODULUS = 2 ** HASH_BITS - 1
class W_LongObject(W_AbstractLongObject):
"""This is a wrapper of rbigint."""
@@ -192,7 +195,26 @@
def hash__Long(space, w_value):
- return space.wrap(w_value.num.hash())
+ return space.wrap(_hash_long(space, w_value.num))
+
+def _hash_long(space, v):
+ i = v.numdigits() - 1
+ if i == -1:
+ return 0
+
+ # compute v % HASH_MODULUS
+ x = _widen_digit(0)
+ while i >= 0:
+ x = (x << SHIFT) + v.widedigit(i)
+ # efficient x % HASH_MODULUS: as HASH_MODULUS is a Mersenne
+ # prime
+ x = (x & HASH_MODULUS) + (x >> HASH_BITS)
+ while x >= HASH_MODULUS:
+ x -= HASH_MODULUS
+ i -= 1
+ x = intmask(intmask(x) * v.sign)
+ return -2 if x == -1 else x
+
def add__Long_Long(space, w_long1, w_long2):
return W_LongObject(w_long1.num.add(w_long2.num))
diff --git a/pypy/objspace/std/test/test_floatobject.py
b/pypy/objspace/std/test/test_floatobject.py
--- a/pypy/objspace/std/test/test_floatobject.py
+++ b/pypy/objspace/std/test/test_floatobject.py
@@ -95,8 +95,6 @@
assert 42.0 == float(42)
def test_float_hash(self):
- # these are taken from standard Python, which produces
- # the same but for -1.
import math
import sys
diff --git a/pypy/objspace/std/test/test_longobject.py
b/pypy/objspace/std/test/test_longobject.py
--- a/pypy/objspace/std/test/test_longobject.py
+++ b/pypy/objspace/std/test/test_longobject.py
@@ -221,14 +221,23 @@
assert x ^ 0x555555555 == 0x5FFFFFFFF
def test_hash(self):
- # ints have the same hash as equal longs
- for i in range(-4, 14):
- assert hash(i) == hash(int(i))
- # might check too much -- it's ok to change the hashing algorithm
- assert hash(123456789) == 123456789
- assert hash(1234567890123456789) in (
- -1895067127, # with 32-bit platforms
- 1234567890123456789) # with 64-bit platforms
+ import sys
+ modulus = sys.hash_info.modulus
+ for x in (list(range(200)) +
+ [1234567890123456789, 18446743523953737727,
+ 987685321987685321987685321987685321987685321]):
+ y = x % modulus
+ assert hash(x) == hash(y)
+ assert hash(-x) == hash(-y)
+ assert hash(modulus - 1) == modulus - 1
+ assert hash(modulus) == 0
+ assert hash(modulus + 1) == 1
+
+ assert hash(-1) == -2
+ value = -(modulus + 1)
+ assert hash(value) == -2
+ assert hash(value * 2 + 1) == -2
+ assert hash(value * 4 + 3) == -2
def test_math_log(self):
import math
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
