Author: Carl Friedrich Bolz <[email protected]>
Branch:
Changeset: r65000:902241cca7dc
Date: 2013-06-26 12:07 +0200
http://bitbucket.org/pypy/pypy/changeset/902241cca7dc/
Log: merge faster-str-of-bigint
speed up str(long) significantly, thanks to an algorithm proposed by
Nathan Hurst on pypy-dev:
http://mail.python.org/pipermail/pypy-dev/2013-May/011433.html
diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py
--- a/rpython/rlib/rbigint.py
+++ b/rpython/rlib/rbigint.py
@@ -434,11 +434,11 @@
@jit.elidable
def repr(self):
- return _format_decimal(self, addL=True)
+ return self.format(BASE10, suffix="L")
@jit.elidable
def str(self):
- return _format_decimal(self)
+ return self.format(BASE10)
@jit.elidable
def eq(self, other):
@@ -1974,45 +1974,27 @@
BASE10 = '0123456789'
BASE16 = '0123456789abcdef'
-def _format(a, digits, prefix='', suffix=''):
- """
- Convert a bigint object to a string, using a given conversion base.
- Return a string object.
- """
- size_a = a.numdigits()
-
- base = len(digits)
- assert base >= 2 and base <= 36
-
- # Compute a rough upper bound for the length of the string
- i = base
- bits = 0
- while i > 1:
- bits += 1
- i >>= 1
- i = 5 + len(prefix) + len(suffix) + (size_a*SHIFT + bits-1) // bits
- s = [chr(0)] * i
- p = i
- j = len(suffix)
- while j > 0:
- p -= 1
- j -= 1
- s[p] = suffix[j]
-
- if a.sign == 0:
- p -= 1
- s[p] = '0'
- elif (base & (base - 1)) == 0:
+def _format_base2_notzero(a, digits, prefix='', suffix=''):
+ base = len(digits)
# JRH: special case for power-of-2 bases
accum = 0
accumbits = 0 # # of bits in accum
- basebits = 1 # # of bits in base-1
+ basebits = 0
i = base
- while 1:
+ while i > 1:
+ basebits += 1
i >>= 1
- if i <= 1:
- break
- basebits += 1
+
+ # Compute a rough upper bound for the length of the string
+ size_a = a.numdigits()
+ i = 5 + len(prefix) + len(suffix) + (size_a*SHIFT + basebits-1) //
basebits
+ result = [chr(0)] * i
+ next_char_index = i
+ j = len(suffix)
+ while j > 0:
+ next_char_index -= 1
+ j -= 1
+ result[next_char_index] = suffix[j]
i = 0
while i < size_a:
@@ -2021,9 +2003,9 @@
assert accumbits >= basebits
while 1:
cdigit = intmask(accum & (base - 1))
- p -= 1
- assert p >= 0
- s[p] = digits[cdigit]
+ next_char_index -= 1
+ assert next_char_index >= 0
+ result[next_char_index] = digits[cdigit]
accumbits -= basebits
accum >>= basebits
if i < size_a - 1:
@@ -2032,162 +2014,82 @@
else:
if accum <= 0:
break
-
i += 1
+ j = len(prefix)
+ while j > 0:
+ next_char_index -= 1
+ j -= 1
+ result[next_char_index] = prefix[j]
+
+ if a.sign < 0:
+ next_char_index -= 1
+ result[next_char_index] = '-'
+
+ assert next_char_index >= 0 # otherwise, buffer overflow (this is
also a
+ # hint for the annotator for the slice below)
+ return ''.join(result[next_char_index:])
+
+_FORMAT_MINDIGITS = 5 # 36 ** 5 fits in 32 bits, there may be a better choice
for this
+
+def _format_int(val, digits):
+ base = len(digits)
+ j = 0
+ out = []
+ while val:
+ out.append(digits[val % base])
+ val //= base
+ out.reverse()
+ return "".join(out)
+
+
+def _format_recursive(x, i, output, pts, digits, size_prefix):
+ # bottomed out with min_digit sized pieces
+ # use str of ints
+ if i < 0:
+ # this checks whether any digit has been appended yet
+ if output.getlength() == size_prefix:
+ if x.sign == 0:
+ pass
+ else:
+ s = _format_int(x.toint(), digits)
+ output.append(s)
+ else:
+ s = _format_int(x.toint(), digits)
+ output.append_multiple_char(digits[0], _FORMAT_MINDIGITS - len(s))
+ output.append(s)
else:
- # Not 0, and base not a power of 2. Divide repeatedly by
- # base, but for speed use the highest power of base that
- # fits in a digit.
- size = size_a
- pin = a # just for similarity to C source which uses the array
- # powbase <- largest power of base that fits in a digit.
- powbase = _widen_digit(base) # powbase == base ** power
- power = 1
- while 1:
- newpow = powbase * base
- if newpow >> SHIFT: # doesn't fit in a digit
- break
- powbase = newpow
- power += 1
+ top, bot = x.divmod(pts[i]) # split the number
+ _format_recursive(top, i-1, output, pts, digits, size_prefix)
+ _format_recursive(bot, i-1, output, pts, digits, size_prefix)
- # Get a scratch area for repeated division.
- scratch = rbigint([NULLDIGIT] * size, 1, size)
+def _format(x, digits, prefix='', suffix=''):
+ if x.sign == 0:
+ return prefix + "0" + suffix
+ base = len(digits)
+ assert base >= 2 and base <= 36
+ if (base & (base - 1)) == 0:
+ return _format_base2_notzero(x, digits, prefix, suffix)
+ negative = x.sign < 0
+ if negative:
+ x = x.neg()
+ rbase = rbigint.fromint(base)
+ two = rbigint.fromint(2)
- # Repeatedly divide by powbase.
- while 1:
- ntostore = power
- rem = _inplace_divrem1(scratch, pin, powbase, size)
- pin = scratch # no need to use a again
- if pin._digits[size - 1] == NULLDIGIT:
- size -= 1
+ pts = [rbase.pow(rbigint.fromint(_FORMAT_MINDIGITS))]
+ stringsize = _FORMAT_MINDIGITS
+ while pts[-1].lt(x):
+ pts.append(pts[-1].pow(two))
+ stringsize *= 2
+ pts.pop() # remove first base**2**i greater than x
- # Break rem into digits.
- assert ntostore > 0
- while 1:
- nextrem = rem // base
- c = rem - nextrem * base
- p -= 1
- assert p >= 0
- s[p] = digits[c]
- rem = nextrem
- ntostore -= 1
- # Termination is a bit delicate: must not
- # store leading zeroes, so must get out if
- # remaining quotient and rem are both 0.
- if not (ntostore and (size or rem)):
- break
- if size == 0:
- break
+ output = StringBuilder(stringsize)
+ if negative:
+ output.append('-')
+ output.append(prefix)
+ _format_recursive(x,len(pts)-1, output, pts, digits, output.getlength())
- j = len(prefix)
- while j > 0:
- p -= 1
- j -= 1
- s[p] = prefix[j]
-
- if a.sign < 0:
- p -= 1
- s[p] = '-'
-
- assert p >= 0 # otherwise, buffer overflow (this is also a
- # hint for the annotator for the slice below)
- return ''.join(s[p:])
-
-
-DECIMAL_SHIFT = 0 # computed as max(E such that 10**E fits in a digit)
-while 10 ** (DECIMAL_SHIFT + 1) <= 2 ** SHIFT:
- DECIMAL_SHIFT += 1
-DECIMAL_BASE = 10 ** DECIMAL_SHIFT
-
-# an RPython trick: this creates a nested sequence of calls that are
-# all inlined into each other, making an unrolled loop. Moreover the
-# calls are done in the "wrong" order to be written as a regular loop:
-# the first digit that is append-ed to the builder is the most
-# significant one (corresponding to the innermost call).
-_succ = specialize.memo()(lambda n: n + 1)
[email protected](3)
-def _add_decimal_digits(builder, value, ndigits, digit_index=1):
- assert value >= 0
- if digit_index < ndigits:
- assert digit_index < DECIMAL_SHIFT
- _add_decimal_digits(builder, value // 10, ndigits, _succ(digit_index))
- builder.append(chr(ord('0') + value % 10))
- else:
- assert value < 10
- builder.append(chr(ord('0') + value))
-_add_decimal_digits._always_inline_ = True
-
-
-def _format_decimal(a, addL=False):
- """ Optimized version of _format(a, BASE10, '', 'L' if addL else ''). """
- if a.sign == 0:
- if addL:
- return "0L"
- else:
- return "0"
-
- size_a = a.numdigits()
- negative = a.sign < 0
-
- # quick and dirty upper bound for the number of digits
- # required to express a in base DECIMAL_BASE:
- #
- # #digits = 1 + floor(log2(a) / log2(DECIMAL_BASE))
- #
- # But log2(a) < size_a * PyLong_SHIFT, and
- # log2(DECIMAL_BASE) = log2(10) * DECIMAL_SHIFT
- # > 3 * DECIMAL_SHIFT
-
- size = 1 + size_a * SHIFT // (3 * DECIMAL_SHIFT)
- pout = [NULLDIGIT] * size
-
- # convert array of base _PyLong_BASE digits in pin to an array of
- # base _PyLong_DECIMAL_BASE digits in pout, following Knuth (TAOCP,
- # Volume 2 (3rd edn), section 4.4, Method 1b).
- size = 0
- for i in range(size_a-1, -1, -1):
- hi = a.digit(i)
- for j in range(size):
- z = (_widen_digit(pout[j]) << SHIFT) | hi
- hi = _store_digit(z // DECIMAL_BASE)
- pout[j] = _store_digit(z - _widen_digit(hi) * DECIMAL_BASE)
- assert hi >= 0
- while hi:
- pout[size] = hi % DECIMAL_BASE
- hi //= DECIMAL_BASE
- size += 1
- sizem1 = size - 1
- assert sizem1 >= 0
-
- # calculate exact length of output string, and allocate
- decimal_digits_in_last_part = 1
- rem = pout[sizem1]
- tenpow = 10
- while rem >= tenpow:
- tenpow *= 10
- decimal_digits_in_last_part += 1
- strlen = (addL + negative +
- decimal_digits_in_last_part + (sizem1) * DECIMAL_SHIFT)
-
- builder = StringBuilder(strlen)
-
- # start with the negative sign, if needed
- if negative:
- builder.append('-')
-
- # pout[size-1] produces 'decimal_digits_in_last_part' digits.
- # Then the remaining pout[size-2] through pout[0] contribute exactly
- # DECIMAL_SHIFT digits each.
- decimal_digits = decimal_digits_in_last_part
- for i in range(sizem1, -1, -1):
- _add_decimal_digits(builder, pout[i], decimal_digits)
- decimal_digits = DECIMAL_SHIFT
-
- # done
- if addL:
- builder.append('L')
- return builder.build()
-
+ output.append(suffix)
+ return output.build()
def _bitwise(a, op, b): # '&', '|', '^'
""" Bitwise and/or/xor operations """
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
@@ -31,11 +31,14 @@
assert rbigint.frombool(True).tolong() == 1
def test_str(self):
- for i in range(100):
- n = 3 ** i
- r1 = rbigint.fromlong(n)
+ n = 1
+ r1 = rbigint.fromint(1)
+ three = rbigint.fromint(3)
+ for i in range(300):
+ n *= 3
+ r1 = r1.mul(three)
assert r1.str() == str(n)
- r2 = rbigint.fromlong(-n)
+ r2 = r1.neg()
assert r2.str() == str(-n)
def test_floordiv(self):
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
