Integer Caching in Python


An integer in Python is not a traditional 2, 4, or 8-byte implementation but rather it is implemented as an array of digits in base 230 which enables Python to support super long integers. Since there is no explicit limit on the size, working with integers in Python is extremely convenient as we can carry out operations on very long numbers without worrying about integer overflows. This convenience comes at a cost of allocation being expensive and trivial operations like addition, multiplication, division being inefficient.

Each integer in python is implemented as a C structure illustrated below.

struct _longobject {
    ...
    Py_ssize_t    ob_refcnt;      // <--- holds reference count
    ...
    Py_ssize_t    ob_size;        // <--- holds number of digits
    digit         ob_digit[1];    // <--- holds the digits in base 2^30
};

It is observed that smaller integers in the range -5 to 256, are used very frequently as compared to other longer integers and hence to gain performance benefit Python preallocates this range of integers during initialization and makes them singleton and hence every time a smaller integer value is referenced instead of allocating a new integer it passes the reference of the corresponding singleton.

Here is what Python's official documentation says about this preallocation

The current implementation keeps an array of integer objects for all integers between -5 and 256 when you create an int in that range you actually just get back a reference to the existing object.

In the CPython's source code this optimization can be traced in the macro IS_SMALL_INT and the function get_small_int in longobject.c. This way python saves a lot of space and computation for commonly used integers.

Verifying smaller integers are indeed a singleton

For a CPython implementation, the in-built id function returns the address of the object in memory. This means if the smaller integers are indeed singleton then the id function should return the same memory address for two instances of the same value while multiple instances of larger values should return different ones, and this is indeed what we observe

>>> x, y = 36, 36
>>> id(x) == id(y)
True


>>> x, y = 257, 257
>>> id(x) == id(y)
False

The singletons can also be seen in action during computations. In the example below, we reach the same target value 6 by performing two operations on three different numbers, 2, 4, and 10, and we see the id function returning the same memory reference in both the cases.

>>> a, b, c = 2, 4, 10
>>> x = a + b
>>> y = c - b
>>> id(x) == id(y)
True

Verifying if these integers are indeed referenced often

We have established that Python indeed is consuming smaller integers through their corresponding singleton instances, without reallocating them every time. Now we verify the hypothesis that Python indeed saves a bunch of allocations during its initialization through these singletons. We do this by checking the reference counts of each of the integer values.

Reference Counts

Reference count holds the number of different places there are that have a reference to the object. Every time an object is referenced the ob_refcnt, in its structure, is increased by 1, and when dereferenced the count is decreased by 1. When the reference count becomes 0 the object is garbage collected.

In order to get the current reference count of an object, we use the function getrefcount from the sys module.

>>> ref_count = sys.getrefcount(50)
11

When we do this for all the integers in range -5 to 300 we get the following distribution

Reference counts of interger values

The above graph suggests that the reference count of smaller integer values is high indicating heavy usage and it decreases as the value increases which asserts the fact that there are many objects referencing smaller integer values as compared to larger ones during python initialization.

The value 0 is referenced the most - 359 times while along the long tail we see spikes in reference counts at powers of 2 i.e. 32, 64, 128, and 256. Python during its initialization itself requires small integer values and hence by creating singletons it saves about 1993 allocations.

The reference counts were computed on a freshly spun python which means during initialization it requires some integers for computations and these are facilitated by creating singleton instances of smaller values.

In usual programming, the smaller integer values are accessed much more frequently than larger ones, having singleton instances of these saves python a bunch of computation and allocations.

References


Arpit Bhayani

Arpit's Newsletter

CS newsletter for the curious engineers

❤️ by 17000+ readers

If you like what you read subscribe you can always subscribe to my newsletter and get the post delivered straight to your inbox. I write essays on various engineering topics and share it through my weekly newsletter.




Other essays that you might like


Constant Folding in Python

3917 reads 2021-01-10

Every programming language aims to be performant and Python is no exception. In this essay, we dive deep into Python int...

Making Python Integers Iterable

1790 reads 2020-06-14

In Python, Integers are not iterables but we can make them iterable by implementing __iter__ function. In this essay, we...

Personalize your Python Prompt

1763 reads 2020-02-21

Personalization is what we all love. In this article we find how we could personalize the Python interpreter prompt >>>...

Changing Python

1121 reads 2020-01-03

I changed the Python's source code and made addition incorrect and unpredictable. The addition operation will internally...


Be a better engineer

A set of courses designed to make you a better engineer and excel at your career; no-fluff, pure engineering.


System Design Masterclass

A masterclass that helps you become great at designing scalable, fault-tolerant, and highly available systems.

800+ learners

Details →

Designing Microservices

A free playlist to help you understand Microservices and their high-level patterns in depth.

17+ learners

Details →

GitHub Outage Dissections

A free playlist to help you learn core engineering from outages that happened at GitHub.

67+ learners

Details →

Hash Table Internals

A free playlist to help you understand the internal workings and construction of Hash Tables.

25+ learners

Details →

BitTorrent Internals

A free playlist to help you understand the algorithms and strategies that power P2P networks and BitTorrent.

42+ learners

Details →

Topics I talk about

Being a passionate engineer, I love to talk about a wide range of topics, but these are my personal favourites.




Arpit's Newsletter read by 17000+ engineers

🔥 Thrice a week, in your inbox, an essay about system design, distributed systems, microservices, programming languages internals, or a deep dive on some super-clever algorithm, or just a few tips on building highly scalable distributed systems.



  • v12.7.8
  • © Arpit Bhayani, 2022

Powered by this tech stack.