1. thomie
  2. pypy

Commits

stian  committed 4ffb2ca

Vast improvement, especially to add and mul by self

  • Participants
  • Parent commits e14a09f
  • Branches improve-rbigint

Comments (0)

Files changed (2)

File pypy/rlib/rbigint.py

View file
  • Ignore whitespace
         _check_digits(digits)
         make_sure_not_resized(digits)
         self._digits = digits
+        self.size = len(digits)
         self.sign = sign
 
     def digit(self, x):
     setdigit._always_inline_ = True
 
     def numdigits(self):
-        return len(self._digits)
+        return self.size
     numdigits._always_inline_ = True
     
     @staticmethod
         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.
     
             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.
     
             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.
     
         i = c = self.numdigits()
         if i == 0:
             self.sign = 0
+            self.size = 1
             self._digits = [NULLDIGIT]
             return
         
             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()
         carry >>= SHIFT
         i += 1
     z.setdigit(i, carry)
-    z._positivenormalize()
+    z._normalize()
     return z
 
 def _x_sub(a, b):
                 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:
             z.setdigit(pz, z.widedigit(pz) + carry)
         assert (carry >> SHIFT) == 0
         i += 1
-    z._positivenormalize()
+    z._normalize()
     return z
 
 
     _v_iadd(ret, shift, i, r1, r1.numdigits())
     _v_iadd(ret, shift * 3, i, r3, r3.numdigits())
 
-    ret._positivenormalize()
+    ret._normalize()
     return ret
 
 
 
     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):
     # 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.
         bsize -= nbtouse
         nbdone += nbtouse
 
-    ret._positivenormalize()
+    ret._normalize()
     return ret
 
 def _inplace_divrem1(pout, pin, n, size=0):

File pypy/translator/goal/targetbigintbenchmark.py

View file
  • Ignore whitespace
         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