From 696cf43b58cf1ddb7a3ab3c5bee6709e3b3653d9 Mon Sep 17 00:00:00 2001 From: Tim Peters Date: Wed, 24 May 2006 21:10:40 +0000 Subject: Heavily fiddled variant of patch #1442927: PyLong_FromString optimization. ``long(str, base)`` is now up to 6x faster for non-power-of-2 bases. The largest speedup is for inputs with about 1000 decimal digits. Conversion from non-power-of-2 bases remains quadratic-time in the number of input digits (it was and remains linear-time for bases 2, 4, 8, 16 and 32). Speedups at various lengths for decimal inputs, comparing 2.4.3 with current trunk. Note that it's actually a bit slower for 1-digit strings: len speedup ---- ------- 1 -4.5% 2 4.6% 3 8.3% 4 12.7% 5 16.9% 6 28.6% 7 35.5% 8 44.3% 9 46.6% 10 55.3% 11 65.7% 12 77.7% 13 73.4% 14 75.3% 15 85.2% 16 103.0% 17 95.1% 18 112.8% 19 117.9% 20 128.3% 30 174.5% 40 209.3% 50 236.3% 60 254.3% 70 262.9% 80 295.8% 90 297.3% 100 324.5% 200 374.6% 300 403.1% 400 391.1% 500 388.7% 600 440.6% 700 468.7% 800 498.0% 900 507.2% 1000 501.2% 2000 450.2% 3000 463.2% 4000 452.5% 5000 440.6% 6000 439.6% 7000 424.8% 8000 418.1% 9000 417.7% --- Lib/test/test_builtin.py | 75 ++++++++++++++++++ Misc/NEWS | 6 ++ Objects/longobject.c | 200 ++++++++++++++++++++++++++++++++++++----------- 3 files changed, 237 insertions(+), 44 deletions(-) diff --git a/Lib/test/test_builtin.py b/Lib/test/test_builtin.py index 48d50d8..ed28153 100644 --- a/Lib/test/test_builtin.py +++ b/Lib/test/test_builtin.py @@ -980,6 +980,81 @@ class BuiltinTest(unittest.TestCase): self.assertRaises(ValueError, long, '53', 40) self.assertRaises(TypeError, long, 1, 12) + self.assertEqual(long('100000000000000000000000000000000', 2), + 4294967296) + self.assertEqual(long('102002022201221111211', 3), 4294967296) + self.assertEqual(long('10000000000000000', 4), 4294967296) + self.assertEqual(long('32244002423141', 5), 4294967296) + self.assertEqual(long('1550104015504', 6), 4294967296) + self.assertEqual(long('211301422354', 7), 4294967296) + self.assertEqual(long('40000000000', 8), 4294967296) + self.assertEqual(long('12068657454', 9), 4294967296) + self.assertEqual(long('4294967296', 10), 4294967296) + self.assertEqual(long('1904440554', 11), 4294967296) + self.assertEqual(long('9ba461594', 12), 4294967296) + self.assertEqual(long('535a79889', 13), 4294967296) + self.assertEqual(long('2ca5b7464', 14), 4294967296) + self.assertEqual(long('1a20dcd81', 15), 4294967296) + self.assertEqual(long('100000000', 16), 4294967296) + self.assertEqual(long('a7ffda91', 17), 4294967296) + self.assertEqual(long('704he7g4', 18), 4294967296) + self.assertEqual(long('4f5aff66', 19), 4294967296) + self.assertEqual(long('3723ai4g', 20), 4294967296) + self.assertEqual(long('281d55i4', 21), 4294967296) + self.assertEqual(long('1fj8b184', 22), 4294967296) + self.assertEqual(long('1606k7ic', 23), 4294967296) + self.assertEqual(long('mb994ag', 24), 4294967296) + self.assertEqual(long('hek2mgl', 25), 4294967296) + self.assertEqual(long('dnchbnm', 26), 4294967296) + self.assertEqual(long('b28jpdm', 27), 4294967296) + self.assertEqual(long('8pfgih4', 28), 4294967296) + self.assertEqual(long('76beigg', 29), 4294967296) + self.assertEqual(long('5qmcpqg', 30), 4294967296) + self.assertEqual(long('4q0jto4', 31), 4294967296) + self.assertEqual(long('4000000', 32), 4294967296) + self.assertEqual(long('3aokq94', 33), 4294967296) + self.assertEqual(long('2qhxjli', 34), 4294967296) + self.assertEqual(long('2br45qb', 35), 4294967296) + self.assertEqual(long('1z141z4', 36), 4294967296) + + self.assertEqual(long('100000000000000000000000000000001', 2), + 4294967297) + self.assertEqual(long('102002022201221111212', 3), 4294967297) + self.assertEqual(long('10000000000000001', 4), 4294967297) + self.assertEqual(long('32244002423142', 5), 4294967297) + self.assertEqual(long('1550104015505', 6), 4294967297) + self.assertEqual(long('211301422355', 7), 4294967297) + self.assertEqual(long('40000000001', 8), 4294967297) + self.assertEqual(long('12068657455', 9), 4294967297) + self.assertEqual(long('4294967297', 10), 4294967297) + self.assertEqual(long('1904440555', 11), 4294967297) + self.assertEqual(long('9ba461595', 12), 4294967297) + self.assertEqual(long('535a7988a', 13), 4294967297) + self.assertEqual(long('2ca5b7465', 14), 4294967297) + self.assertEqual(long('1a20dcd82', 15), 4294967297) + self.assertEqual(long('100000001', 16), 4294967297) + self.assertEqual(long('a7ffda92', 17), 4294967297) + self.assertEqual(long('704he7g5', 18), 4294967297) + self.assertEqual(long('4f5aff67', 19), 4294967297) + self.assertEqual(long('3723ai4h', 20), 4294967297) + self.assertEqual(long('281d55i5', 21), 4294967297) + self.assertEqual(long('1fj8b185', 22), 4294967297) + self.assertEqual(long('1606k7id', 23), 4294967297) + self.assertEqual(long('mb994ah', 24), 4294967297) + self.assertEqual(long('hek2mgm', 25), 4294967297) + self.assertEqual(long('dnchbnn', 26), 4294967297) + self.assertEqual(long('b28jpdn', 27), 4294967297) + self.assertEqual(long('8pfgih5', 28), 4294967297) + self.assertEqual(long('76beigh', 29), 4294967297) + self.assertEqual(long('5qmcpqh', 30), 4294967297) + self.assertEqual(long('4q0jto5', 31), 4294967297) + self.assertEqual(long('4000001', 32), 4294967297) + self.assertEqual(long('3aokq95', 33), 4294967297) + self.assertEqual(long('2qhxjlj', 34), 4294967297) + self.assertEqual(long('2br45qc', 35), 4294967297) + self.assertEqual(long('1z141z5', 36), 4294967297) + + def test_longconversion(self): # Test __long__() class Foo0: diff --git a/Misc/NEWS b/Misc/NEWS index d0d00e9..625dd74 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -12,6 +12,12 @@ What's New in Python 2.5 alpha 3? Core and builtins ----------------- +- Patch #1442927: ``long(str, base)`` is now up to 6x faster for non-power- + of-2 bases. The largest speedup is for inputs with about 1000 decimal + digits. Conversion from non-power-of-2 bases remains quadratic-time in + the number of input digits (it was and remains linear-time for bases + 2, 4, 8, 16 and 32). + - Bug #1334662: ``int(string, base)`` could deliver a wrong answer when ``base`` was not 2, 4, 8, 10, 16 or 32, and ``string`` represented an integer close to ``sys.maxint``. This was repaired by patch diff --git a/Objects/longobject.c b/Objects/longobject.c index e04699e..dc2311a 100644 --- a/Objects/longobject.c +++ b/Objects/longobject.c @@ -277,9 +277,9 @@ _long_as_ssize_t(PyObject *vv) { overflow: PyErr_SetString(PyExc_OverflowError, "long int too large to convert to int"); - if (sign > 0) + if (sign > 0) return PY_SSIZE_T_MAX; - else + else return PY_SSIZE_T_MIN; } @@ -1304,7 +1304,34 @@ long_format(PyObject *aa, int base, int addL) return (PyObject *)str; } -/* *str points to the first digit in a string of base base digits. base +static int digval[] = { + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 37, 37, 37, 37, 37, 37, + 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, + 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37, + 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, + 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37 +}; + +/* *str points to the first digit in a string of base `base` digits. base * is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first * non-digit (which may be *str!). A normalized long is returned. * The point to this routine is that it takes time linear in the number of @@ -1328,20 +1355,8 @@ long_from_binary_base(char **str, int base) n >>= 1; /* n <- total # of bits needed, while setting p to end-of-string */ n = 0; - for (;;) { - int k = -1; - char ch = *p; - - if (ch <= '9') - k = ch - '0'; - else if (ch >= 'a') - k = ch - 'a' + 10; - else if (ch >= 'A') - k = ch - 'A' + 10; - if (k < 0 || k >= base) - break; + while (digval[Py_CHARMASK(*p)] < base) ++p; - } *str = p; n = (p - start) * bits_per_char; if (n / bits_per_char != p - start) { @@ -1361,17 +1376,7 @@ long_from_binary_base(char **str, int base) bits_in_accum = 0; pdigit = z->ob_digit; while (--p >= start) { - int k; - char ch = *p; - - if (ch <= '9') - k = ch - '0'; - else if (ch >= 'a') - k = ch - 'a' + 10; - else { - assert(ch >= 'A'); - k = ch - 'A' + 10; - } + int k = digval[Py_CHARMASK(*p)]; assert(k >= 0 && k < base); accum |= (twodigits)(k << bits_in_accum); bits_in_accum += bits_per_char; @@ -1427,33 +1432,140 @@ PyLong_FromString(char *str, char **pend, int base) } if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X')) str += 2; + start = str; if ((base & (base - 1)) == 0) z = long_from_binary_base(&str, base); else { - z = _PyLong_New(0); - for ( ; z != NULL; ++str) { - int k = -1; - PyLongObject *temp; - - if (*str <= '9') - k = *str - '0'; - else if (*str >= 'a') - k = *str - 'a' + 10; - else if (*str >= 'A') - k = *str - 'A' + 10; - if (k < 0 || k >= base) - break; - temp = muladd1(z, (digit)base, (digit)k); - Py_DECREF(z); - z = temp; +/*** +Binary bases can be converted in time linear in the number of digits, because +Python's representation base is binary. Other bases (including decimal!) use +the simple quadratic-time algorithm below, complicated by some speed tricks. + +First some math: the largest integer that can be expressed in N base-B digits +is B**N-1. Consequently, if we have an N-digit input in base B, the worst- +case number of Python digits needed to hold it is the smallest integer n s.t. + + BASE**n-1 >= B**N-1 [or, adding 1 to both sides] + BASE**n >= B**N [taking logs to base BASE] + n >= log(B**N)/log(BASE) = N * log(B)/log(BASE) + +The static array log_base_BASE[base] == log(base)/log(BASE) so we can compute +this quickly. A Python long with that much space is reserved near the start, +and the result is computed into it. + +The input string is actually treated as being in base base**i (i.e., i digits +are processed at a time), where two more static arrays hold: + + convwidth_base[base] = the largest integer i such that base**i <= BASE + convmultmax_base[base] = base ** convwidth_base[base] + +The first of these is the largest i such that i consecutive input digits +must fit in a single Python digit. The second is effectively the input +base we're really using. + +Viewing the input as a sequence of digits in base +convmultmax_base[base], the result is "simply" + + (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1 + +where B = convmultmax_base[base]. +***/ + register twodigits c; /* current input character */ + Py_ssize_t size_z; + int i; + int convwidth; + twodigits convmultmax, convmult; + digit *pz, *pzstop; + char* scan; + + static double log_base_BASE[37] = {0.0e0,}; + static int convwidth_base[37] = {0,}; + static twodigits convmultmax_base[37] = {0,}; + + if (log_base_BASE[base] == 0.0) { + twodigits convmax = base; + int i = 1; + + log_base_BASE[base] = log((double)base) / + log((double)BASE); + for (;;) { + twodigits next = convmax * base; + if (next > BASE) + break; + convmax = next; + ++i; + } + convmultmax_base[base] = convmax; + assert(i > 0); + convwidth_base[base] = i; + } + + /* Find length of the string of numeric characters. */ + scan = str; + while (digval[Py_CHARMASK(*scan)] < base) + ++scan; + + /* Create a long object that can contain the largest possible + * integer with this base and length. Note that there's no + * need to initialize z->ob_digit -- no slot is read up before + * being stored into. + */ + size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1; + assert(size_z > 0); + z = _PyLong_New(size_z); + if (z == NULL) + return NULL; + z->ob_size = 0; + + /* `convwidth` consecutive input digits are treated as a single + * digit in base `convmultmax`. + */ + convwidth = convwidth_base[base]; + convmultmax = convmultmax_base[base]; + + /* Work ;-) */ + while (str < scan) { + /* grab up to convwidth digits from the input string */ + c = (digit)digval[Py_CHARMASK(*str++)]; + for (i = 1; i < convwidth && str != scan; ++i, ++str) { + c = (twodigits)(c * base + + digval[Py_CHARMASK(*str)]); + assert(c < BASE); + } + + convmult = convmultmax; + /* Calculate the shift only if we couldn't get + * convwidth digits. + */ + if (i != convwidth) { + convmult = base; + for ( ; i > 1; --i) + convmult *= base; + } + + /* Multiply z by convmult, and add c. */ + pz = z->ob_digit; + pzstop = pz + z->ob_size; + for (; pz < pzstop; ++pz) { + c += (twodigits)*pz * convmult; + *pz = (digit)(c & MASK); + c >>= SHIFT; + } + /* carry off the current end? */ + if (c) { + assert(c < BASE); + assert(z->ob_size < size_z); + *pz = (digit)c; + ++z->ob_size; + } } } if (z == NULL) return NULL; if (str == start) goto onError; - if (sign < 0 && z != NULL && z->ob_size != 0) + if (sign < 0) z->ob_size = -(z->ob_size); if (*str == 'L' || *str == 'l') str++; -- cgit v0.12