Author: stian
Branch: bigint-with-int-ops
Changeset: r66026:f9a280100f28
Date: 2013-08-09 02:33 +0200
http://bitbucket.org/pypy/pypy/changeset/f9a280100f28/
Log: Support the binary xor/or/and ops. Support Long Int compare.
- pidigits improve performance by 12%.
- INT.__rsub__(LONG) doesn't return NotImplanted anymore (causes an
objectspace test to fail)
- lib-python tests pass, test_rbigint pass.
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
@@ -168,17 +168,17 @@
return space.newbool(w_long1.num.int_ge(w_int2.intval))
def lt__Int_Long(space, w_int1, w_long2):
- return space.newbool(rbigint.fromint(w_int1.intval).lt(w_long2.num))
+ return space.newbool(w_long2.num.int_gt(w_int1.intval))
def le__Int_Long(space, w_int1, w_long2):
- return space.newbool(rbigint.fromint(w_int1.intval).le(w_long2.num))
+ return space.newbool(w_long2.num.int_ge(w_int1.intval))
def eq__Int_Long(space, w_int1, w_long2):
- return space.newbool(rbigint.fromint(w_int1.intval).eq(w_long2.num))
+ return space.newbool(w_long2.num.int_eq(w_int1.intval))
def ne__Int_Long(space, w_int1, w_long2):
- return space.newbool(rbigint.fromint(w_int1.intval).ne(w_long2.num))
+ return space.newbool(w_long2.num.int_ne(w_int1.intval))
def gt__Int_Long(space, w_int1, w_long2):
- return space.newbool(rbigint.fromint(w_int1.intval).gt(w_long2.num))
+ return space.newbool(w_long2.num.int_lt(w_int1.intval))
def ge__Int_Long(space, w_int1, w_long2):
- return space.newbool(rbigint.fromint(w_int1.intval).ge(w_long2.num))
+ return space.newbool(w_long2.num.int_le(w_int1.intval))
def hash__Long(space, w_value):
@@ -333,12 +333,21 @@
def and__Long_Long(space, w_long1, w_long2):
return newlong(space, w_long1.num.and_(w_long2.num))
+def and__Long_Int(space, w_long1, w_int2):
+ return newlong(space, w_long1.num.int_and_(w_int2.intval))
+
def xor__Long_Long(space, w_long1, w_long2):
return W_LongObject(w_long1.num.xor(w_long2.num))
+def xor__Long_Int(space, w_long1, w_int2):
+ return W_LongObject(w_long1.num.int_xor(w_int2.intval))
+
def or__Long_Long(space, w_long1, w_long2):
return W_LongObject(w_long1.num.or_(w_long2.num))
+def or__Long_Int(space, w_long1, w_int2):
+ return W_LongObject(w_long1.num.int_or_(w_int2.intval))
+
def oct__Long(space, w_long1):
return space.wrap(w_long1.num.oct())
@@ -356,8 +365,22 @@
return (space.config.objspace.std.withsmalllong and
sys.maxint == 2147483647)
-# binary ops
-for opname in ['add', 'sub', 'mul', 'div', 'floordiv', 'truediv', 'mod',
'divmod', 'lshift']:
+# binary ops with fast way to handle ints.
+for opname in ['add', 'sub', 'mul', 'mod', 'lshift']:
+ exec compile("""
+def %(opname)s_ovr__Int_Int(space, w_int1, w_int2):
+ if recover_with_smalllong(space) and %(opname)r != 'truediv':
+ from pypy.objspace.std.smalllongobject import %(opname)s_ovr
+ return %(opname)s_ovr(space, w_int1, w_int2)
+ w_long1 = delegate_Int2Long(space, w_int1)
+ return %(opname)s__Long_Int(space, w_long1, w_int2)
+""" % {'opname': opname}, '', 'exec')
+
+ getattr(model.MM, opname).register(globals()['%s_ovr__Int_Int' % opname],
+ W_IntObject, W_IntObject, order=1)
+
+# binary ops without fast way to handle ints.
+for opname in ['div', 'floordiv', 'truediv', 'divmod']:
exec compile("""
def %(opname)s_ovr__Int_Int(space, w_int1, w_int2):
if recover_with_smalllong(space) and %(opname)r != 'truediv':
diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py
--- a/rpython/rlib/rbigint.py
+++ b/rpython/rlib/rbigint.py
@@ -61,6 +61,8 @@
return False
return True
+int_in_valid_range._always_inline_ = True
+
# Debugging digit array access.
#
# False == no checking at all
@@ -656,9 +658,9 @@
def sub(self, other):
if other.sign == 0:
return self
- if self.sign == 0:
+ elif self.sign == 0:
return rbigint(other._digits[:other.size], -other.sign, other.size)
- if self.sign == other.sign:
+ elif self.sign == other.sign:
result = _x_sub(self, other)
else:
result = _x_add(self, other)
@@ -732,13 +734,13 @@
# Fallback to long.
return self.mul(rbigint.fromint(b))
+ if self.sign == 0 or b == 0:
+ return NULLRBIGINT
+
asize = self.numdigits()
digit = abs(b)
bsign = -1 if b < 0 else 1
- if self.sign == 0 or b == 0:
- return NULLRBIGINT
-
if digit == 1:
return rbigint(self._digits[:self.size], self.sign * bsign, asize)
elif asize == 1:
@@ -775,7 +777,7 @@
if mod.sign * other.sign == -1:
if div.sign == 0:
return ONENEGATIVERBIGINT
- div = div.sub(ONERBIGINT)
+ div = div.int_sub(1)
return div
@@ -798,7 +800,7 @@
return ONENEGATIVERBIGINT if other.sign == -1 else
ONERBIGINT
return NULLRBIGINT
elif digit & (digit - 1) == 0:
- mod = self.and_(rbigint([_store_digit(digit - 1)], 1, 1))
+ mod = self.int_and_(digit - 1)
else:
# Perform
size = self.numdigits() - 1
@@ -839,7 +841,7 @@
return ONENEGATIVERBIGINT if other < 0 else ONERBIGINT
return NULLRBIGINT
elif digit & (digit - 1) == 0:
- mod = self.and_(rbigint([_store_digit(digit - 1)], 1, 1))
+ mod = self.int_and_(digit - 1)
else:
# Perform
size = self.numdigits() - 1
@@ -885,7 +887,7 @@
mod = mod.add(w)
if div.sign == 0:
return ONENEGATIVERBIGINT, mod
- div = div.sub(ONERBIGINT)
+ div = div.int_sub(1)
return div, mod
@jit.elidable
@@ -1037,7 +1039,7 @@
if self.sign == 0:
return ONENEGATIVERBIGINT
- ret = self.add(ONERBIGINT)
+ ret = self.int_add(1)
ret.sign = -ret.sign
return ret
@@ -1135,14 +1137,26 @@
return _bitwise(self, '&', other)
@jit.elidable
+ def int_and_(self, other):
+ return _int_bitwise(self, '&', other)
+
+ @jit.elidable
def xor(self, other):
return _bitwise(self, '^', other)
@jit.elidable
+ def int_xor(self, other):
+ return _int_bitwise(self, '^', other)
+
+ @jit.elidable
def or_(self, other):
return _bitwise(self, '|', other)
@jit.elidable
+ def int_or_(self, other):
+ return _int_bitwise(self, '|', other)
+
+ @jit.elidable
def oct(self):
if self.sign == 0:
return '0L'
@@ -2496,6 +2510,89 @@
return z.invert()
_bitwise._annspecialcase_ = "specialize:arg(1)"
+def _int_bitwise(a, op, b): # '&', '|', '^'
+ """ Bitwise and/or/xor operations """
+
+ if not int_in_valid_range(b):
+ # Fallback to long.
+ return _bitwise(a, op, rbigint.fromint(b))
+
+ if a.sign < 0:
+ a = a.invert()
+ maska = MASK
+ else:
+ maska = 0
+ if b < 0:
+ b = ~b
+ maskb = MASK
+ else:
+ maskb = 0
+
+ negz = 0
+ if op == '^':
+ if maska != maskb:
+ maska ^= MASK
+ negz = -1
+ elif op == '&':
+ if maska and maskb:
+ op = '|'
+ maska ^= MASK
+ maskb ^= MASK
+ negz = -1
+ elif op == '|':
+ if maska or maskb:
+ op = '&'
+ maska ^= MASK
+ maskb ^= MASK
+ negz = -1
+
+ # JRH: The original logic here was to allocate the result value (z)
+ # as the longer of the two operands. However, there are some cases
+ # where the result is guaranteed to be shorter than that: AND of two
+ # positives, OR of two negatives: use the shorter number. AND with
+ # mixed signs: use the positive number. OR with mixed signs: use the
+ # negative number. After the transformations above, op will be '&'
+ # iff one of these cases applies, and mask will be non-0 for operands
+ # whose length should be ignored.
+
+ size_a = a.numdigits()
+ if op == '&':
+ if maska:
+ size_z = 1
+ else:
+ if maskb:
+ size_z = size_a
+ else:
+ size_z = 1
+ else:
+ size_z = size_a
+
+ z = rbigint([NULLDIGIT] * size_z, 1, size_z)
+ i = 0
+ while i < size_z:
+ if i < size_a:
+ diga = a.digit(i) ^ maska
+ else:
+ diga = maska
+ if i == 0:
+ digb = b ^ maskb
+ else:
+ digb = maskb
+
+ if op == '&':
+ z.setdigit(i, diga & digb)
+ elif op == '|':
+ z.setdigit(i, diga | digb)
+ elif op == '^':
+ z.setdigit(i, diga ^ digb)
+ i += 1
+
+ z._normalize()
+ if negz == 0:
+ return z
+
+ return z.invert()
+_int_bitwise._annspecialcase_ = "specialize:arg(1)"
ULONGLONG_BOUND = r_ulonglong(1L << (r_longlong.BITS-1))
LONGLONG_MIN = r_longlong(-(1L << (r_longlong.BITS-1)))
diff --git a/rpython/rlib/test/test_rbigint.py
b/rpython/rlib/test/test_rbigint.py
--- a/rpython/rlib/test/test_rbigint.py
+++ b/rpython/rlib/test/test_rbigint.py
@@ -550,6 +550,15 @@
res2 = getattr(operator, mod)(x, y)
assert res1 == res2
+ def test_int_bitwise(self):
+ for x in gen_signs([0, 1, 5, 11, 42, 43, 2 ** 30]):
+ for y in gen_signs([0, 1, 5, 11, 42, 43, 3 ** 30, 2 ** 31]):
+ lx = rbigint.fromlong(x)
+ for mod in "xor and_ or_".split():
+ res1 = getattr(lx, 'int_' + mod)(y).tolong()
+ res2 = getattr(operator, mod)(x, y)
+ assert res1 == res2
+
def test_mul_eq_shift(self):
p2 = rbigint.fromlong(1).lshift(63)
f1 = rbigint.fromlong(0).lshift(63)
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
