Python 3.10.7 (main, Sep 10 2022, 07:37:51) [Clang 13.0.0 (clang-1300.0.29.30)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import tracemalloc as tm
>>> x = 1 << 30000000
>>> y = x - 257
>>> tm.start()
>>> i = x - y
>>> print(i, tm.get_traced_memory()[0])
257 4009531
Yep. Take a look at the function x_sub in longobject.c, which makes an effort to strip leading “digits” (i.e., limbs) of x and y while they match. In the case y = x + 257, the leading digits match all the way down to the lowest digit. In the case y = x - 257, there’s a mismatch in lengths right at the start.
Here’s another example:
Python 3.10.7 (main, Sep 10 2022, 07:37:51) [Clang 13.0.0 (clang-1300.0.29.30)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import tracemalloc as tm
>>> x = 10**10**7
>>> y = x + 257
>>> tm.start()
>>> i = y % x
>>> print(i, tm.get_traced_memory()[0])
257 4438801
In other words, if you’re looking for a general principle that Python ints shouldn’t waste space, then I’m afraid that there isn’t one. There’s an effort not to gratuitously waste space, but that’s not quite the same.
Is that the size of i? Or is it the amount of memory that the C runtime and Python runtime allocated?
:>>> x = int('0'*10**7 + '257')
:>>> sys.getsizeof(i)
28
i is only 28 bytes.
I expect that the rest of the memory that tracemalloc is reporting is used to process the int(s) and has been put into look aside lists for fast reuse later. I recall hearing about
such lists in python and C runtimes - but have not read the python code to confirm.
Yeah, unfortunately int.__sizeof__ is not perfectly accurate in these cases, as it computes only based on Py_SIZE(self), which is set to the “virtual” size, i.e., big enough to only include the last nonzero digit, regardless of the actual size of the underlying allocated memory.
Yes, that’s why I called it “leak”, as it keeps temporarily used memory allocated. In quotes because it does get freed when the ints get deleted and because it’s apparently not an oversight.
/* Normalize (remove leading zeros from) an int object.
Doesn't attempt to free the storage--in most cases, due to the nature
of the algorithms used, this could save at most be one word anyway. */
static PyLongObject *
long_normalize(PyLongObject *v)
Sounds like it was decided that larger savings are too rare or insignificant to care about.
What seems odd is that there are so many leading zeros.
I guess that is down to the string to int conversion algorithm guessing the size required for the result assuming no leading “0” in the input.
And thus avoiding a reallocate of the int data,
FWIW, I’d be happy to accept a PR that modified the str to int conversions to take leading zeros into account before allocating space for the result. It would still end up overestimating the number of limbs needed in some cases, but with some care we shouldn’t ever be overestimating by more than one limb for reasonably-sized numbers.