[Python-checkins] cpython: Issue #14339: Improve speed of bin, oct and hex builtins. Patch by Serhiy

Fri Apr 20 22:21:46 CEST 2012

http://hg.python.org/cpython/rev/dcd3344b6d5b
changeset: 76439:dcd3344b6d5b
user: Mark Dickinson <mdickinson at enthought.com>
date: Fri Apr 20 21:21:24 2012 +0100
summary:
 Issue #14339: Improve speed of bin, oct and hex builtins. Patch by Serhiy Storchaka (with minor modifications).
files:
 Misc/NEWS | 3 +
 Objects/longobject.c | 61 +++++++++++++++++--------------
 2 files changed, 36 insertions(+), 28 deletions(-)

diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -10,6 +10,9 @@
 Core and Builtins
 -----------------
 
+- Issue #14339: Speed improvements to bin, oct and hex functions. Patch by
+ Serhiy Storchaka.
+
 - Issue #14098: New functions PyErr_GetExcInfo and PyErr_SetExcInfo.
 Patch by Stefan Behnel.
 
diff --git a/Objects/longobject.c b/Objects/longobject.c
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -1672,11 +1672,10 @@
 {
 register PyLongObject *a = (PyLongObject *)aa;
 PyObject *v;
- Py_ssize_t i, sz;
+ Py_ssize_t sz;
 Py_ssize_t size_a;
- char *p;
- char sign = '0円';
- char *buffer;
+ Py_UCS1 *p;
+ int negative;
 int bits;
 
 assert(base == 2 || base == 8 || base == 10 || base == 16);
@@ -1688,6 +1687,7 @@
 return NULL;
 }
 size_a = ABS(Py_SIZE(a));
+ negative = Py_SIZE(a) < 0;
 
 /* Compute a rough upper bound for the length of the string */
 switch (base) {
@@ -1704,33 +1704,40 @@
 assert(0); /* shouldn't ever get here */
 bits = 0; /* to silence gcc warning */
 }
- /* compute length of output string: allow 2 characters for prefix and
- 1 for possible '-' sign. */
- if (size_a > (PY_SSIZE_T_MAX - 3) / PyLong_SHIFT / sizeof(Py_UCS4)) {
- PyErr_SetString(PyExc_OverflowError,
- "int is too large to format");
+
+ /* Compute exact length 'sz' of output string. */
+ if (size_a == 0) {
+ sz = 3;
+ }
+ else {
+ Py_ssize_t size_a_in_bits;
+ /* Ensure overflow doesn't occur during computation of sz. */
+ if (size_a > (PY_SSIZE_T_MAX - 3) / PyLong_SHIFT) {
+ PyErr_SetString(PyExc_OverflowError,
+ "int is too large to format");
+ return NULL;
+ }
+ size_a_in_bits = (size_a - 1) * PyLong_SHIFT +
+ bits_in_digit(a->ob_digit[size_a - 1]);
+ /* Allow 2 characters for prefix and 1 for a '-' sign. */
+ sz = 2 + negative + (size_a_in_bits + (bits - 1)) / bits;
+ }
+
+ v = PyUnicode_New(sz, 'x');
+ if (v == NULL) {
 return NULL;
 }
- /* now size_a * PyLong_SHIFT + 3 <= PY_SSIZE_T_MAX, so the RHS below
- is safe from overflow */
- sz = 3 + (size_a * PyLong_SHIFT + (bits - 1)) / bits;
- assert(sz >= 0);
- buffer = PyMem_Malloc(sz);
- if (buffer == NULL) {
- PyErr_NoMemory();
- return NULL;
- }
- p = &buffer[sz];
- if (Py_SIZE(a) < 0)
- sign = '-';
-
- if (Py_SIZE(a) == 0) {
+ assert(PyUnicode_KIND(v) == PyUnicode_1BYTE_KIND);
+
+ p = PyUnicode_1BYTE_DATA(v) + sz;
+ if (size_a == 0) {
 *--p = '0';
 }
 else {
 /* JRH: special case for power-of-2 bases */
 twodigits accum = 0;
 int accumbits = 0; /* # of bits in accum */
+ Py_ssize_t i;
 for (i = 0; i < size_a; ++i) {
 accum |= (twodigits)a->ob_digit[i] << accumbits;
 accumbits += PyLong_SHIFT;
@@ -1739,7 +1746,6 @@
 char cdigit;
 cdigit = (char)(accum & (base - 1));
 cdigit += (cdigit < 10) ? '0' : 'a'-10;
- assert(p > buffer);
 *--p = cdigit;
 accumbits -= bits;
 accum >>= bits;
@@ -1754,10 +1760,9 @@
 else /* (base == 2) */
 *--p = 'b';
 *--p = '0';
- if (sign)
- *--p = sign;
- v = PyUnicode_DecodeASCII(p, &buffer[sz] - p, NULL);
- PyMem_Free(buffer);
+ if (negative)
+ *--p = '-';
+ assert(p == PyUnicode_1BYTE_DATA(v));
 return v;
 }
 
-- 
Repository URL: http://hg.python.org/cpython
