https://github.com/python/cpython/commit/e59260b1c0165567438211082a181fb7b74b385a commit: e59260b1c0165567438211082a181fb7b74b385a branch: main author: Pieter Eendebak <[email protected]> committer: eendebakpt <[email protected]> date: 2026-11-18T16:56:11+01:00 summary:
gh-100687: Reduce frequency of overallocation in `x_add()` (#158002) * gh-100687: Reduce frequency of overallocation in x_add() x_add() allocated a digit for the carry out of the top digit on every call. In most cases that digit is zero and long_normalize() drops it from the digit count, but the allocation keeps its size, so the result uses more memory than its value needs for as long as it lives. Allocate the carry digit only when the top digits of the operands sum to at least PyLong_MASK, the only case in which a carry out of the top digit is possible. When no carry digit was allocated the top digit of the result is at least the top digit of the larger operand, so the result is already normalized and is returned directly. This applies to same-sign additions and opposite-sign subtractions, which go through x_add(); x_sub() is unchanged. Extends PR 100688 by Mark Dickinson, which contributed the size test and the tests. Co-authored-by: Mark Dickinson <[email protected]> Co-Authored-By: Claude Fable 5.1 <[email protected]> * Apply batched suggestions from code review Co-authored-by: Stan Ulbrych <[email protected]> --------- Co-authored-by: Mark Dickinson <[email protected]> Co-authored-by: Claude Fable 5.1 <[email protected]> Co-authored-by: Stan Ulbrych <[email protected]> files: A Misc/NEWS.d/next/Core_and_Builtins/2023-01-02-14-54-12.gh-issue-100687.yenIag.rst M Lib/test/test_long.py M Objects/longobject.c diff --git a/Lib/test/test_long.py b/Lib/test/test_long.py index c16bf1b1fe020e..ce72c256774d77 100644 --- a/Lib/test/test_long.py +++ b/Lib/test/test_long.py @@ -1734,6 +1734,20 @@ class MyInt(int): # GH-117195 -- This shouldn't crash object.__sizeof__(1) + def test_long_add_overallocate(self): + # see gh-100687 + x = (MASK//2) * (MASK+1) + x2 = (MASK//2 + 1) * (MASK+1) + self.assertEqual(x + x2, MASK * (MASK + 1)) + + def test_karatsuba_single_digit_parts(self): + # gh-100687: k_mul() adds the halves of its operands with x_add(), + # and those halves can be single digits. + a = 1 + (1 << (SHIFT * 70)) + b = 1 << (SHIFT * 139) + self.assertEqual(a * b, (1 << (SHIFT * 139)) + (1 << (SHIFT * 209))) + self.assertEqual(b * a, a * b) + def test_hash(self): # gh-136599 self.assertEqual(hash(-1), -2) diff --git a/Misc/NEWS.d/next/Core_and_Builtins/2023-01-02-14-54-12.gh-issue-100687.yenIag.rst b/Misc/NEWS.d/next/Core_and_Builtins/2023-01-02-14-54-12.gh-issue-100687.yenIag.rst new file mode 100644 index 00000000000000..f4f63584b1659e --- /dev/null +++ b/Misc/NEWS.d/next/Core_and_Builtins/2023-01-02-14-54-12.gh-issue-100687.yenIag.rst @@ -0,0 +1,2 @@ +Reduce the memory used by the result of adding two large :class:`int` +values. Such additions are also slightly faster for most sizes. diff --git a/Objects/longobject.c b/Objects/longobject.c index 09bfe4ad464128..4a3117c43de5e1 100644 --- a/Objects/longobject.c +++ b/Objects/longobject.c @@ -3755,7 +3755,13 @@ x_add(PyLongObject *a, PyLongObject *b) size_a = size_b; size_b = size_temp; } } - z = long_alloc(size_a+1); + assert(size_a >= 1); + /* A carry out of the top digit is only possible if the top digits sum + to at least PyLong_MASK; only then allocate a digit for it. */ + digit top_sum = a->long_value.ob_digit[size_a - 1] + + (size_b == size_a ? b->long_value.ob_digit[size_b - 1] : 0); + int extra_digit = top_sum >= PyLong_MASK; + z = long_alloc(size_a + extra_digit); if (z == NULL) return NULL; for (i = 0; i < size_b; ++i) { @@ -3768,8 +3774,13 @@ x_add(PyLongObject *a, PyLongObject *b) z->long_value.ob_digit[i] = carry & PyLong_MASK; carry >>= PyLong_SHIFT; } - z->long_value.ob_digit[i] = carry; - return long_normalize(z); + if (extra_digit) { + z->long_value.ob_digit[i] = carry; + return long_normalize(z); + } + assert(carry == 0); + assert(z->long_value.ob_digit[i - 1] != 0); + return z; } /* Subtract the absolute values of two integers. */ _______________________________________________ Python-checkins mailing list -- [email protected] To unsubscribe send an email to [email protected] https://mail.python.org/mailman3//lists/python-checkins.python.org Member address: [email protected]
