[Python-checkins] cpython: Issue #25402: in int-to-decimal-string conversion, reduce intermediate storage
mark.dickinson
python-checkins at python.org
Mon Aug 29 12:27:05 EDT 2016
https://hg.python.org/cpython/rev/1902e1d79e25
changeset: 102939:1902e1d79e25
user: Mark Dickinson <dickinsm at gmail.com>
date: Mon Aug 29 17:26:43 2016 +0100
summary:
Issue #25402: in int-to-decimal-string conversion, reduce intermediate storage requirements and relax restriction on converting large integers. Patch by Serhiy Storchaka.
files:
Misc/NEWS | 4 ++++
Objects/longobject.c | 19 +++++++++++--------
2 files changed, 15 insertions(+), 8 deletions(-)
diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -10,6 +10,10 @@
Core and Builtins
-----------------
+- Issue #25402: In int-to-decimal-string conversion, improve the estimate
+ of the intermediate memory required, and remove an unnecessarily strict
+ overflow check. Patch by Serhiy Storchaka.
+
- Issue #27214: In long_invert, be more careful about modifying object
returned by long_add, and remove an unnecessary check for small longs.
Thanks Oren Milman for analysis and patch.
diff --git a/Objects/longobject.c b/Objects/longobject.c
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -1591,6 +1591,7 @@
Py_ssize_t size, strlen, size_a, i, j;
digit *pout, *pin, rem, tenpow;
int negative;
+ int d;
enum PyUnicode_Kind kind;
a = (PyLongObject *)aa;
@@ -1608,15 +1609,17 @@
But log2(a) < size_a * PyLong_SHIFT, and
log2(_PyLong_DECIMAL_BASE) = log2(10) * _PyLong_DECIMAL_SHIFT
- > 3 * _PyLong_DECIMAL_SHIFT
+ > 3.3 * _PyLong_DECIMAL_SHIFT
+
+ size_a * PyLong_SHIFT / (3.3 * _PyLong_DECIMAL_SHIFT) =
+ size_a + size_a / d < size_a + size_a / floor(d),
+ where d = (3.3 * _PyLong_DECIMAL_SHIFT) /
+ (PyLong_SHIFT - 3.3 * _PyLong_DECIMAL_SHIFT)
*/
- if (size_a > PY_SSIZE_T_MAX / PyLong_SHIFT) {
- PyErr_SetString(PyExc_OverflowError,
- "int too large to format");
- return -1;
- }
- /* the expression size_a * PyLong_SHIFT is now safe from overflow */
- size = 1 + size_a * PyLong_SHIFT / (3 * _PyLong_DECIMAL_SHIFT);
+ d = (33 * _PyLong_DECIMAL_SHIFT) /
+ (10 * PyLong_SHIFT - 33 * _PyLong_DECIMAL_SHIFT);
+ assert(size_a < PY_SSIZE_T_MAX/2);
+ size = 1 + size_a + size_a / d;
scratch = _PyLong_New(size);
if (scratch == NULL)
return -1;
--
Repository URL: https://hg.python.org/cpython
More information about the Python-checkins
mailing list