Author: stian
Branch: improve-rbigint
Changeset: r56361:4ffb2cad4eaa
Date: 2012-07-12 17:47 +0200
http://bitbucket.org/pypy/pypy/changeset/4ffb2cad4eaa/
Log: Vast improvement, especially to add and mul by self
diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -145,6 +145,7 @@
_check_digits(digits)
make_sure_not_resized(digits)
self._digits = digits
+ self.size = len(digits)
self.sign = sign
def digit(self, x):
@@ -172,7 +173,7 @@
setdigit._always_inline_ = True
def numdigits(self):
- return len(self._digits)
+ return self.size
numdigits._always_inline_ = True
@staticmethod
@@ -755,7 +756,7 @@
assert newsize >= 0
z.setdigit(newsize, accum)
- z._positivenormalize()
+ z._normalize()
return z
lshift._always_inline_ = True # It's so fast that it's always benefitial.
@@ -775,7 +776,7 @@
accum >>= SHIFT
z.setdigit(oldsize, accum)
- z._positivenormalize()
+ z._normalize()
return z
lqshift._always_inline_ = True # It's so fast that it's always benefitial.
@@ -810,7 +811,7 @@
z.setdigit(i, newdigit)
i += 1
wordshift += 1
- z._positivenormalize()
+ z._normalize()
return z
rshift._always_inline_ = True # It's so fast that it's always benefitial.
@@ -859,6 +860,7 @@
i = c = self.numdigits()
if i == 0:
self.sign = 0
+ self.size = 1
self._digits = [NULLDIGIT]
return
@@ -866,23 +868,12 @@
i -= 1
assert i > 0
if i != c:
- self._digits = self._digits[:i]
+ self.size = i
if self.numdigits() == 1 and self._digits[0] == NULLDIGIT:
self.sign = 0
+ self._digits = [NULLDIGIT]
- #_normalize._always_inline_ = True
-
- def _positivenormalize(self):
- """ This function assumes numdigits > 0. Good for shifts and such """
- i = c = self.numdigits()
- while i > 1 and self._digits[i - 1] == NULLDIGIT:
- i -= 1
- assert i > 0
- if i != c:
- self._digits = self._digits[:i]
- if self.numdigits() == 1 and self._digits[0] == NULLDIGIT:
- self.sign = 0
- _positivenormalize._always_inline_ = True
+ _normalize._always_inline_ = True
def bit_length(self):
i = self.numdigits()
@@ -1005,7 +996,7 @@
carry >>= SHIFT
i += 1
z.setdigit(i, carry)
- z._positivenormalize()
+ z._normalize()
return z
def _x_sub(a, b):
@@ -1105,7 +1096,7 @@
z.setdigit(pz, z.widedigit(pz) + carry)
assert (carry >> SHIFT) == 0
i += 1
- z._positivenormalize()
+ z._normalize()
return z
elif digit and digit & (digit - 1) == 0:
@@ -1131,7 +1122,7 @@
z.setdigit(pz, z.widedigit(pz) + carry)
assert (carry >> SHIFT) == 0
i += 1
- z._positivenormalize()
+ z._normalize()
return z
@@ -1219,7 +1210,7 @@
_v_iadd(ret, shift, i, r1, r1.numdigits())
_v_iadd(ret, shift * 3, i, r3, r3.numdigits())
- ret._positivenormalize()
+ ret._normalize()
return ret
@@ -1236,8 +1227,8 @@
lo = rbigint(n._digits[:size_lo], 1)
hi = rbigint(n._digits[size_lo:], 1)
- lo._positivenormalize()
- hi._positivenormalize()
+ lo._normalize()
+ hi._normalize()
return hi, lo
def _k_mul(a, b):
@@ -1331,7 +1322,7 @@
# See the (*) comment after this function.
_v_iadd(ret, shift, i, t3, t3.numdigits())
- ret._positivenormalize()
+ ret._normalize()
return ret
""" (*) Why adding t3 can't "run out of room" above.
@@ -1425,7 +1416,7 @@
bsize -= nbtouse
nbdone += nbtouse
- ret._positivenormalize()
+ ret._normalize()
return ret
def _inplace_divrem1(pout, pin, n, size=0):
diff --git a/pypy/translator/goal/targetbigintbenchmark.py
b/pypy/translator/goal/targetbigintbenchmark.py
--- a/pypy/translator/goal/targetbigintbenchmark.py
+++ b/pypy/translator/goal/targetbigintbenchmark.py
@@ -35,24 +35,24 @@
Sum: 142.686547
Pypy with improvements:
- mod by 2: 0.007535
- mod by 10000: 3.686409
- mod by 1024 (power of two): 0.011153
- Div huge number by 2**128: 2.162245
- rshift: 2.211261
- lshift: 2.711231
- Floordiv by 2: 1.481641
- Floordiv by 3 (not power of two): 4.067045
- 2**500000: 0.155143
- (2**N)**5000000 (power of two): 0.098826
- 10000 ** BIGNUM % 100 1.742109
- i = i * i: 4.836238
- n**10000 (not power of two): 6.196422
- Power of two ** power of two: 0.038207
- v = v * power of two 3.629006
- v = v * v 8.220768
- v = v + v 4.998141
- Sum: 46.253380
+ mod by 2: 0.005984
+ mod by 10000: 3.664320
+ mod by 1024 (power of two): 0.011461
+ Div huge number by 2**128: 2.146720
+ rshift: 2.319716
+ lshift: 1.344974
+ Floordiv by 2: 1.597306
+ Floordiv by 3 (not power of two): 4.197931
+ 2**500000: 0.033942
+ (2**N)**5000000 (power of two): 0.050020
+ 10000 ** BIGNUM % 100 1.960709
+ i = i * i: 3.902392
+ n**10000 (not power of two): 5.980987
+ Power of two ** power of two: 0.013227
+ v = v * power of two 3.478328
+ v = v * v 6.345457
+ v = v + v 2.770636
+ Sum: 39.824111
A pure python form of those tests where also run
Improved pypy | Pypy | CPython 2.7.3
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit
