How is python storing integers out of range?

user_14021711 0
Viewed 100

We have a list in python. When it's empty it is of size 28.

import sys
a= []
print(sys.getsizeof(a))

output: 28

when I add one integer element in the list:

import sys
a= [1]
print(sys.getsizeof(a))
print(type(a[0]))

output:

32
<class 'int'>

So, for each integer I am adding, the list allocates 4 bytes per integer dynamically.

In this manner, the maximum size of the integer element in the list should be 231 -1 which is 2147483647.

But when I use the following code:

import sys
a= [1,2,5,5000000000000000000000000000000000000000000000000000000000000]

print(sys.getsizeof(a))
print(type(a[-1]))

The output is:

44
<class 'int'>
[Finished in 0.2s

This number is 5 × 1029, which is way above the limit. In binary the number is: 1100011100100010111100001110111110011101100000001010101011010110010000100100110100111010110100101011011110111001011111101111010100001111010101000000000000000000000000000000000000000000000000000000000000 which is 202 characters long, which implies that it would need 202 bits. Python is still storing it using 4 bytes without any loss.

How does this work? Is there some sort of compression going on under the hood? I have searched this through the official documentation and still didn't understand how this is happening.

What I found:

Also, the original inspiration for this question is : https://youtu.be/gDqQf4Ekr2A?list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&t=123 Any help/explanation is appreciated. Thank You.

memory memory-management python
2 Answers

It's a great question.

And here is an easy to run observation how it works

Simply run this code in the python shell, and observe memory usage of the python process (in top/htop etc). After a few minutes, you should see how MBs are being consumed by this code.

gogol = 10**100
gogoplex = 10**gogol

... until this hit the limit of your RAM. The only limit for a bignum in a python, which is used to represent integers.

user_14161440

There is no compression for integers (though the interpreter is free to decide how to internally represent them), but your measurement methodology is flawed.

sys.getsizeof() only returns the size of the object itself; if it's a container and you care about the sizes of the objects contained within, you'll need a more recursive getsizeof.

import sys


def sizeof_iterable(it):
    # TODO: doesn't correctly do e.g. dicts, or recursive structures
    return sum(sys.getsizeof(i) for i in it)


items = [1, 2, 5, 50 ** 20, "this is dog"]

lst = []

print("list", sys.getsizeof(lst) + sizeof_iterable(lst))

for item in items:
    print("item", item, sys.getsizeof(item))
    lst.append(item)
    print("list", len(lst), sys.getsizeof(lst) + sizeof_iterable(lst))

On my machine, this prints out

list 56
item 1 28
list 1 116
item 2 28
list 2 144
item 5 28
list 3 172
item 9536743164062500000000000000000000 40
list 4 212
item this is dog 60
list 5 304

i.e. an empty list requires 56 bytes, the integer 1 requires 28 bytes, a list containing that integer requires 116 bytes (altogether, though the 1 is only stored once), the number 9536743164062500000000000000000000 requires 40 bytes, the string "this is dog" 60 bytes, etc.

AKX_516850
Related