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]

Reply via email to